JP2001167060A

JP2001167060A - タスク並列化方法

Info

Publication number: JP2001167060A
Application number: JP34709099A
Authority: JP
Inventors: Yuichiro Aoki; 雄一郎青木; Makoto Sato; 真琴佐藤
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1999-12-07
Filing date: 1999-12-07
Publication date: 2001-06-22
Also published as: US20010003187A1

Abstract

(57)【要約】【課題】従来は、実行可能なタスク数が利用可能なプ
ロセッサ数より少ない場合に発生するアイドルプロセッ
サを有効利用できない。【解決手段】タスク内で参照される可能性のあるデー
タまたはタスクに含まれる命令コードをコンパイル時に
検出し、該データまたは命令コードを、タスクが割り当
てられるプロセッサに近い記憶装置へ転送する命令から
なる情報転送タスクを生成し、タスクを実行していない
アイドルプロセッサに次に割り当てる次実行タスクとし
て各プロセッサで実行中のタスクで最も早く終了するタ
スクを求め、この次実行タスクに対する情報転送タスク
がアイドルプロセッサで実行されるよう割り当てる命令
からなる情報転送タスクスケジュール処理を、並列コン
パイラが生成するタスクスケジュール処理に追加する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ソースプログラム
をタスクに分割して、並列計算機で実行可能なプログラ
ムまたはオブジェクトコードに翻訳・変換する並列化コ
ンパイラのタスク並列化技術に関わり、特に、高速実行
可能なプログラムまたはオブジェクトコードを出力する
のに好適なタスク並列化方法に関するものである。

【０００２】

【従来の技術】従来、並列化コンパイラにおけるタスク
の並列化は、例えば、合田憲人、岩崎清、岡本雅巳、笠
原博徳、成田誠之助著「共有メモリ型マルチプロセッ
サシステム上でのＦｏｒｔｒａｎ粗粒度タスク並列処理
の性能評価」情報処理学会論文誌、１９６６年３月号、
Vol.３７、No.３、４１８−４２９ページ(以降、「文献
１」と記載)で述べられているように、次の３つのステ
ップから構成される。

【０００３】（１）プログラムをタスクと呼ばれる小部
分に分割する。（２）タスク間の制御の流れ、変数の参照順序関係か
ら、各タスクの「実行可能条件」を導出する。（３）タスクおよびタスク先頭に挿入した実行可能条件
を含む「タスクスケジュール処理」から構成されるプロ
グラムまたはオブジェクトコードを生成する。

【０００４】ここで、「実行可能条件」とは、タスク間
の実行順序関係を表した条件であり、この条件を満たし
たタスクは実行開始してよいことを意味する。また、
「タスクスケジュール処理」とは、タスクを実行してい
ないアイドルプロセッサの有無とタスクの実行可能条件
の成立を監視し、実行可能条件を満たしたタスクをアイ
ドルプロセッサに割り当てて実行させる処理である。

【０００５】例えば、次のようなプログラムを考える。
尚、左端の番号はプログラムの行番号である。 1:#define N 1000 2:int a[N],b[N],c[N],i,j,k; 3:main(){ 4: for(i=0;i<N;i++) { /* タスク１*/ 5: a[i] = i * 2; 6: } 7: for(j=1;j<N;j++) { /* タスク２*/ 8: if(j==1) {b[0] = 0;} 9: b[j] = a[j] + b[j-1]; 10: if(j==N-1) {printf("b[N-1] = %d\n",b[j]);} 11: } 12: for(k=1;k<N;k++) { /* タスク３*/ 13: if(k==1) {c[0] = 0;} 14: c[k] = a[k] + c[k-1]; 15: } 16:}

【０００６】このプログラム例には３つのループがあ
る。これを１つのループを１つのタスクとしてタスク並
列化すると、プログラムの４〜６行目がタスク１、７〜
１１行目がタスク２、１２〜１５行目がタスク３にな
る。タスク間の制御の流れを考慮してタスクにまたがっ
て参照される変数を調べると、タスク１で定義された配
列ａがタスク２およびタスク３で使用されているため、
タスク２およびタスク３はタスク１の終了後でないと実
行してはいけないことがわかる。ここで、定義とは変数
に値を代入すること、使用とは変数の値を用いることで
ある。

【０００７】以上より、各タスクの実行可能条件は、タ
スク１に関しては無条件(いつでも実行開始可能)、タス
ク２とタスク３に関してはタスク１の終了となる。この
タスク並列化プログラムを、プロセッサ２台を用いて並
列実行した場合の各タスクの実行の様子を示したのが図
１５のタスク実行グラフである。

【０００８】図１５は、タスク実行状況を表わすタスク
実行グラフの一例を示す説明図である。図１５のタスク
実行グラフ１５００１において、横軸はプログラム実行
開始からの時間、縦軸はプロセッサ番号、グラフ中の四
角が各タスクが実行された区間である。

【０００９】実行可能条件と図１５から分かるように、
タスク１と同時に実行できるタスクが存在しないため、
プロセッサ（０）がタスク１を実行している間はプロセ
ッサ（１）がアイドルプロセッサとなる。

【００１０】

【発明が解決しようとする課題】解決しようとする問題
点は、従来の技術では、プログラム実行中のある時点
で、実行可能なタスク数が利用可能なプロセッサ数より
少ない場合に発生するアイドルプロセッサを有効利用す
ることができない点である。

【００１１】本発明の目的は、これら従来技術の課題を
解決し、アイドルプロセッサを有効利用して、実行時間
が短縮されたプログラムまたはオブジェクトコードの出
力を可能とするタスク並列化方法を提供することであ
る。

【００１２】

