数理解析研究所講究録902 巻 1995 年 49-63

49

応答型逐次プロセスの部分計算を用いた並列実行
Parallel Decomposition of Reactive Sequential Processes Using
Partial Evaluation
村上昌己

Masaki Murakami
岡山大学工学部

Faculty of Engineering, Okayama University

murakami@momo.it.okayama-u.ac.jp
概要

本稿では、通信動作からコンティニュエーションへの関数の形で定義された逐次的なプロセスについて、並列に実行可能ないくつかの部分プロセスによって構成された形に変換する方法の –般的な枠組みについて述べる.
本稿で述べる方法の基本的な考え方は次のようなものである. 通信動作の実行の間、すなわち外部からの入力の待ち合わせや出力の計算を行なっている問に、 その通信動作によるコンティニュエーションの部分計算を並行して行なう. さらにコンティニュエーションの部分計算も並行に行なうことによって、パイプライン並列性を引き出すことが可能であることを示す.

1

はじめに

筆者は先に、 CSP で記述された並行プロセスを部分評価する方法について報告した [Mu92]. そこで提案した方法は次のようなものである. プロ
セス $P$ とその実行環境についての制約条件 $P$ に対して、 $P$ を満足する環境のもとでは $P$ と動作によって区別することができないプロセス $P’$ とする.

このとき $P’$ を $P$ といる.

から組織的に求めるために、構文的な変換規則系を用[Mu92] では、逐次型プログラムの部分計算手法が与えられたとき、$P$それを拡張して並行プロセスの変換規則系を構成するための–般的な方法

50を与えた. すなわち並行プロセスの部分計算のための、逐次型プログラムの部分計算手法の応用の枠組みを示した. そこでは を記述するために、$P$

時相論理式を用いた.

そこで提案された規則系には以下のような問題点が残されていた. 第–に、並行合成に関する規則が適用できる場合が強く制限されている点である. すなわち, という 2 つ以上のサブプロセスの並行合成によって定められるプロセス
について、変換規則が適用できるためには、 とがお互いに値を送り合うということがなく本質的に–方向にのみ値が流れることが必要であった. このため、そこで述べられた規則系では変換でを部分計算すきない場合がみられた. そこで双方向に通信を行なう
を逐次的な非決定性
るためには、 [Ho85] で述べられた等式を用いて$P_{1}$$P_{2}$$P_{1}$$P_{1}||P_{2}$$\ovalbox{\tt\small REJECT}$$P_{1}||P_{2}$$P_{1}||P_{2}$のプロセスに展開した後に、部分計算を行なわなければならなかった.
第二に、 [Mu92] の規則で陽に与えられた変換規則は主に、応答型のプ

ロセスの部分計算を、逐次型プログラムの部分計算に帰着するものであった. そこでは、逐次的なプロセスを新たに並列化するための具体的な手法は示されていない. したがって古典的な逐次型プログラムの部分計算法と内部で逐次的に実行される計算の効率を向上させるの組み合せでは、各を–旦逐次的なプロセのみであった. したがって上に述べたようにスに変換してしまった後に部分計算を行なった結果では、 もともとを逐で実現されていた並列性が失われている可能性も考えられる.
次的な非決定性のプロセスに展開するために用いた等式を逆に用いることによって、らを展開した形のプロセスをもとの形に戻すことは可能であるが、部分計算の結果が偶々そのような等式が適用できる形をしている
場合は殆ど期待できない.
また与えられたプロセスのネットワークトポロジを大きく変更することによって効率的な並列アルゴリズムを得る等の変換も期待できず、変換能力にも不満が残るものである.
$P_{i}$$P_{1}||P_{2}$$P_{1}||P_{2}$$P_{1}||P_{2}$$P_{1}||$

以上のような問題点は、逐次的なプロセスを複数の並列なサブプロセスに分割する方法を与えることによって解決されることが期待できる.
そこで本稿では、逐次的なプロセスの動作を複数の並列なプロセスに

51

よってシミュレートする方法の–般的な枠組みについて述べる. ここで述べる方法は再び古典的な逐次型プログラムの部分計算手法の応用のための枠組みである. すなわち具体的な部分計算の手法が与えられたとき、 それを拡張して逐次型プロセスの並列化の手法を構成する方法について述べる.
ここで対象とする逐次型プロセスは、 通信動作からコンティニュエーショ
ンへの関数の形で定義されたものであるとする. 本稿で述べる並列花手法の基本的な考え方は、以下のようなものである. 通信動作の実行の問、すなわち外部からの入力の待ち合わせやプロセスの内部変数の値を用いて出力値の計算を行なっている問に、その通信動作によるコンティニュエーショ
ンの部分計算を並行して行なう. このように実行前でなく実行の途中にプ

ログラムの部分計算を行なうという考え方は、並列計算に固有のものである. さらにコンティニュエーションの部分計算も並行に行なうことによって、 さらに並列に実行可能なプロセスに分割できることを示す. これは逐次プログラムのパイプライン並列実行を、 陽に記述したものであると考えることができる.

2

準備

2.1

CSP

本稿では逐次型プロセスを記述するために CSP を用いる.

$\mathrm{c}\mathrm{s}\mathrm{P}[\mathrm{H}\mathrm{o}85]$

では、 プロセスの動作は通信動作からプロセスへの関数である、 という定式化をしている. 通信動作は入力命令 $c?x$ と出力命令 $c!v$ によって実行される.

は通信チャネル名であり、入力命令と出力命令が揃って実行されることにより、 変数 に式 を評価した結果の値が送られる. また同じ通信チャネル名の入力動作が 2 つ以上のプロセスに出現する場合は、それらは同時に実行される.
ここで

$c$

$x$

$v$

本稿ではこのような通信動作 m’ からそれを実行した後に得られるプロ

セス乃に写像する関数を表記するため、 以下のような guarded command
風表記を用いる.
$\{m_{1}arrow P_{1}[\cdots[m_{n}arrow P_{n}\}$

ここで [は、 決定性の選択をあらわす記号であり、 $j\neq k$ ならば $m_{j}\neq m_{k}$52である. または動作の集合 $M$ に対して$\{[_{7n_{i}\in M}m_{i}arrow P_{i}\}$と表記も用いる. 全く動作しないプロセスを、 nill であらわす.
これらのプロ *スのセマンティクスは失敗集合 (failures) によって定義される.

定義 2. 1: [失敗集合] [Ho85] プロセス P が実行することができる動作のP の実行する通信動作の系列の集合を traCes $(P)(\subset(\alpha(P))^{*})$
集合を$\alpha(P)_{\text{、}}$

であらわすことにする.
このときプロセス P の失敗集合は、 $fai\iota_{ur}es(P)$ は以下のように定義される.
$fai\iota_{ureS}(P)=\{(\overline{m}, R)|.

\overline{m}\in traC.eS(P), R\in refuSa\iota s(P/\overline{m})\}$

また

refuSalS$(Q)=\{R|R\text{はプロセス}$の環境が $Q$ に実行させようとしている動作の集合.
$Q$

かつ R のいずれの要素についても、$Q$である. また$P/\overline{m}$が直ちにデッドロックする可能性がある.

}は、 プロセス P が系列–m を実行した結果残るプロセス、

すなわち P の–m によるコンティニュエーションである. 失敗集合が等しい

二つのプロセスを等価なプロセスと呼ぶ.

P が化\in I(m’) であるときの失敗集合は,
以下のように定められる.
$arrow P_{i}$$\}$$P_{i}$の失敗集合を用いて$fai\iota_{u}reS(P)=\{([m_{i}]\wedge R\overline{m},)|(\overline{m},R)\in fai\iota ures(Pi)\}\cup$$\{([]_{)}R)|\forall i\in I, m_{\mathrm{i}}\not\in R\}$

ここで ml\triangle m2 は有限系列 ml と有限又は無限系列 m2 の連接を表わす. すな

53

わち,
$\overline{m_{1}}=[m_{1}^{1}, m_{1}^{2k}, \ldots, m_{1}]$(又は m2$=[m_{2}^{1},$,$\overline{m_{2}}=[m_{\mathit{2}}^{1}, m_{2}^{\mathit{2}}, \ldots, m_{\mathit{2}}^{h}]$. . ) のとき,$.]$

$m_{\mathit{2}}^{\mathit{2}},$$\overline{m_{1^{\wedge}}}\overline{m_{\mathit{2}}}=[m_{1}^{1}, m_{1}^{2},,\cdots, m_{1}^{k}, m_{\mathit{2}’ \mathit{2}}^{1\mathit{2}}m, \ldots, m_{\mathit{2}}^{h}]$

(又は
$[]$

$=[m_{1}^{1},$$\ldots]2$$m_{1}^{k},$ $m_{2’ \mathit{2}}^{1}m,$$m_{1}^{\mathit{2}},$$\ldots,$)

は空な系列を表す.

本稿では複数のプロセスハ,
プロセスを$P_{1}||P_{\mathit{2}}$を並行に実行した場合のように動作するのように表記する. 並行に走るプロセスの間の通信は、$P_{\mathit{2}}$出力側と入力側に共通なチャネルを用いて、先に述べた通信動作を使って行なわれる.
P が PlIIPP2 のときの失敗集合は以下のようになる.

failures$(P_{1}||P_{2})=$$\{(\overline{m}, R_{1}\cup R_{\mathit{2}})|$$\overline{m}\in traces(P_{1}||P_{2})$,$(\overline{m}\uparrow\alpha(P_{1}), R_{1})\in fai\iota ureS(P_{1})$,$(\overline{m}\uparrow\alpha(P_{\mathit{2}}), R_{2})\in\cdot fai\iota ureS(P_{\mathit{2}})\}$

ここで$traCes(P_{1}||P_{\mathit{2}})$$=\{t|$$t\uparrow\alpha(P_{1})\in traCes(P_{1}))$$t\uparrow\alpha(P_{2})\in traces(P2))$$t\in(\alpha(P_{1})\cup\alpha(P_{2}))^{*}\}$

