JPH03220669A - 多重ループベクトル化コンパイル方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は電子計算機システムのコンパイラにおける多重
ループベクトル化コンパイル方式に関するものである。

〔従来の技術〕

記憶域上に規則的に並んでいるデータに対して一度に演
算を行うベクトル命令をもつベクトル処理プロセッザに
おいては、−船釣に目的プログラムのうちのベクトル命
令によって実行される部分の割合を大きくすればするほ
ど、プログラムの実行時間を短縮することができる。こ
れは、通常の命令（スカラ命令）を何回も繰り返さなけ
れば行えない演算を１個のベクトル命令で実行すること
ができるからである。従って、このようなヘクＩ・ル処
理プロセソザに対するコンパイラでは、与えられた原始
プログラムを可能な限りベクトル命令による並列実行可
能な形で目的プログラムに変換することが望まれる。

ところで、ベクトル命令をもつベクＩ・ル処理プロセッ
サに対する従来のコンパイラは、一般に、高級言語で記
述された原始プログラムを読み込み構文解析を行って第
１中間テキストを生成する構文解析部と、第１中間テキ
ストから原始プログラム中のループ構造を検出してベク
トル化可能部分の認識を行いムク１〜ル処理用のテキス
トを含む第２中間テキストを生威するベクトル化処理部
と、第２中間テキストから目的プログラムを生成して出
力するコード生成部とから、その主要部が構成されてい
る。

このような従来のコンパイラは、例えば第１０図に示す
ようなＦＯＲＴＲＡＮ言語によって記述されたＤＯルー
プを含む原始プログラムが与えられた場合、構文解析部
がこの原始プログラムを読み込んで第１１図に示すよう
な構成の第１中間テキスト（ステップ３１〜３４）を生
威し、次いで、ベクトル化処理部が第１中間テキストを
変形して第１２図に示すような構成の第２中間テキスト
（ステップＳ１１．３１２）を生威し、コード生成部が
第２中間テキストを読み込んで実際のコードから構成さ
れる目的プログラムを生成し出ノ〕するようにしていた
。

また、上記のような単一のループに限らず、多重ループ
であっても所定の条件が満たされれば一重化によるベク
トル化が可能であった。例えば、第１３図に示すような
多重ＤＯループ含む原始プログラムが与えられた場合、
第１４図に示すように、配列Ａ、　Ｂ、　　Ｃ，Ｄと要
素数を同しにした１次元の配列ＡＡ、ＢＢ、ＣＣ，ＤＤ
を新たに宣言し、ＥＱＵ　Ｉ　ＶＡＬＥＮＣＥ文により
配列Ａ。

Ｂ、Ｃ，Ｄと配列ＡＡ、ＢＢ、ＣＣ，ＤＤとをそれぞれ
一致させることにより、多重ＤＯループ単一のＤＯルー
プ置き換え、この単一のＤＯループ対して第１０図〜第
１２図と同様な手法でベクトル化を行うものである。

〔発明が解決しようとする課題〕

上述したように、従来のコンパイラでは所定の条件のも
と、単一のループに限らず、多重ループであってもベク
トル化が可能であったが、−重化によってベクトル化で
きるための条件が厳しく、それを満たさないような場合
はベクトル化による実行時間短縮の効果が得られないと
いう欠点があった。

すなわち、多重ループについて一重化によるベクトル化
が行える条件としては、 ■ループ中に並列実行に矛盾するデータ依存関係がない
こと ■ループ中の配列要素の定義引用が記憶域上で等間隔で
あること ■ループ中の配列要素の定義引用が記憶域上で一方向で
あること である。なお、■は当然のこととして、■、■は１次元
化した配列（第１４図の例でばＡＡ、　ＢＢＣＣ，ＤＤ
）の要素を順次増減させて行くことから要求される条件
である。