【課題を解決するための手段】上記目的を達成するた
め、本発明のタスク並列化方法は、ソースプログラム
を、並列計算機で実行可能な複数のタスクと、該タスク
をプロセッサへ割り当てるタスクスケジュール処理とを
有するプログラムもしくはオブジェクトコードに変換す
る並列化コンパイラにおけるタスクの並列化方法であっ
て、（ａ）所定の条件を満たしたタスクに関して、この
タスク内で参照される可能性のあるデータや、そのタス
クに含まれる命令コードをコンパイル時に検出し、
（ｂ）これらのデータや命令コードを、もし、それらが
格納されている記憶装置が、タスクスケジュール処理に
よってこのタスクが割り当てられるプロセッサから見
て、最も近い記憶装置なら何もせず、そうでなければ、
より近い別の記憶装置へ転送する命令からなる情報転送
タスクを生成し、（ｃ）タスクを実行していないアイド
ルプロセッサがないか監視し、アイドルプロセッサを発
見したら、このアイドルプロセッサ以外のプロセッサで
実行されているタスクの終了時刻を予測し、予測される
終了時刻が最も早いタスクから、アイドルプロセッサに
次に割り当てられるタスクである次実行タスクを求め、
この次実行タスクに対する情報転送タスクがアイドルプ
ロセッサで実行されるよう割り当てる命令からなる情報
転送タスクスケジュール処理を、タスクスケジュール処
理に追加する処理を行なうことを特徴とする。

【００１３】

【発明の実施の形態】以下、本発明の実施の形態を、図
面により詳細に説明する。図１は、本発明のタスク並列
化方法に係る処理動作例を示すフローチャートであり、
図２は、図１におけるタスク並列化方法によるタスクの
実行状態の概要例を示す説明図、図３は、本発明のタス
ク並列化方法を行う並列化コンパイラの構成例を示すブ
ロック図、図４は、図３における並列化コンパイラを実
行するシステムのハードウェア構成例を示すブロック図
である。

【００１４】まず、図２を用いて本発明のタスク並列化
方法による処理動作の特徴を説明する。図２において、
図２（ａ）は本発明のタスク並列化方法によるタスク１
〜３の実行状態例を示し、図２（ｂ）は従来技術による
タスク１〜３の実行状態を示している。尚、タスク１と
タスク２は同時に実行可能であり、タスク３は、タスク
１とタスク２の終了後でないと実行できない。

【００１５】すなわち、図２（ｂ）に示すように、従来
技術では、タスク２の実行が終了したプロセッサ（２）
は、プロセッサ（１）によるタスク１の実行が終了した
後、タスク３の実行を開始している。このタスク３の実
行には、タスク３で参照されるデータやタスク３に含ま
れる命令コードの共有メモリから例えばキャッシュへの
転送処理が含まれるものとする。

【００１６】そこで、本例のタスク並列化方法では、図
２（ａ）に示すように、タスク２の実行が終了したプロ
セッサ（２）は、プロセッサ（１）によるタスク１の実
行中に、タスク３で参照されるデータやタスク３に含ま
れる命令コードをキャッシュに転送しておく（プリフェ
ッチタスク）。

【００１７】そして、プロセッサ（１）によるタスク１
の実行が終了した後、キャッシュにアクセスしてタスク
３の実行を開始する。このことにより、タスク３の実行
終了時間を、従来技術に比べて、Ｔ時間だけ早めること
ができる。

【００１８】以下、このようなタスク並列化に関わる並
列化コンパイラの処理を、図１を用いて説明する。本例
の並列化コンパイラは、ソースプログラムを入力して、
並列計算機で実行可能な複数のタスクと、このタスクを
プロセッサへ割り当てるタスクスケジュール処理とから
構成されるプログラムもしくはオブジェクトコードを出
力するものである。

【００１９】そのタスクの並列化方法として、まず、コ
ンパイル時に、実行を開始するための所定の条件（実行
可能条件）を満たすタスクに関して、このタスク内で参
照される可能性のあるデータ、もしくは、このタスクに
含まれる命令コードを検出する（ステップ１０１）。

【００２０】次に、検出したデータまたは命令コードが
格納されている記憶装置が、このタスクが上述のタスク
スケジュール処理によって割り当てられるプロセッサか
ら見て最も近い記憶装置であるか否かを判別し、最も近
い記憶装置であれば何もせず、そうでなければ、より近
い別の記憶装置へ転送する命令からなる情報転送タスク
を生成する（ステップ１０２）。

【００２１】最後に、タスクを実行していないアイドル
プロセッサがないか監視し、アイドルプロセッサを発見
したら、このアイドルプロセッサ以外のプロセッサで実
行されているタスクの終了時刻を予測し、予測される終
了時刻が最も早いタスクから、アイドルプロセッサに次
に割り当てられるタスクである次実行タスクを求め、こ
の次実行タスクに対する情報転送タスクが、アイドルプ
ロセッサで実行されるよう割り当てる命令からなる情報
転送タスクスケジュール処理を、次実行タスクをアイド
ルプロセッサへ割り当てるタスクスケジュール処理に追
加する（ステップ１０３）。

【００２２】以上の処理により、図２（ａ）に示すよう
に、タスク２の実行が終了したアイドルプロセッサとし
てのプロセッサ（２）のタスクスケジュール処理に情報
転送タスクスケジュール処理が追加され、その結果、プ
ロセッサ（２）では、プロセッサ（１）によるタスク１
の実行中に、タスク３で参照されるデータやタスク３に
含まれる命令コードをキャッシュに転送しておく（プリ
フェッチタスク）ことができる。

【００２３】次に、図４を用いて、このようなタスク並
列化を行う並列化コンパイラを実行するシステムのハー
ドウェア構成を説明する。

【００２４】図４において、４１はＣＲＴ(Cathode Ray
Tube)等からなり文字や画像を表示出力する表示装置、
４２はキーボードやマウス等からなり操作者からの指示
を入力する入力装置、４３はＨＤＤ(Hard Disk Drive)
等からなり大容量のデータやプログラムを記憶する外部
記憶装置、４４はＣＰＵ(Central Processing Unit)や
主メモリを有して蓄積プログラム方式による演算処理を
行なう情報処理装置、４５は本発明の処理手順に係わる
プログラムやデータを記録した記録媒体としての光ディ
スク、４６は情報処理装置４４からの指示に基づき外部
記憶装置４３に記憶させる光ディスク４５内のデータや
プログラムを読み出す駆動装置である。

【００２５】情報処理装置４４は、外部記憶装置４３に
記憶した光ディスク４５からのデータやプログラムを主
メモリにロードすることにより、図３に示す各部からな
るタスク並列化コンパイラ１０を構成する。以下、図３
を用いてタスク並列化コンパイラ１０を説明する。

【００２６】図３に示すように、タスク並列化コンパイ
ラ１０は、構文解析部１１、タスク並列化部１３、最適
化部１５、コード生成部１７から構成され、入力プログ
ラム９０をコンパイルして出力プログラムを生成する。