である.

また $M$ を通信動作の集合とするとき,$\overline{m}\uparrow M$

は, –m から $M$ に含まれる動作を残し他はすべて取り去ることによって得られる系列である.
またプロセス $P$ と動作の集合 $S(\subset\alpha(P))$ について、$P\backslash S$

は P の動作のうち $s$ に含まれるものを外部から隠した (COnCeal した) プロセスをあら
わす.

54

2.2

プロセスの実行環境

本稿では [Mu92] と同様に、プロセスの環境を表現するために時相論理(TemPOral LOgiC) を用いる. 時相論理式の真/偽は, 時間的の経過を意味する系列を与えることによって定まる.

ここで時間の経過を応答型の並行のプロセスにとっての時間の経過と考えれば, 各時点において実行した通信動作の系列によって表わされる. すなわち時相論理式の真/偽は, プロセスの動作系列を与えることによって定まる. したがって, 逆に動作系列が与えられたときそれが充たす/充たさない制約を記述するために好都合である.
のような時相記号を含むことが許される.
記号等もよく使われるが, 本稿ではとり( (eVentually) 記号や
あえずこれらの記号は含まないものとする. ) これは変換型のパラダイム
において, 入力についての制約を述語論理で記述するような方法を, 応答型のパラダイムに自然に拡張したものといえる. 各記号の意味は, 直観的時相論理では, 論理式に$\mathrm{G},$$\cross$$\cup(\mathrm{u}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{l})$$\mathrm{F}$にはよく知られているように以下の通りである.
が成りたつ.

$\bullet\cross p$:

現在の次の時点で$\mathrm{G}p$:

現在から先のすべての時点で、 が常に成りたつ.

$\bullet$

$p$

$p$

以下では, 与えられた動作系列についての論理式の真/偽を形式的に定める.

通常は時相記号を含まない述語の真偽についてプロセスの内部変数の値から定まる状態の概念を用いて定義することが多い. しかしながら本稿では, 時相記号を含まない述語の真/偽は本質的ではないため, 議論を簡単にするため状態についての詳細な議論はしない. すなわち時相記号を含まない述語についてはそれを真とする動作系列の集合が定められているものとする. すなわち, 与えられた時相記号を含まない述語の集合 $mode\iota s(P)$ がそれぞれ定まっているものとする.
以下では–m を通信動作の有限系列. . ]) とするとき,(又は無限系列$[m_{1)}m_{\mathit{2}}, \ldots, m_{n}]$$[m_{1)}m_{\mathit{2}_{)}}\ldots$)$m_{i},$

$.$

head

$(\overline{m})=m_{1)}$

$p$

について,

$\text{系列}$55

tail $(m)=[m_{i}, \ldots, m_{n}]$(又は$[m_{i)}$. . ) とする.
$.]$

定義 2. 2:$\overline{m}$1.

を通信動作の系列とするとき:$p$が時相記号を含まない述語論理式であるとき,

iff $\overline{m}\in models(p)$$\overline{m}\models p$