しかして、第４図に示すような多重Ｄｏループを含む原
始プログラムが与えられた場合、Ｄ○変数にの増分が「
２」であると共に、内側のＤＯループＤ○変数の終値が
その配列に許される最大値でないので、上記の■の条件
を満たさないため、この原始プログラムは一重化による
ベクトル化が行えず、最も内側のＤｏループについてだ
け、前述した第１０図〜第■２図と同様の手法でベクト
ル化が行えるに過ぎず、よって、生成された目的プログ
ラムを実行するベクトル処理プロセッサでは外側のルー
プ制御および配列の添字計算についてはスカラ命令で順
次実行することを余儀なくされていた。

本発明は上記の点に鑑み提案されたものであり、その目
的とするとごろは、」二記の■、■の条件が満たされれ
ば、■の条件が満たされていない場合であっても一重化
によるベクトル化が行え、より一層の実行時間短縮を達
成することのできる多重ループベクトル化コンパイル方
式を提供することにある。

〔課題を解決するための手段〕

本発明は上記の目的を達成するため、高級言語で記述さ
れた原始プログラムを読み込み構文解析を行って第１中
間テキストを生成する構文解析部と、第１中間テキスト
から原始プログラム中のループ構造を検出してベクトル
化可能部分の認識を行いベク（・ル処理用のテキストを
含む第２中間テキストを生成するベクトル化処理部と、
第２中間テキストから目的プログラムを生成して出力す
るコード生成部とを有し、ベクトル処理プロセッサに対
して、与えられた原始プログラムから目的プログラムを
生成して出力するコンパイル方式において、 前記ベクトル化処理部に、 第１中間テキストから原始プログラムのループ中の制御
の流れを解析する構造解析手段と、ループ中に並列実行
に矛盾するデータ依存関係があるか否かを判定するデー
タ依存関係判定手段と、 並列実行に矛盾しないと判定された部分につき通常のも
しくはマスク使用による多重ループの−・重化が可能か
否かを解析して判定する多重ループ−重化解析手段と、 一重化が可能と判定された部分および並列実行に矛盾し
ないと判定された他の部分を一重化およびもしくはベク
トル化して第２中間テキストを生成するベクトルテキス
ト生成手段とを設けるようにしている。

〔作用〕

本発明の多重ループベクトル化コンパイル方式にあって
は、構文解析部の生成した第１中間テキストに対し、ベ
クトル化処理部の構造解析手段が原始プログラムのルー
プ中の制御の流れを解析し、データ依存関係判定手段が
ループ中に並列実行に矛盾するデータ依存関係があるか
否かを判定し、並列実行に矛盾しないと判定された部分
につき多重ループ−重化解析手段が通常のもしくはマス
ク使用による多重ループの一重化が可能か否かを解析し
て判定し、−重化が可能と判定された部分および並列実
行に矛盾しないと判定された他の部分をベクトルテキス
ト生成手段が一重化およびもしくはベクトル化して第２
中間テキストを生成し、次いで、この第２中間テキスト
からコード生成部が目的プログラムを生成して出力する
。

〔実施例〕

以下、本発明の実施例につき図面を参照して説明する。

第１図は本発明の多重ループベクトル化コンパイル方式
を適用したコンパイラの一実施例を示す構成図である。

第１図において、コンパイラ２は、基本的な構成として
、高級言語で記述された原始プログラム１を読み込み構
文解析を行って第１中間テキスト２４を生成する構文解
析部２１と、第１中間テキスト２４から原始プログラム
１中のループ構造を検出してベクトル化可能部分の認識
を行いベクトル処理用のテキストを含む第２中間テキス
ト２５を生成するベクトル化処理部２２と、第２中間テ
キスト２５から目的プログラム３を生成して出力するコ
ード生成部２３とを含んでいる。

また、本発明の特徴部分として、ベクトル化処理部２２
には、第１中間テキスト２４から原始プログラム１のル
ープ中の制御の流れを解析する構造解析手段２２１と、
ループ中に並列実行に矛盾するデータ依存関係があるか
否かを判定するデータ依存関係判定手段２２２と、デー
タ依存関係判定手段２２２により並列実行に矛盾しない
と判定された部分につき通常のもしくはマスク使用によ
る多重ループの一重化が可能か否かを解析して判定する
多重ループ−重化解析手段２２３と、多重ループ−重化
解析手段２２３により一重化が可能と判定された部分お
よびデータ依存関係判定手段２２２により並列実行に矛
盾しないと判定された他の部分を一重化およびもしくは
ベクトル化して第２中間テキストを生成するベクトルテ
キスト生成手段２２４とが設けられている。