【００２７】以下、各構成部の説明を行う。構文解析部
１１は、入力プログラム９０を入力して中間語９１を出
力する。構文解析部１１の処理は通常のコンパイラの場
合と特に変わらない。タスク並列化部１３は、中間語９
１を入力し、タスク並列化された中間語９１を出力する
ものであり、以下に説明する依存解析部１３１、タスク
解析部１３２、転送情報検出部１３３、中間語変換部１
３４から構成されている。

【００２８】依存解析部１３１は、中間語９１を入力し
てデータ依存関係を解析する。尚、この依存解析部１３
１の処理は通常のコンパイラの場合と特に変わらない。
タスク解析部１３２は、中間語９１を入力してタスク並
列性解析を行なう。このタスク解析部１３２の処理は、
本多弘樹、岩田雅彦、笠原博徳著「Ｆｏｒｔｒａｎプ
ログラム粗粒度タスク間の並列性検出手法」電気情報通
信学会論文誌D-I、１９９０年１２月号、Vol.Ｊ７３-Ｄ
-I、No.１２、９５１−９６０ページ(以降、「文献２」
と記載)で述べられている方法と特に変わらない。

【００２９】転送情報検出部１３３は、中間語９１を入
力して、上述したように実行可能条件を満たすタスクに
関して、このタスク内で参照される可能性のあるデータ
または、このタスクに含まれる命令コードを検出する
等、「情報転送タスク」の生成に必要な情報を解析し、
解析結果をタスクテーブル９３と配列参照範囲テーブル
９４に出力する。

【００３０】中間語変換部１３４は、中間語９１、タス
クテーブル９３、配列参照範囲テーブル９４を入力し
て、「情報転送タスク」および「情報転送タスクスケジ
ュール処理」を含むタスク並列化された中間語９１を出
力するものであり、以下に説明する中間語並列化部１３
４１、タスクスケジュール処理生成部１３４２、タスク
スケジュール処理拡張部１３４３、情報転送タスク生成
部１３４４から構成されている。

【００３１】中間語変換部１３４１は、中間語９１を入
力して、タスク並列化された中間語９１を出力する。タ
スクスケジュール処理生成部１３４２は、中間語変換部
１３４１が出力した中間語９１を入力して、タスクスケ
ジュール処理を含むタスク並列化された中間語９１を出
力する。

【００３２】タスクスケジュール処理拡張部１３４３
は、タスクスケジュール処理生成部１３４２が出力した
中間語９１を入力して、「情報転送タスクスケジュール
処理」を追加したタスクスケジュール処理を含むタスク
並列化された中間語９１を出力する。

【００３３】情報転送タスク生成部１３４４は、タスク
スケジュール処理拡張部１３４３が出力した中間語９１
を入力して、情報転送タスク、情報転送タスクスケジュ
ール処理を追加したタスクスケジュール処理を含むタス
ク並列化された中間語９１を出力する。以上の転送情報
検出部１３３と中間語変換部１３４の処理は、それぞれ
本発明に係わるものである。

【００３４】最適化部１５は、タスク並列化部１３でタ
スク並列化された中間語９１を入力して最適化された中
間語９１を出力する。コード生成部１７は、最適化部１
５で最適化された中間語９１を入力して、タスク並列化
されたプログラムまたはオブジェクトコードを出力す
る。

【００３５】これらの最適化部１５とコード生成部１７
の処理は、通常のコンパイラの場合と特に変わらない。
以下、このような構成のタスク並列化コンパイラ１０に
よるタスクの並列化動作例を、図５を用いて説明する。

【００３６】図５は、図３におけるタスク並列化コンパ
イラを実装する並列計算機システムの構成例を示すブロ
ック図である。本図５における並列計算機システム５１
は、プロセッサ５１１１〜５１１ｎ、キャッシュメモリ
５１７１〜５１７ｎ、共有メモリ５１５、入出力用プロ
セッサ５１２、入出力用コンソール５１９、それらを結
合する相互結合ネットワーク５１３から構成される。

【００３７】図３のタスク並列化コンパイラ１０は、入
出力用コンソール５１９において実行され、これによ
り、図３の入力プログラム９０が並列ソースプログラム
に変換される。さらに、この変換された並列ソースプロ
グラムは、プロセッサ５１１１〜５１１ｎ向けコンパイ
ラによって並列オブジェクトプログラムに変換される。

【００３８】そして、この並列オブジェクトプログラム
は、リンカによりロードモジュールに変換され、入出力
用プロセッサ５１２を通じて共有メモリ５１５にロード
され、各プロセッサ５１１１〜５１１ｎにより実行され
る。

【００３９】この際、共有メモリ５１５にロードされた
ロードモジュールでは、次実行タスクで参照される配列
が存在する記憶装置である共有メモリ５１５に対するア
クセスを、情報転送タスクがアイドルプロセッサで予め
実行する。

【００４０】そのため、次実行タスクの実行開始時に
は、この次実行タスクで参照される配列は、共有メモリ
５１５よりもプロセッサプロセッサ５１１１〜５１１ｎ
に近い別の記憶装置であるキャッシュメモリ５１７１〜
５１７ｎに存在する。その結果、次実行タスクの実行時
間が短くなるので、プログラム実行時間を短縮すること
が可能である。

【００４１】以下、図３における構成のタスク並列化コ
ンパイラ１０の具体的な動作例を、図６に示す入力プロ
グラムを用いて説明する。図６は、図３における入力プ
ログラムの一例を示す説明図である。

【００４２】図６の入力プログラム９０における左端に
ある番号は行番号である。また、１行目は定数Ｎの値を
１０００と定義する文、２行目は、整数変数ｉ，ｊ，
ｋ，ｍと、第２次元目が０〜Ｎ−１の添字を持つ整数型
の１次元配列ａ，ｂ，ｃの宣言文である。

【００４３】３〜２０行目は入力プログラム９０の主処
理関数mainであり、４〜６行目はiをループ制御変数と
するループである。以下、ループは先頭行の行番号を用
いて表す。すなわち、このループはループ４と表す。

【００４４】７〜１１行目はｊをループ制御変数とする
ループ７、１２〜１５行目はｋをループ制御変数とする
ループ１２、１６〜１９行目はｍをループ制御変数とす
るループ１６である。