2.

$\overline{m}\models \mathrm{X}p$iff$tail_{2}(\overline{m})\models p$

3.

$\overline{m}\models \mathrm{G}p$iff$\forall i(1\leq i),$4$\overline{m}\models p_{1}\wedge p_{\mathit{2}}$5.

$\overline{m}\models p_{1}\supset p_{\mathit{2}}$

iff

6.

$\overline{m}\models\forall xp(x)$iff すべてのiff

プロセス P の制約$\overline{m}$$q$$tail_{i}(m)$$\overline{m}\models p_{1}$かつ$\overline{m}\models p_{1}$$\models p$$\overline{m}$

ならば
$X$

$\models p_{\mathit{2}}$$\overline{m}\models p_{\mathit{2}}$について$\overline{m}\models p(x)$を充たす動作系列とは,.

$\overline{m}\in traceS(P),$ $\overline{m}\models q$となるのことである.

このような時相記号を含む論理式の真偽は、時間的の経過を意味する系
列を与えることによって定まる. 本稿では、時間の経過とは応答型の並行のプロセスにとっての時間の経過であり、 それは各時点において実行した

通信動作の系列によって表わされる. 詳しくは [Mu92] を参照されたい.

2.3

限定失敗集合等価

本稿では、部分計算の結果が正しいものであること、すなわち与えられた環境のもとで部分計算前のプロセスと区別のできない動作をすることを表現するために、 限定失敗集合等価の概念を導入する.
定義 2. 3: [失敗集合の による制限]
$q$

56

を動作の有限系列と動作の集合の対の集合、 を動作系列についてのとは、以下のように
時相論理式による制約とする. F の による制限定まる集合である.
$F$$q$$F\downarrow q$$q$$F\downarrow q=\{(\overline{m}, R)|$$(\overline{m}, R)\in F,$$\exists r,$$head(r)\not\in R$,$\exists R’(\overline{m}^{\bigwedge_{r,R}}’)\in F,$ $\overline{m}^{\wedge}r\models q\}$

定義 2. 4: [プロセスの限定失敗集合個価]を動作系列についての時相論理式による制約とする.
なるプロセス, P2 が q のもとで限定等価であるとは、 failureS
failures(乃)\downarrow q を充たすことであり、$\alpha(P_{1})$$q$$P_{1}$$P_{1}\sim P_{2}$$=$\alpha (乃)$(P_{1})\downarrow q=$$wrtq$. と表記する.
$P_{1}.\sim P_{\mathit{2}}wrt$$q$であるようなプロセス$P_{1)}$

乃については、 を満足する動$q$

作系列のみが起こりうる環境で動作している限り、両者が同じプロセスとみなすことができると考えられる. この関係が同値関係であることは、容易に示せる.

3

部分計算と並列分割

本稿で述べる方法の基本的な考え方は以下のようなものである. プロセと P が呼び出されたときの初期条件 を考えたとき、ス$P\mathrm{d}\mathrm{e}\mathrm{f}=\{marrow P_{m}\}$$q$をシミュレートするプロセスの実行が完了するのを待っている問に、となるような を用いて
で m が実行された後の条件」 すなわち$\lceil_{q}$

$m$

$q$

$\supset \mathrm{X}r$$r$の部分計算を打ちを部分計算する. $m$ の実行が完了したところで、がという逐次型のプロセス
切り実行に移る. さらにのによる部分計算は、 m’ の による部分計算と、 ,であった場合、$P_{m}$$P_{m}$$P_{m}$$P_{m}$$P_{m}\mathrm{d}\mathrm{e}\mathrm{f}=\{m’arrow P_{m}’\}$$q’$の部分計算に分割される.
定義 3. 1: [動作のシミュレーション]$q’$$P_{n}’$

57

プロセス

$\{m arrow P\}$

と初期条件

$q$

について、 プロセス Rm, が、 q のもとで動作 $m$ の忠実なシミュレーションであるとは、$R_{m}$

が以下のプロセスについて限定失敗集合等価であることをいう. 通信動作の集合 $C$ を$C\cap\alpha(\{marrow P\})=\emptyset$ とし、 また特別な出力動作 $s!\omega(m)\not\in\alpha(\{marrow P\})$
と

$q$