第２図は構造解析手段２２１において多重ループの構造
解析の結果である解析情報を表現するのに用いる多重Ｄ
○ループ情報テーブル４の論理的構成を示したものであ
り、次の多重Ｄｏ小ループ報テーブルへのポインタ４１
と、Ｄ○ループネストチェーン４２と、Ｄ○ループ−重
化テーブルへのポインタ４３と、配列テーブルへのポイ
ンタ４４と、ベクトルテキストへのポインタ４５と、Ｄ
Ｏ変数のシンボルテーブルへのポインタ４Ｇと、Ｄ○ル
ープ初期値のトライアト４７と、Ｄｏ小ループ値の１−
ライアト４８と、ＤＯループ分値のトライアト４９とか
ら構成されている。

第３図は多重ループ−重化解析手段２２３において一重
化が可能な多重ループを解析した結果の解析情報を表現
するのに用いるＤｏループ一重重化上 １−ブル５の論理的構成を示したものであり、最内側の
多重Ｄ○ループ情報テーブルへのポインタ５１と、マス
ク用配列テーブルへのポインタ５２と、−重化後のＤ○
ループ初期値のトライアト５３と、−重化後のＤＯルー
プ終値のトライアト５４と、−重化後のＤＯループ分値
のトライアト５５と、−重化後のＤｏ小ループ繰り返し
数５６とから構成されている。

以下、従来では多重ループの一重化によるベクトル化が
行えなかった第４図に示す原始プログラムが与えられた
場合を例にとって動作を説明する。

具体的な動作に先立って、本発明による多重ループの一
重化の手法を概念的に説明する。

すなわち、本発明では、第４図の原始プログラムを第５
図に示すような２つの多重ＤＯループ含む形にし、最初
の多重Ｄｏ小ループ元の原始プログラムにおける多重Ｄ
Ｏループ同しＤｏ変数を用い、その最内側ではマスク用
配列Ｗに値「１」を代入するだけの命令を置き、次の多
重ＤＯループはＤ○変数の増分を全て「１」とすると共
に、２ 内側のＤ○変数のＰ、（Ｉｉ！をその配列で許される最
大値とし、そのループの最内側でマスク用配列Ｗの要素
が例えば「１」である場合にのみ元の原始プログラム中
におけると同し定義引用を行わせる。

つまり、第４図の原始プログラムにおける多重ＤＯルー
プが一重化できなかったのは、Ｄｏ変＠Ｋが増分「２」
で変化するため、「ループ中の配列要素の定義引用が記
憶域上で等間隔でなければならない」という−重化の条
件に合致しないためであったので、Ｄ○変数にの増分を
強制的に「１」にすると共に、内側のＤｏ小ループＤｏ
変数の終値をその配列で許される最大値としてしまうの
である。ただし、そのままでは、Ｄ○変変数部「２」「
４」、・・・等およびＤｏ変数Ｉ、ＪがＩＴ、ＪＪより
も大きいもの等の、プログラム作成者の意図していない
配列要素についても定義引用が行われてしまうこととな
るため、これを防止するために元の原始プログラムと同
じＤ○変数の多重ＤＯループ残し、その多重ループの中
で演算を実際に行うべきことを示す情報をマスク用配列
Ｗに書き込み、続く多重ＤＯループおいてマスク用配列
Ｗの要素を参照し、その値が「１」である場合にのみ定
義引用を行うようにしている。

