JPH04184540A - 並列化コンパイル方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は６、複数の並列実行可能なブロモ・ｙすから成
る並列計算機システムに対して、与えられたソースプロ
グラムからオブジェクトプログラムを生成して供給する
コンパイラにおいて、プログラム中のループ構造を検出
し、並列実行命令を生成する並列化コンパイル方式に関
するものである。

従来の技術 第３図に示された、行列ａとベクトルｂの積を求めてそ
の結果をベクトルＣに格納するＦＯＲＴＲＡＮプログラ
ムか、並列実行される場合を考える。

第３図に示されたプログラムにおいて、外側のｄＯ小ル
ープ００はインデックス変数ｉについて並列に実行する
ことが可能であり、したがって、ｄＯ小ループ００の内
側にある代入文３０１、ｄｏ／レープ３０２に現れるイ
ンデックス変数ｉを固定して、並列に実行することが可
能である。８台のプロセッサを用いて、第３図に示され
たプログラムを並列に実行する様子を第４図に示す。

第４図（１）では前記インテ・ンクスｉ＝１と固定して
、第一のプロセッサで代入文３０１、ｄｏ／レープ３０
２を実行することを表しており、同様に第４図（ｋ）で
は第にのプロセッサで前記インテ・ｙクス変数ｉ＝にと
固定して代入文３０１、ｄｏループ３０２を実行するこ
とを表している。ただし、ｋ−２、・・・、８である。

第３図に示されたようなＦＯＲＴＲＡＮプログラムを並
列実行させるには、たとえば８台のプロセッサを用いて
、第４図に示したように、ｄｏルーズのインデックス変
数を各プロセフすで固定して実行させることになる。

次に、第５図に示されたような、ｄＯループ５００内に
スカラー変数Ｘ、分岐命令５０３が含まれるようなＦＯ
ＲＴＲＡＮプログラムを考える。従来、第５図に示した
ように、内側のｄＯルーズ５０２内に、代入文５０４の
ようにスカラー変数Ｘが回帰的に現れていたり、分岐命
令５０３があると、並列実行させないコンパイル方式が
とられている。

発明が解決しようとする課題 しかしながら上記のような方式では、実際には並列実行
させることが可能なプログラムでも、並列実行命令を生
成できない場合が生じ、コンパイラの能力が低下する。

本発明はかかる問題を解決するもので、ｄｏループ内に
スカラー変数または分岐命令が存在する場合でも並列計
算機システムで実行可能なオブジェクトプログラムを生
成する並列化コンパイル方式を提供することを目的とす
るものである。

課題を解決するための手段 上記課題を解決するために、本発明の並列化コンパイル
方式は、複数の並列実行可能な１０七ツサから成る並列
計算機システムに対して、４えられたソースプログラム
からオブジェクトプログラムを生成して供給するコンパ
イラにおいて、前記ソースコードを字句に分解する字句
解析部と、前記字句解析部で字句解析された結果から構
文を認識し中間コードを生成する構文解析部と、前記中
間コードからループ構造を検出して並列実行可能部分の
抽出を行う並列性抽出部と、前記並列性抽出部の指示に
よって起動されるコード生成部とを備え、前記並列性抽
出部は、ループの構造を検出し、前記ループが多重ルー
プである場合に、各ループに関してデータ参照関係を解
析して、ループ間でデータ参照関係の生じないループに
関して並列実行命令を生成する機能を有するものである
。

そして本発明の中間コードは、ソースプログラム中でル
ープを構成する構文に相当する部分を他ノードとのリン
ク情報をもつ親ノードとし、前記ループ内の実行文に相
当する部分を他ノードとのリンク情報をもつ子ノードと
するリスト補遺として表現され、前記子ノードに相当す
る実行文が分岐命令である場合には、その分岐先の実行
文に相当するノードとリンクするように表現されるもの
である。

また本発明の並列性抽出部は、中間コードの第一ノード
から、その子ノードに相当する第二ノードへのリンクを
辿り、さらに、そのリンクを順次辿っていき、２つ以上
の子ノードをもつ第ｎノードまできたとき、前記第一ノ
ードから前記第ｎノードに相当するループに関して並列
実行命令を生成する機能を有するものである。

また、本発明の並列性検出部は、スカラー変数がループ
内に現れた場合に、前記スカラー変数が最初に代入文の
左辺に現れている場合に、並列実行命令を生成する機能
を有するものである。

実に、本発明の並列性抽出部は、ループ内に分岐命令が
現れた場合、前記分岐命令の分岐先にリンクされたノー
ドの親ノードに相当するループから外側のループに関し
て並列実行命令を生成する機能を有するものである。

