JPH056712B2

JPH056712B2 -

Info

Publication number: JPH056712B2
Application number: JP59213315A
Authority: JP
Inventors: Masaki Aoki; Hiroshi Nakada; Toshihiro Hirabayashi
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1984-10-12
Filing date: 1984-10-12
Publication date: 1993-01-27
Also published as: JPS61100862A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、ベクトル計算機用のオブジエクト・
モジユールを作成するコンパイラ、特にベクトル
化された複数のDOループ間における命令の逐次
化処理方式に関するものである。

〔従来技術と問題点〕

ベクトル計算機においては、演算器の高速化と
その演算器に見合うデータの供給能力が、実行効
率向上の重要な鍵である。このため最近のベクト
ル計算機では、並列動作可能な２本のロード／ス
トア・パイプラインを用意し、データの供給能力
を高めている。しかし、複数のロード／ストア・
パイプラインが並列に動作することにより、メモ
リ・アクセス命令の同期化（逐次化と同義）が必
要となつてきた。ハードウエアでは、このような
同期化は困難であり、従来のベクトル計算機を含
むシステムでは、これをソフトウエアで実現して
いる。

ベクトル計算機のハードウエアでは、メモリ・
アクセス命令の同期化手段としては、下記のもの
がある。

(a) パイプラインID ベクトルのメモリ・アクセス命令が動作するパ
イプラインを指定するもので、順序関係を保証す
る必要のあるメモリ・アクセス命令を同一のパイ
プラインで動作させることにより同期を取ること
が出来る。

(b) 同期化命令（POST／WAIT命令）メモリ・アクセス命令間の順序関係を同期化命
令で保証する方法である。この方法を用いること
により、POST命令以前のメモリ・アクセス命令
とWAIT命令以後のメモリ・アクセス命令との
同期を取ることが出来る。

同期化処理においては、単にメモリ・アクセス
命令の順序関係を保証するだけではなく、実行性
能が低下しないように効率的に同期化を行う必要
がある。しかしながら、従来のコンパイラにおい
ては、ベクトル化された複数のDOループ間での
データの依存関係を考慮していなかつた。そのた
め、個々のDOループ単位にその終了時点で逐次
化処理が成されており、並列処理計算における実
行効率低下の一因となつていた。

〔発明の目的〕

本発明は、上記の考察に基づくものであつて、
複数のDOループ間において最適な命令の逐次化
処理を施し、実行性能を高めることを目的として
いる。

〔目的達成のための手段〕

そしてそのため、本発明の命令の逐次化方式はベクトル化後の中間テキストについて逐次化処
理を施す逐次化処理部を持つコンパイラにおい
て、上記逐次化処理部が、制御の流れが一定のDOループ群を取り出す
処理と、配列に出現する添字を参照して、DOループ
群内のデータ依存関係を調べる処理と、 DOループ間にベクトルとスカラの依存関係
があるか否かを調べる処理と、で依存関係なしとされたことを条件に、パ
イプラインIDによる多重ループ内の逐次化を
施す処理と、で依存関係ありとされたことを条件に、
DOループ単位に逐次化を施す処理と、の逐次化の効率が良好か否かを調べる処理
と、の処理で良好でないとされたことを条件
に、DOループ間の逐次化を施す処理と、の逐次化の効率が良好か否かを調べる処理
と、の処理で良好でないとされたことを条件
に、DOループ内の逐次化を施す処理とを行うように構成されていることを特徴とするものである。

〔発明の実施例〕

以下、本発明を図面を参照しつつ説明する。第
１図は本発明のコンパイラの概要を示す図であ
る。このコンパイラは、ベクトル計算機を含むシ
ステムで実行されるオブジエクト・モジユールを
生成するVPコンパイラである。第１図において、
１はソース解析部、２は番地割付け部、３はベク
トル化部、４は逐次化処理部、５は中間テキスト
最適化部、６はレジスタ割付け部、７は命令生成
部をそれぞれ示している。ソース解析部１は、宣
言文で定義された配列や変数とソース・プログラ
ムの手続き部における取扱との矛盾を検出した
り、未定義の配列や変数が定義又は参照されてい
ないかを調べると共に、ソース・プログラムをブ
ロツク化したりするものである。番地割付け部２
は、データに対してメモリ領域を割付たり、配列
や変数に対して初期値を与えたりするものであ
る。ベクトル化部３は、DOループをベクトル命
令列に変換するものである。逐次化処理部４は、
命令の逐次化を行うものである。本発明は逐次化
処理部４に関するものである。中間テキスト最適
化部５は、ベクトル化後の最適化等を行うもので
ある。レジスタ割付け部６は、データをレジスタ
に割付ける等の処理を行うものである。命令生成
部７は、中間テキストを機械語命令に変換するも
のである。