そして、第５図のように変形されたもののうち、２番目
の多重ＤＯループ、第１３図および第１４図で説明した
のと同様の手法で一重化する。この状態を第６図に示す
。そして、この−重化したＤ○ループを第１０図〜第１
２図で説明したのと同様の手法でベクトル化する。また
、１番目の多重ＤＯループついても、最内側のＤｏ小ル
ープついて第１０図〜第１２図で説明したのと同様の手
法でベクトル化できる。なお、実際の動作では第４図の
原始プログラムの解析結果に基づいて直接に該当する多
重Ｄ○ループ部分の一重化およびベクトル化が行われる
ため、第５図および第６図のような形に変換された状態
が存在するわけではない。

次に、上記の例につき、第１図の実施例の各手段による
動作を説明する。

先ず、原始プログラム１が与えられてコンパイラ２が起
動されると４、構文解析部２１は原始プログラム１を読
み込み、構文解析を行って第（中間テキスト２４を生成
する。第４図の原始プログラム１に刻しては、第７図に
示すような構成の第１中間テキスト２４　（ステップ２
４０１〜２４１２）が生成される。

次いで、ベクトル化処理部２２の構造解析手段２２１は
第１中間テキスト２４を読み込み、ループを認識してそ
の制御の流れを解析する。具体的には次のような処理を
行う。

■第１中間テキスト２４を分岐を単位としたブロックに
分割する。ここで、分岐はループの出口もしくは人口に
相当する。第７図の第１中間テキスト２４の場合は、ス
テップ２４０２．２４０４．２４０６で分割される。

■ループ部分を文単位のフ１コックに分割する。

■プログラム全体の制御の流れを解析して各ブロックの
関係を求める。

■各々のブロックで定義引用されている配列および変数
に対して、ブロックへの人出情報を■５ 収集する。

なお、上記の解析結果は第２図に示した多重り。

ループ情報テーブル４を用いて表現される。例えば、第
７図の第１中間テキスト２４の各ＤＯループ情報は第８
図に示すように、多重ＤＯループ報テーブルへのポイン
タ６から始まる多重ＤＯループ報テーブル４．ａ、４ｂ
、４．ｃのチェーンおよびその内容として表現される。

ただし、この時点では第８図中のＤＯループ重化テーブ
ル５ａは付加されていない。

次いで、第１図において、データ依存関係判定手段２２
２は解析情報を利用し、ループ中に並列実行に矛盾する
データ依存関係があるか否かを判定する。第４図の原始
プログラムＩについて作威された第８図の解析情報から
は、並列実行に矛盾しないものと判定される。

次いで、多重ループ−重化解析手段２２３はデータ依存
関係判定手段２２２によって並列実行に矛盾しないと判
定された部分につき多重ループの一重化が可能か否かを
解析して判定する。具体的６ には次の処理を行う。

■Ｄ○ループ内で定義引用されている配列・変数に対し
て定義引用関係が全て矛盾していないものを候補として
取り出す。

■その多重Ｄｏ小ループ対応する多重ＤＯループ報テー
ブル４のＤ○変数情報４７．４８゜４９より、配列・変
数の定義引用が多重Ｄ○ループを通して記憶域上で一つ
の方向性をもつか否かを調べる。第４図の原始プログラ
ム１について作威された第８図の解析情報からは、一つ
の方向性をもつものと判定される。

■一つの方向性をもつ場合には、多重Ｄ○ループを一重
化できると判定し、ＤＯループ重化テーブル５を作成す
る。今の例では、第８図においてＤｏ小ループ重化テー
ブル５ａが作威され、チェーニングされる。

■ＤＯループー重化テーブル５ａが作成された後、その
多重Ｄｏ小ループ外側のＤｏ小ループＤ○変数の値が変
化する時に、配列要素の定義引用の記憶域上の位置の増
減の大きさが一定であるか否かを調べる。すなわち、ル
ープ中の配列要素の定義引用が記憶域上で等間隔である
か否かを調べる。第８図の解析情報からは、最外側のＤ
ＯループＤｏ変数の増分が「２」であるため、増減の大
きさは一定でないと判定される。

■増減の大きさが一定でないと判定された場合、マスク
用配列の領域を確保し、その情報をマスク用配列テーブ
ル（図示せず）として作威し、Ｄ○ループ一重化テーブ
ル５にチェ一二ソグする。第８図の解析情報では、ＤＯ
ループ重化テーブル５ａにマスク用配列テーブルがチェ
一二ソグされる。

■マスク用配列テーブルがチェーニングされた場合、−
重化後のＤ○変数の繰り返し数等の情報をＤｏ小ループ
重化テーブル５に設定する。第８図の解析情報では、−
重化後のＤＯループ数の繰り返し数はｒ　１．　ＯＯ＊
　５０　＊ＫＫＪとなる。すなわち、繰り返し数は内側
のＤ○変数のそれぞれの最大値と最り（イリリのＤ○変
数の終値とを掛は合わせたものとなる。

次いで、第１図において、ベクトルテキスト生成手段２
２４は多重ループ−重化解析手段２２３により一重化が
可能と判定された部分およびデータ依存関係判定手段２
２２により並列実行に矛盾しないと判定された部分を解
析情報を用いて一重化およびもしくはベクトル化して第
２中間テキスト２５を生成する。具体的には次のような
処理を行う。

■並列実行可能部分をベクトル処理するために必要とな
るベクトル長設定用のテキストを生成する。例えば、第
８図の解析情報からは、通常の並列実行可能部分はなく
、マスク用配列を使うことにより一重化可能な多重ＤＯ
ループ１組あることが判明するため、その多重ＤＯルー
プ一重化に必要なベクトル長設定用のテキストとして、
第９図中のステップ２５０５およびステップ２５１ｏに
示すようなテキストを生成する。なお、ステップ２５０
５はマスク設定用の多重ＤＯループ最内９９ 側のＤＯループベクトル化する際に必要となるものであ
り、そのベクトル長はＤｏ変数■の終値であるｒｌ　ｌ
となる。ステップ２５１０は一重化されたＤＯループベ
クトル化する際に必要となるものであり、そのベクトル
長は一重化後のＤＯループ繰り返し数であるｒｌｏＯ＊
５０＊ＫＫｊとなる。

■通常の並列実行可能部分に対し、ベクトル処理用のテ
キストを生成する。第８図の解析情報からは通常の並列
実行可能部分はないことが判明するので、この処理は行
わない。

■−一重化可能多重ＤＯループ対し、その処理用のテキ
ストを生成する。マスク用配列を使うことにより一重化
可能な多重ＤＯループある場合、この処理は次のように
行う。

（ａｌマスク設定用の多重ＤＯループ外側のスカラ命令
による部分のテキストを生成すると共に、マスク用配列
に所定値を代入するテキストを生成する。今の例におい
ては、外側のスカラ命令として、第９図のステップ２５
０１０ 〜２５０４，２５０７．２５０８に示すテキストを生成
すると共に、ベクトル化された最内側のＤ○変数の終値
を保証するためにステップ２５０９に示すテキストを生
成する。また、マスク用配列に所定値を代入するテキス
トとしてステップ２５０６に示すテキストを生成する。

ｆｂｌマスク用配列配列要素がいくつの時にマスクをオ
ンとするかというマスク情報を設定するためのテキスト
を生成する。今の例においては、第９図のステップ２５
１■に示すテキストを生成する。

（Ｃｌマスクがオンの時に所定の定義引用を行うテキス
トを生成する。今の例においては、第９図のステップ２
５１２〜２５１４に示すテキストを生成する。

■次に、ムク１〜ルテキスト生成手段２２４は、通常の
並列実行可能部分をベクトル処理するために必要となる
後処理用のテキストを生成する。今の例の場合は該当す
るものがないのでこの処理は行わない。

次に、コード生成部２３は上記のようにして生成された
第２中間テキスト２５を読み込み、対応する機械語のコ
ードによる目的プログラム３を生成する。

〔発明の効果〕

以上説明したように、本発明の多重ループベクトル化コ
ンパイル方式にあっては、ループ中に並列実行に矛盾す
るデータ依存関係がないこととループ中の配列要素の定
義引用が記憶域上で一方向であることとが満たされれば
、ループ中の配列要素の定義引用が記憶域上で等間隔で
なくても配列の定義引用の部分をループから出してベク
トル化できるため、多重ループの全体を一重化してベク
トル化する場合と同等とまではいかないが、最も内側の
ループのみをベクトル化する場合に比して大幅な実行時
間短縮の効果が期待できる。