作用 本発明は前記した方式により、従来のプログラミング言
語で記述されたプログラムからデータ参照関係を解析し
、そのデータ参照関係を崩さな１）ように並列実行命令
を生成する。その際、ｄＯループ中にスカラー変数およ
び分岐命令が存在していても、スカラー変数のデータ依
存関係および分岐命令の分岐先を解析することで、並列
実行命令を生成することができる。

実施例 以下本発明の一実施例を図面に基づいて説明する。

第′１図は本発明の一実施例におけるコンノ（イラの構
成図である。第１図において、１００はソースプログラ
ム、１０１はソースコードを字句に分解する字句解析部
１０２と、字句解析部１０２で字句解析された結果から
構文を認識し中間コードを生成する構文解析部１０３と
、前記中間コードからループ構造を検出して並列実行可
能部分の抽出を行う並列性抽出部１０４と、並列性抽出
部１０４の指示によって起動されるコード生成部１０５
とを備えたコンパイラ、１０６はオブジェクトプログラ
ムをそれぞれ表している。

第１図において、コンパイラ１０１はソースプログラム
１００をオブジェクトプログラム１０６に変換するが、
この変換処理は第１図に示した字句解析部１０２、構文
解析部１０３、並列性抽出部１０４、コード生成部１０
５で行われる。そして、並列性抽出部１０４でプログラ
ム中のループ構造が認識され並列実行可能部分の抽出が
行われる。

第２図は並列性抽出部１０４の詳細な処理手順を示す流
れ図である。第２図において、まずプログラム中のルー
プ構造の検出手続き２００を行い、次にループの構造を
調べる手続き２０１を行って、並列化可能なループが存
在するかどうかの判断２０２を行い、並列化可能なルー
プが存在する場合、各ループに関してデータ参照関係を
調べる手続き２０３を行って、並列化可能かどうかの判
断２０５を行い、並列化可能な場合には、並列化できる
場合のコード生成手続き２０６を行う、並列化可能かど
うかの判断２０５の結果、並列化不可能な場合には、並
列化できない場合のコード生成手続き２０４を行う。ま
た、並列化可能ループが存在するかどうかの判断２０２
を行った結果、並列化可能ループが存在しない場合には
、並列化できない場合のコード生成手続き２０４を行う
。

第２図中のループ構造を調べる手続き２０１について、
第５図のプログラムを例に用いて説明する。

第５図に示されたプログラムが、コン／＜イラ１０１の
構文解析部１０３により、第６図に示されるような中間
コードに変換される場合を考える。

第６図において、６００，６０２はそれぞれｄＯループ
を構成するための第一の６０文、第二の６０文を表して
おり、第５図の外側のｄＯループ５００中の実行文は、
それぞれ子ノードである第一の代入文６０１、第二の６
０文６０２、第二の代入文６０３、第一のｃａｎｔ　１
ｎｕｅ文６０４で表され、それぞれ第一のリンク６０８
によって親ノードである第一の６０文６００とつながっ
ている。同様に、第５図の内側のｄＯルーグ５０２中の
実行文は、それぞれ子ノードである第三の代入文６０５
、条件分岐文６０６、第二のｃｏｎｔｉｎｕｅ文６０７
で表され、それぞれ第二のリンク６０９によって第二の
ｄｏ文６０２とつながっている。さらに、条件分岐文６
０６は、分岐先の実行文に相当するノードである第二の
代入文６０３にリンク６１０でつながっている。

第６図で、第一の６０文６００から第１のリンク６０８
を辿っていくと、複数の実行文６０１．６０２．６０３
があり、また、条件分岐文６０６の分岐先である第二の
代入文６０３は、第一の６０文６００に第１のリンク６
０８でつながっている。したがって、この中間コードか
ら、ループの構造を調べる手続き２０１は、外側のルー
プ５００に関して並列化可能であると判断する０次に、
各ループに関してデータ参照関係を調べる手続き２０３
は、外側のｄＯループ５００中の実行文について、イン
デックスｉに関して、並列実行できるかを調べる。内側
のｄｏルーグ５０２では、第三の代入文５０４でスカラ
ー変数Ｘが回帰的に出現しているが、このスカラー変数
Ｘは第一の代入文５０１で左辺にあるなめに、前記イン
デックス変数量について、データの参照関係が生じない
ので、並列化可能であると判断できる。

したがって、８台のプロセッサで並列実行する場合、第
７図に示すように、外Ｑｌｌ　ｄ　ｏループ５００を、
前記インデックス変数ｉを各プロセッサで固定すること
で、並列に実行できる。