【００４５】図７および図８は、図１における出力プロ
グラムの一例を示す説明図である。図７および図８の左
端にある番号は行番号である。

【００４６】１行目は定数Ｎの値を１０００と定義する
文、２行目は、整数変数ｉ，ｊ，ｋ，ｍと、第１次元目
が０〜Ｎ−１の添字範囲を持つ整数型の１次元配列ａ，
ｂ，ｃの宣言文、３〜６行目は、定数INIT_EXEC_MT_NU
M、NPE、NTASK、NO_TASKの値を、それぞれ「−９９」、
「２」、「４」、「−９８」に定義する文である。

【００４７】７行目は整数変数newMT,succMT,tmp5,tmp
6,tmp7,tmp8,0〜NPE-1の添字範囲を持つ整数型の１次元
配列ExecMTの宣言文、８行目は整数変数ii,kk,kk,mm,my
PEの宣言文、９〜１５行目は、複素数変数TaskGranular
ity、整数変数SuccTaskNo、複素数変数StartTime、真偽
値型変数Finishを要素として持つ構造体TaskDataの宣言
文、１６行目は、０〜NTASKの添字範囲を持ち、構造体T
askDataを要素とする配列TDataの宣言文である。

【００４８】１７〜８９行目が出力プログラム９２の主
処理関数mainである。そのうち、２７〜３２、３７〜３
８、４０〜４１、４５〜４６、５２〜５３、５８〜５
９、６４、８４、８６〜８７行目がタスクスケジュール
処理を行なう部分である。

【００４９】４２〜４４行目がタスク１、４７〜５１行
目がタスク２、５４〜５７行目がタスク３、６０〜６３
行目がタスク４、１８〜２６、３３〜３６、３９、６５
〜６７、７２〜７３、７８〜７９、８３、８５行目が情
報転送タスクスケジュール処理を行なう部分、６８〜７
１行目がタスク２に対する情報転送タスク、７４〜７７
行目がタスク３に対する情報転送タスク、８０〜８２行
目がタスク４に対する情報転送タスクである。

【００５０】以下、このような図６に示す入力プログラ
ム９０と図７，８に示す出力プログラム９２に関わる図
３のタスク並列化コンパイラ１０内の個々の処理を説明
する。

【００５１】まず、構文解析部１１により、入力プログ
ラム９０を入力して中間語９１を出力する。尚、中間語
９１は図６の入力プログラム９０に対応しているので、
以下の説明では、図６の入力プログラム９０を中間語９
１のソースプログラムイメージの表現として用いる。

【００５２】次に、タスク並列化部１３は、依存解析部
１３１、タスク解析部１３２、転送情報検出部１３３、
中間語変換部１３４により次のような処理を行う。

【００５３】依存解析部１３１では、Alfred V.Aho、Ra
vi Sethi、Jeffrey D.Ullman著、「Compilers」、Addis
on-Wesley Publishing Company、1986に説明されている
処理により、中間語９１を入力してデータ依存関係を解
析する。

【００５４】タスク解析部１３２は、中間語９１を入力
してタスク並列性解析を行なう。図６の入力プログラム
９０では、ループ４がタスク１、ループ７がタスク２、
ループ１２がタスク３、ループ１６がタスク４と解析さ
れる。また、タスク１〜４の実行可能条件は、それぞれ
「タスク１：条件なし」、「タスク２：タスク１の終
了」、「タスク３：タスク１の終了」、「タスク４：タ
スク３の終了」と解析される。

【００５５】これらの実行可能条件をまとめて図９に示
すように記憶する。図９は、図３のタスク解析部により
図６の入力プログラムから解析した実行可能条件をまと
めた表の構成例を示す説明図である。

【００５６】本例の実行可能条件の表９５においては、
各タスク１〜４の実行可能条件が、「タスク１：条件な
し」、「タスク２：タスク１の終了」、「タスク３：タ
スク１の終了」、「タスク４：タスク３の終了」として
まとめて登録されている。

【００５７】さらに、タスク解析部１３２は、そのタス
クの実行終了をプログラムの終了とみなせる唯一のタス
クである「プログラム終了タスク」を、以下の一般的な
技術により求める。

【００５８】すなわち、タスクをノード、タスク間の制
御依存関係をエッジとする「タスクグラフ」を作成し、
この「タスクグラフ」に処理を含まないダミータスクで
ある「プログラム終了タスク」を加え、エッジの始点を
持たないタスクから「プログラム終了タスク」へのエッ
ジを設けて、「プログラム終了タスク」とする。

【００５９】但し、「プログラム終了タスク」を終点と
するエッジが１本しかない場合は、そのエッジの始点で
あるタスクを「プログラム終了タスク」とみなせるの
で、図６の入力プログラム９０では、タスク４をプログ
ラム終了タスクとすることができる。

【００６０】このようなタスク解析部１３２の処理の詳
細に関しては、上述の文献２で述べられている技術と特
に変わらないので、これ以上は述べない。

【００６１】次に、転送情報検出部１３３は、中間語９
１を入力して、タスク１〜４の各々に対し、タスク内で
参照される配列の参照範囲を解析してその結果を配列参
照範囲テーブル９４に出力し、タスク実行時間の見積も
りと、そのタスクの終了で初めて実行可能条件が満たさ
れるタスク総数の解析を行ない、それらの結果をタスク
テーブル９３に出力する。

【００６２】ここで、参照とは変数が定義または使用さ
れること、変数とはスカラ変数または配列のこと、定義
とは変数に値を代入すること、使用とは変数の値を用い
ること、配列の参照範囲とは、その配列の参照される可
能性がある添字範囲のことを指す。

【００６３】以下、転送情報検出部１３３の処理動作例
を、図１０と図１１を用いて説明する。図１０は、図３
における転送情報検出部の処理手順例を示すフローチャ
ートであり、図１１は、図１０における転送情報検出部
の処理手順により得られるタスクテーブルと配列参照範
囲テーブルの構成例を示す説明図である。

【００６４】図３の転送情報検出部１３３が図６の入力
プログラム９０に対して、図１０におけるステップ１３
３１〜１３３６の処理を行うことにより、図１１に示す
タスクテーブル９３１〜９３４と配列参照範囲テーブル
９４２〜９４６が得られる。

