Committed-Choice 型言語 Fleng における粒度制御法の評価
荒 木

拓 也y

田

中 英

彦y

Committed-Choice 型言語 Fleng は，データフロー同期の機構を用いることにより，容易に大量の並列性を抽出することが可能である．しかし，実行の粒度が非常に細かいため，同期やゴール（ Flengにおける実行の単位）の起動といった，細粒度実行に由来するオーバヘッドが大きい．プログラムの粒度を大きくすることができれば，オーバヘッドを低減することができる．しかし，Fleng においてプログラムの意味を変えずに粒度を大きくすることは容易ではない．我々は Fleng における粒度制御法としてゴール融合と強制インライン展開を提案している．ゴール融合法は複数のゴールを 1 つのゴールにまとめることにより，粒度を大きくする手法である．安全にゴール融合を行うためには精密なデータフロー解析が必須であるため，解析に時間がかかったり，大きなプログラムでは十分粒度を大きくできない可能性がある．また，強制インライン展開は同期部分のコードを含めてインライン展
開することにより粒度を大きくする手法である．強制インライン展開ではコード量が増大したり，同期部分のコードが残ることによりオーバヘッドが完全に排除できない可能性がある．本研究では実行
時間，コンパイル時間，出力コードの大きさなどについて，このこの 2 つの手法の比較評価と検討を行う．
Evaluation of Granularity Control Methods ofa Committed-Choice Language Fleng

Takuya Araki and Hidehiko Tanakayy

A committed-choice language Fleng can extract much parallelism easily from any programs
using data ow synchronization. However, there is large overhead such as synchronization andgoal (a unit of Fleng computation) invocation, because the granularity of execution is veryne. If granularity of a program is coarsened, such overhead can be reduced; but it is noteasy without changing semantics of the program. We proposed goalfusion and force inlining
as granularity control methods of a Fleng program. Goalfusion method coarsens granularity by fusing goals into one goal. In order to fuse goals safely, precise data ow analysis isrequired, which may take a lot of time and may make it impossible to coarsen granularityof a large program. Force inlining method coarsens granularity by inlining goals including
synchronization code. Force inlining method may explode the size of a program and may notdelete overhead completely because synchronization codes still remain after inlining. In thisstudy, we evaluate these two methods by execution time, compilation time, output code size,and so on.

1.

えずに粒度を大きくすることは容易ではない．

はじめに

本来，粒度と並列度はトレード オフの関係にあり，

Committed-Choice 型言語 Fleng は，データフロ

粒度を大きくする際には並列度の低下に注意する必要

ー同期の機構を用いることにより，容易に大量の並列がある．しかし，Fleng では粒度を大きくすることが性を抽出することが可能である．しかし，実行の粒度大変困難であるため，現在は，並列度の低下には注意が非常に細かいため，同期やゴール（ Fleng におけるを払わず，粒度を大きくすることだけを目的として研実行の単位）の起動といった，細粒度実行に由来する究を進めている．

2)

オーバヘッド が大きい．プログラムの粒度を大きくす

我々は Fleng における粒度制御法としてゴール融ることができれば，オーバヘッド を低減することがで

合7) と強制インライン展開6) を提案している．それぞきる．しかし，Fleng においてプログラムの意味を変れの手法は実行時間やコンパイル時間，コード サイズなどの面で利点，欠点があると思われる．
本研究では，強制インライン展開手法の実装を行い，

y 東京大学工学系研究科

文献 7) で実装，評価を行ったゴール融合法との比較，

School of Engineering, The University of Tokyo
1

2
評価を行う．両方の手法を同時に適用した場合も評価

まるものはシンボルを表す．変数は大文字で始まる．

の対象とした．

この場合，さきほどと同様に，第一引数がきまるまで

本論文の構成は以下の通りである．2章で，対象言語である Fleng について説明し，3章で Fleng の基本的な実装技術について説明する．4章で，ゴール融合

サスペンドし，値が決まったところでアクティベイト
され，その値によって分岐を行う．
また，算術演算は法について簡単に説明する．5章で，強制インライン

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

法について説明し，6章で，強制 インライン法の実装のように定義されている．ここで \#" のついた変数はについて説明する．そして，7章で両手法の比較評価

具体化されるまで待つことを表す．また，\compute"を行い，8章で関連研究について述べる．最後に 9章

はサスペンド せずに実行し，ほぼアセンブ リ言語のでまとめを行う．

add 命令にコンパイルされる．したがって，compute2.

Committed-Choice 型言語 Fleng

Fleng は論理型言語を祖先とする並列記号処理言語である．シンタックスは Prolog のものとよく似ていを用いる際は#によって値が具体化されていることを保証しなければならない．