第７図（１）では前記インデックス変数ｉ＝１と固定し
て、第一のプロセッサで第一の代入文５０１、内側のｄ
Ｏルー１５０２、第二の代入文５０５を実行することを
表しており、残りのプロセッサでも同様に前記インデッ
クス変数ｉの値を固定して、第一の代入文５０１、内側
のｄＯルー１５０２、第二の代入文５０５を実行するこ
とを表している。このように、外側のｄｏループ５００
について並列実行可能な命令が生成できる。

発明の詳細 な説明したように、本発明によれば、ｄｏループ中にス
カラー変数および分岐命令が存在していても、スカラー
変数のデータ依存関係および分岐命令の分岐先を解析す
ることで、並列実行命令を生成することができ、コンパ
イラの処理能力の向上が図れ、その実用的効果は大きい
。

【図面の簡単な説明】

第１図は本発明の一実施例のコンパイラの構成図、第２
図はコンパイラの並列性抽出部の詳細な処理手順を示し
た流れ図、第３図はＦＯＲＴＲＡＮプログラムの一例図
、第４図は第３図のプログラムが並列計算機システムで
実行される様子を示した図、第５図はＦＯＲＴＲＡＮプ
ログラムの他の一例図、第６図は第５図のプログラムが
構文解析によって作られた中間コードを示す図、第７図
は第５図のプログラムが並列計算機システムで実行され
る様子を示した図である。 １００・・・ソースプログラム、１０１・・・コンパイ
ラ、１０２・・・字句解析部、１０３・・・構文解析部
、１０４・・・並列性抽出部、１０５・・・コード生成
部、１０６・・・オブジェクトプログラム、２００・・
・ループの検出手続き、２０１・・・ループ構造を調べ
る手続き、２０２・・・並列化可能ループが存在するか
どうかを判断する手続き、２０３・・・各ルーズに関し
てデータ参照関係を調べる手続き、２０４・・・並列化
できない場合のコード生成手続き、２０５・・・並列化
可能かどうかを判断する手枕き、２０６・・・並列化で
きる場合のコード生成手続き。 代理人　　　森　　本　　義　　弘 第１図 第　２　図 −：ｊ３図 麹マ　Ｎ　ＱＮ　Ｎ

Claims (1)

1. 【特許請求の範囲】 １、複数の並列実行可能なプロセッサから成る並列計算
   機システムに対して、与えられたソースプログラムから
   オブジェクトプログラムを生成して供給するコンパイラ
   において、前記ソースコードを字句に分解する字句解析
   部と、前記字句解析部で字句解析された結果から構文を
   認識し中間コードを生成する構文解析部と、前記中間コ
   ードからループ構造を検出して並列実行可能部分の抽出
   を行う並列性抽出部と、前記並列性抽出部の指示によつ
   て起動されるコード生成部とを備え、前記並列性抽出部
   は、ループの構造を検出し、前記ループが多重ループで
   ある場合に、各ループに関してデータ参照関係を解析し
   て、ループ間でデータ参照関係の生じないループに関し
   て並列実行命令を生成する機能を有することを特徴とす
   る並列化コンパイル方式。 ２、中間コードは、ソースプログラム中でループを構成
   する構文に相当する部分を他ノードとのリンク情報をも
   つ親ノードとし、前記ループ内の実行文に相当する部分
   を他ノードとのリンク情報をもつ子ノードとするリスト
   構造として表現され、前記子ノードに相当する実行文が
   分岐命令である場合には、その分岐先の実行文に相当す
   るノードとリンクするように表現されることを特徴とす
   る請求項１記載の並列化コンパイル方式。 ３、並列性抽出部は、中間コードの第一ノードから、そ
   の子ノードに相当する第二ノードへのリンクを辿り、さ
   らに、そのリンクを順次辿っていき、２つ以上の子ノー
   ドをもつ第ｎノードまできたとき、前記第一ノードから
   前記第ｎノードに相当するループに関して並列実行命令
   を生成する機能を有することを特徴とする請求項１記載
   の並列化コンパイル方式。 ４、並列性抽出部は、スカラー変数がループ内に現れた
   場合に、前記スカラー変数が最初に代入文の左辺に現れ
   ている場合に、並列実行命令を生成する機能を有するこ
   とを特徴とする請求項１記載の並列化コンパイル方式。 ５、並列性抽出部は、ループ内に分岐命令が現れた場合
   、前記分岐命令の分岐先にリンクされたノードの親ノー
   ドに相当するループから外側のループに関して並列実行
   命令を生成する機能を有することを特徴とする特許請求
   の範囲第１項記載の並列化コンパイル方式。