【００６５】図１１においては、タスクテーブル９３２
と配列参照範囲テーブル９４２，９４３のみフィールド
を詳細に示している。タスクテーブル９３１〜９３４
は、それぞれ図６のタスク１〜４に対応するタスクテー
ブルである。

【００６６】以下、タスクテーブル９３２を例にとっ
て、タスクテーブルの各フィールド９３２１〜９３２５
を説明する。フィールド９３２１には次のタスクテーブ
ルへのポインタを格納する。図中、フィールド９３２１
から右に向いた矢印がこのポインタに対応する。次のタ
スクテーブルがない場合はNULL値を格納する。

【００６７】フィールド９３２２にはタスク番号を格納
する(図中、「２」が記載)。フィールド９３２３には、そ
のタスクに関して見積もられたタスク実行時間を格納す
る(図中、「６００５」が記載)。

【００６８】フィールド９３２４には、そのタスクの終
了で初めて実行可能条件が満たされるタスクの総数であ
る次実行タスク数を格納する(図中、「０」が記載)。フィ
ールド９３２５には、そのタスク内で参照される配列の
配列参照範囲テーブルへのポインタを格納する。図中、
フィールド９３２５から下に向いた矢印がこのポインタ
に対応する。そのタスクに関して配列参照範囲テーブル
がない場合はNULL値を格納する。

【００６９】次に、配列参照範囲テーブル９４２〜９４
６において、図６のタスク２の解析結果を収めたのが配
列参照範囲テーブル９４２と９４３、タスク３の解析結
果を収めたのが配列参照範囲テーブル９４４と９４５、
タスク４の解析結果を収めたのが配列参照範囲テーブル
９４６である。タスク１は配列参照範囲テーブルをもた
ない。

【００７０】以下、配列参照範囲テーブル９４２を例に
とって、配列参照範囲テーブルのフィールド９４２１〜
９４２３を説明する。フィールド９４２１には、そのタ
スク内で参照される配列の配列名を格納する（図中、
「ａ」が記載）。

【００７１】フィールド９４２２には、そのタスク内で
参照される配列の参照範囲を「配列添字の下限値：配列
添字の上限値」の形式で格納する（図中、「１：Ｎ−
１」が記載）。

【００７２】フィールド９４２３には、そのタスク内で
参照される次の配列の配列参照範囲テーブルへのポイン
タを格納する。図中、フィールド９４２３から下に向い
た矢印がこのポインタに対応する。次の配列参照範囲テ
ーブルがない場合はNULL値を格納する。

【００７３】以下、このような転送情報検出部１３３の
処理を中間語９１に適用した結果について説明する。ま
ず、図１０のステップ１３３１の処理を適用する。ここ
では、転送情報検出部１３３で未処理のタスクの例とし
てタスク２を選択する。

【００７４】次に、ステップ１３３２の処理を中間語９
１に適用する。ステップ１３３２は、所定の条件を満た
すタスクを選択する処理である。タスク解析部１３２で
解析したタスク２の実行可能条件は「タスク１の終了」
なので常に真ではない。従って、NO方向へ処理が分岐
し、ステップ１３３３へ移る。

【００７５】次に、ステップ１３３３の処理を中間語９
１に適用すると、タスク２内で参照される配列ａ、配列
ｂの配列参照範囲が次のように解析される。まず、タス
ク２のループ制御変数jが１〜Ｎ−１の値をとることか
ら、添字がjである９行目の配列ａの参照範囲は「１：
Ｎ−１」と解析される。

【００７６】同様に配列ｂに関しては、添字が０である
８行目での参照範囲は「０」、添字がjである９行目左
辺での参照範囲は「１：Ｎ−１」、添字がj-1である９
行目右辺での参照範囲は「０：Ｎ−２」、添字がN-1で
ある１０行目での参照範囲は「Ｎ−１」と解析されるの
で、これらの和集合をとって、タスク２での配列ｂの参
照範囲が「０：Ｎ−１」となる。

【００７７】以上の解析結果は配列参照テーブル９４
２、９４３に格納される。まず、配列名ａが配列参照テ
ーブル９４２のフィールド９４２１に、配列参照範囲
「１：Ｎ−１」がフィールド９４２２に、配列名ｂが配
列参照テーブル９４３のフィールド９４３１に、配列参
照範囲「０：Ｎ−１」がフィールド９４３２に、それぞ
れ格納される。

【００７８】また、配列参照範囲テーブル９４２へのポ
インタがタスクテーブル９３２のフィールド９３２５
に、配列参照範囲テーブル９４３へのポインタが配列参
照テーブル９４２のフィールド９４２３に、配列参照テ
ーブル９４３のフィールド９４３３にNULLが、それぞれ
格納される。

【００７９】次に、ステップ１３３４を中間語９１に適
用すると、タスク２のタスク実行時間であるコストが以
下のようにして見積もられる。まず、図６の入力プログ
ラム９０の１行目よりＮは１０００なので、入力プログ
ラム９０タスク２の７行目のループは９９９回まわるこ
とがわかる。

【００８０】タスク２の８行目では、if文の条件判定を
コスト１、帰結節の代入文b[0]=0をコスト１と見積も
る。この条件判定は各ループ繰り返しで、帰結節はルー
プ制御変数jが１の時のみ実行されるから、８行目の合
計コストは１０００となる。

【００８１】タスク２の９行目では、代入文右辺のa[j]
およびb[j-1]のロード、加算、左辺のb[j]のストアを各
々コスト１と見積もる。この代入文は各ループ繰り返し
で実行されるから、９行目の合計コストは３９９６とな
る。

【００８２】タスク２の１０行目では、if文の条件判定
をコスト１、帰結節のprintf文をコスト１０と見積も
る。この条件判定は各ループ繰り返しで、帰結節はルー
プ制御変数jが９９９の時のみ実行されるから、１０行
目の合計コストは１０９９となる。

【００８３】以上を合計すると、タスク２のコストは６
００５となり、この値が図１１におけるタスクテーブル
９３１のフィールド９３１３に格納される。

【００８４】次に、ステップ１３３５を中間語９１に適
用する。図３のタスク解析部１３２で解析された実行可
能条件を表にした図９より、「タスク２の終了」を実行
可能条件にもつタスクは存在しないことから、タスク２
の終了で初めて実行可能条件が満たされるタスクの総数
は０となり、その値が図１１におけるタスクテーブル９
３２のフィールド９３２４に格納される。