compute と=はサスペンド せずに実行可能なため，ゴールのフォークではなく，リダクション時に直接実るが，バックトラックを行わないという点で，セマン行される．また，複数の compute ，=があった場合は，ティクスは大きく異なる．

記述順に逐次に実行される．

Fleng は，また，ゴール融合や強制インライン展開は Fleng プ
ログラムから Fleng プログラムへのトランスレータと すべてのゴールを並列に実行する
 単一代入変数を用いたデータフロー同期をとる

して実現されている．そのため，ボディー内で分岐がことにより，高並列なプログラムの実行が可能である．

扱えるよう，コンパイラを拡張してある．ボディー内でこの点が Fleng の大きな特徴になっている．以下に例の分岐は (Cond--> Then ; Else) で表す．この分岐をあげながら説明する．

は条件部の Cond を評価するときに必要な変数はすべ

foo(A,R):- add(A,1,B), mul(B,2,R).
これは，R = (A + 1) * 2 を実行する述語 foo のて値が決まっていることを仮定し，サスペンド を起こ定義である．述語は 1 つまたは複数の定義節で定義さ

If-Then-Else と呼び，コンパイルされると，手続き型れる．この場合は 1 つの定義節で定義されている．定言語と同様，単なる分岐命令にコンパイルされる．

義節は \:-" で区切られており，\:-" の左側をヘッド，

先ほどの分岐の例を Non-Blocking If-Then-Else を

右側をボデ ィという．

Fleng における計算の単位はゴールと呼ばれる．このプログラムの場合，foo(A,R) という初期ゴールが与えられると，add(A,1,B) ，mul(B,2,R) という 2 つさずに実行する．このため，この分岐を Non-Blocking

用いて表現すると次のようになる．

foo(#A,R):- (A == true --> R = 1; R = 0).
3.

基本的な実装技術のゴールに書き換えられる．この書き換えの操作をリ

データフロー同期を実現するため，ゴールは計算機

ダクションという．書き換えられた add と mul はそれの中では図 1 のような形で表されている．この図は先ぞれが並列に実行される．しかし，この場合，mul の

ほどの例

方は B の値が決定するまで実行することはできない．

foo(A,R):- add(A,1,B), mul(B,2,R).

このような場合，add の実行が終了し B の値が決まで，foo(3,R) を呼びだし，mul が add よりも先に実るまで，mul は実行を中断（サスペンド ）し，add の行されようとしたため，サスペンド している状態であ実行が終了し B の値が決定すると，実行を再開（アクる（説明のため，簡略化してある）．

ティベイト ）する．この機構を矛盾なく実現するため，

foo(3,R) を呼び出した時点で add と mul の 2 つの変数は単一代入であり，書き換えることはできない．

ゴールにリダクションされる．この時点で，述語名，分岐は次のように表す．

引数といったゴールに関する情報がメモリ上に保存さfoo(true,R):- R = 1.
foo(false,R):- R = 0.

れる．これをゴールフレームと呼ぶ．変数 B はリダ
クション時は未定義なので，UDF（ UNDEF: 未定義）

この述語は 2 つの定義節から構成されており，第一型の変数としてメモリ上に確保し，ゴールフレームに引数が true ならば R = 1 ，false ならば R = 0 を実はその領域へのポインタ（ VAR で表す）を書き込む．

行する．ここで，true や false のように小文字で始図のように mul がサスペンド した場合は，サスペ3compute(+,A,1,B), compute(B,2,R).
add

このように 2 つのゴール add と mul を 1 つにまと

mul

INT

3

VAR

INT

1

INT

VAR

UDF

めている．

VAR

図1

このようにすることで，add mul を末尾呼び出しす2
UDF

ゴールの表現Fig. 1 Representation of goals.

れば，ゴールフレーム作成の手間ははなくなる．また，mul は add の後に実行するということが分かっているので，値が決まっているかどうかをチェックする同期コード も不要になる．また，2 つの compute の間

ンド した原因の変数 B に mul へのポインタを保持すの値の授受に使われている変数 B は生成時に値が決る☆ ．add の実行が終り，B の値を決定する際には，Bまっていることが保証されるので，メモリをアロケー

を待ってサスペンド しているゴール（ mul ）のゴール

トせず，レジスタを使えるようになるというのも重要

フレームをたぐ り，アクティベイトする．

な点である．

新たにゴールを実行する際は，ゴールフレームから

ただし，このような融合が常に可能なわけではない．

引数などの情報を取り出して実行する．ここで，リダ

安易なゴール融合は，プログラムのデッドロックを引

クションが終了した後，次に実行するゴールは今リダき起こす．そのため，プログラムのデータフロー解析

クションした最後のゴールであることを考えると，最を行い，プログラムの意味を変えないことを保証して後のゴールのゴールフレームの作成は冗長である．直行う必要がある．

前にゴールフレームにセーブした情報と同じ情報を依存関係の解析は，「 存在するかも知れない」といっ

ロード することになるためである．このため，最後のた潜在的なものも含めて解析し，保守的に行う必要がゴールはゴールフレームを作成せず，レジスタに引数ある．データフロー解析の精度が融合できるゴールのを設定した後，その述語の定義にジャンプすることで数に大きな影響を与えるため，プログラム全体にわた実行を行う．これを末尾呼び出しの最適化と呼ぶ．末

る大域的なデータフロー解析を行っている．

尾呼び出しをする述語が自分自身の場合（末尾再帰の場合）は，ループの実行と同様になる．

大きなプログラムでは十分な解析が行えなかったり，
複数のファイルで構成されるプ ログラムでは，完全以上に述べたような機構のみを用いて実装した場合，な情報の伝搬が行えなかったりするため，十分な数の ゴールフレームの確保 ゴールフレームへの情報のセーブ /ロード
 値が決定しているかのチェック

ゴールが融合できない可能性がある．また，大きなプなどのオーバヘッドがかかる．特に add などの算術演算の場合，C などの逐次言語ではほぼアセンブラ 1 命
令で済むことを考えると，大変なオーバヘッド だとい
える．
4.

ゴール融合

ログラムの場合は特に，データフロー解析に長い時間がかかるため，コンパイル時間が長くなるという問題
があった．
5.

強制インライン展開

そこで，我々は，データフロー解析の必要のない粒度制御手法として，強制インライン展開を提案した6) ．
通常のインライン展開では，ヘッド部に同期がない（サこのようなオーバヘッド を削減するために，文献 7)