要約すると、本発明は、ベクトル化後の中間テ
キスト（命令列）において、ベクトル化の技術
（配列に出現する添字の振るまい方）を応用して、
広範囲にデータ依存関係を把握し、データ依存関
係（逐次化に必要なデータ）に対してパイプライ
ンID又は同期化命令を用いて最適な命令の逐次
化処理を施すものである。

第２図は本発明の命令の逐次化処理の流れを示
す図である。

制御の流れが一定のDOループ群を取出す。
第３図は制御の流れが一定なDOループ群の例
を示すものであり、矢印Ａ−Ｂ、Ｃ−Ｄ、Ｅ−
Ｆ等が制御の流れが一定なDOループ群をしめ
す。制御の流れが一定であるプログラム構造と
は、飛び出し／飛び込みがないプログラム構造
のことであり、最適化コンパイラ作成者にとり
自明のことである。

DOループ群内のデータ依存関係を把握す
る。即ち、複数次元の添字に対して重なりをチ
エツクスする。この際、上位次元の添字情報に
おいて、ずれが生じていれば下位次元において
重なりはない。例えば下記のようなプログラム
があつたとする。

DO 10 Ｊ＝１，Ｎ DO 10 Ｉ＝１，ＮＡ（Ｉ，Ｊ）＝Ａ（Ｉ，Ｊ−１）＋Ｓ 10 CONTINUE この文章は下記のように展開される。

DO 10 Ｉ＝１，Ｎ 10 Ａ（Ｉ，１）＝Ａ（Ｉ，Ｏ）＋Ｓ DO 10′I＝１，Ｎ 10′A（Ｉ，２）＝Ａ（Ｉ，１）＋Ｓこの例において、内側のDOループでは２次
元目の添字が異なるため、Ａのメモリ・アクセ
スに対して重なりはない（逐次化不必要）。し
かし、外側のループを考えたときＡのストアと
Ａのロードで重なりが生じ、逐次化を行う必要
がある。

DOループ間にベクトルとスカラの依存関係
があるか否かを調べる。Yesのときはの処理
を行い、Noのときはの処理を行う。

多重DOループ内の逐次化を行う。、即ち外
側の回転によるデータの依存関係に基づき逐次
化を行う。

DOループ単位の逐次化を行う。逐次化は、
パイプラインID又は同期化命令により行われ
る。

効率をチエツクする。即ち、パイプライン
IDの密度を調べる。NGであればの処理を行
う。効率が良好か否かの判定基準は実行性能に
より決定され、ハードウエア毎の特性による。

DOループ間の逐次化を行う。即ち、最内次
元のみ（上から下のみ）のデータ依存関係に基
づいて逐次化を行う。逐次化は、パイプライン
ID又は同期化命令により行われる。

効率をチエツクする。NGであればの処理
を行う。効率が良好か否かの判定基準は実行性
能により決定され、ハードウエア毎の特性によ
る。

DOループ内の逐次化を行う。即ち、DOル
ープ内の閉じたデータ依存関係に基づいて逐次
化を行う。逐次化は、パイプラインID又は同
期化命令により行われる。

次に本発明を具体例で説明する。いま、下記の
ようなDOループ群を考える。

DO 10 Ｊ＝２，100 DO 10 Ｉ＝２，100 Ａ（Ｉ，Ｊ）＝Ａ（Ｉ−１，Ｊ−１）＋Ａ（Ｉ，
Ｊ−１） 10 CONTINUE この例では、内側DOループの回転によるデー
タ依存関係はない。しかし、外側DOループの回
転により→、→なるデータ依存関係が生
ずる。なお、はＡ（Ｉ，Ｊ）を、はＡ（Ｉ−
１，Ｊ−１）を、はＡ（Ｉ，Ｊ−１）を示して
いる。この場合、広域的な範囲（外側のDOルー
プのデータ依存関係）で同期化を行うと、ない
しのメモリ・アクセスに対して同一のパイプラ
インIDが必要になるため、並列処理効率が著し
く悪くなる。従つて、局所的範囲で（内側DOル
ープのデータ依存関係で）同期化を行う方が良
い。このとき、他範囲のデータ依存関係は、
POST／WAIT命令により同期化を取る。

