近年、コスト・パフォーマンスのよい並列処理環境として計算機クラスタ環境 が注目されている。 計算機クラスタ環境において、並列プログラムを容易に開発可能とするために は、計算機クラスタ環境に適した並列化コンパイラを提供しなければならない。 しかし、計算機クラスタ環境の構成は様々であり、すべての計算機クラスタ環 境を対象とする汎用的な並列化コンパイラの開発は、非常に困難である。 そこで、我々は並列化コンパイラの構築ツールとして、並列化コンパイラ・ ツールキットを開発している。 並列化コンパイラ・ツールキットでは、並列化戦略に沿ってプログラムを並列 処理単位へ分割する処理と、並列処理単位を計算機環境に対応させて割り当て る処理で構成される。
本論文では、並列化戦略を反映したプログラム分割処理として、並列化戦略を ルールで表現することによりプログラムの並列化を可能とする手法を提案する。 本手法では、プログラムの並列化処理を依存グラフの変形処理でモデル化する。 依存グラフ上のノードを並列処理単位と捉え、互いに依存しないノードを生成 するように依存グラフを変形操作することで並列処理を達成する。 このとき、変形処理をルールとして表現し、並列化ポリシと定義する。 並列化ポリシを自由に構成することで、様々な並列化手法を表現することがで きる。 そして、並列化ポリシを依存グラフに適用することで、意図した並列化処理が 実現される。 並列化ポリシの適用に対しては、複数の並列化ポリシの衝突・競合などの問題 や、適用により生じる実行の妨げとなる依存関係や冗長な情報となる依存関係 の問題を解決しなければならない。 衝突・競合の問題では、適用順序を決定する機構を設け、依存グラフの変形を一意にする処理を施す。 また、問題となる依存関係を依存グラフの変形操作により取り除くアルゴリズムを提案する。