JPH04114237A - 並列化コンパイル方式 - Google Patents
並列化コンパイル方式Info
- Publication number
- JPH04114237A JPH04114237A JP2234877A JP23487790A JPH04114237A JP H04114237 A JPH04114237 A JP H04114237A JP 2234877 A JP2234877 A JP 2234877A JP 23487790 A JP23487790 A JP 23487790A JP H04114237 A JPH04114237 A JP H04114237A
- Authority
- JP
- Japan
- Prior art keywords
- loop
- parallel
- variables
- scalar
- executed
- 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
Landscapes
- Multi Processors (AREA)
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
産業上の利用分野
本発明（よ 複数の並列実行可能なプロセッサから成る
並列計算機システムに対して、与えられたソースプログ
ラムからオブジェクトプログラムを生成して供給するコ
ンパイラにおいて、プログラム中のループ構造を検出し
更にループ内に存在するスカラー変数を配列変数に置
き換えることによって並列実行命令を生成する並列化コ
ンパイル方式に関すム 従来の技術 複数の並列実行可能なプロセッサから成る並列計算機シ
ステムの一実施例を第３図に示す。第３図に示した並列
計算機システムは 第一のプロセッサモジュール１、第
二のプロセッサモジュール２、 ・・・ 第へのプロセ
ッサモジュール８の計８個のプロセッサモジュールから
構成される。第一のプロセッサモジュールｌはプロセッ
シングユニット９と共有メモリ１０から成る。第二 第
二・・・ 第へのプロセッサモジュールも同様にプロセ
ッシングユニットと共有メモリからそれぞれ構成されも 共有メモリ１０に対してプロセッシングユニット９によ
り、ローカル・アドレス／デーツノくス４７から書き込
み及び読み出しを行なうことができると同時に 他のプ
ロセッシングユニット１１，１３．１５，１７，１９，
２１．２３によってＬ 共通・アドレス／データバス２
５から書き込み及び読み出しを行なうことができも 同
様に 共有メモリ１２．１４．１６，１８，２０，２２
．２４ ｋ 同一の前記プロセッサモジュール内にあ
るブロモ・ンシングユニット１１，１３，１５，１７，
１９．２１．２３により、ローカル・アドレス／データ
バス４７からそれぞれ書き込み及び読み出しを行なうこ
とができると同時番へ 他のプロセッサモジュール内に
あるプロセッシングユニットによってＬ 共通・アドレ
ス／データバス２５から書き込み及び読み出しを行なう
ことができる。
並列計算機システムに対して、与えられたソースプログ
ラムからオブジェクトプログラムを生成して供給するコ
ンパイラにおいて、プログラム中のループ構造を検出し
更にループ内に存在するスカラー変数を配列変数に置
き換えることによって並列実行命令を生成する並列化コ
ンパイル方式に関すム 従来の技術 複数の並列実行可能なプロセッサから成る並列計算機シ
ステムの一実施例を第３図に示す。第３図に示した並列
計算機システムは 第一のプロセッサモジュール１、第
二のプロセッサモジュール２、 ・・・ 第へのプロセ
ッサモジュール８の計８個のプロセッサモジュールから
構成される。第一のプロセッサモジュールｌはプロセッ
シングユニット９と共有メモリ１０から成る。第二 第
二・・・ 第へのプロセッサモジュールも同様にプロセ
ッシングユニットと共有メモリからそれぞれ構成されも 共有メモリ１０に対してプロセッシングユニット９によ
り、ローカル・アドレス／デーツノくス４７から書き込
み及び読み出しを行なうことができると同時に 他のプ
ロセッシングユニット１１，１３．１５，１７，１９，
２１．２３によってＬ 共通・アドレス／データバス２
５から書き込み及び読み出しを行なうことができも 同
様に 共有メモリ１２．１４．１６，１８，２０，２２
．２４ ｋ 同一の前記プロセッサモジュール内にあ
るブロモ・ンシングユニット１１，１３，１５，１７，
１９．２１．２３により、ローカル・アドレス／データ
バス４７からそれぞれ書き込み及び読み出しを行なうこ
とができると同時番へ 他のプロセッサモジュール内に
あるプロセッシングユニットによってＬ 共通・アドレ
ス／データバス２５から書き込み及び読み出しを行なう
ことができる。
第４図に示された 行列ＡとベクトルＢの積を求めてそ
の結果をベクトルＣに格納するＦＯＲＴＲＡＮプログラ
ムを第３図に示した並列計算機システムで実行される場
合を考えも 第４図に示されたプログラムにおいて、外側のＤＯルー
プ４０はインデックス変数１について並列に実行するこ
とが可能であり、従って内側のループ４１の実行を第３
図の各プロセッシングユニットがそれぞれインデックス
変数Ｉを固定して実行することができも その様子を第
５図の（１）〜（８）に示す。
の結果をベクトルＣに格納するＦＯＲＴＲＡＮプログラ
ムを第３図に示した並列計算機システムで実行される場
合を考えも 第４図に示されたプログラムにおいて、外側のＤＯルー
プ４０はインデックス変数１について並列に実行するこ
とが可能であり、従って内側のループ４１の実行を第３
図の各プロセッシングユニットがそれぞれインデックス
変数Ｉを固定して実行することができも その様子を第
５図の（１）〜（８）に示す。
第５図（１）では第一のプロセッサモジュール１でイン
デックス変数Ｉ＝１と固定して内側のループ４１を実行
することを表しており、同様に第５図（ｉ）では第１の
プロセッサモジュールで前記インデックス変数Ｉ＝ｉと
固定して内側のループ４１を実行することを表している
。但Ｌｉ−２、・・・、８であも 第４図に示したようなＦＯＲＴＲＡＮプログラムを第３
図に示したような並列計算機システムで実行させる場合
、第５図で示したようζへ 各プロセッサモジュールで
実行できるようなコードを生成する必要があも 従来
第４図に示したようへ内側のＤｏループ４１の中でスカ
ラー変数Ｘが回帰的に現れている場合に１友 並列実行
させないコンパイル方式がとられていも 発明が解決しようとする課題 しかしながら上記のような方式で（表 実際には並列実
行させることが可能なプログラムで耘 並列実行命令を
生成できない場合が生Ｕ コンパイラの能力が低下すム 本発明はかかる点に鑑へ ＤＯループ中にスカラー変数
が存在する場合でも並列計算機システムで実行可能なオ
ブジェクトプログラムを生成する並列化コンパイル方式
を提供することを目的とすム 課題を解決するための手段 本発明（よ 複数の並列実行可能なプロセッサから成る
並列計算機システムに対して、与えられたソースプログ
ラムからオブジェクトプログラムを生成して供給するコ
ンパイラにおいて、前記ソースコードを字句に分解する
字句解析部と、前記字句解析部で字句解析された結果か
ら構文を認識し中間コードを生成する構文解析部と、前
記中間コードからループ構造を検出して並列実行可能部
分の抽出を行なう並列性抽出部と、前記並列性抽出部の
指示によって起動されるコード生成部とを備え 前記並
列性抽出部（表 ループの構造を検出すると共に前記ル
ープ内に存在するスカラー変数を検出し データ参照関
係を解析して前記ループが並列実行可能であれば 前記
スカラー変数を配列変数に置き換えることによって前記
ループに関して並列実行命令を生成する機能を有する並
列化コンパイル方式である。
デックス変数Ｉ＝１と固定して内側のループ４１を実行
することを表しており、同様に第５図（ｉ）では第１の
プロセッサモジュールで前記インデックス変数Ｉ＝ｉと
固定して内側のループ４１を実行することを表している
。但Ｌｉ−２、・・・、８であも 第４図に示したようなＦＯＲＴＲＡＮプログラムを第３
図に示したような並列計算機システムで実行させる場合
、第５図で示したようζへ 各プロセッサモジュールで
実行できるようなコードを生成する必要があも 従来
第４図に示したようへ内側のＤｏループ４１の中でスカ
ラー変数Ｘが回帰的に現れている場合に１友 並列実行
させないコンパイル方式がとられていも 発明が解決しようとする課題 しかしながら上記のような方式で（表 実際には並列実
行させることが可能なプログラムで耘 並列実行命令を
生成できない場合が生Ｕ コンパイラの能力が低下すム 本発明はかかる点に鑑へ ＤＯループ中にスカラー変数
が存在する場合でも並列計算機システムで実行可能なオ
ブジェクトプログラムを生成する並列化コンパイル方式
を提供することを目的とすム 課題を解決するための手段 本発明（よ 複数の並列実行可能なプロセッサから成る
並列計算機システムに対して、与えられたソースプログ
ラムからオブジェクトプログラムを生成して供給するコ
ンパイラにおいて、前記ソースコードを字句に分解する
字句解析部と、前記字句解析部で字句解析された結果か
ら構文を認識し中間コードを生成する構文解析部と、前
記中間コードからループ構造を検出して並列実行可能部
分の抽出を行なう並列性抽出部と、前記並列性抽出部の
指示によって起動されるコード生成部とを備え 前記並
列性抽出部（表 ループの構造を検出すると共に前記ル
ープ内に存在するスカラー変数を検出し データ参照関
係を解析して前記ループが並列実行可能であれば 前記
スカラー変数を配列変数に置き換えることによって前記
ループに関して並列実行命令を生成する機能を有する並
列化コンパイル方式である。
作用
本発明は前記した方式により、従来のプログラミング言
語で記述されたプログラムからデータ参照関係を解析し
そのデータ参照関係を崩さないように並列実行命令を
生成すも そのＵ Ｄｏ小ループ中スカラー変数が存
在していて耘 そのスカラー変数を配列変数に置き換え
ることで、並列実行命令を生成することができも 実施例 第１図は本発明の一実施例におけるコンパイラの構成図
である。第１図において、 ２６はソースプログラム
２７はソースコードを字句に分解する字句解析部２８と
、字句解析部２８で字句解析された結果から構文を認識
し中間コードを生成する構文解析部２９と、前記中間コ
ードからループ構造を検出して並列実行可能部分の抽出
を行なう並列性抽出部３０と、並列性抽出部３０の指示
によって起動されるコード生成部３１とを備えたコンパ
イラ、 ３２はオブジェクトプログラムをそれぞれ表し
ている。
語で記述されたプログラムからデータ参照関係を解析し
そのデータ参照関係を崩さないように並列実行命令を
生成すも そのＵ Ｄｏ小ループ中スカラー変数が存
在していて耘 そのスカラー変数を配列変数に置き換え
ることで、並列実行命令を生成することができも 実施例 第１図は本発明の一実施例におけるコンパイラの構成図
である。第１図において、 ２６はソースプログラム
２７はソースコードを字句に分解する字句解析部２８と
、字句解析部２８で字句解析された結果から構文を認識
し中間コードを生成する構文解析部２９と、前記中間コ
ードからループ構造を検出して並列実行可能部分の抽出
を行なう並列性抽出部３０と、並列性抽出部３０の指示
によって起動されるコード生成部３１とを備えたコンパ
イラ、 ３２はオブジェクトプログラムをそれぞれ表し
ている。
第１図において、コンパイラ２７はソースプログラム２
６をオブジェクトプログラム３２に変換する。変換処理
は第１図に示した字句解析部２８、構文解析部２９、並
列性抽出部３０、コード生成部３１で行われる。並列性
抽出部３０でプログラム中のループ構造が認識され並列
性が抽出されも第２図は並列性抽出部３０の詳細な処理
手順を示す流れ図であム 第２図において、まずプログ
ラム中のループ構造の検出手続き３３を行なＬ＼データ
参照関係を調べる手続き３４を行なって、並列化可能か
どうかの判断３５を行なって、並列化可能な場合、ルー
プ内にスカラー変数が存在するかどうかの判断３６を行
なって、存在する場合にはスカラー変数を配列変数に置
き換える手続き３７を行なう。その後に並列コードを生
成する手続き３９を行なう。
６をオブジェクトプログラム３２に変換する。変換処理
は第１図に示した字句解析部２８、構文解析部２９、並
列性抽出部３０、コード生成部３１で行われる。並列性
抽出部３０でプログラム中のループ構造が認識され並列
性が抽出されも第２図は並列性抽出部３０の詳細な処理
手順を示す流れ図であム 第２図において、まずプログ
ラム中のループ構造の検出手続き３３を行なＬ＼データ
参照関係を調べる手続き３４を行なって、並列化可能か
どうかの判断３５を行なって、並列化可能な場合、ルー
プ内にスカラー変数が存在するかどうかの判断３６を行
なって、存在する場合にはスカラー変数を配列変数に置
き換える手続き３７を行なう。その後に並列コードを生
成する手続き３９を行なう。
ループ内にスカラー変数が存在するかどうかの判断３６
の結果 存在しない場合に（よ 並列コードの生成３９
を行なう。
の結果 存在しない場合に（よ 並列コードの生成３９
を行なう。
並列化可能かどうかの判断３５を行なった結果並列化不
可能な場合に（よ 並列化できない場合のコード生成手
続き３８を実行すも 第２図中のデータ参照関係を調べる手続き３４について
、第４図のプログラムを例に用いて説明すも 例えば
外側のＤＯ小ループ０についてみると、第５図に示した
よう番へ インデックス変数■について独立に実行で
きることがわかる。これはスカラー変数Ｘの値が外側の
ＤＯ小ループ０内で最初に左辺で定義されている４２か
らであり、スカラー変数Ｘの値が外側のＤＯ小ループ０
にまたがって、参照されていないからである。そこで第
４図に示したプログラム戟 第５図で示されるように並
列に実行されるために（表 スカラー変数Ｘがこの場合
に（よ 八つの要素から成る配列変数Ｘ （Ｉ）で置き
換えられなければならなし〜 そこで、ループ内にスカ
ラー変数が存在するかどうかの判断３６の結果 存在す
る場合には そのスカラー変数Ｘを配列変数Ｘ（１）に
置き換える手続き３７を行なうことにより、第６図に示
したようなプログラムとなム この結果 外側のＤｏ小
ループ３について並列実行可能な命令が生成できも発明
の詳細 な説明したよう！ミ 本発明によれは ＤＯ小ループ中
スカラー変数が存在していてｋ そのスカラー変数を配
列変数に置き換えることで、並列実行命令を生成するこ
とができ、コンパイラの処理能力の向上が図れ その実
用的効果は犬き（℃
可能な場合に（よ 並列化できない場合のコード生成手
続き３８を実行すも 第２図中のデータ参照関係を調べる手続き３４について
、第４図のプログラムを例に用いて説明すも 例えば
外側のＤＯ小ループ０についてみると、第５図に示した
よう番へ インデックス変数■について独立に実行で
きることがわかる。これはスカラー変数Ｘの値が外側の
ＤＯ小ループ０内で最初に左辺で定義されている４２か
らであり、スカラー変数Ｘの値が外側のＤＯ小ループ０
にまたがって、参照されていないからである。そこで第
４図に示したプログラム戟 第５図で示されるように並
列に実行されるために（表 スカラー変数Ｘがこの場合
に（よ 八つの要素から成る配列変数Ｘ （Ｉ）で置き
換えられなければならなし〜 そこで、ループ内にスカ
ラー変数が存在するかどうかの判断３６の結果 存在す
る場合には そのスカラー変数Ｘを配列変数Ｘ（１）に
置き換える手続き３７を行なうことにより、第６図に示
したようなプログラムとなム この結果 外側のＤｏ小
ループ３について並列実行可能な命令が生成できも発明
の詳細 な説明したよう！ミ 本発明によれは ＤＯ小ループ中
スカラー変数が存在していてｋ そのスカラー変数を配
列変数に置き換えることで、並列実行命令を生成するこ
とができ、コンパイラの処理能力の向上が図れ その実
用的効果は犬き（℃
第１図は本発明における実施例のコンパイラの構成図
第２図はコンパイラの並列性抽出部の詳細な処理手順を
示した流れは 第３図は複数の並列実行可能なプロセッ
サから成る並列計算機システムの構成図 第４図はＦＯ
ＲＴＲＡＮプログラムの一例を示した医 第５図は第４
図のプログラムが第３図の並列計算機システムで実行さ
れる様子を示した医 第６図は第４図のプログラム中の
スカラー変数を配列変数で置き換えられたプログラムを
示した図である。 ２６・・・ソースプロゲラＡ ２７・・・コンパイラ
、２８・・・字句解析部 ２９・・・構文解析部 ３０
・・・並列性抽出部 ３１・・・コード生成阻 ３２・
・・オブジェクトプログラム ３３・・・ループの判断
手続き、３４・・・データ参照関係を調べる手続き、
３５・・・並列化可能かどうかを判断する手続き、 ３
６・・・ループ内にスカラー変数が存在するかどうかを
判断する手続き、３７・・・スカラー変数を配列変数に
置き換える手続き、 ３８・・・並列化できない場合の
コード生成手続き、 ９・・・並列化できる場合のコー ド 吊 図 生成手続き。
第２図はコンパイラの並列性抽出部の詳細な処理手順を
示した流れは 第３図は複数の並列実行可能なプロセッ
サから成る並列計算機システムの構成図 第４図はＦＯ
ＲＴＲＡＮプログラムの一例を示した医 第５図は第４
図のプログラムが第３図の並列計算機システムで実行さ
れる様子を示した医 第６図は第４図のプログラム中の
スカラー変数を配列変数で置き換えられたプログラムを
示した図である。 ２６・・・ソースプロゲラＡ ２７・・・コンパイラ
、２８・・・字句解析部 ２９・・・構文解析部 ３０
・・・並列性抽出部 ３１・・・コード生成阻 ３２・
・・オブジェクトプログラム ３３・・・ループの判断
手続き、３４・・・データ参照関係を調べる手続き、
３５・・・並列化可能かどうかを判断する手続き、 ３
６・・・ループ内にスカラー変数が存在するかどうかを
判断する手続き、３７・・・スカラー変数を配列変数に
置き換える手続き、 ３８・・・並列化できない場合の
コード生成手続き、 ９・・・並列化できる場合のコー ド 吊 図 生成手続き。
Claims (1)
- 【特許請求の範囲】 複数の並列実行可能なプロセッサから成る並列計算機シ
ステムに対して、与えられたソースプログラムからオブ
ジェクトプログラムを生成して供給するコンパイラにお
いて、前記ソースコードを字句に分解する字句解析部と
、前記字句解析部で字句解析された結果から構文を認識
し中間コードを生成する構文解析部と、前記中間コード
からループ構造を検出して並列実行可能部分の抽出を行
なう並列性抽出部と、前記並列性抽出部の指示によって
起動されるコード生成部とを備え、 前記並列性抽出部は、ループの構造を検出すると共に前
記ループ内に存在するスカラー変数を検出し、データ参
照関係を解析して前記ループが並列実行可能であれば、
前記スカラー変数を配列変数に置き換えることによって
前記ループに関して並列実行命令を生成する機能を有す
ることを特徴とする並列化コンパイル方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2234877A JPH04114237A (ja) | 1990-09-04 | 1990-09-04 | 並列化コンパイル方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2234877A JPH04114237A (ja) | 1990-09-04 | 1990-09-04 | 並列化コンパイル方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04114237A true JPH04114237A (ja) | 1992-04-15 |
Family
ID=16977728
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2234877A Pending JPH04114237A (ja) | 1990-09-04 | 1990-09-04 | 並列化コンパイル方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH04114237A (ja) |
-
1990
- 1990-09-04 JP JP2234877A patent/JPH04114237A/ja active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH04211830A (ja) | 並列化コンパイル方式 | |
| US5822588A (en) | System and method for checking the use of synchronization locks in a multi-threaded target program | |
| US5852734A (en) | Method and compiler for parallel execution of a program | |
| CN104536898B (zh) | C程序并行区域的检测方法 | |
| Ball | Predicting the effects of optimization on a procedure body | |
| Qiu et al. | Scalable fsm parallelization via path fusion and higher-order speculation | |
| Rul et al. | Function level parallelism driven by data dependencies | |
| US20030126589A1 (en) | Providing parallel computing reduction operations | |
| Adamski et al. | Polyhedral source-to-source compiler | |
| Pol et al. | Trimedia CPU64 application development environment | |
| Chandraiah et al. | Designer-controlled generation of parallel and flexible heterogeneous MPSoC specification | |
| Shei et al. | MATLAB parallelization through scalarization | |
| Barve et al. | Parallelism in C++ programs targeting objects | |
| Demirović et al. | Source Code Analysis for Performance Enhancement of the Mean Shift Algorithm | |
| Cappello et al. | Performance of the NAS benchmarks on a cluster of SMP PCs using a parallelization of the MPI programs with OpenMP | |
| Eassa et al. | ACC_TEST: Hybrid testing approach for OpenACC-based programs | |
| Dai | Code parallelization for the LGDG large-grain dataflow computation | |
| US5335351A (en) | Method for optimizing source program including variables necessary for synchronous/exclusive control | |
| JPH04184540A (ja) | 並列化コンパイル方式 | |
| Bakhtin | Automation of Debugging Parallel Programs in the DVM System | |
| JPH03257579A (ja) | コンパイラの並列化方式 | |
| Layeghi | Cross-Paradigm Compilation across Programming Models: from Imperative to Asynchronous Graph | |
| Moses | How should compilers represent fork-join parallelism? | |
| Rus et al. | Implementation of Sensitivity Analysis for Automatic Parallelization | |
| Li et al. | Run-time data-flow analysis |