スペンドしない）述語しかインライン展開できないが，で，ゴール融合という手法を提案/実装した．この手

強制インライン展開では，ヘッド による同期部分も含法は複数のゴールを 1 つにまとめることで，オーバ

めてインライン展開を行う．たとえば，ヘッドを削減するという手法であり，一種のプログラ

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

ムの逐次化である．先ほどあげた例という算術演算は，A ，B の値を待たなければ計算を

foo(A,R):- add(A,1,B), mul(B,2,R).

してはならないので，compute をそのまま インライの場合は次のようになる．

ン展開することはできない．ここで，このコード のfoo(A,R):- add_mul(A,R).
add_mul(#A,R):-

ヘッド部にある同期部分（ #で値を待っている部分）を☆

実際には複数のゴールが一つの変数を待ってサスペンド する可能性があるので，このポインタはサスペンドしたゴールの リス
トをさすようになっている

Non-blocking If-Then-Else を用いてボデ ィー部に移動することを考える．たとえば，上記の add はadd(A,B,R):(isvar(A)--> suspend(add(A,B,R),A);

4(isvar(B)--> suspend(add(A,B,R),B);
compute(+,A,B,R)).

る一定以上の大きさなら展開しない．
もっとも単純な戦略である．サイズは compute なのようになる．ここで，isvar は変数の値が決定していらいくつ，ゴールの起動ならいくつ，というようるかどうかの判定することを表し，suspend(Goal,Var)に決めているが，後段のコンパイラに負担をかけは，変数 Var に対して Goal をサスペンド することをないよう，行数でも評価している．

表す．このコード は，「 A または B が決定していなけれ 展開しようとしている述語が再帰呼び出しを行っばサスペンド し，そうでなければ計算を行う」というている場合は展開しない．

コード であるため，元のプログラムと同じ意味である．

これは，ループを繰り返しの 1 回分だけ展開する

このように，同期部分をボディー部に移動してしまことになるのであまり効果がないと考え行わない．

えば，どのようなゴールでもインライン展開が可能に

たとえば，なる．先ほどの例

foo(A,R):- add(A,1,B), mul(B,2,R).

foo(...):- bar(...), baz(...).
bar(...):- ..., bar(...).

だと次のようになる．

のような場合，bar は再帰呼び出しを行っている

foo(A,R):(isvar(A)--> suspend(add(A,1,B),A);
compute(+,A,1,B)),(isvar(B)--> suspend(mul(B,2,R),B);
compute(*,B,2,R)).

ので，foo のボデ ィー中の bar は展開しない．

 展開しようとしている述語が自分自身の場合，基本的には展開しない．
ただし，これを展開することはループアンローリ
ングに相当し，効果がある可能性があるので，オ

これにより，foo(A,R) を呼び出す時点で A が決定しプションで指定できるようにした．たとえば，ていれば，ゴールフレームを作らずに計算を行うこと

append([A|B],C,D):D = [A|E], append(B,C,E).
append([],C,D):- D = C.

ができる．
この手法は複雑なデータフロー解析を行わなくてもよいという利点があるが，同期用の分岐命令（ isvar ）の場合，は削除することができない，値が決まっていなかった

前章で述べたような強制インライン展開を行うプロ

append([A|B],C,D) :D = [A|E],(isvar(B)--> suspend(append(B,C,E),B);(islist(B)-->
compute(car,B,F), compute(cdr,B,G),E = [F|H], append(G,C,H);C = E)).

グラムを実装した．プログラムは Fleng 自身で記述のようになる．ただし，今回の評価ではほとんどした，約 3,300 行程度のプログラムである．Fleng プ

効果が見られなかったので，このような展開は行っ場合はオーバヘッド を削減できないという問題点がある．また，むやみに展開するとコード 量が爆発する可能性がある．
6.

強制インライン展開の実装

ログラムを入力とし，展開後の Fleng プログラムを出ていない．

力する．ゴール融合のプログラムが約 6,000 行程度の

 展開しようとしている述語が必ずサスペンド する

Fleng プログラムであったことを考えると，ゴール融ことが分かる場合は展開しない．これはたとえば，

合より実装が容易であったことが分かる．

foo:- bar(X), baz(X).
baz(#X):- ...

また，コンパイラを拡張して，suspend(Goal,Var)の機能を実装し，ボディー部でゴールのサスペンド が出来るようにした．

のよ うな場合，foo において baz の引数 X はbar(X) で初出である．したがって，bar の実行プログラムは，トップゴールを与え，そこから呼びが終了しないかぎり，X の値が定まることはない．

出し木を深さ優先でたどり，葉の部分から順に展開を

このような場合（ bar が展開されない限り），baz

行う．展開する際，任意のゴールを展開の対象にできは展開しない．

るため，コード量を爆発させないよう，何らかの形で展開するゴールを抑制する必要がある．これは次のように行った．

 展開しようとしている述語のサイズを推定し，あ7.
7.1

2 つの粒度制御手法の評価

評価条件

これら，2 つの粒度制御手法を並列推論エンジン

5

PIE641) 上で評価した．PIE64 は Fleng の高速実行を目的に設計された並列計算機であり，64 台の要素プロ
セッサを持つ分散共有メモリマシンである．プロセッ
サは RISC アーキテクチャであり，タグサポートや幾fc

つかの特殊命令以外は一般の RISC プロセッサと同様の命令セットを持つ．
また，相互結合網は自動負荷分散の機能を持ち，負fme

荷値が最小のプロセッサに負荷を割り振ることができるため，評価において，負荷分散の影響は無視できる．

表 1 ゴール融合における制限の影響
Table 1 E ect of limitation (goalfusion).
節内変数の上限数
17
18
19
20
相対速度（1 台 ）1.30 1.29 1.32 1.30
相対速度（64 台 ） 1.35
1.35 1.34 1.34
コンパイル時間
1422 1630 1759 1969
バイナリサイズ
896
897
898
900
相対速度（1 台 ）1.36 1.36 1.37 1.35
相対速度（64 台 ） 1.03
1.05 1.04 1.05
コンパイル時間
368
391
414
571
バイナリサイズ
201
201
201
200

評価対象のプログラムとしては，以下のものを用
エラトステネスのふるいを用いた素数生成

CPU を 1 台だけ用い，測定した．速度は粒度制御を行わない場合を 1 とした相対値，コンパイル時間の単プログラム．5000 までの素数を求めた．36 行の位は秒，バイナリサイズの単位はキロバイトである．

いた．
primesプログラムである．

N-Queens 問 題 を 解 くプ ロ グ ラ ム ．10Queens で評価した．大きさは 41 行である．
fme Fleng プログラムのマクロを展開するプログラム．約 1000 行の実用規模のプログラムである．入力には fme 自身を用いた．
fc Fleng コ ン パ イラ．入 力 に は マ クロ 展 開 後 のQueens を用いた．約 3800 行であり，10 ファイ
queensルに分割されている．

fme と fc については，I/O 時間を省くため，出力を行わない形で評価を行った．
また，1章でも述べたように，本来は粒度を大きく両手法とも実行速度に対する影響はほとんど見られない．それぞれの制限値による速度差は誤差の範囲内である．これは，実行速度に大きく影響するのは計
算木の葉の部分であり，そのような部分は比較的小規模なので，制限が厳しくても融合，展開が行われたか
らではないかと推測される．ただし，制限が大幅に緩和された場合に，実行速度に影響が出てくる可能性はある．
ゴール融合では，制限を厳しくすることによってコ
ンパイル時間がかなり短くなっている．これは，制限を厳しくすることで，データフロー解析をしない部分が増え，解析時間が短くなったためである．

すれば並列度が低下するため，粒度と並列度はトレー強制インライン展開では，制限値によってコンパイ

ド オフの関係にある．しかし，Fleng の場合はこれら

ル時間，バイナリサイズにそれぞれ影響が出ている．

の手法を用いて出来るだけ粒度を大きくしても，まだこれは展開が抑制されることによりプログラムサイズ

オーバヘッド の方が大きいため，粒度はできるだけ大が減少し，それが後段のコンパイラにおけるコンパイ

きくして評価した．

ル時間にも影響しているためである．

また，fme ，fc のような大きなプログラムでは，以下のような制限のもとで粒度制御を行った．

以上のような影響があるが，以降の評価では，最大限に粒度を大きくした場合の評価を行うため，ゴール

まず，ゴール融合では，定義節内の変数の数が 20

融合における定義節内の変数の数は 20 個を上限に，強を越える場合は解析を行わないようにした．これは，

制インライン展開における展開する述語の行数は 100

定義節内の変数の数が増えると依存解析のための情報行を上限とした．これが現在の処理系での限界値であが増大し，メモリ不足で処理できないためである．まる．他の小規模なプログラムはこれらの制限は影響した，強制インライン展開では，大きさが 100 行を越えないため，このような制限はかけていない．

る述語は展開しないようにした（述語のサイズは行数

7.2

実行速度

のみで評価した）．これは，展開後のプログラムのサ

それぞれのプログラムの実行速度を図 2〜図 5 に示

イズが増大し，メモリ不足でコンパイルできなくなる

す☆ ．実行時間の測定値は 3 回実行した値の平均値をのを防ぐためである．

用いた（ガーベジコレクションの時間を含む）．

これらの制限の影響を見るため，制限の値による影響を表 1 と表 2 に示す．

それぞれのグラフの縦軸は粒度最適化を行わない場
合の 1 台の速度を 1 とした相対速度である．横軸はプ

実行時間の測定値は 3 回実行した値の平均値を用いた（ガーベジコレクションの時間を含む）．コンパイ
ル時間は Sun Enterprise 3000 上の Fleng 処理系で☆

グラフは文献 7) と若干異なるが，これは測定条件の違いと，バッ
クエンドのコンパイラのバージョンの違いによる．

6
ãêâ ¥ãêâ¦

¯²
¯­
Ì­

VéÒ

表 2 強制インライン展開における制限の影響
Table 2 E ect of limitation (force inlining).
述語の上限行数
70
80
90
100
fc
相対速度（ 1 台）
1.68 1.67 1.65 1.67
相対速度（ 64 台 ） 1.70
1.70 1.70 1.70
コンパイル時間1732 1775 1840 1965
バイナリサイズ
1495 1519 1545 1584
fme 相対速度（ 1 台） 1.44 1.44 1.44 1.44
相対速度（ 64 台 ） 1.08
1.07 1.07 1.07
コンパイル時間
468
471
471
497
バイナリサイズ
348
348
350
354

®²

Ì®
Ì¯

®­

Ì°
²
­
­

®­

¯­

°­

±­

Úð¾Æ¸!N²­³­

図 4 fme の実行速度
Fig. 4 Execution speed of fme.

Íïæêâð ²­­­®±­®¯­ãà ¥îòââëð¦

Ì­
Ì®
Ì¯
Ì°

µ­
³­
±­
¯­
­

­

®­

¯­

°­

±­

Úð¾Æ¸!N

²­

³­

®±
®¯

Ì­

®­

Ì®

µ

Ì¯

³

Ì°

¯
­

primes 5000 の実行速度
Fig. 2 Execution speed of primes 5000.

­

®­

¯­

°­

±­

Úð¾Æ¸!N²­³­

図 5 fc (Fleng compiler) の実行速度
Fig. 5 Execution speed of fc (Fleng compiler).

®­ Îòââëð
®¯­­

制インライン展開で取り切れなかった条件分岐が影響

®­­­

VéÒ

®³

±

図2

Ì­
Ì®
Ì¯
Ì°

µ­­
³­­
±­­

しているものと思われる．しかし，その差はあまり大きなものではない．その他のプログラムでは O1 は O2よりも速い．これはゴール融合では融合しきれなかった部分を強制インライン展開で拾えているのだと考え

¯­­
­

®µ

VéÒ

VéÒ

®­­

­

®­

¯­

°­

±­

Úð¾Æ¸!N²­³­

10 Queens の実行速度
Fig. 3 Execution speed of 10 Queens.
図3

られる．primes 以外は O3 がもっとも速い．両手法を併用することによる効果があることが分かる．primes
で O3 の速度が若干低下しているのはスケジューリン
グが悪くなったためである．

O3 では primes プログラム中のゴール融合後に強制インライン展開を行った場合を O3

sift([P|Xs], R) :R = [P|Zs1],
filter(P,Xs,Ys),sift(Ys,Zs1).

として示す．これは以後の評価でも共通である．

という部分で， lter 部が インライン展開されて以下

ロセッサ台数を表す．
粒度制御を行わない場合を O0 ，強制インライン展開を行った場合を O1 ，ゴール融合を行った場合を O2 ，fme で若干効果が低いことを除けば，どのプログラ
ムでも粒度制御の効果が見られている．
粒度は出来るだけ大きくして評価したが，台数を増やした際にオリジナルの方が速くなるということはな
い．これにより，並列度の低下による速度低下はないということが分かる．

queens では，O2 の方が O1 よりも速い．これは強のようになっている．

sift([P|Xs], R) :R = [P|Zs1],(isvar(Xs)--> ... ;... ,subgoal_of_filter(...,Ys,...),
),

7

Ì­

Ì®

Ì¯

Ì°

µ
³
±
¯
­

Ì­

Ì®

Ì¯

Ì°

¶­­
µ­­
´­­
³­­
²­­
±­­
°­­
¯­­
®­­
­

°²­­
¶öÔ§îæ>Ë

¿Ð
¥¾öÙî
¶öÔ§î
§öì§ö£6·8îH!
N¯Ýþ
á²ð£6®­¶öÔ§îæ>Ë®¯¶öÔ§îæ>Ë¶öÔ§îæ>Ë

¶
µ
´
³
²
±
°
¯
®
­

ãà

ãêâ

Îòââëð

Íïæêâð

Ì­

図 6 primes, queens のコンパイル時間
Fig. 6 Compilation time of primes and queens.

Ì® Ì¯

°­­­

¿Ð
¥¾öÙî
¶öÔ§î
§öì§ö£6·8îH!
N¯Ýþ
á²ð£6

¯²­­
¯­­­
®²­­
®­­­
²­­
­

Ì°

Ì­ Ì® Ì¯ Ì°

図 7 fme, fc のコンパイル時間
Fig. 7 Compilation time of fme and fc.

sift(Ys,Zs1).
ここで，展開されない場合は末尾呼び出しの最適化を¯

lter に対して行っている．これは，プログラマはデー
タフロー順にプログラムを書く傾向があるので， lterÓ§Íí¸§½
®º¯­±è®º´«®è

®º²«µè

®ºµ¶±è

|®©²

を先に実行した方がサスペンドがおきずに高速なためである．ところが，展開後は lter が展開されている

Ì­
Ì®
Ì¯
Ì°

®
­©²

ので，展開された中の subgoal of lter を末尾呼び出­

しするわけにはいかず，sift の方を末尾呼び出ししている☆ ．sift は subgoal of lter で決定される値を待つÍïæêâð

Îòââë

ãêâ

ãà

図 8 バイナリサイズ
Fig. 8 Binary size.

ので，ここで必ずサスペンドが起こってしまう．これが性能低下の原因である．実際にこの部分の展開を手で抑制すると，O1 同様の高い性能がえられた．このよグラムだと，この傾向がより顕著に現れている．図 7

うな場合は他のプログラムでも起こりうるが，primes

を見ると，強制インライン展開にかかっている時間はのような小さなプログラムでは，一部分のスケジュー

ゴール融合にかかっている時間に比べると圧倒的に短リングの悪さが性能に大きな影響を与えうる．

いが，後段のコンパイラにかかっている時間は強制イ

ただ，このような悪いスケジューリングがおこってンライン展開の方が長い．

いるかどうかはサスペンドした回数だけを見ても分か

また，コンパイル時間は表 1 ，表 2 に示したように，らない．実際，primes の場合は O3 のサスペンド 回数

粒度制御における制限にも依存する．制限の値によっがもっとも少ない．サスペンドが実行時間のクリティては，ゴール融合と強制インライン展開のコンパイル

カルパスに乗っているかどうかが実行時間に影響する

時間が逆転することもありうる．

ためである．暇なプロセッサがいくらサスペンドしていても，実行時間には影響しない．
7.3

コンパイル時間

強制インライン展開とゴール融合を共に行った場合
は，やはりもっとも長い時間がかかっている．
7.4

バイナリサイズ

図 6 と図 7 に primes ，queens ，fme ，fc のそれぞ

図 8 に各プログラムの最適化によるバイナリサイズ

れのコンパイルにかかった時間を示す．コンパイル時の比を表す．最適化を行わない場合のバイナリサイズ

間は Sun Enterprise 3000 上の Fleng 処理系で CPUを 1 とする（最適化を行わない場合の実際のバイナリ

を 1 台だけ用い，測定した．

サイズは，グラフの上に示している）．

強制インライン展開の方がゴール融合よりもコンパ

バイナリサイズはゴール融合の方が強制インライン

イル時間は短くすんでいる．しかし，圧倒的というほ展開よりも小さくなる傾向がある．これは，ゴール融

どでもないのは，強制インライン展開では変換後のプ合の場合，融合によって参照されなくなった定義を削

ログラムの行数が増えるため，後段のコンパイラに負除するためである．強制インライン展開では，サスペ担がかかるためである．fme や fc のような大きなプロ

ンド に備えて元の定義を残しておく必要があるので，☆

この場合は工夫しだいで subgoal of lter の方を末尾呼び出しすることは可能だが，sift の方も展開されてしまうと，かなり困難になる．

バイナリサイズは必ず増加する．
ゴール融合の場合，単純な融合だけが行われるとす
ると，直観的にはバイナリサイズはオリジナルよりも

8減少するように思われるが，実際にはそうではない．

いう概念を提案している．この実行機構では，関数を

これは，たとえば再帰する述語どうしが融合されるこ実行する際，本来はサスペンド に備えてヒープ上にフとによって繰り返しが展開され，初期値の与えられたレームを作成しなければならないが，値が決まってる

1 回目とそうでない 2 回目以降で異なる融合が行われたりすることがあるためである．Primes の O3 でバ
イナリサイズが O1 よりも大きくなっているのは，こと仮定して，スタック上にフレームを作成して実行をのような複雑な融合が行われた後に強制インライン展作成する．インライン展開ではなく，スタックフレーム開が行われたためである．

を用いた関数実行であるという違いはあるが，我々の行う．もし値が決まっていなくてサスペンドしなければならない場合は，その時点でヒープ上にフレームをはこの制限に依存するが，今回の制限に関する限り，

強制インライン展開に近い考え方である．Separation
Constraint Partitioning との併用も考えられている．
しかし，文献 9) では大きなプログラムでの評価はまバイナリサイズの増加は 2 倍以内に収まっており，許だ紹介されていない．