広域的な範囲で同期化が最適な場合の例につい
て説明する。いま、下記のようなDOループ群を
考える。

DO 10 Ｊ＝１，100 DO 10 Ｉ＝１，100 Ａ（Ｉ，Ｊ）＝Ｂ（Ｉ，Ｊ）＋Ａ（Ｉ，Ｊ−１） 10 CONTINUE この例は、先の例と同様の構造を持つが、外側
DOループの回転によるデータ依存関係は→
のみであり、広域的な範囲（外側DOループのデ
ータ依存関係）で同期化を行つても並列処理効率
は高い。なお、はＡ（Ｉ，Ｊ）を、はＡ（Ｉ，
Ｊ−１）を示している。従つて、パイプライン
IDを用いて広域的な範囲で同期化を行う方が最
適である。

広域的な範囲で同期化が最適な場合の他例につ
いて説明する。いま、下記のようなDOループ群
を考える。

DO 10 Ｉ＝１，100 Ａ（Ｉ）＝Ｃ（Ｉ）＋Ｂ（Ｉ−１） 10 CONTINUE DO 20 Ｉ＝１，100 Ｂ（Ｉ）＝Ｃ（Ｉ）＊Ａ（Ｉ＋１） 20 CONTINUE この例においては、局所的な範囲で同期化を行
つた場合、DOループ間でPOST／WAIT命令に
より同期が取られるため、並列処理効率が悪くな
つてしまう。しかしDOループ間のデータ依存関
係で同期化した場合には、→及び→にパ
イプラインIDが必要となるのみで、並列処理効
率も高い。なお、はＡ（Ｉ）を、はＢ（Ｉ−
１）を、はＢ（Ｉ）を、はＡ（Ｉ＋１）を示し
ている。

局所的な範囲で同期化が最適な場合の他例につ
いて説明する。いま、下記のようなDOループ群
を考える。

DO 10 Ｉ＝１，100 Ａ（Ｉ）＝Ｃ（Ｉ） 10 CONTINUE DO 20 Ｊ＝１，50 Ｂ（Ｊ）＝Ａ（50） 20 CONTINUE この例では、DOループ間にベクトルとスカラ
の依存関係があるので、DOループ単位で逐次化
を行う。上記のDOループ群に対応するベクトル
命令列は下記のようになる。

VL VR1，Ｃ（１：100） VST VR1 Ａ（１：100） VPT VWT VL VR2，Ａ（50） VST VR2，Ｂ（１：50）なお、VLはベクトル・ロード命令、VSTはベ
クトル・ストア命令、VPTはPOST命令、VWT
はWAIT命令、VRXはベクトル・レジスタをそ
れぞれ示す。

〔発明の効果〕

以上の説明から明らかなように、本発明によれ
ば、データ依存関係を広範囲に把握し、最適な逐
次化処理を行うことにより、ベクトル化された
DOループ間（ベクトル命令列）及びその他の範
囲（スカラ命令列）との並列性が高まり、実行効
率が向上する。

【図面の簡単な説明】

第１図は本発明のコンパイラの概要を示す図、
第２図は本発明の命令の逐次化処理の流れを示す
図、第３図は制御の流れが一定なDOループ群の
例を示す図である。１……ソース解析部、２……番地割付け部、３
……ベクトル化部、４……逐次化処理部、５……
中間テキスト最適化部、６……レジスタ割付け
部、７……命令生成部。

Claims

【特許請求の範囲】１ベクトル化後の中間テキストについて逐次化
処理を施す逐次化処理部を持つコンパイラにおい
て、上記逐次化処理部が、制御の流れが一定のDOループ群を取り出す
処理と、配列に出現する添字を参照して、DOループ
群内のデータ依存関係を調べる処理と、 DOループ間にベクトルとスカラの依存関係
があるか否かを調べる処理と、で依存関係なしとされたことを条件に、パ
イプラインIDによる多重ループ内の逐次化を
施す処理と、で依存関係ありとされたことを条件に、
DOループ単位に逐次化を施す処理と、の逐次化の効率が良好か否かを調べる処理
と、の処理で良好でないとされたことを条件
に、DOループ間の逐次化を施す処理と、の逐次化の効率が良好か否かを調べる処理
と、の処理で良好でないとされたことを条件
に、DOループ内の逐次化を施す処理とを行うように構成されている。ことを特徴とする命令の逐次化方式。