Towards Cycle Filling as Parallelization(Concurrency Theory and Applications '96)
Yukihide Takayama · Kyoto University Research Information Repository (Kyoto University) · 1997
We give a new formulation of $\mathrm{H}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{e}\mathrm{r}-\mathrm{D}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{l}\mathrm{l}\iota \mathrm{s}\mathrm{i}0\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{A}_{1}1\mathrm{f}\mathrm{o}111\mathrm{R}\mathrm{t}\mathrm{a}$ (HDA) called cubic $al$ Bar- notation.It gives an intrinsic $\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}_{0}11$ of hypercubes which are building $1$ ) $\mathrm{l}\mathrm{o}\mathrm{C}\mathrm{k}.\mathrm{b}$ of HDA.The gain is an $\mathrm{e}\mathrm{x}_{1^{)}}1\mathrm{i}\mathrm{C}\mathrm{i}\mathrm{t}$ and $\mathrm{s}_{\mathrm{L}}\mathrm{i}\mathrm{m}_{1^{)}}1\mathrm{e}$ definition of cycle filling $\mathrm{n}\mathrm{l}\mathrm{a}_{1^{)}}$ .$\mathrm{A}\mathrm{k}o$ we have an $\mathrm{e}\mathrm{x}_{1^{)}}1\mathrm{i}_{\mathrm{C}}\mathrm{i}\mathrm{t}$ $\mathrm{r}\mathrm{e}_{1^{)}}\mathrm{r}\mathrm{p}_{\mathrm{L}}\mathrm{S}$ entation of Hoare traces and Mazurkiewicz traces.The cycle filling map can $[)\mathrm{e}\iota \mathrm{l}\mathrm{s}\mathrm{e}\mathrm{d}$ to realize the idea of cycle filling as parallelization $[2, 8]$ .Combined with the extraction algorithnl of $1^{)\mathrm{r}o}\mathrm{c}\mathrm{p}\mathrm{s}\mathrm{S}\mathrm{e}\mathrm{X}\mathrm{l}$ ) $\mathrm{r}\mathrm{e}\iota \mathrm{q}$ sions fronl HDA [9], the cycle filling $\mathrm{m}\mathrm{a}_{1^{)}}$ will realize a $\mathrm{n}\mathrm{l}\mathrm{e}\mathrm{t}1_{1}\mathrm{o}\mathrm{d}$ of $1)\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{m}$ tran:ifornlation in concurrent $1$) $\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{n}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g}$ languages as geometric $\uparrow \mathrm{r}\mathrm{a}11^{\epsilon \mathrm{f}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{t}}.,0\mathrm{i}_{0\mathrm{n}}$ of higher dilnellsional spaces.1 Introduction In $\mathrm{t},\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{l}$ ) $\mathrm{e}\mathrm{l}$ .we will consid $(^{\backslash },1$ a $\mathrm{p}\mathrm{a}\mathrm{l}_{l}\lambda 11(^{\backslash },1\mathrm{i}_{\mathrm{Z}}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{P}^{\mathrm{r}}\mathrm{o}1)1\mathrm{e}\mathrm{m}$ in $\mathrm{P}\mathrm{l}\cdot \mathrm{o}\mathrm{c}(),\mathrm{s}\mathrm{S}\mathrm{a}(^{\backslash },\mathrm{b}_{1}\cdot \mathrm{a}$ .which is stat,ed as follows: Given a process $\exp_{\mathrm{l}\mathrm{C}\mathrm{S}\mathrm{S}}\mathrm{i}_{0}\mathrm{n}$ P. how can we mechanically find a $1$) $1^{\cdot}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{S}$ expression $Q$ $\mathrm{s}\iota\iota \mathrm{C}\mathrm{h}\mathrm{t},\mathrm{h}_{C\backslash }\mathrm{t},$ $P$ and $Q$ are $\mathrm{f}$ ) $\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{l}\mathrm{n}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{r}$ and ($?$ is more parallel t,han $P?\mathrm{F}\mathrm{o}1^{\cdot}$ example.$Q=(a||l)||c$) is a $p_{C\iota\Gamma\prime ll}C,l? earrow,\prime t?,O7|$ , of $P=\mathit{0}$ : $(l)||c)+l)$ : $(a_{\backslash }^{\vee}c+c;a)+c$ ; $(a_{!}.l)+l)$ : $a$ ) wherc $(-|| -)$ and $(-! -)$ are parallel composit,ion and sequent,ial composit,ion.$\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{l}\cdot \mathrm{C}$ may be $\ln^{r}' \mathrm{t}\mathrm{n}\mathrm{y}'\backslash \mathrm{p}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{a}\mathrm{c}\mathrm{h}\mathrm{C}\mathrm{s}$ t,o t,his $\mathrm{p}_{\mathrm{l}\mathrm{O}}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$ .One candidate is the $\mathrm{d}_{\mathrm{C}\mathrm{C}\mathrm{O}1}\mathrm{n}\mathrm{p}_{\mathrm{o}\mathrm{s}}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{t}_{}\mathrm{h}\mathrm{o}\mathrm{d}[4]$ .By decomposit,ion we can check $\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{t},\mathrm{h}\mathrm{e}\mathrm{l}Q$ is a $\mathrm{p}_{C\backslash 1_{C}}\cdot'\iota 11\mathrm{C}\mathrm{l}\mathrm{i}_{7},\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$ of $P,$ $\mathrm{b}_{11}\mathrm{t}$ , an cxplicit, algorithm t,o find $Q\mathrm{f}\mathrm{i}\cdot \mathrm{o}\mathrm{m}P$ is not, given.$\mathrm{A}\mathrm{n}\mathrm{o}\mathrm{t},\mathrm{h}\mathrm{e}\Gamma$ candidate is $\mathrm{M}\mathrm{a}7_{\mathrm{J}}1\mathrm{u}\cdot \mathrm{k}\mathrm{i}\mathrm{e}\mathrm{w}\mathrm{i}_{\mathrm{C}}\mathrm{z}$ style t,race $\mathrm{t}_{r}\mathrm{h}\mathrm{e}\mathrm{o}1^{\cdot}\mathrm{y}[0]\ulcorner$ .Let, [ $P\mathrm{J}= \mathrm{f})\mathrm{e}$ t,he int,$ \mathrm{e}\mathrm{r}_{\mathrm{P}^{1\mathrm{e}\mathrm{t}\mathrm{t}}}\cdot \mathrm{a},\mathrm{i}\mathrm{o}\mathrm{n}$ of P. $H_{P}=\{al)c.acb, l)aC, l)ca.Cal).Cl)a\}$ is t,he set of maximal $\mathrm{H}\mathrm{o}_{C}\lambda 1^{\cdot}\mathrm{C}\mathrm{t}_{1_{C}^{r}},\cdot\iota \mathrm{C}\mathrm{e}\mathrm{s}$ for $P$ and $Ip=\{_{a}\}$ is t,he set, of prefixed independence relat,ion $\mathrm{w}\mathrm{h}\mathrm{c}\mathrm{l}\cdot \mathrm{C} _{\mathrm{f}l}$ means $ol)c=acl)$ .Then we find new set of relations $I=\{ ,$$ ,$$ $ .$ _{b}$ .$_{c}\}$ wit,h some suit,able $\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{l}\cdot \mathrm{i}\mathrm{t},\mathrm{h}\mathrm{m}$ .and merge $I$ and $I_{T}\supset$ to $o\mathrm{b}\mathrm{t},\mathrm{a}\mathrm{i}\mathrm{n}$ t,he merged $1^{\cdot}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t},\mathrm{i}0\mathrm{n}$ $J=\{\}$ .which means $a$ .$l$ ) and $c$ are pairwise commut,ative.Then $\mathrm{t}_{}\mathrm{h}\mathrm{e}$ obt,ained int,$ \mathrm{C}11$) $1^{\cdot}\mathrm{e}\mathrm{t}\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{t}\mathrm{n} \mathrm{i}\mathrm{s}$ equal to [ $Q\mathrm{I}\cdot$ So we $\mathrm{o}\mathrm{t}_{)}\mathrm{t},\mathrm{a}\mathrm{i}\mathrm{n}$ a $\iota)_{C}'\iota 1^{\cdot}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{C}\tau 1\mathrm{i}_{\mathrm{Z}}\mathrm{a}\mathrm{t}_{r}\mathrm{i}0\mathrm{n}$ of $P$ at t,he semant,ics level.However.for $\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\subset\lambda \mathrm{l}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{t}_{}\mathrm{h}\mathrm{e}$ degree of $\mathrm{p}\mathrm{a}\mathrm{l}\subset\backslash \mathrm{u}\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{S}\mathrm{m}$ between $P$ and $Q_{\subset\backslash 1}1\mathrm{d}\mathrm{f}\mathfrak{c}$ ) $1^{\cdot}$ ext,ract,ing t,he $\mathrm{e}\mathrm{x}_{1^{)1\mathrm{C}\mathrm{s}}Q\mathrm{i}\mathrm{o}}\mathrm{S}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{f}\cdot \mathrm{m}$ t,he semant,ical palal1( $\mathrm{Y},1\mathrm{i}_{\mathrm{Z}\mathrm{a}}\mathrm{t},\mathrm{i}_{0}\mathrm{n} $ .we wollld need a richer $\mathrm{s}\mathrm{t}_{111},\cdot \mathrm{c}\cdot \mathrm{t}_{11},1^{\cdot}\mathrm{e}$ in t,he semant,ics dolnain.The $\subset\backslash _{1^{)}\mathrm{p}\mathrm{r}}\mathit{0}$ ach we will $\mathrm{t}_{5\subset}^{\Gamma}\mathrm{t}\mathrm{k}_{1}\urcorner$ , in t,his $\mathrm{p}\mathrm{a}_{1}$ ) $\mathrm{C}1$ is based on Higher-Dimensional Ant,omat,a (HDA) [6.10] model of $\mathrm{t},\mathrm{r}\iota 1\mathrm{t}^{\tau},$ $\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{c}\mathrm{l}\mathrm{u}\cdot 1^{\cdot}\mathrm{C}\mathrm{n}\mathrm{c}\mathrm{y}$ .HDA model is a gcom( $\backslash ,\mathrm{t}_{\mathit{0}}1\mathrm{i}_{\mathrm{C}}1\mathrm{y}$ formalizcd $\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{t},\mathrm{e}1^{\cdot}1_{\mathrm{C}}\mathrm{a}\mathrm{V}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{t},1^{\cdot}t\backslash \mathrm{n}\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{i}_{0}\mathrm{n}$ $\mathrm{s}\mathrm{y}_{\mathrm{S}\mathrm{t}_{\mathrm{C}}\mathrm{l}},\mathrm{n},\backslash '$ .In $\mathrm{t}_{0}\mathrm{h}\mathrm{c}$ model.we int,$ \mathrm{C}\mathrm{l}\mathrm{l}$ ) $1^{\cdot}\mathrm{e}\mathrm{t}$ t,he parallel $\Gamma 1\ln$ of $\mathit{7}7_{\text{ノ}}$ atomic act, $\mathrm{i}o$ ns by t,he $\mathit{7}\mathrm{t}-\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{l}\mathrm{C}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}_{\dot{c}}\iota 1$ $\mathrm{h}\mathrm{y}\iota)\mathrm{e}\mathrm{r}\mathrm{c}\mathrm{l}\mathrm{l}\mathrm{b}\mathrm{t}\mathrm{Y}$ (77,-cllbe) spanned by the alcs $\mathrm{c}\mathrm{o}\mathrm{l}\cdot 1^{\cdot}(\tau \mathrm{s}\iota)0\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{t},\mathit{0}$ t,he at,omic act,ions.$\mathrm{O}11$ t,he $o\mathrm{t},\mathrm{h}\mathrm{e}\mathrm{r}$ hand.nondet, $\mathrm{e}1^{\cdot}1\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{i}_{\mathrm{S}\mathrm{t}\mathrm{i}}9\mathrm{c}\mathrm{r}\mathrm{U}11$ of ?7, $\mathrm{a}\mathrm{t}_{\mathrm{o}\mathrm{n}1},\mathrm{i}_{\mathrm{C}}$ act,ions is $\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}1^{\cdot}\mathrm{p}\mathrm{r}\mathrm{C}\mathrm{t}_{e}\mathrm{e}\mathrm{d}\mathrm{s}\mathrm{i}\mathrm{m}_{1}$ ) $1\mathrm{y}$ by $\mathrm{t},\mathrm{h}$ ($, $ $\mathrm{t}_{1},\cdot \mathrm{c}\mathrm{e}$ spanned $\mathrm{f}$ )$ \mathrm{y}$