特許

J-GLOBAL ID：200903082419327133

コンパイラにおけるコード生成方法及びコンパイラ

発明者： 小笠原 武史 ,  小松 秀昭
出願人/特許権者： インターナショナル・ビジネス・マシーンズ・コーポレイション
代理人 (1件)： 合田 潔 (外2名)
公報種別：公開公報
出願番号（国際出願番号）：特願平6-311764
公開番号（公開出願番号）：特開平8-185325
出願日： 1994年12月15日
公開日（公表日）： 1996年07月16日
要約：

【要約】【目的】 インデックスセットが分配可能、という条件は満たすが、代入文右辺のデータ依存が1つに決められる、という条件は満たさないような特性をもつループを並列化すること。【構成】do i=M, Na(i) = a(x)enddoは、xがコンパイル時に決定されない変数なので、従来技術では並列化できない。そこで、M, Nとxの大小関係に応じて、xも含めてi=M..Nというインデックスセットを複数のプロセッサに分配し、これによって、ループの前に定義された値を使用するプロセッサセットと、ループの後で定義された値を使用するプロセッサセットとを計算し、ループの前後にこれらのプロセッサに対する通信を行わせるコードを挿入することにより、ループ内ではプロセッサ間の通信を行う必要がないようにし、以って実行プログラムの速度を向上させる。

請求項（抜粋）：

複数のプロセッサをもつコンピュータにおいて、ソース・プログラムにおけるループを複数のプロセッサに分割して並列に実行させることにより、プログラムの実行を高速化するようにコードを生成するための、コンパイラにおけるコード生成方法であって、(a) ソース・プログラムを読み込む段階と、(b) 上記ソース・プログラムにおいて、インデックスセットが分配可能かどうかが決まる、という条件は満たすが、代入文右辺のデータ依存が1つに決められる、という条件は満たさないループを見出す段階と、(c) 上記見出されたされたループの最も内側のループのインデックス変数を#IV.dとし、そのループ内の式における、両辺に同一の、N次元(Nは1以上の整数)の配列aをもつ式に着目し、その式の左辺の配列aのm番目(mは1以上でN以下の任意の整数)の添字がc1 * #V1.d + c2(c1,c2は、該最も内側のループにおけるループ不変定数であって、c1 は、0に等しくない)であること、その式の左辺の配列aのm番目の次元が複数のプロセッサ間でブロック状に分配されていることと、及びその式の右辺の配列aのm番目の添字式xが、コンパイル時点では値が不定であるけれどもプログラム実行時点では値が最内ループで不変であるような変数であること、という条件を満足するかどうかを決定する段階と、(d) 上記段階(c)において上記条件が満足されたと決定されたことに応答して、上記c1,c2及び上記m番目の添字の上記複数のプロセッサ間の分配の情報に応じて、上記複数のプロセッサ毎に、ループ計算の添字の下限lbと上限ubを計算し保持する段階と、(e) 上記段階(d)で計算された、上記複数のプロセッサ毎のループ計算の添字の下限lbと上限ubの値と、上記c1,c2と、上記xの値に応じて、受信プロセッサセットを計算する段階と、(f) 上記段階(e)で計算された受信プロセッサセットに応じて、受信プロセッサセットに対する通信を行うコードを生成する段階と、(g) 上記段階(d)で計算されたプロセッサ毎のループ計算の添字の下限lbと上限ubの値に応じて、上記最も内側のループに関して、上記複数のプロセッサ毎にパイプライン化されたループのコードを生成する段階を有する、に記載のコンパイラにおけるコード生成方法。

IPC (3件)：

G06F 9/45 ,  G06F 9/38 330 ,  G06F 15/16 430