【図面の簡単な説明】

第１図は本発明の多重ループベクトル化コンパイル方式
を適用したコンパイラの一実施例を示す構成図、 第２図はＤＯループ解析情報の表現に用いる多重ＤＯル
ープ報テーブルの論理的構成図、第３図はＤＯ小ループ
解析情報の表現に用いるＤｏループ−重化テーブルの論
理的構成図、第４図は多重ＤＯループ含む原始プログラ
ムの例を示す図、 第５図は第４図の原始プログラムを一重化可能な形へ変
換した状態を原始プログラムの形式で示した概念図、 第６図は第５図の原始プログラムの一重化後の状態を原
始プログラムの形式で示した概念図、第７図は第４図の
原始プログラムを構文解析して生成した第１中間テキス
トの構成の概念図（流れ図）、 第８図は第４図の原始プログラム中のＤｏループの解析
情報の表現の例を示す図、 第９図は第７図の第１中間テキストをベクトル化して生
成した第２中間テキストの構成の概念図、第１０図はＤ
Ｏ小ループ含む原始プログラムの３ 例を示す図、 第１１図は第１０図の原始プログラムを構文解析して生
成した第１中間テキストの構成の概念図、第１２図は第
１１図の第１中間テキストをベクトル化して生成した第
２中間テキストの構成の概念図、 第１３図は多重ＤＯループ含む原始プログラムの例を示
す図および、 第１４図は第１３図の原始プログラムの一重化後の状態
を原始プログラムの形式で示した図である。 図において、 １・・・・・・・・・原始プログラム ２・・・・・・・・・コンパイラ ２１・・・・・・構文解析部 ２２・・・・・・ベクトル化処理部 ２２１・・・構造解析手段 ２２２・・・データ依存関係判定手段 ２２３・・・多重ループ−重化解析手段２２４・・・ベ
クトルテキスト生成手段４ ２３・・・・・・コード生底部 ２４・・・・・・第１中間テキスト ２５・・・・・・第２中間テキスト ３・・・・・・・・・目的プログラム ４・・・・・・・・・多重ＤＯループ報テーブル５・・
・・・・・・・Ｄ○ループ一重化テーブル６・・・・・
・・・・ポインタ

Claims (2)

【特許請求の範囲】
1. （１）高級言語で記述された原始プログラムを読み込み
   構文解析を行って第１中間テキストを生成する構文解析
   部と、第１中間テキストから原始プログラム中のループ
   構造を検出してベクトル化可能部分の認識を行いベクト
   ル処理用のテキストを含む第２中間テキストを生成する
   ベクトル化処理部と、第２中間テキストから目的プログ
   ラムを生成して出力するコード生成部とを有し、ベクト
   ル処理プロセッサに対して、与えられた原始プログラム
   から目的プログラムを生成して出力するコンパイル方式
   において、 前記ベクトル化処理部に、 第１中間テキストから原始プログラムのループ中の制御
   の流れを解析する構造解析手段と、ループ中に並列実行
   に矛盾するデータ依存関係があるか否かを判定するデー
   タ依存関係判定手段と、 並列実行に矛盾しないと判定された部分につき通常のも
   しくはマスク使用による多重ループの一重化が可能か否
   かを解析して判定する多重ループ一重化解析手段と、 一重化が可能と判定された部分および並列実行に矛盾し
   ないと判定された他の部分を一重化およびもしくはベク
   トル化して第２中間テキストを生成するベクトルテキス
   ト生成手段とを設けたことを特徴とする多重ループベク
   トル化コンパイル方式。
2. （２）多重ＤＯループ情報テーブルおよびＤＯループ一
   重化テーブルを用いてＤＯループの解析情報を表現した
   ことを特徴とする請求項１記載の多重ループベクトル化
   コンパイル方式。