並列化コンパイラに関する研究


本研究では、Work-Time C言語で記述されたプログラムを、 通信関数の呼び出しを含むC言語で記述されたSPMDプログラムへ 変換するトランスレータの作成を行っている。
また、通信関数のAPIとしては、 MPI(Message Passing Interface) を用いている。これにより、MPIをサポートする多くの並列計算機や COW(Cluster Of Workstations)環境上での実行が可能である。

本トランスレータの動作の概要を説明する。

本トランスレータでは、par文によるデータ並列計算 および並列再帰の実行をサポートしている。 また、Work-Time Cソースコードに対して以下に示す最適化を施すため、良好な実行性能を 持つSPMDプログラムを生成することができる。


データ並列計算における通信の最適化

計算に必要なデータが他プロセッサのローカルメモリにある場合には通信が発生する。 現在の並列計算機においては、四則演算命令などの実行時間に比べて、通信に要する時間が 非常に大きい。この通信に要する時間を削減することによりSPMDプログラムの性能を向上 させることができる。本トランスレータでは、データ並列計算時に以下の通信最適化を 行っている。

通信のループ追い出し
ループ中で他プロセッサの持つデータを参照しているが、その値はループ中で一定である場合、 ループ開始前にデータを受信して一時領域に持つ事で、ループ中で毎回通信する事を防ぐ。
メッセージの集成
同じプロセッサ間で複数のデータを転送する場合、それらのデータをバッファに格納して まとめた後、一括して転送する。
メッセージのベクトル化
ループの各イタレーションで連続した領域を参照しているが、領域内の値はループ中で一定である場合、 ループ開始前にその領域をベクトルとして一括転送する。
メッセージの融合
上記により、二つのベクトル通信で同プロセッサへの転送領域が重複する場合、 二つの領域の和集合を転送するような一つのベクトル通信へ変換する。


並列再帰の実行方式

並列再帰を効率良く実行するためには、並列に実行する再帰呼び出しの 数や計算量を考慮した実行方式が必要である。本トランスレータでは、 以下の3つの実行方式をサポートしており、Work-Time Cのソースコード中で そのコードに適した実行方式を選択することができる。

simple法
再帰呼び出しの処理にプロセッサの集合を割り当てる実行方式である。 並列再帰を行う際、プロセッサ集合を適当な部分集合に分割し、 各再帰呼び出しに部分集合を割り当てる。集合に含まれるプロセッサ 数が1になると、それ以降は1台のプロセッサが再帰処理を行う。 この手法では、プロセッサの割り当て処理が単純なため、プロセッサ管理 のオーバヘッドを抑えることができる。
dynamic法
マネージャ・ワーカモデルに基づく実行方式である。 並列再帰を行う際、管理用プロセッサ(マネージャ)にアイドル状態の プロセッサ(ワーカ)を要求し、そのプロセッサに再帰呼び出しを割り当てる。 この方式では、プロセッサの割り当てを動的に決定し、処理を終えたプロセッサ にも再び処理を割り当てることができるため、プロセッサ間の負荷の偏りを抑制 することができる。
PD法
simple法と同様に、再帰呼び出しにプロセッサ集合を割り当てる実行方式 である。この実行方式では、再帰処理を終えたプロセッサ集合を他の再帰処理を 行っている集合に追加するため、dynamic法と同様の負荷均等化を行うことが できる。さらに、dynamic法では管理用プロセッサが少ない場合、そのプロセッサに 管理負荷が集中し、性能が低下する可能性があるが、この方式では各プロセッサ集合 がそれぞれ独立に管理されるため、負荷の集中を防ぐことができる。


SPMD(Single Program Multiple Data)プログラム

並列実行の際、各プロセッサは同一のプログラムを用いて、各ローカルメモリ上の データを処理する。データの内容によって異なる処理を行う、他のプロセッサが 持つデータを必要とする場合は通信によってそのデータを取得する、等は可能。
プロセッサが どの命令を実行するか、どのプロセッサと通信するか、等は、プロセッサID を元に決定するようにプログラム中に予め記述されている。


萩原研究室ホームページに戻る
萩原研の研究内容のページへ戻る