【００８５】次に、ステップ１３３６を中間語９１に適
用する。タスク１，３，４のうち転送情報検出部１３３
で未処理のものが存在すれば、NO方向へ処理が分岐して
ステップ１３３１へ戻り、次のタスクに関してステップ
１３３２〜１３３６を繰り返し、存在しなければ転送情
報検出部１３３を終了する。以上で、転送情報検出部１
３３の処理動作例の説明を終了する。

【００８６】次に、図３の中間語変換部１３４の処理を
図６の入力プログラム９０に適用した結果について説明
する。中間語変換部１３４は、中間語９１、タスクテー
ブル９３、配列参照範囲テーブル９４を入力して、タス
クスケジュール処理、情報転送タスクスケジュール処
理、情報転送タスクを持つタスク並列化された中間語９
１を出力する。

【００８７】尚、タスク並列化された中間語９１は図
７，８の出力プログラム９２に対応しているので、以下
の説明では、図７，８の出力プログラム９２をタスク並
列化された中間語９１のソースプログラムイメージの表
現として用いる。

【００８８】まず、図３の中間語変換部１３４は、中間
語並列化部１３４１の処理を中間語９１に適用する。こ
の結果挿入された中間語が、図７，８の出力プログラム
９２の３〜６、２８〜２９、８８行目である。

【００８９】３〜６行目は変数を定義する文である。２
８行目は並列実行部分の開始を表すコンパイラ指示文で
あり、# pragma omp parallelで並列実行部分の開始を
示し、PRIVATE(myPE,newMT)で、プロセッサ番号を表す
変数myPE、変数newMTが各プロセッサで別々の変数にな
るように指示している。

【００９０】８８行目は並列実行部分の終了を示すコン
パイラ指示文である。２９行目はプロセッサ番号を表す
変数myPEの設定文であり、この文の右辺はプロセッサ番
号問い合わせ関数get_processor_numである。

【００９１】次に、タスクスケジュール処理生成部１３
４２の処理を中間語９１に適用する。この結果挿入され
たタスクスケジュール処理にあたる中間語が、図７，８
の出力プログラム９２の３０〜３２行目、３７行目、４
０〜４１行目、４５〜４６行目、５２〜５３行目、５８
〜５９行目、６４行目、８４〜８５行目、８７行目であ
る。

【００９２】３０、８７行目のwhileループは、プログ
ラム終了タスクであるタスク４が実行終了するまで全プ
ロセッサがwhileループを回ってタスクスケジュール処
理を実行し続ける処理である。

【００９３】３１、３７行目は、この２文の間がクリテ
ィカルセクションであることを示す指示文であり、この
２つの指示文で挟まれた部分は、１度に１台のプロセッ
サでしか実行できない排他処理であることを表す。

【００９４】３２行目の代入文では、実行可能条件を満
たしたタスクのタスク番号を関数GET_MT_FROM_QUEUEで
取り出し、変数newMTに設定している。実行可能条件を
満たしたタスクが存在しない場合は、該関数は定数変数
NO_TASKを返す。この関数の処理の内容は、上述の文献
１で述べられている技術と特に変わらないので、ここで
は詳細には述べない。

【００９５】４０〜４１行目、４５〜４６行目、５２〜
５３行目、５８〜５９行目、６４行目、８４行目は、３
２行目で変数newMTに設定されたタスク番号に従って実
行するタスクを選択する部分である。８５行目は、実行
終了したタスクの終了フラグを設定する処理である。終
了フラグはタスク実行終了を示すフラグであり、タスク
毎に設けられている。

【００９６】次に、タスクスケジュール処理拡張部１３
４３の処理を中間語９１に適用した場合を説明する。図
１２は、図３におけるタスクスケジュール処理拡張部の
処理手順例を示すフローチャートである。

【００９７】図１２に示すように、図３におけるタスク
スケジュール処理拡張部１３４３は、ステップ１３４３
１〜１３４３６の各処理を、中間語に対して行う。

【００９８】まず、ステップ１３４３１の処理を中間語
９１に適用する。この結果挿入された中間語が、図７，
８の出力プログラム９２における６５〜６７行目、７２
〜７３行目、７８〜７９行目、８３行目である。

【００９９】ここで挿入された中間語は、変数newMTに
情報転送タスクのタスク番号が設定されていたら、その
情報転送タスクを実行する処理を意味する。ここでは、
情報転送タスクのタスク番号は、情報転送タスクに対す
る元のタスクのタスク番号に、タスク総数を加えたもの
とする。図７，８の出力プログラム９２では、タスク１
〜４に対する情報転送タスクには、それぞれ５〜８のタ
スク番号を与える。

【０１００】次に、ステップ１３４３２の処理を中間語
９１に適用する。この結果挿入された中間語が、図７，
８の出力プログラム９２の３９行目であり、情報転送タ
スクを除くタスクの実行開始時刻を構造体TDataに設定
する文である。この文の右辺の関数present_timeは、現
時刻を与える関数である。

【０１０１】次に、ステップ１３４３３の処理を中間語
９１に適用する。この結果挿入された中間語が、図７，
８の出力プログラム９２の２７行目、３８行目、８６行
目である。２７行目は配列ExecMTの初期化文、３８行目
は各プロセッサが現在実行しているタスクのタスク番号
を配列ExecMTに設定する文、８６行目は配列ExecMTの値
を初期値に戻す文である。

【０１０２】次に、ステップ１３４３４の処理を中間語
９１に適用する。この結果挿入された中間語が、図７，
８の出力プログラム９２の３３、３６行目である。これ
は、関数GET_MT_FROM_QUEUEが返した値が、その時点で
実行可能条件を満たしたタスクが存在しないことを意味
する定数変数NO_TASKかどうかを調べる文である。

【０１０３】次に、ステップ１３４３５の処理を中間語
９１に適用する。この結果挿入された中間語が、図７，
８の出力プログラム９２の１８〜２６行目、３４行目の
文である。

【０１０４】１８〜２５行目では、図１１に示すタスク
テーブル９３１〜９３４を用いて、転送情報検出部１３
３のステップ１３３４で見積もられたタスク実行時間を
構造体TDataのTaskGranularityフィールドに、図１０の
ステップ１３３５で数えられた次実行タスク数を構造体
TDataのSuccTaskNoフィールドに設定する。