今回の評価では，強制インライン展開の際，展開する述語の行数は 100 行を上限とした．バイナリサイズ

容範囲内であると考えられる．
7.5

考

察

また，大山らは future を使った並列オブジェクト
指向言語 Schematic において，強制インライン展開と強制インライン展開は複雑なデータフロー解析を行

同様の手法を独立に提案している3) ．彼らの評価でも，わないのにもかかわらず，多くの場合で十分な速度向

このような手法が効果的であることが示されている．

上を示していることが注目される．バイナリサイズはCommitted-Choice 型言語における研究としては，
KLIC における伊川らによる研究がある5) ．あるゴール b があるゴール a に依存している場合，ゴール a がサスペンド すると，ゴール b をスケジューリングして若干大きめになる傾向があるが，これが問題にならな
い限り，粒度制御手法としては十分な効力があると考えられる．
単一代入変数を用いてデータフロー同期をとるといも必ずサスペンド してしまう．この研究ではこれを防う実行機構を持つ言語は，Fleng 以外にもたくさんあぐため，依存関係のあるゴールを一つのスレッドといる．Fleng のように全てがそうであるという言語は多う単位にまとめ，スレッド を単位にしてスケジューリ

くないが，たとえば他の Committed-Choice 型言語

ングを行う．この場合，ゴール a とゴール b は一つの（ KL1 など）やデータフロー関数型言語（ Id など）がスレッド にまとめられるので，a がサスペンド すると，そうであるし，一部にこのような機構を採り入れた言b がスケジューリングされることはない．この手法で語としては future を使った Lisp やオブジェクト指向

