JPS63304325A

JPS63304325A - 並列化コンパイル方法

Info

Publication number: JPS63304325A
Application number: JP62139729A
Authority: JP
Inventors: Kyoko Iwazawa; 岩澤　京子; Giichi Tanaka; 義一田中; Shizuo Goto; 志津雄後藤
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1987-06-05
Filing date: 1987-06-05
Publication date: 1988-12-12
Anticipated expiration: 2015-06-19
Also published as: JP3053092B2; US5067068A

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、並列計算機システムに係り、特に遂行実行型
の高級言語から、並列に実行するのに好適なオブジェク
トプログラムを生成する方式に関する。

〔従来の技術〕

コンパイラの最適化の対象としてのループ基本インダク
シヨン変数とは次のように定義することができる。ルー
プにおいて、各繰り返し回数で再帰的に定義され、ルー
プの繰り返し回数工の関数である。

典型的な例では、次のようなプログラムが書ける。Ｄｏ
　　１０　　Ｉ＝１．ｖＫ＝に十Ａ　（１）Ｊ＝Ｊ＋１１　０　　ＣＯＮＴＩＮＵＥループ制御変数工をはじめとして、ＦＯＲＴＲＡＮのソ
ースプログラムには、このような形で定義される計算の
出現頻度は非常に高い、しかも、ループの回数に同期し
て変化する。このような性質を利用して、従来の逐次型
計算機のためには種々の最適化手法が研究されており、
Ａ、Ｖ、Ａｈｏ　　Ｊ、Ｄ。

Ｌｌｌｌｍａｎの“Ｐｒ１ｎｃｉｐｌｅｓ　ｏｆ　Ｃｏ
ｍｐｉｌｅｒ　Ｄｅｓｉｇｎ”にもＰ２Ｓ５−Ｐ４７１
に１ｎｄｕｃｔｉｏｎ　ｖａｒｉａｂｌａｅｌｅｍｉｎ
ａｔｉｏｎとして論じられている。

これらの手法は、逐次的に実行する計算機に付しては、
有効であるが、並列処理に対する最適化と言うことはで
きず、並列処理向上にインダクシヨン変数の最適化につ
いて論じているものはない。

本発明の適用対象は、以下のような条件を満たす基本イ
ンダクシヨン変数に限る。

（２）ａはループが繰り返されても値が変わらない、ル
ープ不変変数である。

このような基本インダクシヨン変数を以下イオダクショ
ン変数と呼ぶ。

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

従来技術では、再帰的に定義されるインダクシヨン変数
の計算は、逐次的に実行されるか又は、プロセッサ間の
ネットワーク通信を利用して行なわれてきた。しかし、
数値計算の分野で用いられるＦＯＲＴＲＡＮ言語は、Ｄ
Ｏループの制御変数をはじめとして、配列の添字など、
再帰的な定義されるインダクシヨン変数がしばしば現れ
、これらについて最適化を施すことが、オブジェクト性
能の向上にもつながる。しかし、ＤＯループの繰り返し
を並列に実行する並列計算機システムにおいては、これ
らのインダクシヨン変数の最適化について配慮されてい
ない。

たとえば、第３図のようなプログラムで、Ｄ。

１０ループやＤｏ３０ループについて、ループの繰り返
し回数ごとに並列に行なうと次のような障害が起こる０
文１７がＪの定義式であるが、ループの１回目の実行を
行うためには、ループのＩ　−１回目に計算したＪの値
を使う、第１２図のように並列に実行するためには、Ｉ
−１回目の計算を実行するプロセッサから１回目の計算
を実行するプロセッサへ、Ｊの値を転送しなければなら
ない。

従って、各プロセッサ間の通信手段の無い並列機では並
列実行することができず１通信手段があっても、１回前
の計算が終われるのを待つため並列性は損われ、さらに
、データの通信のために時間がかかる。これは、文１８
のＲや、文２４のＩＡにも同様である。１回目に計算し
た値を用いて、新たな値を定義する。再帰的な定義は、
このように、並列処理にとっては、逐次処理に比べ、実
行効率劣化の大きな要因となる。

本発明の目的は、これらＦＯＲＴＲＡＮプログラムにし
ばしば出現する再帰的なインダクシヨン変数の計算を、
再帰性が無くなるよう、ループ回数を用いた式に変換し
、プロセッサ間の通信を行うことなく並列に実行するオ
ブジェクトを生成することである。

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

上記目的は、コンパイラの並列処理部において、インダ
クシヨン変数検出部と、初期値生成部と。