【０１０５】例えばタスク２の場合では、図１１におけ
るタスクテーブル９３２のフィールド９３２２に格納さ
れている値２を、図７，８の出力プログラム９２の１
９、２３行目の代入文左辺の構造体TDataの添字に、ま
た、フィールド９３２３に格納されている値「６００
５」を、出力プログラム９２の１９行目の代入文右辺
に、フィールド９３２４に格納されいている値０を、出
力プログラム９２の２３行目の代入文右辺に設定する。

【０１０６】図７，８の出力プログラム９２の２６行目
は各タスクの終了フラグの初期化文である。また、同３
４行目は取得した次実行タスクのタスク番号を変数newM
Tに設定する代入文であり、この代入文右辺の関数Predi
ctSuccMTは、次実行タスクの番号を取得するための関数
（次実行タスク番号取得関数）である。尚、この実行タ
スク番号取得関数の処理の内容については、後述の図１
４を用いて説明する。

【０１０７】最後に、ステップ１３４３６の処理を中間
語９１に適用する。この結果挿入された中間語が、図
７，８の出力プログラム９２の３５行目である。これ
は、変数succMTの値である取得された次実行タスクのタ
スク番号にタスク総数を加えて、次実行タスクに対する
情報転送タスクのタスク番号を得る処理である。

【０１０８】以上で、タスクスケジュール処理拡張部１
３４３の処理の説明を終る。次に、情報転送タスク生成
部１３４４の処理を中間語９１に適用した場合を説明す
る。

【０１０９】図１３は、図３における情報転送タスク生
成部の処理手順例を示すフローチャートである。本図１
３に示すように、図３における情報転送タスク生成部１
３４４はステップ１３４４１〜１３４４４からなる処理
をおこなう。

【０１１０】まず、ステップ１３４４１の処理を図３の
中間語９１に適用する。ここでは、未処理のタスクの例
としてタスク２を選択する。次に、ステップ１３４４２
の処理を中間語９１に適用する。図３のタスク解析部１
３２で解析したタスク２の実行可能条件は「タスク１の
終了」なので常に真ではない。従って、ここでは、NO方
向へ処理が分岐してステップ１３３４３へ移る。

【０１１１】次に、ステップ１３４４３の処理を中間語
９１に適用する。図１１で示すタスク２の配列参照範囲
テーブル９４２、９４３の情報を利用して挿入された中
間語が、図７，８の出力プログラム９２の６８〜７１行
目である。

【０１１２】これは、配列参照範囲テーブル９４２のフ
ィールド９４２１に格納されている配列名ａとフィール
ド９４２２に格納されている参照範囲１：Ｎ−１、配列
参照範囲テーブル９４３のフィールド９４３１に格納さ
れている配列名ｂとフィールド９４３２に格納されてい
る参照範囲０：Ｎ−１より作成された、添字１〜Ｎ−１
の範囲の配列ａの要素と、添字０〜Ｎ−１の範囲の配列
ｂの要素を使用するループである。

【０１１３】次に、ステップ１３４４４の処理を中間語
９１に適用する。タスク１、３、４のうち、未処理のも
のが存在すれば、NO方向へ処理が分岐してステップ１３
４４１へ戻り、次のタスクに関して同様にステップ１３
４４２〜１３４４３を繰り返す。また、未処理のタスク
が存在しなければステップ１３４４を終了する。

【０１１４】以上で、図３における情報転送タスク生成
部１３４４の処理動作例、および、図３における中間語
変換部１３４の処理動作例の説明を終る。

【０１１５】このようにして、中間語変換部１３４でタ
スク並列化された中間語９１を、最適化部１５は入力
し、最適化された中間語９１を出力する。そして、コー
ド生成部１７は、最適化部１５で最適化された中間語９
１を入力して、図７，８に示す出力プログラム９２を出
力する。尚、これらの最適化部１５、コード生成部１７
の処理の内容は通常のコンパイラの場合と特に変わらな
いので、ここでは詳細には述べない。

【０１１６】以上で、本発明に係るタスク並列化方法の
一例の説明を終り、図１４で、次実行タスク番号取得関
数、すなわち、図７，８の出力プログラム９２の３４行
目の代入文右辺の関数PredictSuccMTの処理の内容を説
明する。

【０１１７】図１４は、次実行タスク番号取得関数の処
理例を示すフローチャートである。図７，８の出力プロ
グラム９２の３４行目の代入文右辺の関数PredictSuccM
Tは引数を２個持つ。第１引数は、各タスクのタスク実
行時間、次実行タスク数、タスク実行開始時間、タスク
終了フラグを格納した構造体TData、第２引数は、各プ
ロセッサで現在実行中のタスク番号を格納した配列Exec
MTである。

【０１１８】本図１４に示すように、次実行タスク番号
取得関数は、ステップ２１１〜２１４の処理を行う。ま
ずステップ２１１では、現在実行中のタスクを検出す
る。これは、関数PredictSuccMTの第２引数である配列E
xecMTの添字をプロセッサ番号とした要素の値を調べ
て、実行中のタスクのタスク番号を取得する処理であ
る。

【０１１９】次にステップ２１２では、実行中の各タス
クの実行終了までの残り時間を予測する。これは、関数
PredictSuccMTの第１引数である構造体TDataを用いて計
算する。現在実行中のタスクのタスク番号をIとする
と、残り時間の予測式は、次のようにして与えられる。

【０１２０】残り時間＝見積もられたタスク実行時間−（現時刻−タスク実行
開始時刻) ＝TData[I].TaskGranularity−（present_time()−TDat
a[I].StartTime）

【０１２１】さらにステップ２１３では、ステップ２１
２の結果より、残り時間が最小である最小残り時間タス
クを求める。そしてステップ２１４では、この最小残り
時間タスクの実行終了後に実行可能になるタスクを探
し、このタスクの次実行タスク数が最多のタスクを次に
実行される次実行タスクとする。

【０１２２】これは、現在未実行のタスクから、該最小
残り時間タスクが終了すると実行可能条件が真になるタ
スク群を探し、そのタスク群から、TData構造体のSuccT
askNoフィールドの値が最大のタスクを求める処理であ
る。以上で、次実行タスク番号取得関数の説明を終る。