は，ゴール a が実行可能になった場合でもゴール b が言語，Compositional C++ などがある．これらの言実行可能であるとは保証されないので，ゴール融合よ

語でも同様の問題が指摘されているが，これらの言語

りもゆるい結合である．また，この研究ではサスペンに今回紹介したような粒度制御手法を適用することをド コストの低減を目的としているという点で，我々の考えると，実装の容易さからいって強制インライン展

研究とは異なるが，プログラムの逐次化によって効率開が有利であると考えられる．

向上を目指しているという点は共通している．

もちろん，ゴール融合と強制インライン展開を併用

また，強制インライン展開の考え方は，オブジェクトすることで，さらなる効率の向上が見られているため，指向言語における，メソッド 呼び出しの最適化8) との可能であれば併用することが望ましいであろう．

類似性があると思われる．この手法では，メソッド呼び

8.

関連研究

出しの最適化を行う際に，レシーバクラスを予測して，インライン展開を可能にする．たとえば，r.draw()

データフロー関数型言語の分野でも，このような研というコード において，r のクラスがほとんどの場合

究はさかんに行われている．データフロー関数型言語

Box であると予測できるならば，以下のようにコンパイルできる（記法は C++に従う）の一種 Id では，データフローグラフの複数のノードを一つのスレッドにまとめることでオーバヘッドを削減する研究が行われている．Separation Constraint

Partitioning4) と呼ばれるアルゴリズムが有名であり，本研究のゴール融合も大きな影響を受けている．

if(r.class == Box)
Box::draw(); // インライン展開できる
else
r.draw();

また，日下部らの研究9) では V のような非ストリク

強制インライン展開の場合は，値が決定していると予トなデータフロー言語の実装において suspensive と測しているわけだが，デ ィスパッチと関数呼び出しを

9
削除している点で類似性があると考えられる．
9.

おわりに

本研究では，Committed-Choice 型言語 Fleng において，細粒度実行のオーバヘッドを削除する 2 つの手法，ゴール融合と強制インライン展開について，強制
インライン展開の実装を行った上で，比較評価と検討を行った．強制インライン展開は，容易に実装できるが，かなりの程度のオーバヘッド を削減できることが分かった．また両手法を併用することにより，さらなる速度向上がえられることを示した．
本研究は，PIE64 上での評価のみを示した．今後の課題として，ワークステーション上の Fleng 処理系の改善を行った上で，マルチプロセッサワークステー
ション上で評価を行い，C などの言語と Fleng 処理系の比較を行うことがあげられる．
謝辞

有益な御意見を頂いた査読者の方に感謝致し

リング最適化, 情報処理学会研究報告 プログラ
ミング研究会, 96-PRO-10, Vol. 96, No. 107, pp.