について、
$\{[_{c\in c}carrow R’[marrow\{s!\omega(m)arrow nil\}\}$

ここで $R’$ \iota よやはり $m$ のを$R_{m}$のもとで忠実なシミュレーションで、 C 及びと共有するもとする 1.
$q$

ここで C は $R_{m}$ の部分計算出力動作集合と呼び $PEO(R_{m})$また $s!\omega(m)$ は$R_{m}$$s!\omega$と表記する.

の停止信号と呼び halt $(R_{m})$ と表記する.

定義 3.1 で q が恒真な述語 (true) であるとき、 $R$ は単に $m$ の忠実なシ
ミュレーションであるという.

定義 3. 2: [忠実な部分計算]
プロセス $P$ について、通信動作の集合 C がまた特別な入力動作 $s?u$ について $s?u\not\in\alpha(\{7narrow P\})$ とする. プロセス $R$$(C\cap\alpha(\{marrow P\})=\emptyset)_{\text{、}}$が、 プロセス P の条件

による忠実な部分計算であるとは、 R が以下のプ
ロセスと等価であることをいう.
$q$$\{[_{C\in C^{C}}arrow R’[s?uarrow P’\}$

ここで $R’$ はやはりプロセス P の条件

び$s?\omega$

を $R$ と共有する 2. また $P’$ は

$q$

$q$

による忠実な部分計算で、 C およについて $P$と限定失敗集合等価であるようなプロセスであるものとする.
ここで $C$ は R の部分計算入力動作集合と呼び $PEI(R)$ と表記する.
$s?\omega$

または R の起動信号と呼び wake $(R)$ と表記する.

1 後に導入する記法を用いれば、 $PEO(R_{m})=PEO(R’)$ かつ halt $(R_{m})=ha\iota_{t}(R’)$ と書ける.
2 定義 31 の場合と同様に、後に導入する記法を用いれば、 $PEI(R)=PEI(R’)$ かっ Wake $(R)=wake(R’)$
と書ける.

58

命題 1
プロセス $\{marrow P\}$ と条件$\cross q$

について、 プロセス $R$ を $m$ の忠実なシ

ミュレーション、 $Q$ をプロセス P の条件

による忠実な部分計算で、かつ$q$

PEO(R)=PEi(Q)=C であり、 halt $(R)$ と Wake $(Q)$ によって R から への通信 が行なわれるものとする. このとき $\{marrow P\}$ は以下のプロセスとについて限定失敗集合等価である.
$Q$

$S$

$\cross q$$(R||Q)\backslash \backslash (C\cup\{s\})$.

上のプロセスの動作は直観的には、以下のようなものである. R が動作 $m$の実行を完了させるまでは、 $Q$ は R の実行によって得られた情報を $C\in C$
は $m$ のによって受けとり、それを用いて P の部分計算を行なっている.
実行が実際に完了したので、 $Q$ に P の部分計算を打ち切らせて得られたプ$S$

ロセス (定義 3.2 の $P’$ )$\prime \text{の}$実行を開始させるはたらきをする.

定義 3. 3: [動作の部分計算]
プロセス $\{marrow P\}$ と初期条件 について、通信動作の集合 C が $C$ 口$q$\alpha ({m\rightarrow P})=\emptyset 、また特別な 力動作$\text{入}\backslash$$P\})$$s?\omega(u)$とする. プロセス R が、動作 $m$ のは、 R が以下のプロセスと

$q$

$q$

について $s?\omega(u)\not\in\alpha(\{marrow$による忠実な部分計算であるとについて限定失敗集合等価であることをいう.

$\{[_{C\in C^{C}}arrow R’[s?\omega(u)arrow Q\}$

ここで $R’$ はやはり、プロセス P の条件

による忠実な部分計算で、 C お
よび $s?\omega(u)$ を $R$ と共有する 3. また $Q$ は $m$ の忠実なシミュレーションであるプロセスと について限定失敗集合等価であるとする.
ここで $C$ は R の部分計算動作集合と呼び $PE(R)$ と表記する. また $s?\omega(u)$
$q$

$q$

は R の起動信号と呼び Wake $(R)$ と表記する.

また R が動作の部分計算であるとき、 R の停止信号 halt $(R)$ とは halt $(Q)$ のことを指す.

命題 2
3 やはり定義 3.1 とと書ける.

$\prod\overline{\iota \mathrm{J}}$様に、後に導入する記法を用いれば、 $PE(R)=PE(R’)$ かつ Wake $(R)=wake(R^{;})$

59

プロセス $\{marrow P\}$ と初期条件
の

$q$

$q$

について、以下のプロセスは $\{marrow P\}$による忠実な部分計算 $P’$ と等価である.
$(R||R’)\backslash (PEI(R’)\cup\{s’\})$

ここで、 R は $m$ の$q$.

による忠実な部分計算であり、 $PEI(P’)$ $\cup PEI(R’)=$$PE(R)$ かつ wake $(R)=wake(P’)$ .

またの $q’$ による忠実な部分計算である.

ここで $s’=halt(R)=wake(R’)$ である.

$q\supset \mathrm{X}q’$

なる $q’$ とするとき、 $R’$ は $P$

命題 2 には直観的には、 $\{marrow P\}$ の による部分計算は、動作 $m$ のによる部分計算と、. P の(ただし) による部分計算に分割することができることを意味している. この分割をさらに P の部分計算にも再帰的に適用することにより、 プロセスの部分計算が動作の部分計算に分割され、並列に実行可能となる可能性を示している. このことは、逐次的なプ
ロセスをパイプライン並列に実行することに対応する.
$q$

$q’$

$q$

$q\supset\cross q’$

命題 1 および命題 2 では、逐次型プロセスのうちでも最初の分岐が無い $\{marrow P\}$ という形のプロセスを扱った. 一般的には逐次型プロセスは2 章で述べたように分岐を含む形で与えられることがありうる. このような–般的な場合のうち、 $\{m_{1}arrow P_{1}[\cdots[m_{n}arrow P_{n}\}$ のように分岐の数が有限である場合は、本稿で述べた方法を拡張し、 $1\leq i\leq n$ について

$m_{i}$のシ

ミュレーション及び乃の部分計算を並列に実行することにより、複数のプ
ロセスに分割することができる. これは所謂 OR 並列性を引き出していることに対応する.

4

変換例の概要

この節では、先に述べた枠組みにもとづいて、与えられた逐次型プロセ
スを並列化するための変換方法の例について述べる.
変換手法の概要は以下のようなものとなる$P_{n}\}$であるとき、 この変換結果をtranS $(P)$$P$$\mathrm{d}\mathrm{e}\mathrm{f}=\{m_{1}arrow P_{1}$$[[m_{n}arrow$60と表記することにする. tranS $(P)$ は、初期化のためのプロセス Init と、 $P$に対応するプロセスネットワークを起動する decomp $(P)$ を起動する.
乃に対応する 個のプロセス Nodei 及
deComP $(P)$ は、各分岐$m_{i}arrow$$\mathrm{n}$$\text{、}$び外部との通信の整合をとるためのゲートウェイとして働くプロセス等の補助的なプロセスを起動する.
Wj4 よ、外部との通信に使われるチャの実行を処理するプはさらに、各
ネル名の数だけ起動される.
ロセス Actに分かれる.
と各 に対応する decomp
これらのプロセスは起動された後実行が進むにしたがって、木状のトポ
ロジーをもつプロセスネットワークを構成する. この木構造は、 $P$ をその$GW_{j}$$G$$N_{\mathit{0}}de_{i}$$(m_{i})$$m_{i}$$(P_{i})$$P_{i}$

定義にしたがって展開して得られる木構造に対応するものである. すなわ
ち木の根から子孫に至る道は、P の具体的な計算のトレースをあらわしている. P が起動されると、実行中にどの通信動作を行なうかによって親から子へ至る枝のひとつが選ばれる. この動作を、変換後のプロセス tranS $(P)$ では token という特別な制御用の信号を根から子孫に向けて送ることによってシミュレートする.

tranS $(P)$ は以下のような形のプロセスと七て定義される.

transdecomp$(P)\mathrm{d}\mathrm{e}\mathrm{f}=Init||decomp(P)$$(P)\mathrm{d}\mathrm{e}\mathrm{f}=\{Getinputarrow($$Gettoken||Forwardinput||$$GW_{1}||GW_{\mathit{2}}||\cdots||GW_{l}||$$Node_{1}||\cdots||Node_{n})\}$$N_{\mathit{0}}de_{i}$$\mathrm{d}\mathrm{e}\mathrm{f}=Act(m_{i})||deComP(Pi)$

各プロセスのはたらきは、 以下のようなものである。
$\bullet$Init:$decom_{\mathrm{P}}(P)$に対して token を発行する. これによって decomp $(P)$がアクティヴな状態となり、外部との通信動作を行なうことができる
ようになる.

61$\bullet$$\bullet$decomp $(Q)$ :が起動される以前の計算の結果を $GetinP^{ut}$ で受けとり、プロセス $Q$ に対応する木状のネットワークを起動する. このネットワークは、 tOken が届くまでに、 $GetinP^{ut}$ によって受け取った計算の途中結果を用いて $Q$ の起動後に行なわれる計算をあらかじめ進めておく. これによって、 $Q$ を起動以前に部分計算している.
$Q$

Gettoken : 起動された decomp $(P)$ は、 このプロセスが token を受けとることによって、実行がコンティニュエーション P が呼び出されたところまで進行したことを認識する. 受け取った tOke 鱈よ、次の世代の選ばれた枝に、 Act
によって転送される.
$(m_{i})$$\bullet$:tranS $(P)$ によって起動された各プロセスと P の外部との同期
及び通信の整合をとるためのプロセスである. 外部との通信に使わ$GW_{j}$れる j 番目のチャネルが出力チャネルであるか入力チャネルであるかによって動作が場合分けされる.
$\bullet$

Forwardinput: 以前の計算結果を受け取るという通信動作 (Getinputと同様) を行ない、子孫の decomp プロセスに継続的に転送し続ける.
転送された中間結果によって、 P のコンティニュエーションの部分計

算が継続的に続けられる.
$\bullet$Act$(m_{i})$: m’ が入力動作の場合と出力動作の場合で、動きが異なるが、いずれの場合も P の外部との通信動作によってどの枝が選ばれるか、

すなわちどの子孫に tOken が転送されるかを制御する.

-m’ が出力動作 $c!f(x)$ であった場合:
tOken が届くまでは、前のレベルから送られてきた入力
もとに $f(x)$ の値をあらかじめ計算し、 deComP$(P_{i})$

$X$

の値を

に結果を先まわりして送っておく.

tOken が届いたら、 出力 $f(x)$ を外部に公開して貰うため
送る.

わち、

$GW_{i}$$m_{i}$$GW_{i}$にが出力を実際公開したことを知らせてきたら (すなの枝が選ばれて実行されたら)1 token を decomp

送る.

-m’ が入力動作 $c?x$ であった場合:$(P_{i})$

に

62

$-$

token を受け取ったら、外部からの通信イベントを待つようにに外部からの通信イベントが実際に届いたら、 $to-$に知らせる.
ken と外部から届いた入力値を decomp $(Pi)$ に送る$GW_{i}$$m_{i}$

以上のようにして、 もとの $P$ と等価な動作を行なうプロセスの定義を得ることができる.

5

考察

本稿では逐次的なプロセスが与えられたとき、それを部分計算の手法を用いて並列なフ 白セスに分割する方法の–般的な枠組みを与えた. 実際は、$\circ$

具体的な部分計算手法が与えらた際、 それが用いられるのは定義 3.3 のを求める部分である. その後に命題 2 により、命題 1 の $R_{)}Q$ が構或でき$Q$

このように本稿で述べた方法は、並列化のための具体的な変換手法ではなく、与えられた部分計算手法を並列化に応用するための方法を示したる.

ものである.

したがって本稿の方法を用いた並列化手法は、具体的な部分計算手法の中身に依存することなく、 その正しさが示されるという点に特徴がある.
また既存の (並列化とは関係のない) 部分計算手法を、新たな並列化のための変換手法のに応用できる可能性を示しているという点でも特徴があるといえる.

本稿で述べた変換では、逐次的に実行されていた場合には内部変数に格納されて暗黙のうちにコンティニュエーションに送られていた値を、変換後はプロセス問の通信動作を用いてコンティニュエーションに対応するプ
ロセスに送っているため、通信のオーバーヘッドが生ずる. このように機械的な並列化が実行の効率化にどのような場合に有効であるかについての評価は、今後の課題である.
謝辞: 岡山大学山崎進教授以下知能情報処理講座の皆様には、 有益な議論と研究上の御支援をいただきました. 記して感謝します.

63

参考文献
[Ho85] C. A. R. Hoare, Communicating Sequential Processes, PrenticeHall (1985)[Mu92] 村上, 応答型並行プロセスのための時相論理式を用いた部分計算法,
ソフトウェア科学会, プログラム変換・合成研究会,(1992)