公差・公比生成部と、式変換部を設けることにより達成
される。

インダクシヨン変数検出部は、先立つ処理により検出し
た並列化の対象とするループについて、再帰的に定義さ
れているインダクシヨン変数を検出し、該インダクシヨ
ン変数の値がループ繰り返し回数と、ループ実行中値が
変わらないループ不変変数のみによって計算できるか否
かを判定する。

初期値生成部は、前記条件を満足したインダクシヨン変
数の初期値を設定するコードを生成する。

公差・公比生成部は、前記条件を満足したインダクシヨ
ン変数の公差値か又は公比値を設定するコードを生成す
る。

式変換部は、再帰的に定義されていたインダクシヨン変
数の定義式を、ループ不変な初期値と、公差値または公
比値を用いた定義式に変換する。

以上のようにして、再帰的な定義式を、再帰的ではない
定義式に変換することができ、その結果この計算を通信
を使うことなく、並列に実行できるようになる。

〔作用〕

インダクシヨン変数の検出部、初期値生成部、公差・公
比生成部、定義式変換部は、ループ中にあるインダクシ
ヨン変数に対して、以下のように作用する。

インダクシヨン変数の検出部は、第３図の並列化対象ル
ープＤｏｌＯについては、インダクシヨン変数ＪとＲを
検出する。もう１つの並列化対象ループＤ０３０につい
ては、インダクシヨン変数ＩＡを検出する。

初期値生成部は、第３図のＤｏｌＯループのＪとＲに対
しては、ループに入る前のＪとＲの値を保持する新しい
変数ＪφおよびＲφを用いて、初期値を定義する式を生
成する。もう１つの並列化対象ループＤ　ｏ　３０につ
いては、ＩＡの初期値１を検出する。

公差・公比生成部は、第３図のＤ０１０ループのＪにつ
いては公差５を、Ｒについては公比Ａを検出する。Ｄｏ
３０ループのＩＡについては公差■−（Ｉ＋１）／２を
生成する。

大変換部は、ループ繰り返し回数とループで値の変わら
ない不変式を用いた式に変換する。第３図のＤｏｌＯル
ープのＪについては、Ｊ＝Ｊ＋５をＪ＝Ｊφ＋５傘工で
置換し、Ｒについては、Ｒ＝Ｒφ拳Ａ傘傘工で置換する
。Ｄｏ３０ル−プのＩＡについては、ＩＡ＝１＋Ｉ傘（
Ｉ−１）／２を挿入する。

上記のようにして、インダクシヨン変数の再帰性を除き
、プロセッサ間でデータの通信を行なうことなく並列に
実行することができる。

〔実施例〕

以下、本発明のＦＯＲＴＲＡＮコンパイラにおける実施
例を図表を参照しつつ説明する。

第２図に、本発明を適用するコンパイラ全体の構造を示
す、第２図の構文解析部９がＦＯＲＴＲＡＮのソースプ
ログラム１２を入力し、これを中間語６に変換する。中
間部１０はこれを入力として、最適化や並列化を行い、
中間語６を変形する。コード生成部１１は、中間部１０
が変形した中間語からオブジェクトコード１３を生成す
る０本発明は中間部１０に係り、オブジェクトコード７
の並列実行できる部分をふやすことにより実行効率を上
げるものである。

第２図の中間部１０のうち、並列化のための式変換に係
わる部分の構成を第１図に示す、第２図の入力するソー
スプログラム１２の例として、第３図にＦＯＲＴＲＡＮ
プログラムをあげ、説明する。第３図のＦＯＲＴＲＡＮ
プログラムから、ＤｏｌＯのループとＤｏ３０のループ
を並列に実行するプログラムを生成する。

第１図において、インダクシヨン変数検出部２は、ソー
スプログラムを構文解析した中間語６を入力として、第
４図のフローチャートのように動作し、第５図に示すイ
ンダクシヨンテーブル７を作る。

インダクシヨン変数検出処理は並列処理対象のループの
中の最内側ループから、並列処理対象ループに至るまで
順次、行なう、まず処理２８が。

Ｄ　ｏ　１０のループを処理対象とする。処理２９が基
本インダクシヨン変数として、ループ制御変数Ｉを検出
し、処理３０がＩのレコード３９を作る。

処理３１の判定を経て、処理２９が基本インダクシヨン
変数Ｊの定義文１７を検出し、処理３０がＪのレコード
４０を作る。同様に、処理３０が、Ｒのレコード４１を
作る。

