データフロー解析に基づく関数型言語 Valid の並列化コンパイラ

概要

論文の詳細を見る
本論文では,関数型プログラムを共有メモリ型マシン上で並列実行するためのコンパイル手法,および,実装方式を提案する.用いた言語はValid,ターゲットマシンはSequent Symmetry S2000で,関数適用レベルの並列処理を実現する.コンパイラは,まず,ソースプログラムからデータフロー解析に基づくコントロールフローグラフを生成する.グラフはDAGで,ノードで命令を,アークでコントロールフローを表す.次に,グラフを関数適用ノードの子孫と,それ以外の部分に分割し,各部分グラフ毎に命令の実行順序をスケジュールする.最後に各命令をターゲットマシンのコードへ変換する.関数適用の並列実行は,fork-joinタイプの方式で行う.共有メモリマシンでは,排他制御が頻繁に生じると処理が逐次化され期待した台数効果を得ることが因難になる.我々は,排他制御の頻度,時間を減らすために,実行タスクキューの複数化,階層化,不可分なマシンコードの使用などの工夫を行った.評価では,Symmetry上で16個のプロセッサを用い,実行速度について,Cプログラム,SISALプログラムとの比較を行った.また,実行効率に対する粒度の影響,Validの拡張による並列制御のオーバヘッドの解決も試み評価した.結果を報告し,本手法の有効性について検討する.
1994-04-15

データフロー解析に基づく関数型言語 Valid の並列化コンパイラ

スポンサーリンク

概要

著者

関連論文

スポンサーリンク