JPH07110800A - 最適化並列コンパイル装置及び最適化並列コンパイル方法 - Google Patents
最適化並列コンパイル装置及び最適化並列コンパイル方法Info
- Publication number
- JPH07110800A JPH07110800A JP5255609A JP25560993A JPH07110800A JP H07110800 A JPH07110800 A JP H07110800A JP 5255609 A JP5255609 A JP 5255609A JP 25560993 A JP25560993 A JP 25560993A JP H07110800 A JPH07110800 A JP H07110800A
- Authority
- JP
- Japan
- Prior art keywords
- loop
- variable
- parallelization
- data
- detecting
- 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.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F8/00—Arrangements for software engineering
- G06F8/40—Transformation of program code
- G06F8/41—Compilation
- G06F8/43—Checking; Contextual analysis
- G06F8/433—Dependency analysis; Data or control flow analysis
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F8/00—Arrangements for software engineering
- G06F8/40—Transformation of program code
- G06F8/41—Compilation
- G06F8/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
- G06F8/451—Code distribution
- G06F8/452—Loops
Landscapes
- Engineering & Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】
【目的】 プログラムループの並列化を行なう際に、デ
ータ転送数が最小となる最適化コンパイル装置及び方法
並びにそれを用いたプログラム変換装置を提供する。 【構成】 入力手段２０１から入力されたソースプログ
ラムは、中間コード生成手段２０２で中間コードに変換
される。この中間コードからループ検出手段２０３、参
照変数検出手段２０４によってループ、ループ中で参照
される変数が検出される。さらにデータ転送数検出手段
２０７によってループの並列化によって必要となるデー
タ転送数を並列化対象ループごとに計算する。並列化判
定手段２０９はデータ転送数が最小となる並列化ループ
を決定し、ループの並列化を行なう。
ータ転送数が最小となる最適化コンパイル装置及び方法
並びにそれを用いたプログラム変換装置を提供する。 【構成】 入力手段２０１から入力されたソースプログ
ラムは、中間コード生成手段２０２で中間コードに変換
される。この中間コードからループ検出手段２０３、参
照変数検出手段２０４によってループ、ループ中で参照
される変数が検出される。さらにデータ転送数検出手段
２０７によってループの並列化によって必要となるデー
タ転送数を並列化対象ループごとに計算する。並列化判
定手段２０９はデータ転送数が最小となる並列化ループ
を決定し、ループの並列化を行なう。
Description
【０００１】
【産業上の利用分野】本発明は、プログラムを並列計算
機用のプログラムに変換する最適化並列コンパイル装置
及び並列化コンパイラの最適化方法に関する。
機用のプログラムに変換する最適化並列コンパイル装置
及び並列化コンパイラの最適化方法に関する。
【０００２】
【従来の技術】近年、プログラムを並列に実行する並列
計算機システムの開発が進んでいる。並列計算機はプロ
グラムを実行する複数のＰＥ（プロセッシングエレメン
ト）を有し、それぞれのＰＥにプログラムを与えること
で並列処理を実現する。通常、ＦＯＲＴＲＡＮ等の高級
言語で記述されるソースプログラムは、シリアル処理を
前提に記述される。これらのソースプログラムを並列計
算機で実行させるためには、ソースプログラムからオブ
ジェクトプログラムを生成するコンパイラに並列実行用
のオブジェクトプログラムを生成する機能を持たせる必
要がある。
計算機システムの開発が進んでいる。並列計算機はプロ
グラムを実行する複数のＰＥ（プロセッシングエレメン
ト）を有し、それぞれのＰＥにプログラムを与えること
で並列処理を実現する。通常、ＦＯＲＴＲＡＮ等の高級
言語で記述されるソースプログラムは、シリアル処理を
前提に記述される。これらのソースプログラムを並列計
算機で実行させるためには、ソースプログラムからオブ
ジェクトプログラムを生成するコンパイラに並列実行用
のオブジェクトプログラムを生成する機能を持たせる必
要がある。
【０００３】従来、ソースプログラムから並列計算機用
のオブジェクトプログラムを生成するコンパイラとし
て、ソースプログラムに含まれるdoループのような繰り
返し処理から並列性を抽出し、ループの繰り返しを各Ｐ
Ｅに割り当てて、並列実行させるという方法が採られて
いる。これは各多重ループ単位で並列性の抽出がなされ
る。以上のことは文献「David A.Padua, et al.:Advanc
ed compiler optimizations for supercomputers, Comm
unications of the ACM,pp1184-1201(1986)」に記載さ
れている。なお、以下の説明では、プログラムにおいて
繰り返し実行されうる命令の集合をループ（またはルー
プ処理）と呼び、ループにおける１回分の処理を繰り返
しと呼ぶ。
のオブジェクトプログラムを生成するコンパイラとし
て、ソースプログラムに含まれるdoループのような繰り
返し処理から並列性を抽出し、ループの繰り返しを各Ｐ
Ｅに割り当てて、並列実行させるという方法が採られて
いる。これは各多重ループ単位で並列性の抽出がなされ
る。以上のことは文献「David A.Padua, et al.:Advanc
ed compiler optimizations for supercomputers, Comm
unications of the ACM,pp1184-1201(1986)」に記載さ
れている。なお、以下の説明では、プログラムにおいて
繰り返し実行されうる命令の集合をループ（またはルー
プ処理）と呼び、ループにおける１回分の処理を繰り返
しと呼ぶ。
【０００４】例えば図３に示したＦＯＲＴＲＡＮプログ
ラムでは、第一の多重ループ３０１、３０２と、第二の
多重ループ３０３、３０４は並列化可能と判定され、並
列化された後のプログラムは図８（ａ）,（ｂ）のよう
になる。図８（ａ）は第一の多重ループを並列化した様
子を示しており、図８（ｂ）は第二の多重ループを並列
化した様子を示している。以上のように従来技術では、
各多重ループ単位で、ループの並列化を行なっていた。
ラムでは、第一の多重ループ３０１、３０２と、第二の
多重ループ３０３、３０４は並列化可能と判定され、並
列化された後のプログラムは図８（ａ）,（ｂ）のよう
になる。図８（ａ）は第一の多重ループを並列化した様
子を示しており、図８（ｂ）は第二の多重ループを並列
化した様子を示している。以上のように従来技術では、
各多重ループ単位で、ループの並列化を行なっていた。
【０００５】
【発明が解決しようとする課題】しかしながら上記の従
来技術によれば、各多重ループ単位でそのループの並列
化を行なうため、必ずしもデータの転送数が最小となる
並列化とはなっていないという問題点があった。つま
り、図８（ａ）,（ｂ）のように並列化されたプログラ
ムを図１に示すような並列計算機で実行する場合、図８
（ａ）に示した状態で各ＰＥが並列実行した後で、図８
（ｂ）に示すように各ＰＥが並列実行するためには、図
８（ａ）で計算された結果ａ（ｉ，ｊ），ｉ，ｊ＝１〜
８が図８（ｂ）に示す計算に必要になる。図９はＰＥ１
の実行に必要なデータ転送の様子を示しており、図８
（ａ）で示した状態で各ＰＥが並列に実行した後で、図
９に示すようなデータの移動（データ転送）が必要にな
ってくる。
来技術によれば、各多重ループ単位でそのループの並列
化を行なうため、必ずしもデータの転送数が最小となる
並列化とはなっていないという問題点があった。つま
り、図８（ａ）,（ｂ）のように並列化されたプログラ
ムを図１に示すような並列計算機で実行する場合、図８
（ａ）に示した状態で各ＰＥが並列実行した後で、図８
（ｂ）に示すように各ＰＥが並列実行するためには、図
８（ａ）で計算された結果ａ（ｉ，ｊ），ｉ，ｊ＝１〜
８が図８（ｂ）に示す計算に必要になる。図９はＰＥ１
の実行に必要なデータ転送の様子を示しており、図８
（ａ）で示した状態で各ＰＥが並列に実行した後で、図
９に示すようなデータの移動（データ転送）が必要にな
ってくる。
【０００６】本発明は上記問題点に鑑み、ループの並列
化をする際に、データ転送数が最小になる最適化並列コ
ンパイル装置及び最適化並列コンパイル方法を提供する
ことを目的とする。
化をする際に、データ転送数が最小になる最適化並列コ
ンパイル装置及び最適化並列コンパイル方法を提供する
ことを目的とする。
【０００７】
【課題を解決するための手段】上記課題を解決するため
本発明の最適化並列コンパイル装置は、複数のプログラ
ム文からなり、繰り返し処理を実行するループを含むプ
ログラムを並列計算機用コードに変換する最適化並列コ
ンパイル装置であって、ソースプログラムから中間コー
ドに変換する中間コード生成手段と、前記中間コードか
ら繰り返し処理を実行するループを検出するループ検出
手段と、前記ループ検出手段によって検出されたループ
の繰り返しごとに参照される変数を検出する参照変数検
出手段と、前記ループ検出手段によって検出されたルー
プの繰り返しごとに既に左辺で定義された変数群と前記
参照変数検出手段から出力される右辺で参照される変数
とからデータ転送数を検出するデータ転送数検出手段
と、並列化判定手段と、前記並列化判定手段により並列
化が可能であると決定された場合、左辺にある変数群を
格納する左辺変数格納手段とを備えたものである。
本発明の最適化並列コンパイル装置は、複数のプログラ
ム文からなり、繰り返し処理を実行するループを含むプ
ログラムを並列計算機用コードに変換する最適化並列コ
ンパイル装置であって、ソースプログラムから中間コー
ドに変換する中間コード生成手段と、前記中間コードか
ら繰り返し処理を実行するループを検出するループ検出
手段と、前記ループ検出手段によって検出されたループ
の繰り返しごとに参照される変数を検出する参照変数検
出手段と、前記ループ検出手段によって検出されたルー
プの繰り返しごとに既に左辺で定義された変数群と前記
参照変数検出手段から出力される右辺で参照される変数
とからデータ転送数を検出するデータ転送数検出手段
と、並列化判定手段と、前記並列化判定手段により並列
化が可能であると決定された場合、左辺にある変数群を
格納する左辺変数格納手段とを備えたものである。
【０００８】前記並列化判定手段は、前記参照変数検出
手段によって検出された変数を入力し、ループにまたが
ったデータ依存関係をあるか否かを判定するデータ参照
関係判定手段と、前記データ転送数検出手段から出力さ
れるデータ転送数と前記データ参照関係判定手段から出
力されるデータ依存関係の有無情報に基づいて並列化可
能か否かを判定する最適判定手段とを有することが望ま
しい。
手段によって検出された変数を入力し、ループにまたが
ったデータ依存関係をあるか否かを判定するデータ参照
関係判定手段と、前記データ転送数検出手段から出力さ
れるデータ転送数と前記データ参照関係判定手段から出
力されるデータ依存関係の有無情報に基づいて並列化可
能か否かを判定する最適判定手段とを有することが望ま
しい。
【０００９】前記参照変数検出手段は、左辺変数検出手
段と、右辺変数検出手段とを有することが望ましい。
段と、右辺変数検出手段とを有することが望ましい。
【００１０】また、本発明の最適化並列コンパイル方法
は、複数のプログラム文からなり、繰り返し処理を実行
するループを含むプログラムを並列計算機用コードに変
換する最適化並列コンパイル方法であって、ソースプロ
グラムから中間コードに変換する中間コード生成ステッ
プと、前記中間コードから繰り返し処理を実行するルー
プを検出するループ検出ステップと、ループの繰り返し
ごとに参照される変数を検出する左辺の変数検出ステッ
プと右辺の変数検出ステップと、データ参照関係判定ス
テップと、前記データ参照関係判定ステップでデータ依
存関係が無いと判定された場合、前記ループ検出ステッ
プによって検出されたループの繰り返しごとに既に左辺
で定義された変数群と前記右辺の変数検出ステップによ
り検出された右辺で参照される変数とからデータ転送数
を検出するデータ転送数検出ステップと、データ転送数
の最小となるループを検出するステップと、並列化ルー
プで左辺の変数を登録するステップと、並列化オブジェ
クトを生成するステップと、前記データ参照関係判定ス
テップでデータ依存関係があると判定された場合、並列
化できない場合のオブジェクトを生成するステップとを
有するものである。
は、複数のプログラム文からなり、繰り返し処理を実行
するループを含むプログラムを並列計算機用コードに変
換する最適化並列コンパイル方法であって、ソースプロ
グラムから中間コードに変換する中間コード生成ステッ
プと、前記中間コードから繰り返し処理を実行するルー
プを検出するループ検出ステップと、ループの繰り返し
ごとに参照される変数を検出する左辺の変数検出ステッ
プと右辺の変数検出ステップと、データ参照関係判定ス
テップと、前記データ参照関係判定ステップでデータ依
存関係が無いと判定された場合、前記ループ検出ステッ
プによって検出されたループの繰り返しごとに既に左辺
で定義された変数群と前記右辺の変数検出ステップによ
り検出された右辺で参照される変数とからデータ転送数
を検出するデータ転送数検出ステップと、データ転送数
の最小となるループを検出するステップと、並列化ルー
プで左辺の変数を登録するステップと、並列化オブジェ
クトを生成するステップと、前記データ参照関係判定ス
テップでデータ依存関係があると判定された場合、並列
化できない場合のオブジェクトを生成するステップとを
有するものである。
【００１１】
【作用】本発明は上記した手段により、データ転送数検
出手段は、既に並列化されているループの代入文の左辺
にある変数とこれから並列化を行なうループにある代入
文の右辺の変数の関係からデータ転送数を計算する。並
列化判定手段は、データ転送数が最小となる並列化ルー
プを決定して並列化を行なう。
出手段は、既に並列化されているループの代入文の左辺
にある変数とこれから並列化を行なうループにある代入
文の右辺の変数の関係からデータ転送数を計算する。並
列化判定手段は、データ転送数が最小となる並列化ルー
プを決定して並列化を行なう。
【００１２】
【実施例】本発明のプログラム変換装置の一実施例につ
いて具体例を挙げて説明する。
いて具体例を挙げて説明する。
【００１３】図２は、本発明の一実施例におけるコンパ
イル装置の機能ブロック図である。２０１は入力手段
で、外部から入力されるソースプログラムを取り込む。
２０２は中間コード生成手段で、高級言語、例えばＦＯ
ＲＴＲＡＮで記述されたソースプログラムを変換して、
中間コードで記述されたプログラムを生成する。２０３
はループ検出手段で、ソースプログラムに含まれるルー
プ処理を検出する。
イル装置の機能ブロック図である。２０１は入力手段
で、外部から入力されるソースプログラムを取り込む。
２０２は中間コード生成手段で、高級言語、例えばＦＯ
ＲＴＲＡＮで記述されたソースプログラムを変換して、
中間コードで記述されたプログラムを生成する。２０３
はループ検出手段で、ソースプログラムに含まれるルー
プ処理を検出する。
【００１４】２０４はループ処理中で参照される変数を
検出する参照変数検出手段であり、参照変数検出手段２
０４はループ検出手段２０３で検出されたループごとに
中間コード生成手段２０２で生成された中間コードか
ら、式の左辺にある変数を検出する左辺の変数検出手段
２０５と、式の右辺にある変数を検出する右辺の変数検
出手段２０６とを含む。
検出する参照変数検出手段であり、参照変数検出手段２
０４はループ検出手段２０３で検出されたループごとに
中間コード生成手段２０２で生成された中間コードか
ら、式の左辺にある変数を検出する左辺の変数検出手段
２０５と、式の右辺にある変数を検出する右辺の変数検
出手段２０６とを含む。
【００１５】２０７はデータ転送数検出手段で、ループ
検出手段２０３で検出されたループごとに右辺の変数検
出手段２０６からの右辺の変数と左辺の変数格納手段２
０８からの左辺の変数とから並列化によるデータ転送数
を計算する。
検出手段２０３で検出されたループごとに右辺の変数検
出手段２０６からの右辺の変数と左辺の変数格納手段２
０８からの左辺の変数とから並列化によるデータ転送数
を計算する。
【００１６】２０９は並列化判定手段で、データ参照関
係判定手段２１０と最適判定手段２１１とからなり、デ
ータ参照関係判定手段２１０は左辺の変数検出手段２０
５と右辺の変数検出手段２０６からデータ依存関係があ
るかどうかを判定し、その結果とデータ転送数検出手段
２０７により検出されたデータ転送数とから並列実行ル
ープを決定する。並列実行ループが決定されると、左辺
の変数格納手段２０８で並列化により左辺にある変数群
を記憶する。
係判定手段２１０と最適判定手段２１１とからなり、デ
ータ参照関係判定手段２１０は左辺の変数検出手段２０
５と右辺の変数検出手段２０６からデータ依存関係があ
るかどうかを判定し、その結果とデータ転送数検出手段
２０７により検出されたデータ転送数とから並列実行ル
ープを決定する。並列実行ループが決定されると、左辺
の変数格納手段２０８で並列化により左辺にある変数群
を記憶する。
【００１７】２１２はオブジェクト生成手段で、並列化
判定手段２０９が並列化可能と判定したとき、並列実行
用のオブジェクトプログラムを生成し、並列化不可と判
定したとき、通常のオブジェクトプログラムを生成す
る。２１３は出力手段で、オブジェクトプログラムを出
力する。例えば、プログラムを記憶するディスク装置等
である。
判定手段２０９が並列化可能と判定したとき、並列実行
用のオブジェクトプログラムを生成し、並列化不可と判
定したとき、通常のオブジェクトプログラムを生成す
る。２１３は出力手段で、オブジェクトプログラムを出
力する。例えば、プログラムを記憶するディスク装置等
である。
【００１８】以上のように構成された本発明の実施例に
おけるコンパイラについて、図４に示す処理フローを用
いてその動作を説明する。
おけるコンパイラについて、図４に示す処理フローを用
いてその動作を説明する。
【００１９】まずステップ４０１では、コンパイルされ
る前のソースプログラムは、入力手段２０１に入力され
る。このソースプログラムの例としてＦＯＲＴＲＡＮで
記述されたプログラムを図３に示す。このプログラムは
外側のループ３０１（変数ｉに関するｄｏ １０のルー
プ）の中にループ３０２（変数ｊに関するｄｏ １０の
ループ）を含んだ多重ループと、外側のループ３０３
（変数ｊに関するｄｏ ２０のループ）の中にループ３
０４（変数ｉに関するｄｏ ２０のループ）を含んだ多
重ループがある。ステップ４０２では、入力手段２０１
から入力されたソースプログラムは、中間コード生成手
段２０２によって中間コードに変換される。
る前のソースプログラムは、入力手段２０１に入力され
る。このソースプログラムの例としてＦＯＲＴＲＡＮで
記述されたプログラムを図３に示す。このプログラムは
外側のループ３０１（変数ｉに関するｄｏ １０のルー
プ）の中にループ３０２（変数ｊに関するｄｏ １０の
ループ）を含んだ多重ループと、外側のループ３０３
（変数ｊに関するｄｏ ２０のループ）の中にループ３
０４（変数ｉに関するｄｏ ２０のループ）を含んだ多
重ループがある。ステップ４０２では、入力手段２０１
から入力されたソースプログラムは、中間コード生成手
段２０２によって中間コードに変換される。
【００２０】ステップ４０３では、中間コードが生成さ
れるとループ検出手段２０３は、中間コードに含まれる
ループ処理を検出する。具体的には、図３のようなＦＯ
ＲＴＲＡＮにおいては、ループ検出手段２０３は、ソー
スプログラム中のｄｏ文とｃｏｎｔｉｎｕｅ文のペアを
判別し、それをループ処理として検出する。ステップ４
０４では、ループ処理の有無を判断し、その判断結果に
従って、存在する場合にはステップ４０５へ進み、存在
しない場合にはステップ４１２に進む。
れるとループ検出手段２０３は、中間コードに含まれる
ループ処理を検出する。具体的には、図３のようなＦＯ
ＲＴＲＡＮにおいては、ループ検出手段２０３は、ソー
スプログラム中のｄｏ文とｃｏｎｔｉｎｕｅ文のペアを
判別し、それをループ処理として検出する。ステップ４
０４では、ループ処理の有無を判断し、その判断結果に
従って、存在する場合にはステップ４０５へ進み、存在
しない場合にはステップ４１２に進む。
【００２１】次にループ処理が存在する場合、ステップ
４０５,４０６では、参照変数検出手段２０４は抽出さ
れたループ処理における変数を検出する。図３における
ｄｏループ３０１、３０２において、参照変数検出手段
２０４は、式の左辺にある配列ａ（ｉ,ｊ）と、式の右
辺にある配列ｂ（ｉ,ｊ）、ｃ（ｉ,ｊ）とを検出する。
４０５,４０６では、参照変数検出手段２０４は抽出さ
れたループ処理における変数を検出する。図３における
ｄｏループ３０１、３０２において、参照変数検出手段
２０４は、式の左辺にある配列ａ（ｉ,ｊ）と、式の右
辺にある配列ｂ（ｉ,ｊ）、ｃ（ｉ,ｊ）とを検出する。
【００２２】この後ステップ４０７では、データ参照関
係判定手段２１０によってデータ依存関係があるかどう
かを判定する。その結果、データ依存関係がある場合は
ステップ４１２に進み、データ依存関係が無い場合はス
テップ４０８に進む。
係判定手段２１０によってデータ依存関係があるかどう
かを判定する。その結果、データ依存関係がある場合は
ステップ４１２に進み、データ依存関係が無い場合はス
テップ４０８に進む。
【００２３】ステップ４０８では、データ転送数検出手
段２０７により右辺の変数検出手段２０６と左辺の変数
格納手段２０８からデータ転送数を計算する。この結果
からステップ４０９では、最適判定手段２１１でデータ
転送数が最小となる並列化ループを決定する。
段２０７により右辺の変数検出手段２０６と左辺の変数
格納手段２０８からデータ転送数を計算する。この結果
からステップ４０９では、最適判定手段２１１でデータ
転送数が最小となる並列化ループを決定する。
【００２４】次にステップ４１０では、並列化ループが
決定された後、そのループ中で、式の左辺にある変数が
登録済みの変数として左辺の変数格納手段２０８に格納
される。続いて、オブジェクト生成手段２１２により、
並列化判定手段２０９の結果から並列化可能であれば並
列化ループのオブジェクトを生成し（ステップ４１
１）、並列化不可能であれば並列化されていないループ
のオブジェクトを生成する（ステップ４１２）。最後に
ステップ４１３では、出力手段２１３により、オブジェ
クトプログラムが出力装置等（例えば、ディスク装置）
に出力する。
決定された後、そのループ中で、式の左辺にある変数が
登録済みの変数として左辺の変数格納手段２０８に格納
される。続いて、オブジェクト生成手段２１２により、
並列化判定手段２０９の結果から並列化可能であれば並
列化ループのオブジェクトを生成し（ステップ４１
１）、並列化不可能であれば並列化されていないループ
のオブジェクトを生成する（ステップ４１２）。最後に
ステップ４１３では、出力手段２１３により、オブジェ
クトプログラムが出力装置等（例えば、ディスク装置）
に出力する。
【００２５】ここで、データ転送数を計算して転送数の
最小となる並列化ループが決定される様子を、図２、
３、５、６、７及び処理フローを示す図４を参照しつつ
具体的に説明する。
最小となる並列化ループが決定される様子を、図２、
３、５、６、７及び処理フローを示す図４を参照しつつ
具体的に説明する。
【００２６】まず、図３の第一の多重ループ（外側ルー
プ３０１、内側ループ３０２）の外側ループ３０１が並
列化ループであると並列化判定手段２０９で判定された
とする。このときに、第二の多重ループ（外側ループ３
０３、内側ループ３０４）の並列化がどのようになされ
るかを説明する。
プ３０１、内側ループ３０２）の外側ループ３０１が並
列化ループであると並列化判定手段２０９で判定された
とする。このときに、第二の多重ループ（外側ループ３
０３、内側ループ３０４）の並列化がどのようになされ
るかを説明する。
【００２７】第一の多重ループが並列化されたときに、
左辺の変数格納手段２０８には左辺の変数登録がなされ
ている。例えば、配列ａに関しては図５に示すように各
ＰＥに割り当てられている。このとき、第二の多重ルー
プについて、ループ内の式３０５が左辺の変数検出手段
２０５と右辺の変数検出手段２０６に入力されると、左
辺の変数検出手段２０５は、左辺の変数ｄ（ｉ，ｊ）を
検出し（ステップ４０５）、右辺の変数検出手段２０６
は、右辺の変数ａ（ｉ，ｊ）、ｅ（ｉ，ｊ）を検出する
（ステップ４０６）。データ参照関係判定手段２１０
は、これらの変数の添字部は揃っているため、外側ルー
プ３０３、内側ループ３０４のどちらのループに関して
も、ループにまたがったデータ参照関係がないと判定す
る（ステップ４０７）。ループにまたがったデータ参照
関係がないため、次のステップ４０８に進むことにな
る。
左辺の変数格納手段２０８には左辺の変数登録がなされ
ている。例えば、配列ａに関しては図５に示すように各
ＰＥに割り当てられている。このとき、第二の多重ルー
プについて、ループ内の式３０５が左辺の変数検出手段
２０５と右辺の変数検出手段２０６に入力されると、左
辺の変数検出手段２０５は、左辺の変数ｄ（ｉ，ｊ）を
検出し（ステップ４０５）、右辺の変数検出手段２０６
は、右辺の変数ａ（ｉ，ｊ）、ｅ（ｉ，ｊ）を検出する
（ステップ４０６）。データ参照関係判定手段２１０
は、これらの変数の添字部は揃っているため、外側ルー
プ３０３、内側ループ３０４のどちらのループに関して
も、ループにまたがったデータ参照関係がないと判定す
る（ステップ４０７）。ループにまたがったデータ参照
関係がないため、次のステップ４０８に進むことにな
る。
【００２８】データ転送数検出手段２０７は既に登録済
みの左辺の変数と右辺の変数検出手段２０６により検出
された変数とからデータ転送数を各ループについて並列
化した場合のそれぞれについて計算する。ここでは、既
に登録済みの左辺の変数として、図５のように各ＰＥに
割り当てられているとする。右辺の変数にａ（ｉ，ｊ）
が存在するため、この変数ａに関してデータ転送数を外
側ループ３０３について並列化した場合と、内側ループ
３０４について並列化した場合とでそれぞれ計算する。
外側ループ３０３について並列化したとすると、図６に
示すように変数ａが各ＰＥに割り当てられることにな
る。例えば、ＰＥ１についてみると、右辺で参照される
変数はａ（１，１）、ａ（２，１）、ａ（３，１）、ａ
（４，１）、ａ（５，１）、ａ（６，１）、ａ（７，
１）、ａ（８，１）であり、図６に示したように、既に
左辺の変数として登録されているのをみると、ａ（２，
１）はＰＥ２に、ａ（３，１）はＰＥ３に、ａ（４，
１）はＰＥ４に、ａ（５，１）はＰＥ５に、ａ（６，
１）はＰＥ６に、ａ（７，１）はＰＥ７に、ａ（８，
１）はＰＥ８にそれぞれ割り当てられている。従って、
データ転送数はＰＥ１については７となる。同様に、Ｐ
Ｅ２〜ＰＥ８について考慮すると、７×８＝５６とな
る。
みの左辺の変数と右辺の変数検出手段２０６により検出
された変数とからデータ転送数を各ループについて並列
化した場合のそれぞれについて計算する。ここでは、既
に登録済みの左辺の変数として、図５のように各ＰＥに
割り当てられているとする。右辺の変数にａ（ｉ，ｊ）
が存在するため、この変数ａに関してデータ転送数を外
側ループ３０３について並列化した場合と、内側ループ
３０４について並列化した場合とでそれぞれ計算する。
外側ループ３０３について並列化したとすると、図６に
示すように変数ａが各ＰＥに割り当てられることにな
る。例えば、ＰＥ１についてみると、右辺で参照される
変数はａ（１，１）、ａ（２，１）、ａ（３，１）、ａ
（４，１）、ａ（５，１）、ａ（６，１）、ａ（７，
１）、ａ（８，１）であり、図６に示したように、既に
左辺の変数として登録されているのをみると、ａ（２，
１）はＰＥ２に、ａ（３，１）はＰＥ３に、ａ（４，
１）はＰＥ４に、ａ（５，１）はＰＥ５に、ａ（６，
１）はＰＥ６に、ａ（７，１）はＰＥ７に、ａ（８，
１）はＰＥ８にそれぞれ割り当てられている。従って、
データ転送数はＰＥ１については７となる。同様に、Ｐ
Ｅ２〜ＰＥ８について考慮すると、７×８＝５６とな
る。
【００２９】次に、内側ループ３０４について並列化し
たとすると、図７のようになり、全く転送する必要はな
くなり、転送数は０と計算される（ステップ４０８）。
たとすると、図７のようになり、全く転送する必要はな
くなり、転送数は０と計算される（ステップ４０８）。
【００３０】最適判定手段２１１は、データ転送数が最
小となる並列化ループを決定する（ステップ４０９）。
ここでは、転送数０となる内側ループ３０４について並
列化することとなる。左辺の変数登録手段２０８は、内
側ループ３０４について並列化した場合の各ＰＥへの割
り当てを考慮して、左辺の変数ｄが左辺の変数格納手段
２０８により記憶される（ステップ４１０）。
小となる並列化ループを決定する（ステップ４０９）。
ここでは、転送数０となる内側ループ３０４について並
列化することとなる。左辺の変数登録手段２０８は、内
側ループ３０４について並列化した場合の各ＰＥへの割
り当てを考慮して、左辺の変数ｄが左辺の変数格納手段
２０８により記憶される（ステップ４１０）。
【００３１】
【発明の効果】以上のように本発明の最適化並列コンパ
イル装置及び最適化並列コンパイル方法によれば、デー
タ転送数を考慮した並列化が行なえるため、データ転送
によるオーバーヘッドを最小とする並列化が可能とな
り、その結果、実効性能向上が図れる。
イル装置及び最適化並列コンパイル方法によれば、デー
タ転送数を考慮した並列化が行なえるため、データ転送
によるオーバーヘッドを最小とする並列化が可能とな
り、その結果、実効性能向上が図れる。
【図１】並列計算機の構成を示すブロック図
【図２】同実施例におけるコンパイラの機能ブロック図
【図３】ソースプログラムの例を示した図
【図４】同実施例におけるコンパイラの処理フロー図
【図５】図３のソースプログラムにおける第一の多重ル
ープの変数ａの各ＰＥへの割り当てを示した図
ープの変数ａの各ＰＥへの割り当てを示した図
【図６】図３のソースプログラムにおける第二の多重ル
ープ（外側ループ）の変数ａの各ＰＥへの割り当てを示
した図
ープ（外側ループ）の変数ａの各ＰＥへの割り当てを示
した図
【図７】図３のソースプログラムにおける第二の多重ル
ープ（内側ループ）の変数ａの各ＰＥへの割り当てを示
した図
ープ（内側ループ）の変数ａの各ＰＥへの割り当てを示
した図
【図８】図３のソースプログラムにおける第一、第二の
多重ループの繰り返しが各ＰＥへ割り当てられる様子を
示した図
多重ループの繰り返しが各ＰＥへ割り当てられる様子を
示した図
【図９】従来例での１ＰＥ当りのデータ転送の様子を示
した図
した図
２０２ 中間コード生成手段 ２０３ ループ検出手段 ２０４ 参照変数検出手段 ２０５ 左辺の変数検出手段 ２０６ 右辺の変数検出手段 ２０７ データ転送数検出手段 ２０８ 左辺の変数格納手段 ２０９ 並列化判定手段 ２１０ データ参照関係判定手段 ２１１ 最適判定手段 ２１２ オブジェクト生成手段
Claims (4)
- 【請求項１】複数のプログラム文からなり、繰り返し処
理を実行するループを含むプログラムを並列計算機用コ
ードに変換する最適化並列コンパイル装置であって、 ソースプログラムから中間コードに変換する中間コード
生成手段と、 前記中間コードから繰り返し処理を実行するループを検
出するループ検出手段と、 前記ループ検出手段によって検出されたループの繰り返
しごとに参照される変数を検出する参照変数検出手段
と、 前記ループ検出手段によって検出されたループの繰り返
しごとに既に左辺で定義された変数群と前記参照変数検
出手段から出力される右辺で参照される変数とからデー
タ転送数を検出するデータ転送数検出手段と、 並列化判定手段と、 前記並列化判定手段により並列化が可能であると決定さ
れた場合、左辺にある変数群を格納する左辺変数格納手
段とを備えた最適化並列コンパイル装置。 - 【請求項２】並列化判定手段は、前記参照変数検出手段
によって検出された変数を入力し、ループにまたがった
データ依存関係をあるか否かを判定するデータ参照関係
判定手段と、 前記データ転送数検出手段から出力されるデータ転送数
と前記データ参照関係判定手段から出力されるデータ依
存関係の有無情報に基づいて並列化可能か否かを判定す
る最適判定手段とを有することを特徴とする請求項１記
載の最適化並列コンパイル装置。 - 【請求項３】参照変数検出手段は、 左辺変数検出手段と、 右辺変数検出手段とを有することを特徴とする請求項１
記載の最適化並列コンパイル装置。 - 【請求項４】複数のプログラム文からなり、繰り返し処
理を実行するループを含むプログラムを並列計算機用コ
ードに変換する最適化並列コンパイル方法であって、 ソースプログラムから中間コードに変換する中間コード
生成ステップと、 前記中間コードから繰り返し処理を実行するループを検
出するループ検出ステップと、 ループの繰り返しごとに参照される変数を検出する左辺
の変数検出ステップと、 右辺の変数検出ステップと、 データ参照関係判定ステップと、 前記データ参照関係判定ステップでデータ依存関係が無
いと判定された場合、前記ループ検出ステップによって
検出されたループの繰り返しごとに既に左辺で定義され
た変数群と前記右辺の変数検出ステップにより検出され
た右辺で参照される変数とからデータ転送数を検出する
データ転送数検出ステップと、 データ転送数の最小となるループを検出するステップ
と、 並列化ループで左辺の変数を登録するステップと、 並列化オブジェクトを生成するステップと、 前記データ参照関係判定ステップでデータ依存関係があ
ると判定された場合、並列化できない場合のオブジェク
トを生成するステップとを有する最適化並列コンパイル
方法。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5255609A JPH07110800A (ja) | 1993-10-13 | 1993-10-13 | 最適化並列コンパイル装置及び最適化並列コンパイル方法 |
| US08/322,609 US5634059A (en) | 1993-10-13 | 1994-10-13 | Device and method for parallelizing compilation optimizing data transmission |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5255609A JPH07110800A (ja) | 1993-10-13 | 1993-10-13 | 最適化並列コンパイル装置及び最適化並列コンパイル方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH07110800A true JPH07110800A (ja) | 1995-04-25 |
Family
ID=17281120
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5255609A Pending JPH07110800A (ja) | 1993-10-13 | 1993-10-13 | 最適化並列コンパイル装置及び最適化並列コンパイル方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5634059A (ja) |
| JP (1) | JPH07110800A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2012086148A1 (ja) * | 2010-12-21 | 2012-06-28 | パナソニック株式会社 | コンパイル装置、コンパイルプログラム及びループ並列化方法 |
Families Citing this family (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB9305263D0 (en) * | 1993-03-15 | 1993-05-05 | Univ Westminster | Parrallel computation |
| CN1149476C (zh) * | 1995-03-16 | 2004-05-12 | 松下电器产业株式会社 | 资源分配装置 |
| JP3626784B2 (ja) * | 1995-03-17 | 2005-03-09 | 富士通株式会社 | 分散メモリ型並列計算機におけるデータ更新方法およびプログラム変換装置 |
| GB2299422B (en) * | 1995-03-30 | 2000-01-12 | Sony Uk Ltd | Object code allocation in multiple processor systems |
| JP3505266B2 (ja) * | 1995-06-15 | 2004-03-08 | 三洋電機株式会社 | プログラム実行装置 |
| JPH1040223A (ja) * | 1996-06-17 | 1998-02-13 | Internatl Business Mach Corp <Ibm> | 分散並列システムにおける集合通信認識の最適化方法 |
| CA2288614C (en) * | 1999-11-08 | 2004-05-11 | Robert J. Blainey | Loop allocation for optimizing compilers |
| US7000227B1 (en) * | 2000-09-29 | 2006-02-14 | Intel Corporation | Iterative optimizing compiler |
| US6952821B2 (en) * | 2002-08-19 | 2005-10-04 | Hewlett-Packard Development Company, L.P. | Method and system for memory management optimization |
| US7484079B2 (en) * | 2002-10-31 | 2009-01-27 | Hewlett-Packard Development Company, L.P. | Pipeline stage initialization via task frame accessed by a memory pointer propagated among the pipeline stages |
| US8726238B2 (en) * | 2010-02-22 | 2014-05-13 | International Business Machines Corporation | Interactive iterative program parallelization based on dynamic feedback |
| US20110271265A1 (en) * | 2010-04-28 | 2011-11-03 | Drozdov Alexander Y | Method of automatic generation of executable code for multi-core parallel processing |
| CN102483701A (zh) * | 2010-07-05 | 2012-05-30 | 松下电器产业株式会社 | 程序生成装置、程序生产方法及程序 |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3053092B2 (ja) * | 1987-06-05 | 2000-06-19 | 株式会社日立製作所 | 並列化コンパイル方法 |
| JPH01108638A (ja) * | 1987-10-21 | 1989-04-25 | Hitachi Ltd | 並列化コンパイル方式 |
| JP2749039B2 (ja) * | 1987-11-06 | 1998-05-13 | 株式会社日立製作所 | オブジェクト生成方法 |
| JP2738692B2 (ja) * | 1988-01-29 | 1998-04-08 | 株式会社日立製作所 | 並列化コンパイル方法 |
| JPH03111971A (ja) * | 1989-09-27 | 1991-05-13 | Toshiba Corp | ベクトル化診断方式 |
| JPH04211830A (ja) * | 1990-02-05 | 1992-08-03 | Matsushita Electric Ind Co Ltd | 並列化コンパイル方式 |
| JPH0475139A (ja) * | 1990-07-18 | 1992-03-10 | Toshiba Corp | ループ並列化装置 |
| JPH04293150A (ja) * | 1991-03-20 | 1992-10-16 | Hitachi Ltd | コンパイル方法 |
| US5437034A (en) * | 1991-04-19 | 1995-07-25 | Hitachi, Ltd. | Method of generating from source program object program by which final values of variables for parallel execution are guaranteed |
| JP3280449B2 (ja) * | 1993-03-01 | 2002-05-13 | 富士通株式会社 | コンパイル装置 |
-
1993
- 1993-10-13 JP JP5255609A patent/JPH07110800A/ja active Pending
-
1994
- 1994-10-13 US US08/322,609 patent/US5634059A/en not_active Expired - Fee Related
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2012086148A1 (ja) * | 2010-12-21 | 2012-06-28 | パナソニック株式会社 | コンパイル装置、コンパイルプログラム及びループ並列化方法 |
| JP5810316B2 (ja) * | 2010-12-21 | 2015-11-11 | パナソニックＩｐマネジメント株式会社 | コンパイル装置、コンパイルプログラム及びループ並列化方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5634059A (en) | 1997-05-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2921190B2 (ja) | 並列実行方式 | |
| JP2738692B2 (ja) | 並列化コンパイル方法 | |
| JP3317825B2 (ja) | ループ最適化翻訳処理方法 | |
| JPH07110800A (ja) | 最適化並列コンパイル装置及び最適化並列コンパイル方法 | |
| JPH0814817B2 (ja) | 自動ベクトル化方法 | |
| CN104536898B (zh) | C程序并行区域的检测方法 | |
| JP2001167060A (ja) | タスク並列化方法 | |
| US5790859A (en) | Method of, system for, and computer program product for efficient identification of private variables in program loops by an optimizing compiler | |
| US5067068A (en) | Method for converting an iterative loop of a source program into parellelly executable object program portions | |
| JPH06324881A (ja) | メモリデータの重なり判定機能を備えたコンパイラ装置 | |
| CN103250135A (zh) | 编译装置、编译程序及循环并列化方法 | |
| US20170206068A1 (en) | Program optimization based on directives for intermediate code | |
| JPH04293150A (ja) | コンパイル方法 | |
| JPH04307624A (ja) | ループ最適化方法及び装置 | |
| Song et al. | What can we gain by unfolding loops? | |
| JP2865694B2 (ja) | コンパイル方法 | |
| JP2789977B2 (ja) | 実行情報採取用プログラム生成装置 | |
| Deng et al. | Superword level parallelism vectorization method for signal processing algorithms oriented to double loops | |
| JP3734658B2 (ja) | コンパイラ装置およびコンパイラプログラムを記録したコンピュータ読取可能な記録媒体 | |
| JP2001175617A (ja) | コンパイラ並列化方法 | |
| JPH0379741B2 (ja) | ||
| JPH09160784A (ja) | 並列化コンパイル方式 | |
| JP3034582B2 (ja) | コンパイル処理方式 | |
| JP3311775B2 (ja) | ポインタベクトル化方式 | |
| JP2682215B2 (ja) | 並列処理時の手続き呼出し方式 |