Ｄ　ｏ　３０のループについては、処理２８が、まずＤ
　ｏ　２０を処理対象ループとして、Ｊのレコード４４
．ＩＢのレコード４５、ＩＡのレコード４６を作る。さ
らに、処理３２の判定から処理３４に進み、処理３５が
、処理対象ループをＤ０２０とする。処理２９と３０が
ループ制御変数工のレコード４２を作り、処理３１と３
２の判定を経て、処理３３がＩＡのレコード４３を作る
。

次に、第５図のインダクシヨンテーブルを入力として、
初期値生成部２が、登録された各基本インダクシヨン変
数に対して、ループ内で値が変わらないループ不変変数
である初期値を検出し、第７図のようにインダクシヨン
テーブルを更新する。

必要ならばこれを計算するコードを生成する。

処理の概要を第６図にフローチャートで示す。

まず、第５図のＤｏｌＯループのレコード３６より、Ｄ
０１０ループのインダクシヨン変数について処理を行う
、第６図の処理６０が、制御変数Ｉについて初期値１を
検出し、処理６３が、１を第７図に示すインダクシヨン
テーブルのレコード３９のフィールド７０に登録する。

第５図のインダクシヨンテーブルのレコード４０のＪつ
いては、ループの外側からの依存が検出できないため、
処理６１の判定から処理６４が、第８図に示す代入文１
４を生成、挿入し、新たに導入した左辺の変数Ｊφをイ
ンダクシヨンテーブルのレコード４０のフィールド７０
に登録すし、第７図のレコード４０のようにする。第５
図のレコード４１のＲについても同様に、処理６４が第
８図に示す代入文１５を生成、挿入し、新たに導入した
変数Ｒφをインダクシヨンテーブルのレコード４１のフ
ィールド７０に登録し、第７図のレコード４１のように
する。

この後、処理６５による判定を経て、Ｄ　ｏ　３０ルー
プの処理に移る。

ループ制御変数■について、初期値１を検出し処理６３
がレコード４２のフィールド７１に登録し、第７図の４
２のようにする。同様に、ＩＡについても、処理６０が
、文２０の定義を検出し、処理６３がレコード４３のフ
ィールド７１に登録し、第７図の４３のようにする。

更新されたインダクシヨンテーブル７を入力として、公
差・公比生成部４が、インダクシヨン変数に対して公差
か公比のいずれかを検出する。

処理の概要を第９図に示す。

まず、ＤｏｌＯループについて処理を施す。

ＤｏｌＯループは、内側にループを持たないため、処理
８５の判定から処理９３に進む、Ｊは右辺を統括する演
算子が加算であるため、処理９４が公差５を検出し、イ
ンダクシヨンテーブルのレコード４０のフィールド７６
に５を登録し、７９にはｎｉｌを登録する。Ｒは右辺を
統括する演算子が乗算であるため、処理９５が公比Ａを
検出し、インダクシヨンテーブルのレコード４，１のフ
ィールド７６にｎｉｌを７９にＡを登録する。

この後、処理９２による判定を経て、Ｄｏ３０ループの
処理に移る。

ＩＡについては、内側ループ（Ｄｏ２０）についてもイ
ンダクシヨン変数であるため、処理８５の判定から処理
８６に進む。処理８６がＤ０２０ループ内の文２５を検
出した後、処理８６により、この公差・公比生成部が再
帰的に呼ばれる。この時は、Ｄｏ２０は内側ループを持
たないため、ＤｏｌＯループのＪと同様公差１を検出し
、インダクシヨンテーブルのレコード４６のフィールド
７８に１を８１にｎｉｌを登録し、呼び出し元へもどる
。フィールド７８の１に公差であるため、処理８９へ進
む、処理８９は、内側ループのループ長が、レコード４
４より工であるため、公差１の内側ループ１回１回る時
の総和を求める。この例だと、工は当該ループ（Ｄｏ３
０ループ）の制御変数であるため、ループ１回目から工
回目まで１を加えた総和はｌ５（Ｉ−１）／２となり、
これがＩＡの公差である。これをインダクシヨンテーブ
ル４３のフィールド７７に登録し、フィールド８０には
ｎｉｌを登録する。上記のようにして、並列化対象ルー
プのインダクシヨン変数、Ｊ、Ｒ。

ＩＡの公差又は公比を得ることができた。第７図のイン
ダクシヨンテーブルで空白のフィールドは必要ないため
、値を設定する処理は行わない。

最後に、定義式を公比・公差及びループ回数を用いた式
に変換し、インダクシヨン変数における複数のループ回
数にまたがる依存を削除する。

第７図のインダクシヨンテーブルを入力として、大変換
部５の処理フローを第１０図に示す、これにより、第８
図のソースプログラムは第１１図のようになる。

まず、Ｄ　ｏ　１０ループについて処理を施す、内側に
ループを持たないため、処理１００の判定から処理１０
２に進み、インダクシヨン変数Ｊの時は、処理１０３が
、第８図の文１７を第１１図の文１０７に置換し、イン
ダクシヨン変数Ｒの時は。

処理１０４が第８図の文１８を第１１図の文１０８に置
換する。

この後、処理１０５の判定を経て、Ｄｏ３０ループの処
理に進む、インダクシヨン変数ＩＡは、内側ループでも
インダクシヨン変数であるため、処理１００の判定から
、処理１０１に進む。処理１０１は、第８図の文２２と
文２３の間に、第１１図に示す様に文１１０を挿入する
。

以上のようにして、第３図のプログラムを第１１図に変
換すると、ＤｏｌＯループ、Ｄｏ３０ループの各繰り返
し回数ごとに全く独立に並列実行することが可能となる
。ループの繰り返し回数をまたがる依存は無いため、プ
ロセッサ間に通信が無い並列機でも並列処理可能でなる
。第１２図にその様子を示す。

〔発明の効果〕

本発明によれば、ＦＯＲＴＲＡＮ　ａｔｅのプログラム
によく現われる、再帰的に定義されるインダクシヨン変
数の再帰性を解消することができる。

この結果、並列に実行するプロセッサの間に通信手段が
無いマシンでも並列に実行することができ、また、通信
する手段があるマシンについても通信によるオーバヘッ
ドを削減することができる。

このようにして、並列マシン向きの実効性能の高いオブ
ジェクトコードを生成することができる。

【図面の簡単な説明】

第１図は並列化処理部の一部、第２図はコンパイラの全
体図、第３図は実施例説明のためのソースプログラム例
、第４図はインダクシヨン変数検出部の処理概要、第５
図はインダクシヨンテーブル、第６図は初期値生成部の
処理概要、第７図はインダクシヨンテーブル、第８図は
初期値生成部の変換例、第９図は公差・公比生成部の処
理概要、第１０図は定義式変換部の処理概要、第１１図
は並列化処理部の出力であるプログラムの変換例、第１
２図はプログラムの並列実行列である。１・・・自動並列化部、２・・・インダクシヨン変数検
出部、３・・・初期値生成部、４・・・公差・公比生成
部、５・・・大変換部、６・・・中間語、７・・・イン
ダクシヨンテーブル、８・・・ＦＯＲＴＲＡＮコンパイ
ラ、９・・・構文解析部、１０・・・中間部、１１・・
・コード生成部、１２・・・ＦＯＲＴＲＡＮソースプロ
グラム、１３・・・オブジェクトコード、１４〜２７・
・・ＦＯＲＴＲＡＮプログラム、２８〜３５・・・処理
部、３６〜３８・・・ループテーブル、３９〜４６・・
・インダクシヨンテーブル、６０〜６５・・・処理部、
７０〜８１・・・インダクシヨンテーブル、８５〜９５
・・・処理部、１００〜１０５・・・処理部、１０７〜
１０９・・・ＦＯＲＴＲＡＮ実行文、１１０〜１１２・
・・Ｈｏ５ｔ計算機の実行、１１３〜１１８・・・プロ
セッサエレメントによる並列実行。

Claims

【特許請求の範囲】

１、高級言語で記述されたソースプログラムを並列計算
機による並列実行のための命令列を含むオブジェクトコ
ードを生成するコンパイラにおいて、遂次実行型のプロ
グラムを並列実行型のプログラムに変換する並列化部を
備え、該並列化部は、並列化の対象とするループの中の
再帰的に定義されるインダクシヨン変数を検出するイン
ダクシヨン変数検出部と、検出したインダクシヨン変数
の初期値を計算するコードを生成する初期化生成部と、
インダクシヨン変数の公差や公比を計算するコードを生
成する公差・公比生成部と、インダクシヨン変数の定義
式を、計算した初期値や公差又は公比と、ループ回数を
用いて定義する式に変換する式変換部を備えてなり、該
並列化部が、再帰的に定義されるインダクシヨン変数を
ループの繰り返し画数と、ループの実行中値が変わらな
いループ不変変数によつて定義されるように変換する並
列化コンパイル方式。