43{48 (1996).
6) 荒木拓也, 田中英彦: Committed-Choice 型言語
Fleng のインライン展開による粒度制御手法, 情報処理学会第 53 回全国大会, Vol. 1, No. 3E-8,
pp. 347{348 (1996).
7) 荒木拓也, 田中英彦: Committed-Choice 型言語
Fleng における静的粒度最適化, 情報処理学会論文誌, Vol. 38, No. 9, pp. 1771{1780 (1997).
8) 小野寺民也: オブジェクト指向言語におけるメッ
セージ送信の高速化技 法, 情報処理学会誌, Vol.38,
No. 4, pp. 301{310 (1997).
9) 日下部茂, 森本徹雄, 雨宮真人: 非ストリクトデー
タフロープログラム実行におけるスタッ クフレー
ムの利用, 情報処理学会研究報告 プログラミング研究会, 97-PRO-14, Vol. 97, No. 78, pp. 73{78(1997).

荒木 拓也（学生会員）

1971 年生．1994 年東京大学工学

ます．

参 考 文 献1) Araki, T., Hidaka, Y., Nakada, H., Koike,
H. and Tanaka, H.: System Integration of the
Parallel Inference Engine PIE64, Workshop on
Parallel Logic Programming attached to International Symposium on Fifth Generation Com-

puter Systems 1994 , pp. 64{76 (1994).
2) Nilsson, M. and Tanaka, H.: Fleng Prolog - thelanguage which turns supercomputers into Prolog machines, Logic Programming '86, LNCS
264 , Springer-Verlag, pp. 170{179 (1989).
3) Oyama, Y., Taura, K. and Yonezawa, A.:
An Ecient Compilation Framework for Language Based on a Concurrent Process Calculus,
Euro-Par'97 Parallel Processing, LNCS 1300 ,Springer-Verlag, pp. 546{553 (1997).
4) Schauser, K. E., Culler, D. E. and Goldstein,
S. C.: Separation Constraint Partitioning {A New Algorithm for Partitioning Non-strict
Programs into Sequential Threads, POPL '95 ,ACM, pp. 259{271 (1995).
5) 伊川雅彦, 大野和彦, 五島正裕, 森眞一郎, 中島浩, 富田眞治: KLIC におけるゴール・スケジュー

部電気工学科卒業．1996 年同大学院
情報工学専攻修士課程修了．現在，同大学院博士課程に在学中．並列プロ
グラミング言語の最適化の研究に従事．並列論理型言語，並列関数型言語，並列オブジェ
クト指向言語，並列化コンパイラなどに興味を持つ．
田中 英彦（正会員）

1943 年生．1965 年東京大学工学部電子工学科卒業．1970 年同大学
院博士課程終了．工学博士．同年東京大学工学部講師．1971 年助教授，

1978 年〜1979 年ニューヨーク市立大学客員教授，1987 年教授現在に至る．計算機アーキ
テクチャ，並列処理，人工知能，自然言語処理，分散
処理，CAD 等に興味を持っている．
「 非ノイマンコン
ピュータ」「，情報通信システム」著，「計算機アーキテク
チャ」「，VLSI コンピュータ I ，II 」「，ソフトウエア指向
アーキテクチャ」共著，New Generation Computing
編集長，情報処理学会，電子情報通信学会，人工知能学会，ソフトウエア科学会，IEEE ，ACM ，各会員．