Committed-Choice 型言語 Fleng における静的粒度制御手法

荒木 拓也, 小池汎平, 田中英彦
東京大学工学部

compute, Non blocking の分岐は値が決まっていることを保証して使う必要がある. Fleng00で add を書く
Committed-Choice 型言語 Fleng は, 単一代入変数によっ と, 次のようになる.
1

はじめにて同期をとりながらすべてのゴールを並列に実行するこ,とにより 非定型的な問題においても並列度を最大限抽.

,する並列実行は粒度が小さ過ぎるため, 同期, ゴールの出して実行可能な言語である しかし ゴールを単位と起動などのオーバーヘッド が大きい。

add(#A,#B,R):- compute(+,A,B,R).
44.1

粒度制御手法
粒度を大きくする際の問題点

foo(U,V,R,S):- add(U,U,R), mul(V,V,S).

,の add と mul を 1 つのゴールに融合して,,foo(U,V,R,S):- add_mul(U,V,R,S).
しまう可能性がある.
本稿では, Fleng においてプログラムの意味を変えず add_mul(#U,#V,R,S):compute(+,U,U,R), compute(*,V,V,S).に粒度を大きくする手法について述べる.
関連研究として粒度を大きくすることはできない. なぜならば,同様の問題は Non-Strict な関数型言語でも存在する. 文 ?- foo(1,Tmp,Tmp,S) という呼び出しに対して, 最初
献 [1] では, Non-Strict な関数型言語のプログラムを, 意 のプログラムは答を返すが (Tmp = 2, S = 4), 変更後味を変えることなく, 複数の逐次スレッド に分割するア のプログラムは Tmp の値が決まらないのでデッド ロッルゴリズムが提案されている. 我々のアルゴリズムは基 クするからである.
Fleng プログラムの粒度を大きくする際には, このよ
本的にはこれを採用するが, Fleng に適用するため幾つうなデッド ロックをひきおこす変換を避けなければならかの拡張, 変更を加えている.
ない.
アルゴリズムFleng は Committed-Choice 型言語の一種であり, ほぼGHC からガード ゴールを取り除いたものに相当する. 文献 [1] では, 潜在的な依存関係という概念を用いてこガード の機構はヘッド ユニフィケーションによってのみ の問題を解決するアルゴリズムを提案している.
上の述語 foo のデータフローグラフを書くと図 1のよ実現されている.
純粋な Fleng のレベルでは, 粒度を大きくするための うになる (図では入出力変数を丸で囲んでいる). この低レベルな記述ができない. このため, 我々は Fleng の上 データフローグラフにおいて, add と mul が 1 つのゴー位互換で, Fleng の記述力を高めた言語 Fleng00 用い, ルにできないのは R が V の, あるいは S が U の入力にこれを粒度を調整する際のターゲット言語としている. なる可能性があるためである. これを潜在的な依存関係と呼び, 点線で表す (図 1). 点線でつながれたゴール同Fleng00では,
 Non-Variable Annotation:
foo U
V
値がバインド されるまで待つ. #で表す.
muladd システム述語 compute:
サスペンド せずに実行する.
RS Non-Blocking の分岐:
サスペンド せずに分岐する.
図 1: 1 つのゴールにできない例などが導入されている.
士は 1 つのゴールにはまとめることができない.
A static granularity control method of a committed- 反対に, 点線でつながっていなければ 1 つのゴールにchoice language Fleng
まとめることが可能である. 例えば
Takuya ARAKI, Hanpei KOIKE, Hidehiko TANAKA
Faculty of Engineering,the University of Tokyo
このオーバーヘッド を取り除くためには 粒度を大きくする必要があるが これはプログラムの意味を変えて

23

Fleng

4.2

foo(U,V,S):- add(U,U,R), mul(R,V,S).

2. S はすでにU, V に依存しているので, S → U, V という潜在的な依存関係はあり得ない. したがって, これらは 1 つのゴールにまとめることが可能である.

fooVUのデータフローグラフは図 のようになる

foobarRmul

VUSadd

図R

3: 間接的な出力変数

モード の分からない変数

モード が分からない変数を引,的な依存関係を作る可能性がある. 例えば,mul数とするゴールを呼び出す場合は それらの変数が潜在S

図

foo(U,V,T):add(U,U,R),mul(V,V,S),bar(U,V,R,S,T).
bar(U,V,S,R,T):- ...

2: 1 つのゴールにできる例

ゴールの扱い4.3[1] では, データフローグラフのノード に現れるも を考えると, bar の中で, R = V, S = U が行なわれる可の (算術演算等) のみを扱っているが, Fleng において一 能性がある. したがって, 変数 R, S は foo にローカルな変数であるが, R と V, S と U の間に潜在的な依存関係
般のゴールを対象とすると,を作るので, add と mul は 1 つのゴールにすることは出 間接的な入力変数
来ない (図 4).
文献

 間接的な出力変数
 モード の分からない変数

foo.

/,の扱いが問題となる 間接的な入力 出力変数とは その/U

VaddmulRS

T

ゴールから呼び出されるサブゴールで入力 出力される.

変数を表す

間接的な入力変数

入力を待たなければならないのは,bar,

実際にはサブゴールであるから データフローグラフ上,

図.

では つながっていないものと等価に扱う

5

4: モード の分からない変数

まとめ, Fleng
プログラムの粒度を静的に大きくする手法を提案した.
ができないので 1 つのゴールにまとめることはできな 粒度と並列度はトレード オフの関係にあるため, 実際にい. この依存関係を間接的な依存関係と呼び, 波線で表 粒度を大きくする場合は最適な粒度を見つける必要があす. 例えばる. 今後, このトレード オフをとりながら粒度制御を行なうプログラムを実装し, 評価を行なう予定である.
間接的な出力変数

ゴールが実行されてから値が決まる.

,

関数型言語において提案されている方法をもとにまで遅延が存在する したがって 出力を直接使うこと

foo(U,V,S):- bar(U,U,R),mul(R,V,S).
bar(#A,#B,R):- compute(+,A,B,C),add(1,C,R).

参考文献[1] K. E. Schauser, D. E. Culler, and S. C. Goldstein.
Separation constraint partitioning { a new algo間接的な依存関係は, 依存関係があることは示すので,rithm for partitioning non-strict programs into se潜在的な依存関係を除去するために使うことは可能であ
quential threads. In, pp. 259{271. ACM,る. 例えば図 3の場合, S → U という潜在的な依存関係
1995.
はあり得ない.
, 3の場合 図 のようになる.

POPL '95