JPH054712B2 - - Google Patents
Info
- Publication number
- JPH054712B2 JPH054712B2 JP61011577A JP1157786A JPH054712B2 JP H054712 B2 JPH054712 B2 JP H054712B2 JP 61011577 A JP61011577 A JP 61011577A JP 1157786 A JP1157786 A JP 1157786A JP H054712 B2 JPH054712 B2 JP H054712B2
- Authority
- JP
- Japan
- Prior art keywords
- unrolling
- loop
- program
- operation sequence
- vector operation
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F15/00—Digital computers in general; Data processing equipment in general
- G06F15/76—Architectures of general purpose stored program computers
- G06F15/80—Architectures of general purpose stored program computers comprising an array of processing units with common control, e.g. single instruction multiple data processors
- G06F15/8053—Vector processors
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Devices For Executing Special Programs (AREA)
- Complex Calculations (AREA)
Description
【発明の詳細な説明】
〔概要〕
自動ベクトル化対象プログラムのコンパイルに
あたつて、ベクトル化後のベクトル演算列に関す
る外側ループ中のデータ依存関係を把握し、その
結果に従つて、外側ループの回転数を１／Ｎと
し、ベクトル演算列をＮ倍に展開することによ
り、コンパイルされたプログラムの実行性能を向
上させる。
あたつて、ベクトル化後のベクトル演算列に関す
る外側ループ中のデータ依存関係を把握し、その
結果に従つて、外側ループの回転数を１／Ｎと
し、ベクトル演算列をＮ倍に展開することによ
り、コンパイルされたプログラムの実行性能を向
上させる。
本発明は、ベクトル計算機を持つデータ処理装
置によつて実行されるプログラムをコンパイルす
る処理方式に係り、特にループ中のベクトル演算
列をアンローリングするベクトル演算列ループア
ンローリング処理方式に関するものである。
置によつて実行されるプログラムをコンパイルす
る処理方式に係り、特にループ中のベクトル演算
列をアンローリングするベクトル演算列ループア
ンローリング処理方式に関するものである。
例えばFORTRAN言語等により作成されたプ
ログラムを、ベクトル計算機を用いて実行させる
ために、DOループの配列等について、自動的に
ベクトル演算列を生成するコンパイラが用いられ
ている。このコンパイラが生成するオプジエクト
について、ベクトル化率を上げることは、ベクト
ル計算機による実行性能を向上させるために重要
な課題とされている。しかしながら、ハードウエ
ア資源であるベクトル計算機を最大限有効に使う
には、ベクトル化後のベクトル演算列を最適にス
ケジユーリングすることも必要である。
ログラムを、ベクトル計算機を用いて実行させる
ために、DOループの配列等について、自動的に
ベクトル演算列を生成するコンパイラが用いられ
ている。このコンパイラが生成するオプジエクト
について、ベクトル化率を上げることは、ベクト
ル計算機による実行性能を向上させるために重要
な課題とされている。しかしながら、ハードウエ
ア資源であるベクトル計算機を最大限有効に使う
には、ベクトル化後のベクトル演算列を最適にス
ケジユーリングすることも必要である。
この最適スケジユーリングとは、ベクトル計算
機におけるロード・ストアパイプライン、加算パ
イプライン、乗算パイプライン等を流れるデータ
の密度を濃くし、実行の待ち時間が少なくなるよ
うに、ベクトル演算列を並べることである。
機におけるロード・ストアパイプライン、加算パ
イプライン、乗算パイプライン等を流れるデータ
の密度を濃くし、実行の待ち時間が少なくなるよ
うに、ベクトル演算列を並べることである。
この最適スケジユーリングのため、従来、ソー
スレベルのスカライメージで、ユーザの手作業に
より、プログラムをチユーニングすることが行わ
れていた。
スレベルのスカライメージで、ユーザの手作業に
より、プログラムをチユーニングすることが行わ
れていた。
しかし、ユーザが手作業により、ソースプログ
ラムをチユーニングした場合、次のような問題が
発生する。
ラムをチユーニングした場合、次のような問題が
発生する。
スカライメージでベクトル版にチユーニング
したソースプログラムは、ベクトル処理機能を
持たない汎用計算機上では、実行性能が低下す
る可能性がある。
したソースプログラムは、ベクトル処理機能を
持たない汎用計算機上では、実行性能が低下す
る可能性がある。
チユーニングするために多大な労力および時
間を要する。
間を要する。
ソースプログラムの記述性が損なわれる。
ユーザのチユーニングにより性能が低下し、
逆効果となることがある。
逆効果となることがある。
本発明は上記問題点を解決するため、ベクトル
演算列をループアンローリングすることにより、
ソースプログラムから自動的に最適化されたオブ
ジエクトを生成する１方式を提供することを目的
としている。
演算列をループアンローリングすることにより、
ソースプログラムから自動的に最適化されたオブ
ジエクトを生成する１方式を提供することを目的
としている。
第１図は本発明の基本構成例ブロツク図を示
す。
す。
第１図において、１０は高級言語により記述さ
れたソースプログラム、１１はCPUおよびメモ
リ等からなる処理装置、１２はソースプログラム
１０を機械語のオブジエクトに翻訳するコンパイ
ラ、１３はプログラム入力部、１４はベクトル化
処理部、１５はデータ依存関係解析部、１６はア
ンローリング実施条件判定部、１７はアンローリ
ング処理部、１８はオブジエクト生成部、１９は
ソースプログラム１０に対応する機械語コード列
からなるオブジエクトプログラムを表す。
れたソースプログラム、１１はCPUおよびメモ
リ等からなる処理装置、１２はソースプログラム
１０を機械語のオブジエクトに翻訳するコンパイ
ラ、１３はプログラム入力部、１４はベクトル化
処理部、１５はデータ依存関係解析部、１６はア
ンローリング実施条件判定部、１７はアンローリ
ング処理部、１８はオブジエクト生成部、１９は
ソースプログラム１０に対応する機械語コード列
からなるオブジエクトプログラムを表す。
プログラム入力部１３は、ソースプログラム１
０から処理すべきソースステートメントを入力す
る。この入力プログラムを解析することにより、
中間テキストが生成される。コンパイラ１２は、
自動ベクトル化機能を備えており、ベクトル化処
理部１４によつて、中間テキストを解読し、ベク
トル化可能なものを検出して、ベクトル演算列を
生成する。
０から処理すべきソースステートメントを入力す
る。この入力プログラムを解析することにより、
中間テキストが生成される。コンパイラ１２は、
自動ベクトル化機能を備えており、ベクトル化処
理部１４によつて、中間テキストを解読し、ベク
トル化可能なものを検出して、ベクトル演算列を
生成する。
データ依存関係解析部１５は、多重ループにお
ける内側のループが、ベクトル化処理部１４によ
つて、ベクトル化されている場合に、そのベクト
ル化されたベクトル演算列の外側ループにおける
データ依存関係を解析するものである。
ける内側のループが、ベクトル化処理部１４によ
つて、ベクトル化されている場合に、そのベクト
ル化されたベクトル演算列の外側ループにおける
データ依存関係を解析するものである。
アンローリング実施条件判定部１６は、データ
依存関係解析部１５による解析結果により、予め
各データ依存関係に対応してアンローリングの可
否情報が登録されたテーブルを検索することによ
り、アンローリングの可否を判定する。ループの
アンローリングとは、外側ループの回転数を１／
Ｎ（Ｎは２以上の整数）とし、ベクトル演算列を
Ｎ倍に展開する処理である。
依存関係解析部１５による解析結果により、予め
各データ依存関係に対応してアンローリングの可
否情報が登録されたテーブルを検索することによ
り、アンローリングの可否を判定する。ループの
アンローリングとは、外側ループの回転数を１／
Ｎ（Ｎは２以上の整数）とし、ベクトル演算列を
Ｎ倍に展開する処理である。
アンローリング処理部１７は、アンローリング
実施条件判定部１６により、アンローリング可と
判定された場合に、ベクトル演算列を分解して、
ループアンローリングを行う。外側ループの回転
数は、１／Ｎに削減されるが、端数が出る場合に
は、その残りのベクトル演算列による処理命令列
を、ループの外側に付加する。
実施条件判定部１６により、アンローリング可と
判定された場合に、ベクトル演算列を分解して、
ループアンローリングを行う。外側ループの回転
数は、１／Ｎに削減されるが、端数が出る場合に
は、その残りのベクトル演算列による処理命令列
を、ループの外側に付加する。
ベクトル化され、アンローリングされた中間テ
キストは、必要に応じてさらに他の手段により最
適化される。オブジエクト生成部１８は、最終的
にオブジエクトプログラム１９を生成する。
キストは、必要に応じてさらに他の手段により最
適化される。オブジエクト生成部１８は、最終的
にオブジエクトプログラム１９を生成する。
以下、FORTRANプログラムのループアンロ
ーリングを例にして、本発明の作用を説明する。
ーリングを例にして、本発明の作用を説明する。
例えば、
DO 10 Ｊ＝１，100
DO 10 Ｉ＝１，10000
Ａ（Ｉ，Ｊ）＝Ｂ（Ｉ，Ｊ）＋Ｃ（Ｉ，Ｊ）＊
Ｄ（Ｉ，Ｊ） 10 CONTINUE という二重ループのプログラムは、ベクトル化処
理部１４により、内側ループについて、次のよう
にベクトル化が行われる。
Ｄ（Ｉ，Ｊ） 10 CONTINUE という二重ループのプログラムは、ベクトル化処
理部１４により、内側ループについて、次のよう
にベクトル化が行われる。
DO 10 Ｊ＝１，100
Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ）＊
Ｄ（＊，Ｊ） 10 CONTINUE ここで、配列中の「＊」は、１から10000まで
の値をとるベクトル・パラメータであつて、ベク
トル長は10000である。
Ｄ（＊，Ｊ） 10 CONTINUE ここで、配列中の「＊」は、１から10000まで
の値をとるベクトル・パラメータであつて、ベク
トル長は10000である。
アンローリング処理部１７は、これについて、
次のようにループアンローリングを行う。
次のようにループアンローリングを行う。
DO 10 Ｊ＝１，100，２
Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ）＊
Ｄ（＊，Ｊ） Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ＋１）＋Ｃ（＊，
Ｊ＋１）＊Ｄ（＊，Ｊ＋１） 10 CONTINUE 即ち、ループ制御変数の増分値を２倍にするこ
とにより、外側ループのループ回転数を1/2とし、
内部のベクトル演算列を分解して２倍にする。３
重展開以上についても同様である。展開されたベ
クトル演算列は、個別にベクトル計算機における
パイプラインによつて処理されるので、パイプラ
インの処理密度を高密度化することが可能にな
り、パイプライン・スケジユーリングが最適化さ
れる。
Ｄ（＊，Ｊ） Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ＋１）＋Ｃ（＊，
Ｊ＋１）＊Ｄ（＊，Ｊ＋１） 10 CONTINUE 即ち、ループ制御変数の増分値を２倍にするこ
とにより、外側ループのループ回転数を1/2とし、
内部のベクトル演算列を分解して２倍にする。３
重展開以上についても同様である。展開されたベ
クトル演算列は、個別にベクトル計算機における
パイプラインによつて処理されるので、パイプラ
インの処理密度を高密度化することが可能にな
り、パイプライン・スケジユーリングが最適化さ
れる。
また、次のような場合には、ベクトル演算にお
ける共通式の最適化によるベクトルテキスト最適
化が可能になる。例えば、ベクトル化後のベクト
ル演算列が、 DO 10 Ｊ＝１，100 Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ）＋Ａ（＊，Ｊ） 10 CONTINUE であるとする。ここで、配列中の「＊」は、前例
と同様に、１から10000までの値をとるベクト
ル・パラメータである。
ける共通式の最適化によるベクトルテキスト最適
化が可能になる。例えば、ベクトル化後のベクト
ル演算列が、 DO 10 Ｊ＝１，100 Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ）＋Ａ（＊，Ｊ） 10 CONTINUE であるとする。ここで、配列中の「＊」は、前例
と同様に、１から10000までの値をとるベクト
ル・パラメータである。
アンローリング処理部１７は、これについて、
次のようにループアンローリングを行う。
次のようにループアンローリングを行う。
DO 10 Ｊ＝１，100，２
Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ）＋Ａ（＊，Ｊ）
…… Ａ（＊，Ｊ＋２）＝Ｂ（＊，Ｊ＋１）＋Ａ（＊，
Ｊ＋１） …… 10 CONTINUE このベクトル演算列における右辺第２項は、
ベクトル演算列の左辺と同じ値をとる。ベクト
ル計算機により、ベクトル演算列を実行する
と、ベクトルレジスタにＡ（＊，Ｊ＋１）が得ら
れるので、次のベクトル演算列の実行におい
て、Ａ（＊，Ｊ＋１）をロードする必要がない。
これにより、高速実行が可能になり、ベクトルテ
キストの最適化が可能になる。
…… Ａ（＊，Ｊ＋２）＝Ｂ（＊，Ｊ＋１）＋Ａ（＊，
Ｊ＋１） …… 10 CONTINUE このベクトル演算列における右辺第２項は、
ベクトル演算列の左辺と同じ値をとる。ベクト
ル計算機により、ベクトル演算列を実行する
と、ベクトルレジスタにＡ（＊，Ｊ＋１）が得ら
れるので、次のベクトル演算列の実行におい
て、Ａ（＊，Ｊ＋１）をロードする必要がない。
これにより、高速実行が可能になり、ベクトルテ
キストの最適化が可能になる。
第２図は本発明の一実施例処理説明図、第３図
はアンローリング可否テーブルの例、第４図はデ
ータ依存関係値とアンローリング展開数との関連
を説明する図を示す。
はアンローリング可否テーブルの例、第４図はデ
ータ依存関係値とアンローリング展開数との関連
を説明する図を示す。
本発明によるループアンローリング処理は、例
えば第２図に示すように行われる。なお、この処
理は、処理対象ループ内にベクトル化された演算
列が存在するときに呼び出される。以下の説明に
おける処理番号〜は、第２図に示す番号〜
に対応する。
えば第２図に示すように行われる。なお、この処
理は、処理対象ループ内にベクトル化された演算
列が存在するときに呼び出される。以下の説明に
おける処理番号〜は、第２図に示す番号〜
に対応する。
データ依存関係値をもとに、第３図に示すよ
うなアンローリング可否テーブルを検索する。
うなアンローリング可否テーブルを検索する。
なお、データ依存関係値およびアンローリン
グ可否テーブルについては、後に詳述する。
グ可否テーブルについては、後に詳述する。
アンローリング可否テーブルを検索した結果
により、アンローリングの可／不可を判定し、
アンローリングが不可である場合には、アンロ
ーリングによる最適化処理を行わずに、次の最
適化処理へ進む。
により、アンローリングの可／不可を判定し、
アンローリングが不可である場合には、アンロ
ーリングによる最適化処理を行わずに、次の最
適化処理へ進む。
他のアンローリング実施条件についても判定
する。この条件として、例えばループの回転数
が２以上（陽に判明している場合）であるこ
と、ループの出口が１つであること、ループ内
でベクトル長の変化がないことなどがある。ま
た、アンローリングにより、実行効率がよくな
るかどうかの条件についても判定する。これら
の各条件が満足されない場合、次の最適化処理
へ進む。
する。この条件として、例えばループの回転数
が２以上（陽に判明している場合）であるこ
と、ループの出口が１つであること、ループ内
でベクトル長の変化がないことなどがある。ま
た、アンローリングにより、実行効率がよくな
るかどうかの条件についても判定する。これら
の各条件が満足されない場合、次の最適化処理
へ進む。
ループアンローリングのために、外側ループ
の回転数を１／Ｎにする。なお、説明を簡単に
するために、以下、Ｎ＝２の場合について説明
する。
の回転数を１／Ｎにする。なお、説明を簡単に
するために、以下、Ｎ＝２の場合について説明
する。
ベクトル演算列を２倍にする。即ち、元のベ
クトル演算列に対して、配列の添字式の値を歩
進したベクトル演算列を生成して付加する。
クトル演算列に対して、配列の添字式の値を歩
進したベクトル演算列を生成して付加する。
ループ回転数が定数であるかどうかを判定す
る。定数でない場合には、処理へ制御を移
す。
る。定数でない場合には、処理へ制御を移
す。
元のループ回転数が偶数であるか奇数である
かを判定する。偶数である場合、次の最適化処
理へ進み、奇数である場合には、処理を実行
する。
かを判定する。偶数である場合、次の最適化処
理へ進み、奇数である場合には、処理を実行
する。
元のループにおいて最後に実行されるベクト
ル演算列の部分を、新しいループの外に付加し
て、次の最適化処理へ進む。
ル演算列の部分を、新しいループの外に付加し
て、次の最適化処理へ進む。
ループ回転数が変数である場合、ダイナミツ
クに回転数を判定するテキストを生成して、付
加する。
クに回転数を判定するテキストを生成して、付
加する。
回転数の判定に対応して、1/2にした回転数
の端数となる分のベクトル演算列をループの外
に付加する。その後、次の最適化処理へ進む。
の端数となる分のベクトル演算列をループの外
に付加する。その後、次の最適化処理へ進む。
ベクトル演算列をループアンローリングする場
合、アンローリングによつて、配列の定義／参照
に関するベクトル計算機による実行順番が意図し
ないものとなつて、正しい結果が得られなくなる
可能性がある。そのため、本発明では、予め、次
のようなデータ依存関係値を求めておき、これに
よつて、アンローリングの可否を決定する。
合、アンローリングによつて、配列の定義／参照
に関するベクトル計算機による実行順番が意図し
ないものとなつて、正しい結果が得られなくなる
可能性がある。そのため、本発明では、予め、次
のようなデータ依存関係値を求めておき、これに
よつて、アンローリングの可否を決定する。
データ依存関係値は、ループ内における前後す
る配列添字式の相対的な値関係を示すものと考え
てよい。例えば、前に現れる配列が、Ａ（Ｉ）で
あつて、後に現れる配列が、Ａ（Ｉ＋２）である
とき、データ依存関係値は、制御変数Ｉが共通し
ているので、Ｉ＝０として、次のように求められ
る。
る配列添字式の相対的な値関係を示すものと考え
てよい。例えば、前に現れる配列が、Ａ（Ｉ）で
あつて、後に現れる配列が、Ａ（Ｉ＋２）である
とき、データ依存関係値は、制御変数Ｉが共通し
ているので、Ｉ＝０として、次のように求められ
る。
（０）−（０＋２）＝−２
データ依存関係値の種類は、例えば、以下の通
りである。
りである。
（記号） （意味）
φ：重なりなし（データ依存関係なし）．
＋：順方向のデータ依存関係あり．
−：逆方向のデータ依存関係あり．
＊：制御変数が出現していない．
？：データ依存関係が不明である．
＋OR−：順方向のデータ依存関係あり．
（スカラとベクトル）
０：同じ位置をアクセスしている．
＋の値：順方向にいくつ、ずれているかを表す．
−の値：逆方向にいくつ、ずれているかを表す．
アンローリングの可否は、以上のようなデータ
依存関係値によつて、決められる。そのため、例
えば第３図に示すようなアンローリング可否テー
ブルが用いられる。
依存関係値によつて、決められる。そのため、例
えば第３図に示すようなアンローリング可否テー
ブルが用いられる。
第３図図示アンローリング可否テーブルにおい
て、○はアンローリング可能、×はアンローリン
グ不可能、△は値によつて可否が決定されるもの
を表している。縦の列は１次元目のデータ依存関
係値、横の列は２次元目のデータ依存関係値を表
している。
て、○はアンローリング可能、×はアンローリン
グ不可能、△は値によつて可否が決定されるもの
を表している。縦の列は１次元目のデータ依存関
係値、横の列は２次元目のデータ依存関係値を表
している。
DO 10 Ｊ＝１，Ｎ
DO 10 Ｉ＝１，Ｍ
Ａ（Ｉ，Ｊ）＝……
……
10 CONTINUE
このような場合、Ｉが１次元目であり、Ｊが２
次元目である。
次元目である。
第３図において、×印に該当する場合には、ア
ンローリングすることによつて、従来なかつたデ
ータ依存関係が生じることになるので、アンロー
リング不可能とされる。△印に該当する場合に
は、第４図に示すデータ依存関係値と、アンロー
リング展開数とによつて可否が決められる。例え
ば、データ依存関係値が±２である場合、２重展
開（即ち、Ｎ＝２）のときにはアンローリング可
能であるが、３重展開以上（Ｎ≧３）ではアンロ
ーリングが不可能とされる。
ンローリングすることによつて、従来なかつたデ
ータ依存関係が生じることになるので、アンロー
リング不可能とされる。△印に該当する場合に
は、第４図に示すデータ依存関係値と、アンロー
リング展開数とによつて可否が決められる。例え
ば、データ依存関係値が±２である場合、２重展
開（即ち、Ｎ＝２）のときにはアンローリング可
能であるが、３重展開以上（Ｎ≧３）ではアンロ
ーリングが不可能とされる。
次に、FORTRANプログラムの例により、ル
ープアンローリングの具体例を示す。
ープアンローリングの具体例を示す。
(a) ループの回転数が陽に判明している場合であ
つて、回転数が偶数である場合 ［ループアンローリング前］ DO 10 Ｊ＝１，４ Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ） 10 CONTINUE ［ループアンローリング後］ DO 10 Ｊ＝１，４，２ Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ） Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ＋１）＋Ｃ（＊，
Ｊ＋１） 10 CONTINUE (b) 回転数が奇数である場合 ［ループアンローリング前］ DO 10 Ｊ＝１，５ Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ） 10 CONTINUE ［ループアンローリング後］ DO 10 Ｊ＝１，３，２ Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ） Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ＋１）＋Ｃ（＊，
Ｊ＋１） 10 CONTINUE Ａ（＊，５）＝Ｂ（＊，５）＋Ｃ（＊，５） 最後にＪ＝５のベクトル演算列が付加されてい
る。
つて、回転数が偶数である場合 ［ループアンローリング前］ DO 10 Ｊ＝１，４ Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ） 10 CONTINUE ［ループアンローリング後］ DO 10 Ｊ＝１，４，２ Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ） Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ＋１）＋Ｃ（＊，
Ｊ＋１） 10 CONTINUE (b) 回転数が奇数である場合 ［ループアンローリング前］ DO 10 Ｊ＝１，５ Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ） 10 CONTINUE ［ループアンローリング後］ DO 10 Ｊ＝１，３，２ Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ） Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ＋１）＋Ｃ（＊，
Ｊ＋１） 10 CONTINUE Ａ（＊，５）＝Ｂ（＊，５）＋Ｃ（＊，５） 最後にＪ＝５のベクトル演算列が付加されてい
る。
(c) 回転数が不明な場合
［ループアンローリング前］
DO 10 Ｊ＝１，Ｎ
Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ）
10 CONTINUE
［ループアンローリング後］
IF（N.EQ.1）GOTO 20
DO 10 Ｊ＝１，Ｎ−１，２
Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ）
Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ＋１）＋Ｃ（＊，
Ｊ＋１） 10 CONTINUE IF（MOD（Ｎ，２）．EQ.0）GOTO 30 20 CONTINUE Ａ（＊，Ｎ）＝Ｂ（＊，Ｎ）＋Ｃ（＊，Ｎ） 30 CONTINUE 上記実施例では、ループアンローリングの展開
数を２としたが、例えばループの回転数が陽に３
の場合には、３重展開にするというように、多重
展開も可能である。いわゆる最適化制御行によつ
て、ユーザがアンローリングの展開数を外側から
指定できるようにしてもよい。この場合、ユーザ
は、例えば次のような最適化制御行をソースプロ
グラムに記述する。
Ｊ＋１） 10 CONTINUE IF（MOD（Ｎ，２）．EQ.0）GOTO 30 20 CONTINUE Ａ（＊，Ｎ）＝Ｂ（＊，Ｎ）＋Ｃ（＊，Ｎ） 30 CONTINUE 上記実施例では、ループアンローリングの展開
数を２としたが、例えばループの回転数が陽に３
の場合には、３重展開にするというように、多重
展開も可能である。いわゆる最適化制御行によつ
て、ユーザがアンローリングの展開数を外側から
指定できるようにしてもよい。この場合、ユーザ
は、例えば次のような最適化制御行をソースプロ
グラムに記述する。
「＊VOCL LOOP，UNROL（４）」
ここで、＊VOCLは、この行が最適化制御行で
あることを示している。LOOPは、最適化がルー
プに対して有効であることを示す。UNROL（４）
は、４重展開にすべきことを指示している。４重
展開の場合、例えば次のようになる。
あることを示している。LOOPは、最適化がルー
プに対して有効であることを示す。UNROL（４）
は、４重展開にすべきことを指示している。４重
展開の場合、例えば次のようになる。
［ループアンローリング前］
＊VOCL LOOP，UNROL（４）
DO 10 Ｊ＝１，Ｎ
Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ）
10 CONTINUE
［ループアンローリング後］
IF（N.LT.4）GOTO 20
DO 10 Ｊ＝１，Ｎ−１，４
Ａ（＊，Ｊ）＝Ｂ（＊，Ｊ）＋Ｃ（＊，Ｊ）
Ａ（＊，Ｊ＋１）＝Ｂ（＊，Ｊ＋１）＋Ｃ（＊，
Ｊ＋１） Ａ（＊，Ｊ＋２）＝Ｂ（＊，Ｊ＋２）＋Ｃ（＊，
Ｊ＋２） Ａ（＊，Ｊ＋３）＝Ｂ（＊，Ｊ＋３）＋Ｃ（＊，
Ｊ＋３） 10 CONTINUE 20 Ｍ＝MOD（Ｎ，４） IF（M.EQ.0）GOTO 50 IF（M.EQ.1）GOTO 40 IF（M.EQ.2）GOTO 30 Ａ（＊，Ｎ−２）＝Ｂ（＊，Ｎ−２）＋Ｃ
（＊，Ｎ−２） 30 Ａ（＊，Ｎ−１）＝Ｂ（＊，Ｎ−１）＋Ｃ（＊，
Ｎ−１） 40 Ａ（＊，Ｎ）＝Ｂ（＊，Ｎ）＋Ｃ（＊，Ｎ） 50 CONTINUE この例では、ユーザが指定した最適化制御行に
より、アンローリングを４重展開で実施するとと
もに、制御変数がＮであつて、コンパイル時に
は、ループ回転数が不明であるため、回転数判定
テキストを生成して、ループの後に付加してい
る。
Ｊ＋１） Ａ（＊，Ｊ＋２）＝Ｂ（＊，Ｊ＋２）＋Ｃ（＊，
Ｊ＋２） Ａ（＊，Ｊ＋３）＝Ｂ（＊，Ｊ＋３）＋Ｃ（＊，
Ｊ＋３） 10 CONTINUE 20 Ｍ＝MOD（Ｎ，４） IF（M.EQ.0）GOTO 50 IF（M.EQ.1）GOTO 40 IF（M.EQ.2）GOTO 30 Ａ（＊，Ｎ−２）＝Ｂ（＊，Ｎ−２）＋Ｃ
（＊，Ｎ−２） 30 Ａ（＊，Ｎ−１）＝Ｂ（＊，Ｎ−１）＋Ｃ（＊，
Ｎ−１） 40 Ａ（＊，Ｎ）＝Ｂ（＊，Ｎ）＋Ｃ（＊，Ｎ） 50 CONTINUE この例では、ユーザが指定した最適化制御行に
より、アンローリングを４重展開で実施するとと
もに、制御変数がＮであつて、コンパイル時に
は、ループ回転数が不明であるため、回転数判定
テキストを生成して、ループの後に付加してい
る。
以上説明したように、本発明によれば、データ
依存関係を把握することにより、自動的にベクト
ル演算列のループアンローリングがなされること
になり、これにより、パイプライン・スケジユー
リングの最適化が可能になる。また、ベクトルテ
キストの最適化も可能になる。従つて、実行性能
が向上し、ユーザのチユーニング時間を短縮する
ことができる。また、ソースプログラムについ
て、FORTRANプログラム等の記述性を保持す
ることができ、ソースレベルでの汎用計算機との
互換性を維持することができる。
依存関係を把握することにより、自動的にベクト
ル演算列のループアンローリングがなされること
になり、これにより、パイプライン・スケジユー
リングの最適化が可能になる。また、ベクトルテ
キストの最適化も可能になる。従つて、実行性能
が向上し、ユーザのチユーニング時間を短縮する
ことができる。また、ソースプログラムについ
て、FORTRANプログラム等の記述性を保持す
ることができ、ソースレベルでの汎用計算機との
互換性を維持することができる。
第１図は本発明の基本構成例ブロツク図、第２
図は本発明の一実施例処理説明図、第３図はアン
ローリング可否テーブルの例、第４図はデータ依
存関係値とアンローリング展開数との関連を説明
する図を示す。 図中、１０はソースプログラム、１１は処理装
置、１２はコンパイラ、１３はプログラム入力
部、１４はベクトル化処理部、１５はデータ依存
関係解析部、１６はアンローリング実施条件判定
部、１７はアンローリング処理部、１８はオブジ
エクト生成部、１９はオブジエクトプログラムを
表す。
図は本発明の一実施例処理説明図、第３図はアン
ローリング可否テーブルの例、第４図はデータ依
存関係値とアンローリング展開数との関連を説明
する図を示す。 図中、１０はソースプログラム、１１は処理装
置、１２はコンパイラ、１３はプログラム入力
部、１４はベクトル化処理部、１５はデータ依存
関係解析部、１６はアンローリング実施条件判定
部、１７はアンローリング処理部、１８はオブジ
エクト生成部、１９はオブジエクトプログラムを
表す。
Claims (1)
- 【特許請求の範囲】 １ 自動ベクトル化を行うコンパイル処理機能を
有するデータ処理システムにおいて、 コンパイル対象のソースプログラム１０を入力
するプログラム入力部１３と、 該プログラム入力部１３が入力したコンパイル
対象プログラムを解析した結果の中間テキストを
解読し、ベクトル化可能なものを検出して、ベク
トル演算列を生成するベクトル化処理部１４と、 コンパイル対象プログラム中の多重ループにお
ける内側のループが上記ベクトル化処理部１４に
よつてベクトル化されている場合に、ベクトル化
されたベクトル演算列の外側ループにおけるアン
ローリングに関連するデータ依存関係を解析する
データ依存関係解析部１５と、 少なくとも上記データ依存関係解析部１５によ
る解析結果に従つて、アンローリングの可否を判
定するアンローリング実施条件判定部１６と、 該アンローリング実施条件判定部１６により、
アンローリング可と判定された場合に、上記外側
ループの回転数を１／Ｎ（Ｎは２以上の整数）と
し、ベクトル演算列をＮ倍に展開するアンローリ
ング処理部１７とを備えたことを特徴とするベク
トル演算列ループアンローリング処理方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61011577A JPS62169272A (ja) | 1986-01-22 | 1986-01-22 | ベクトル演算列ル−プアンロ−リング処理方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61011577A JPS62169272A (ja) | 1986-01-22 | 1986-01-22 | ベクトル演算列ル−プアンロ−リング処理方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS62169272A JPS62169272A (ja) | 1987-07-25 |
| JPH054712B2 true JPH054712B2 (ja) | 1993-01-20 |
Family
ID=11781767
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61011577A Granted JPS62169272A (ja) | 1986-01-22 | 1986-01-22 | ベクトル演算列ル−プアンロ−リング処理方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS62169272A (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03150636A (ja) * | 1989-11-08 | 1991-06-27 | Matsushita Electric Ind Co Ltd | コンパイル方法 |
| JP2718816B2 (ja) * | 1990-10-19 | 1998-02-25 | 富士通株式会社 | コンパイラ装置 |
| JP2009070070A (ja) * | 2007-09-12 | 2009-04-02 | Nec Corp | コンパイラ及びコンパイル方法 |
-
1986
- 1986-01-22 JP JP61011577A patent/JPS62169272A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS62169272A (ja) | 1987-07-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0735468B1 (en) | Method and apparatus for an optimizing compiler | |
| US5835776A (en) | Method and apparatus for instruction scheduling in an optimizing compiler for minimizing overhead instructions | |
| US10776127B2 (en) | Reducing data hazards in pipelined processors to provide high processor utilization | |
| US6754893B2 (en) | Method for collapsing the prolog and epilog of software pipelined loops | |
| JP3317825B2 (ja) | ループ最適化翻訳処理方法 | |
| US5867711A (en) | Method and apparatus for time-reversed instruction scheduling with modulo constraints in an optimizing compiler | |
| JP3896087B2 (ja) | コンパイラ装置およびコンパイル方法 | |
| Ramamoorthy et al. | A high-level language for horizontal microprogramming | |
| US5537620A (en) | Redundant load elimination on optimizing compilers | |
| US5664193A (en) | Method and apparatus for automatic selection of the load latency to be used in modulo scheduling in an optimizing compiler | |
| US5809308A (en) | Method and apparatus for efficient determination of an RMII vector for modulo scheduled loops in an optimizing compiler | |
| US5613121A (en) | Method and system of generating combined storage references | |
| JPH02217926A (ja) | コード生成方法 | |
| JPH04330527A (ja) | プログラムの最適化方法及びコンパイラ・システム | |
| US6671878B1 (en) | Modulo scheduling via binary search for minimum acceptable initiation interval method and apparatus | |
| JPS63132338A (ja) | コード生成方法 | |
| Krishnaiyer et al. | An advanced optimizer for the IA-64 architecture | |
| US6064820A (en) | Apparatus and method to incrementally update single static assignment (SSA) form | |
| Muthukumar et al. | Software pipelining of nested loops | |
| JP4719415B2 (ja) | 情報処理システム及びコード生成方法 | |
| JP3311381B2 (ja) | コンパイラにおける命令スケジューリング処理方法 | |
| JPH054712B2 (ja) | ||
| JP3840149B2 (ja) | コンパイラ、演算処理システム及び演算処理方法 | |
| CN118092931A (zh) | 基于指导语句的函数向量化方法及系统 | |
| Hong et al. | Rapid prototyping of DSP algorithms on VLIW TMS320C6701 DSP |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |