パイプライン化された依存性グラフからの高速非同期式プロセッサの生成

本研究では、パイプライン動作を表現した依存性グラフ(プロセッサ内で実行される部分処理(基本操作)間の実行順序や条件分岐などを記述した有向グラフ)から、効率的に動作する2相非同期式回路を生成する手段を得ることを目的とし、その基本アルゴリズムを開発した。まず、バイプライン動作を表す依存性グラフを、より効率的に作成するため、以前に開発した依存性グラフのパイプライン化アルゴリズムを抜本的に改良した。次に、以上の研究成果を用いてより一般的な依存性グラフを用いて試験した結果、前年度に開発したアルゴリズムでは、一定の条件を満たしたクラスの依存性グラフにしか適用できないことが判明した。そのため、やはり、条件分岐を含まない場合に限定し、アルゴリズムを改良した。改良したアルゴリズムでは、バイプライン動作を表現した依存性グラフが、動作ステージ間でループ構造を構成する点に着目し、これらのループ構造ごとに、ループの最初に実行される基本操作と最後に実行される基本操作の相を反転させるように、グラフを構成し直す。これによって、並列に動作すべき基本操作対において、稼動相どうしが並列に動作できる2相依存性グラフが生成できるようになった。本アルゴリズムが、上記前提のもとで正当であることについても、ループ構造ごとの繰り返し適用である点に着目し、そのループ構造の複雑度に関する帰納法を適用することで証明可能となった。本方法では、条件分岐を含まない場合に関しては、その目的を達成したが、条件分岐を含む場合のアルゴリズムは未完成である。この点は、条件分岐を含む依存性グラフの構造を、上述のように一般的な構成要素に分解することによって可能となると考えられる。

本研究では、パイプライン動作を表現した依存性グラフ(プロセッサ内で実行される部分処理(基本操作)間の実行順序や条件分岐などを記述した有向グラフ)から、効率的に動作する2相非同期式回路を生成する手段を得ることを目的とし、その基本アルゴリズムを開発した。まず、バイプライン動作を表す依存性グラフを、より効率的に作成するため、以前に開発した依存性グラフのパイプライン化アルゴリズムを抜本的に改良した。次に、以上の研究成果を用いてより一般的な依存性グラフを用いて試験した結果、前年度に開発したアルゴリズムでは、一定の条件を満たしたクラスの依存性グラフにしか適用できないことが判明した。そのため、やはり、条件分岐を含まない場合に限定し、アルゴリズムを改良した。改良したアルゴリズムでは、バイプライン動作を表現した依存性グラフが、動作ステージ間でループ構造を構成する点に着目し、これらのループ構造ごとに、ループの最初に実行される基本操作と最後に実行される基本操作の相を反転させるように、グラフを構成し直す。これによって、並列に動作すべき基本操作対において、稼動相どうしが並列に動作できる2相依存性グラフが生成できるようになった。本アルゴリズムが、上記前提のもとで正当であることについても、ループ構造ごとの繰り返し適用である点に着目し、そのループ構造の複雑度に関する帰納法を適用することで証明可能となった。本方法では、条件分岐を含まない場合に関しては、その目的を達成したが、条件分岐を含む場合のアルゴリズムは未完成である。この点は、条件分岐を含む依存性グラフの構造を、上述のように一般的な構成要素に分解することによって可能となると考えられる。