米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 松下電器産業株式会社

発明の名称 最適化並列コンパイル装置及び最適化並列コンパイル方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平7−110800
公開日 平成7年(1995)4月25日
出願番号 特願平5−255609
出願日 平成5年(1993)10月13日
代理人 【弁理士】
【氏名又は名称】小鍜治 明 (外2名)
発明者 材木 幸治
要約 目的
プログラムループの並列化を行なう際に、データ転送数が最小となる最適化コンパイル装置及び方法並びにそれを用いたプログラム変換装置を提供する。

構成
入力手段201から入力されたソースプログラムは、中間コード生成手段202で中間コードに変換される。この中間コードからループ検出手段203、参照変数検出手段204によってループ、ループ中で参照される変数が検出される。さらにデータ転送数検出手段207によってループの並列化によって必要となるデータ転送数を並列化対象ループごとに計算する。並列化判定手段209はデータ転送数が最小となる並列化ループを決定し、ループの並列化を行なう。
特許請求の範囲
【請求項1】複数のプログラム文からなり、繰り返し処理を実行するループを含むプログラムを並列計算機用コードに変換する最適化並列コンパイル装置であって、ソースプログラムから中間コードに変換する中間コード生成手段と、前記中間コードから繰り返し処理を実行するループを検出するループ検出手段と、前記ループ検出手段によって検出されたループの繰り返しごとに参照される変数を検出する参照変数検出手段と、前記ループ検出手段によって検出されたループの繰り返しごとに既に左辺で定義された変数群と前記参照変数検出手段から出力される右辺で参照される変数とからデータ転送数を検出するデータ転送数検出手段と、並列化判定手段と、前記並列化判定手段により並列化が可能であると決定された場合、左辺にある変数群を格納する左辺変数格納手段とを備えた最適化並列コンパイル装置。
【請求項2】並列化判定手段は、前記参照変数検出手段によって検出された変数を入力し、ループにまたがったデータ依存関係をあるか否かを判定するデータ参照関係判定手段と、前記データ転送数検出手段から出力されるデータ転送数と前記データ参照関係判定手段から出力されるデータ依存関係の有無情報に基づいて並列化可能か否かを判定する最適判定手段とを有することを特徴とする請求項1記載の最適化並列コンパイル装置。
【請求項3】参照変数検出手段は、左辺変数検出手段と、右辺変数検出手段とを有することを特徴とする請求項1記載の最適化並列コンパイル装置。
【請求項4】複数のプログラム文からなり、繰り返し処理を実行するループを含むプログラムを並列計算機用コードに変換する最適化並列コンパイル方法であって、ソースプログラムから中間コードに変換する中間コード生成ステップと、前記中間コードから繰り返し処理を実行するループを検出するループ検出ステップと、ループの繰り返しごとに参照される変数を検出する左辺の変数検出ステップと、右辺の変数検出ステップと、データ参照関係判定ステップと、前記データ参照関係判定ステップでデータ依存関係が無いと判定された場合、前記ループ検出ステップによって検出されたループの繰り返しごとに既に左辺で定義された変数群と前記右辺の変数検出ステップにより検出された右辺で参照される変数とからデータ転送数を検出するデータ転送数検出ステップと、データ転送数の最小となるループを検出するステップと、並列化ループで左辺の変数を登録するステップと、並列化オブジェクトを生成するステップと、前記データ参照関係判定ステップでデータ依存関係があると判定された場合、並列化できない場合のオブジェクトを生成するステップとを有する最適化並列コンパイル方法。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、プログラムを並列計算機用のプログラムに変換する最適化並列コンパイル装置及び並列化コンパイラの最適化方法に関する。
【0002】
【従来の技術】近年、プログラムを並列に実行する並列計算機システムの開発が進んでいる。並列計算機はプログラムを実行する複数のPE(プロセッシングエレメント)を有し、それぞれのPEにプログラムを与えることで並列処理を実現する。通常、FORTRAN等の高級言語で記述されるソースプログラムは、シリアル処理を前提に記述される。これらのソースプログラムを並列計算機で実行させるためには、ソースプログラムからオブジェクトプログラムを生成するコンパイラに並列実行用のオブジェクトプログラムを生成する機能を持たせる必要がある。
【0003】従来、ソースプログラムから並列計算機用のオブジェクトプログラムを生成するコンパイラとして、ソースプログラムに含まれるdoループのような繰り返し処理から並列性を抽出し、ループの繰り返しを各PEに割り当てて、並列実行させるという方法が採られている。これは各多重ループ単位で並列性の抽出がなされる。以上のことは文献「David A.Padua, et al.:Advanced compiler optimizations for supercomputers, Communications of the ACM,pp1184-1201(1986)」に記載されている。なお、以下の説明では、プログラムにおいて繰り返し実行されうる命令の集合をループ(またはループ処理)と呼び、ループにおける1回分の処理を繰り返しと呼ぶ。
【0004】例えば図3に示したFORTRANプログラムでは、第一の多重ループ301、302と、第二の多重ループ303、304は並列化可能と判定され、並列化された後のプログラムは図8(a),(b)のようになる。図8(a)は第一の多重ループを並列化した様子を示しており、図8(b)は第二の多重ループを並列化した様子を示している。以上のように従来技術では、各多重ループ単位で、ループの並列化を行なっていた。
【0005】
【発明が解決しようとする課題】しかしながら上記の従来技術によれば、各多重ループ単位でそのループの並列化を行なうため、必ずしもデータの転送数が最小となる並列化とはなっていないという問題点があった。つまり、図8(a),(b)のように並列化されたプログラムを図1に示すような並列計算機で実行する場合、図8(a)に示した状態で各PEが並列実行した後で、図8(b)に示すように各PEが並列実行するためには、図8(a)で計算された結果a(i,j),i,j=1〜8が図8(b)に示す計算に必要になる。図9はPE1の実行に必要なデータ転送の様子を示しており、図8(a)で示した状態で各PEが並列に実行した後で、図9に示すようなデータの移動(データ転送)が必要になってくる。
【0006】本発明は上記問題点に鑑み、ループの並列化をする際に、データ転送数が最小になる最適化並列コンパイル装置及び最適化並列コンパイル方法を提供することを目的とする。
【0007】
【課題を解決するための手段】上記課題を解決するため本発明の最適化並列コンパイル装置は、複数のプログラム文からなり、繰り返し処理を実行するループを含むプログラムを並列計算機用コードに変換する最適化並列コンパイル装置であって、ソースプログラムから中間コードに変換する中間コード生成手段と、前記中間コードから繰り返し処理を実行するループを検出するループ検出手段と、前記ループ検出手段によって検出されたループの繰り返しごとに参照される変数を検出する参照変数検出手段と、前記ループ検出手段によって検出されたループの繰り返しごとに既に左辺で定義された変数群と前記参照変数検出手段から出力される右辺で参照される変数とからデータ転送数を検出するデータ転送数検出手段と、並列化判定手段と、前記並列化判定手段により並列化が可能であると決定された場合、左辺にある変数群を格納する左辺変数格納手段とを備えたものである。
【0008】前記並列化判定手段は、前記参照変数検出手段によって検出された変数を入力し、ループにまたがったデータ依存関係をあるか否かを判定するデータ参照関係判定手段と、前記データ転送数検出手段から出力されるデータ転送数と前記データ参照関係判定手段から出力されるデータ依存関係の有無情報に基づいて並列化可能か否かを判定する最適判定手段とを有することが望ましい。
【0009】前記参照変数検出手段は、左辺変数検出手段と、右辺変数検出手段とを有することが望ましい。
【0010】また、本発明の最適化並列コンパイル方法は、複数のプログラム文からなり、繰り返し処理を実行するループを含むプログラムを並列計算機用コードに変換する最適化並列コンパイル方法であって、ソースプログラムから中間コードに変換する中間コード生成ステップと、前記中間コードから繰り返し処理を実行するループを検出するループ検出ステップと、ループの繰り返しごとに参照される変数を検出する左辺の変数検出ステップと右辺の変数検出ステップと、データ参照関係判定ステップと、前記データ参照関係判定ステップでデータ依存関係が無いと判定された場合、前記ループ検出ステップによって検出されたループの繰り返しごとに既に左辺で定義された変数群と前記右辺の変数検出ステップにより検出された右辺で参照される変数とからデータ転送数を検出するデータ転送数検出ステップと、データ転送数の最小となるループを検出するステップと、並列化ループで左辺の変数を登録するステップと、並列化オブジェクトを生成するステップと、前記データ参照関係判定ステップでデータ依存関係があると判定された場合、並列化できない場合のオブジェクトを生成するステップとを有するものである。
【0011】
【作用】本発明は上記した手段により、データ転送数検出手段は、既に並列化されているループの代入文の左辺にある変数とこれから並列化を行なうループにある代入文の右辺の変数の関係からデータ転送数を計算する。並列化判定手段は、データ転送数が最小となる並列化ループを決定して並列化を行なう。
【0012】
【実施例】本発明のプログラム変換装置の一実施例について具体例を挙げて説明する。
【0013】図2は、本発明の一実施例におけるコンパイル装置の機能ブロック図である。201は入力手段で、外部から入力されるソースプログラムを取り込む。202は中間コード生成手段で、高級言語、例えばFORTRANで記述されたソースプログラムを変換して、中間コードで記述されたプログラムを生成する。203はループ検出手段で、ソースプログラムに含まれるループ処理を検出する。
【0014】204はループ処理中で参照される変数を検出する参照変数検出手段であり、参照変数検出手段204はループ検出手段203で検出されたループごとに中間コード生成手段202で生成された中間コードから、式の左辺にある変数を検出する左辺の変数検出手段205と、式の右辺にある変数を検出する右辺の変数検出手段206とを含む。
【0015】207はデータ転送数検出手段で、ループ検出手段203で検出されたループごとに右辺の変数検出手段206からの右辺の変数と左辺の変数格納手段208からの左辺の変数とから並列化によるデータ転送数を計算する。
【0016】209は並列化判定手段で、データ参照関係判定手段210と最適判定手段211とからなり、データ参照関係判定手段210は左辺の変数検出手段205と右辺の変数検出手段206からデータ依存関係があるかどうかを判定し、その結果とデータ転送数検出手段207により検出されたデータ転送数とから並列実行ループを決定する。並列実行ループが決定されると、左辺の変数格納手段208で並列化により左辺にある変数群を記憶する。
【0017】212はオブジェクト生成手段で、並列化判定手段209が並列化可能と判定したとき、並列実行用のオブジェクトプログラムを生成し、並列化不可と判定したとき、通常のオブジェクトプログラムを生成する。213は出力手段で、オブジェクトプログラムを出力する。例えば、プログラムを記憶するディスク装置等である。
【0018】以上のように構成された本発明の実施例におけるコンパイラについて、図4に示す処理フローを用いてその動作を説明する。
【0019】まずステップ401では、コンパイルされる前のソースプログラムは、入力手段201に入力される。このソースプログラムの例としてFORTRANで記述されたプログラムを図3に示す。このプログラムは外側のループ301(変数iに関するdo 10のループ)の中にループ302(変数jに関するdo 10のループ)を含んだ多重ループと、外側のループ303(変数jに関するdo 20のループ)の中にループ304(変数iに関するdo 20のループ)を含んだ多重ループがある。ステップ402では、入力手段201から入力されたソースプログラムは、中間コード生成手段202によって中間コードに変換される。
【0020】ステップ403では、中間コードが生成されるとループ検出手段203は、中間コードに含まれるループ処理を検出する。具体的には、図3のようなFORTRANにおいては、ループ検出手段203は、ソースプログラム中のdo文とcontinue文のペアを判別し、それをループ処理として検出する。ステップ404では、ループ処理の有無を判断し、その判断結果に従って、存在する場合にはステップ405へ進み、存在しない場合にはステップ412に進む。
【0021】次にループ処理が存在する場合、ステップ405,406では、参照変数検出手段204は抽出されたループ処理における変数を検出する。図3におけるdoループ301、302において、参照変数検出手段204は、式の左辺にある配列a(i,j)と、式の右辺にある配列b(i,j)、c(i,j)とを検出する。
【0022】この後ステップ407では、データ参照関係判定手段210によってデータ依存関係があるかどうかを判定する。その結果、データ依存関係がある場合はステップ412に進み、データ依存関係が無い場合はステップ408に進む。
【0023】ステップ408では、データ転送数検出手段207により右辺の変数検出手段206と左辺の変数格納手段208からデータ転送数を計算する。この結果からステップ409では、最適判定手段211でデータ転送数が最小となる並列化ループを決定する。
【0024】次にステップ410では、並列化ループが決定された後、そのループ中で、式の左辺にある変数が登録済みの変数として左辺の変数格納手段208に格納される。続いて、オブジェクト生成手段212により、並列化判定手段209の結果から並列化可能であれば並列化ループのオブジェクトを生成し(ステップ411)、並列化不可能であれば並列化されていないループのオブジェクトを生成する(ステップ412)。最後にステップ413では、出力手段213により、オブジェクトプログラムが出力装置等(例えば、ディスク装置)に出力する。
【0025】ここで、データ転送数を計算して転送数の最小となる並列化ループが決定される様子を、図2、3、5、6、7及び処理フローを示す図4を参照しつつ具体的に説明する。
【0026】まず、図3の第一の多重ループ(外側ループ301、内側ループ302)の外側ループ301が並列化ループであると並列化判定手段209で判定されたとする。このときに、第二の多重ループ(外側ループ303、内側ループ304)の並列化がどのようになされるかを説明する。
【0027】第一の多重ループが並列化されたときに、左辺の変数格納手段208には左辺の変数登録がなされている。例えば、配列aに関しては図5に示すように各PEに割り当てられている。このとき、第二の多重ループについて、ループ内の式305が左辺の変数検出手段205と右辺の変数検出手段206に入力されると、左辺の変数検出手段205は、左辺の変数d(i,j)を検出し(ステップ405)、右辺の変数検出手段206は、右辺の変数a(i,j)、e(i,j)を検出する(ステップ406)。データ参照関係判定手段210は、これらの変数の添字部は揃っているため、外側ループ303、内側ループ304のどちらのループに関しても、ループにまたがったデータ参照関係がないと判定する(ステップ407)。ループにまたがったデータ参照関係がないため、次のステップ408に進むことになる。
【0028】データ転送数検出手段207は既に登録済みの左辺の変数と右辺の変数検出手段206により検出された変数とからデータ転送数を各ループについて並列化した場合のそれぞれについて計算する。ここでは、既に登録済みの左辺の変数として、図5のように各PEに割り当てられているとする。右辺の変数にa(i,j)が存在するため、この変数aに関してデータ転送数を外側ループ303について並列化した場合と、内側ループ304について並列化した場合とでそれぞれ計算する。外側ループ303について並列化したとすると、図6に示すように変数aが各PEに割り当てられることになる。例えば、PE1についてみると、右辺で参照される変数はa(1,1)、a(2,1)、a(3,1)、a(4,1)、a(5,1)、a(6,1)、a(7,1)、a(8,1)であり、図6に示したように、既に左辺の変数として登録されているのをみると、a(2,1)はPE2に、a(3,1)はPE3に、a(4,1)はPE4に、a(5,1)はPE5に、a(6,1)はPE6に、a(7,1)はPE7に、a(8,1)はPE8にそれぞれ割り当てられている。従って、データ転送数はPE1については7となる。同様に、PE2〜PE8について考慮すると、7×8=56となる。
【0029】次に、内側ループ304について並列化したとすると、図7のようになり、全く転送する必要はなくなり、転送数は0と計算される(ステップ408)。
【0030】最適判定手段211は、データ転送数が最小となる並列化ループを決定する(ステップ409)。ここでは、転送数0となる内側ループ304について並列化することとなる。左辺の変数登録手段208は、内側ループ304について並列化した場合の各PEへの割り当てを考慮して、左辺の変数dが左辺の変数格納手段208により記憶される(ステップ410)。
【0031】
【発明の効果】以上のように本発明の最適化並列コンパイル装置及び最適化並列コンパイル方法によれば、データ転送数を考慮した並列化が行なえるため、データ転送によるオーバーヘッドを最小とする並列化が可能となり、その結果、実効性能向上が図れる。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013