【０１２３】以上、図１〜図１４を用いて説明したよう
に、本例のタスク並列化方法では、タスクを実行してい
ないアイドルプロセッサがないか監視し、このアイドル
プロセッサを発見したら、他のプロセッサで実行されて
いるタスクの終了時刻を予測し、予測される終了時刻が
最も早いタスクから、アイドルプロセッサに次に割り当
てるタスクである次実行タスクを求める。

【０１２４】そして、この次実行タスクで参照される可
能性のあるデータや、そのタスクに含まれる命令コード
を、そのアイドルプロセッサのキャッシュに転送する情
報転送タスクを作成し、かつ、その情報転送タスクがア
イドルプロセッサで実行されるように割り当てる命令か
らなる情報転送タスクスケジュール処理を作成して、並
列化コンパイラが生成したタスクスケジュール処理に追
加する。

【０１２５】これにより、プロセッサのアイドルタイム
にデータをキャッシュに転送するので、アイドルプロセ
ッサとキャッシュの有効利用を図ることができ、プログ
ラム実行中のある時点で実行可能なタスク数が、利用可
能なプロセッサ数より少ない場合におけるプログラムま
たはオブジェクトコードの実行時間を短縮することが可
能である。

【０１２６】尚、本例のタスク並列化方法により予めキ
ャッシュに読み込んだデータが無効化された場合には、
従来技術の通りに共有メモリにアクセスする。

【０１２７】また、本発明は、図１〜図１４を用いて説
明した例に限定されるものではなく、その要旨を逸脱し
ない範囲において種々変更可能である。例えば、本例で
は、アイドルプロセッサに次に割り当てられるタスクで
参照される可能性のあるデータや、そのタスクに含まれ
る命令コードを、そのアイドルプロセッサのキャッシュ
に転送する情報転送タスクと、その情報転送タスクをア
イドルプロセッサに割り当てるスケジュール処理を作成
しているが、情報転送タスクとしては、それらのデータ
や命令コードを外部記憶装置からメインメモリヘ、ある
いは、他プロセッサのリモートメモリからアイドルプロ
セッサのローカルメモリに転送するものであっても良
い。

【０１２８】

【発明の効果】本発明によれば、プログラム実行中のあ
る時点で、実行可能なタスク数が利用可能なプロセッサ
数より少ない場合でも、タスクが割り当てられていない
アイドルプロセッサを有効利用して実行時間を短縮でき
るプログラムまたはオブジェクトコードを出力すること
ができ、並列計算機システムの性能の向上を図ることが
可能である。

【図面の簡単な説明】

【図１】本発明のタスク並列化方法に係る処理動作例を
示すフローチャートである。

【図２】図１におけるタスク並列化方法によるタスクの
実行状態の概要例を示す説明図である。

【図３】本発明のタスク並列化方法を行う並列化コンパ
イラの構成例を示すブロック図である。

【図４】図３における並列化コンパイラを実行するシス
テムのハードウェア構成例を示すブロック図である。

【図５】図３におけるタスク並列化コンパイラを実装す
る並列計算機システムの構成例を示すブロック図であ
る。

【図６】図３における入力プログラムの一例を示す説明
図である。

【図７】図１における出力プログラムの一例の前半部分
を示す説明図である。

【図８】図１における出力プログラムの一例の後半部分
を示す説明図である。

【図９】図３のタスク解析部により図６の入力プログラ
ムから解析した実行可能条件をまとめた表の構成例を示
す説明図である。

【図１０】図３における転送情報検出部の処理手順例を
示すフローチャートである。

【図１１】図１０における転送情報検出部の処理手順に
より得られるタスクテーブルと配列参照範囲テーブルの
構成例を示す説明図である。

【図１２】図３におけるタスクスケジュール処理拡張部
の処理手順例を示すフローチャートである。

【図１３】図３における情報転送タスク生成部の処理手
順例を示すフローチャートである。

【図１４】次実行タスク番号取得関数の処理例を示すフ
ローチャートである。

【図１５】タスク実行状況を表わすタスク実行グラフの
一例を示す説明図である。

【符号の説明】

１０：タスク並列化コンパイラ、１１：構文解析部、１
３：タスク並列化部、１５：最適化部、１７：コード生
成部、１３１：依存解析部、１３２：タスク解析部、１
３３：転送情報検出部、１３４：中間語変換部、１３４
１：中間語並列化部、１３４２：タスクスケジュール処
理生成部、１３４３：タスクスケジュール処理拡張部、
１３４４：情報転送タスク生成部、４１：表示装置、４
２：入力装置、４３：外部記憶装置、４４：情報処理装
置、４５：光ディスク、４６：駆動装置、５１：並列計
算機システム、５１１１〜５１１ｎ：プロセッサ、５１
２：入出力用プロセッサ、５１３：相互結合ネットワー
ク、５１５：共有メモリ、５１７１〜５１７ｎ：キャッ
シュメモリ、５１９：入出力用コンソール、９０：入力
プログラム、９１：中間語、９２：出力プログラム、９
３，９３１〜９３４：タスクテーブル、９３２１〜９３
２５：フィールド（タスクテーブル）、９４，９４２〜
９４６：配列参照範囲テーブル、９４２１〜９４２３：
フィールド（配列参照範囲テーブル）、９５：実行可能
条件の表、１５００１：タスク実行グラフ。

Claims

【特許請求の範囲】

【請求項１】ソースプログラムを、並列計算機で実行
可能な複数のタスクと該タスクをプロセッサへ割り当て
るタスクスケジュール処理とからなるプログラムもしく
はオブジェクトコードに変換する並列化コンパイラにお
けるタスクの並列化方法であって、予め定められた条件
を満たすタスクＡ内で参照される可能性のあるデータな
らびに上記タスクＡに含まれる命令コードをコンパイル
時に検出するステップと、上記データならびに上記命令
コードを、上記タスクＡが割り当てられるプロセッサに
近い記憶装置へ転送する命令からなる情報転送タスクを
生成するステップと、タスクを実行していないアイドル
プロセッサに次に割り当てる次実行タスクを求めて該次
実行タスクに対する上記情報転送タスクが上記アイドル
プロセッサで実行されるよう割り当てる命令からなる情
報転送タスクスケジュール処理を上記タスクスケジュー
ル処理に追加するステップとを有することを特徴とする
タスク並列化方法。