成蹊大学理工学研究報告
J. Fac. Sci. Tech., Seikei Univ.
Vol.44 No.1 (2007) pp.35-44

Ｃ言語自動並列化トランスレータにおけるマクロタスク拡張
田中 康之＊1，三浦純＊1，甲斐

宗徳＊2

An Extension of Automatic Parallelizing Translator for C Program Using Macro Task
Yasuyuki TANAKA＊1, Jyun MIURA＊1, Munenori KAI＊2,
ABSTRACT：In order to parallelize a C program, a set of source codes, automatically, a series of someanalysis stages are required. They consist of parallelism analysis stage, execution time analysis stage,task granularity analysis stage, task scheduling stage, parallelized code generation stage. Among thesestages, the results of other stages are shared. The authors have proposed a set of shared resources which
are the source codes embedded with dedicated pragma directives. In this paper, a concept of macro task
representation for the pragma directives is proposed. The macro task representation is useful to hide inner
structure in the nest of program control structures at the stages, such as execution time analysis stage andtask scheduling stage. In the parallelized code generation stage, because some MPI communication
function calls are arranged into a single MPI packing communication function, the efficient parallelized
program with reduced overhead can be generated.
Keywords：automatic parallelization, Message Passing Interface, pragmadirective, source code translator（Received March 26, 2007）

１．はじめにータの開発を行っている。

1. 1

1. 2

背景と目的

C 言語自動並列化トランスレータ内では，タスクブロ

コンピュータの性能向上の手段としてマルチプロセッ
1)

本研究におけるマクロタスクの位置づけであるが，そのックと呼ばれる単位でタスクごとの情報が表現される。

ためには並列性と効率を考慮したプログラムを実行しなタスクブロックとは並列実行する際に各プロセスが実行

いとその優れた性能を十分に引き出せないという側面もする最小単位であり，最小の粒度はソースコードのステある。従って，効率的な並列プログラムを作成する必要ートメントとしている。

サシステムが有効であることは明らかがあり，それには並列性の抽出作業や，処理すべきタス

図 1.1 の例のようにタスクブロック内部にはソースコ

クの実行順序を決めるためのスケジューリング作業など

ードの構造上，if 文や for 文などのように複数のタスクを行わなければならない。ところが，その作業にはアプブロックを階層的に含むようなタスクがある。このようリケーションの内部構造および処理システムのアーキテなタスクブロックを「マクロタスク」と呼ぶ。マクロタ

クチャなどの知識が要求されるため，マルチプロセッサ
システムの有効利用という点で利用者にとって大きな障害になっている。
本研究では，ポインタの存在などにより実用的な自動並列化が困難とされている C 言語に対して粗粒度および細粒度並列化 2)を行うことで，実行性能の向上を図った
並列プログラムに変換する C 言語自動並列化トランスレ

if( a == 10 ){マ
クロタスク１マクロタス

a = a * 10;
for( i = 10; i< n; i++ ){
j++;
}

タスク１－
タスク１－１マクロタス
ク１－２
マクロタスク１－２}*1：工学研究科情報処理専攻修士学生：情報処理専攻教授 (kai@st.seikei.ac.jp)*2

図 1. 1－35－

マクロタスク例

スクは，スケジューリング時にそのタスクブロックの内度を決める。部分タスクスケジューリングでは，それら部構造を隠蔽するために用いることができる。

処理すべきタスク集合をどのように各プロセッサに割り

本論文では，すでに提案していた C 言語自動並列化ト
ランスレータの処理の流れ

当て，どのような順序で実行すれば最短時間で処理が完

3)にマクロタスクを考慮して了するのかを決める。

解析を行う必要があることから，マクロタスクの取り扱

次に，全体タスクスケジューリングを行う。最終的な

いにともなう拡張を行った。

粒度での最適スケジューリングを行う。
最終段階の作業として，ターゲットマシンにおいて優２. Ｃ言語自動並列化トランスレータ

れた実行性能を実現するような並列実行コードの自動生成を行う。

C 言語自動並列化トランスレータは，C 言語で記述さ本 研 究 で は ， C 言 語 の 逐 次 プ ロ グ ラ ム か ら MPI

れたソースプログラムに存在する並列性を抽出し，それ（Message Passing Interface）を用いた並列プログラムを活用することで自動的に並列実行コードを生成するもへの自動並列化トランスレータの開発を行った。MPI をのである。本研究で開発する C 言語自動並列化トランス用いることでより汎用性・移植性のあるコードを生成でレータの全体的な処理の流れを図 2.1 に示す。次に各作きる。また，生成される並列プログラムのモデルは Single

業ステージでの解析について説明する。

Program Multiple Data(SPMD)型である。

C ソースプログラム

2.2

解析の流れの変更点(1)

精度の高い実行時間解析への変更

並列性解析

タスク融合された複数のステートメントを含むタス
クブロックの実行時間は個別のステートメントごとの実行時間解析

実行時間の合計値とはならず，パイプライン処理やキ
タスク粒度解析ャッシュの効果を含んだ時間となる。従って，タスク

部分タスクスケジューリング

粒度解析によってまとめられた粒度で再び実行時間を計測する必要がある。

全体タスクスケジューリング

(2)

マクロタスクに対する解析
マクロタスクの実行時間および処理プロセス数はマ

並列化コード生成

クロタスク内部に含まれるサブタスクグラフの実行時間および，処理プロセッサ数となるが，そのサブタス

並列化コードクグラフもさらにマクロタスクを含む場合があるので，
図 2. 1

Ｃ言語自動並列化トランスレータの処理の流れ

階層的なマクロタスクの最も内側のマクロタスクから順に実行時間解析，タスク粒度解析，部分的なタスク
スケジューリングを行い，外側へと繰り返し解析を行

2. 1

各作業ステージでの解析の流れ

うような流れへと変更を行った。

前半の作業ステージとして，解析対象となるソースプ

３．プラグマディレクティブによる共有リソース

ログラムの並列性解析を行う。並列性解析では，プログの改善

ラムに存在するステートメントレベルでの並列性を抽出
する。

3. 1

中盤の作業ステージとして，実行時間解析，タスク粒

従来の共有リソース

度解析，部分タスクスケジューリングを行う。実行時間

図 2.1 のステージがスムーズに連携するためには，全解析では，並列性解析結果に基づき，逐次実行しなけれてのステージ間で共有できるリソースが必要である。著ばならないコードセグメントごとの実行時間と，タスク者ら，すでに C ソースコード上にプラグマディレクティ

間で行うデータ通信時間を求める。タスク粒度解析では，

ブを用いてステージ間で情報を受け渡すことができるよ

並列性解析と実行時間解析から得られた結果に基づき，

うな共有リソースを設計した３)。共有リソースは並列性

各タスクをどのような大きさでプロセッサに割り当てれ解析の結果により生成され，実行時間解析，タスクスケば効率の良い並列処理を行えるのかを考慮してタスク粒

ジューリングやタスク粒度解析時に読み込まれ，解析さ－36－

#pragma acpt TASK( …)
ソースプログラム#pragma acpt DATA(…)

暫定的タスク情報
通信情報
詳細情報

…
共有リソース

タスクコード並列性解析#pragma acpt TASK(…)

ソースコードインタフェース
実行時間解析
スケジューリング結果
タスク粒度情報…
図 3. 2

タスク粒度解析表 3. 1

部分タスクスケジューリング
スケジューリング結果
全体タスクスケジューリング
並列化コード生成

図 3. 1

共有リソースの利用れた情報を順々に追加していく。最終的にソースコード

ソースコードインタフェース例
ソースコードインタフェース情報[InfoType]

名称

TASK

タスク情報インタフェース

DATA

通信情報インタフェース

INFO

詳細情報インタフェース

REDUCT

リダクション情報インタフェース

これらが表す情報について，詳細を以下で説明する。

インタフェースとスケジューリング結果情報を並列コード生成部で読み込み，並列化コードを生成する。図 3.1(1) タスク情報インタフェース

は各解析フェーズが共有リソースであるソースコードイ

タスク情報インタフェースにより表現することが出

ンタフェースを読み込んで解析を行い，その結果を共有

来る情報は以下の通りである。

リソースに戻している関係を表している。

タスクブロックの識別子

従来は並列化のための情報は，タスクの情報を表すソ

タスクブロックのタイプ

ースコードインタフェース，通信データに関する情報をタスクブロックの実行時間持つ通信情報インタフェース，DOALL ループに関する

タスクブロックの大きさ

詳細な情報，スケジューリング結果といった個別のファタスクブロック間の先行制約

イルに分かれていた。本論文では，ソースコード上でこタスクブロック間のデータ通信時間

れらのインタフェースが一元管理できるように情報を統タスクブロックの処理プロセス数

合し，並列化のための情報をすべてソースコード上のプ

これらの情報を表現するプラグマディレクティブのラグマディレクティブに反映することを提案する。

フォーマットは図 3.3 で示すとおりである。

その結果，最終ステージで生成されるスケジューリン

図 3.3 のフォーマットでは，”( Bid ET BT Op PN)”

グ結果を除く，すべての情報の受け渡しはソースコード

で表されているのが，個々のタスクブロック情報であインタフェースを通して行われる。以下で共有リソース

り，”( DN ( Did CT )の変更点について述べる。

の先行制約情報を表している。各要素の詳細は以下で…)”はそのタスクブロックへ説明する。“BT”で表されるタスクブロックのタイプ
3.2 共有リソースの変更点には BASIC・LOOP・SELECT・FUNC がある。BASIC

3.2.1

タイプのタスクブロックは定義している他のブロック

ソースコードインタフェースと変更点

タスクブロックは解析対象のソースコード中にプラグタイプ以外のブロックすべてが当てはまる。LOOP タ

マディレクティブを挿入することで表現される。プラグ

イプのタスクブロックはそのブロックが for や while

マディレクティブは#pragma acpt [ InfoType ] ( … )の文であることを意味する。SELECT タイプのタスクブ

ように記述され，[InfoType]の表記によってどの情報をロックは if 文などの制御文を意味する。そして FUNC表しているかを識別する。図 3.2 はソースコードインタ

タイプのタスクブロックはユーザ定義関数の呼び出し

フェースの例で InfoType の表記とその情報の名称は表であることを意味し，ライブラリ関数の呼び出しは

3.1 のようになっている。

FUNC タイプを持つことはなく BASIC タイプに該当
する。

－37－

タイプのタスクブロックに対するタスク情報インタフ

フォーマットェースの例である。この例ではタスクブロック４が 2#pragma acpt TASK ( Bid ET BT Op PN )つの先行するタスクブロック２と３を持つ事を示して( DN ( Did CT ) …)いる。この場合は，タスクブロック２で書き込まれた
変数 b とタスクブロック３で書き込まれた変数 c をタ

各要素の説明スクブロック４が読み込むため，このような形で先行

Bid: タスクブロック識別子

制約が表されている。タスクブロック５では，ユーザET: 実行時間定義の関数が呼ばれ，関数名が func1 であることを表BT: タスクブロックのタイプわしている。

Op: オプション

PN: 使用プロセス数

DN: 直接先行ブロック数

Did: 直接先行ブロック識別子

CT: 直接先行ブロックとの通信時間

図 3. 3

a=9;
b=0;
c=3;
d=b*c;
func1( );#pragma acpt TASK ( 1 JOB() BASIC 1 ) ( 0 )a=9;#pragma acpt TASK ( 2 JOB() BASIC 1 ) ( 0 )b=0;#pragma acpt TASK ( 3 JOB() BASIC 1 ) ( 0 )c=3;#pragma acpt TASK ( 4 JOB() BASIC 1 )( 2 ( 2 … ) ( 3 …. ) )d=b*c;#pragma acpt TASK ( 5 JOB() FUNC func1 1 ) ( 0 )func1( );タスク情報インタフェースのフォーマット

次に，オプション情報である“Op”はブロックタイ
プ別に必要な情報を追加するためのものである。例えば ， LOOP タ イ プ の タ ス ク ブ ロ ッ ク に は そ れ がDOALL か DOACROSS か，といった情報やイタレー

図 3. 4

ションの繰り返し回数が記述される。また FUNC タイ
プでは呼び出される関数名が記述される。

タスク情報インタフェース例 1

for( i=0; i<100; i++ ){array[i] = array[i] + 2;
Data[i] = array[i] * 5;}

使用プロセス数はタスクブロック内部を処理するプ
ロセス数を表し，タスク粒度解析と部分タスクスケジューリングによって記述される。
“ET(実行時間)”や“CT(先行制約のブロックとの通信時間)”は実行時間解析時に情報が追加される。そして，“DN”や“Did”は，並列性解析時に得た先行ブロック数と先行ブロック識別子情報がそれぞれ表される。このとき，“( Did CT )”は先行ブロック数“DN ”の個数分だけ列挙される。
具体的なタスク情報インタフェースの例を図 3.4 と図 3.5 に示す。実際には，他の情報インタフェースも#pragma acpt TASK ( 5 JOB() LOOP DOALL 100 1 )( 1 ( 1 …) )#pragma acpt + Block Start
for( i=0; i<100; i++ ){#pragma acpt TASK ( 5-1 JOB() BASIC 1 ) ( 0 )array[i] = array[i] + 2;
#pragma acpt TASK ( 5-1 JOB() BASIC 1 )( 1 ( 5-1 COMM() ) )Data[i] = array[i] * 5;}#pragma acpt + Block End

記述されるが，この例ではタスク情報インタフェース

図 3. 5以外は省略している。図 3.5 で使用されている#pragma

タスク情報インタフェース例 2

acpt + Block Start と#pragma acpt + Block End は，

図 3.5 は BASIC と LOOP に対するタスク情報イン

複数のステートメントを囲む場合やマクロタスクブロ

タフェースの例である。タスクブロック 5 を見ると，

ックの有効範囲を表わし，ネストされた形で表すこと

LOOP タイプのタスクブロックとして判定されていができる。また，各タスクブロックの実行時間と通信ることが分かる。また並列性解析により，このループ

時間がそれぞれ JOB()と COMM()となっているが，こ文が DOALL 処理可能で，イタレーション数が 100 回

れらは実行時間解析時に各タスクブロックの実行時間であるという情報が付加されている。

とタスクブロック間の通信時間に自動的に置換される(1-1)

ことになる。

“PN”で表される数はマクロタスク内部を処理するプ

図 3.4 は BASIC タイプのタスクブロックと FUNC

使用プロセス数の追加

ロセス数である。並列性解析後のタスク情報インタフ－38－ェースには，どのタスクも１プロセスで処理されるよ，“Block End”の
スクの範囲は“Block Start Merge”

うになっている。

記述で示す。“Ignore”の表記は実行時間が計測済みのタスクであることを示している。

階層的に，マクロタスク内部の部分タスクスケジューリングを行った結果から使用プロセス数が置き換え

a=9;
b=0;
c=3;
d=b*c;

られ，この数をもとにマクロタスクをスケジューリン
グする。階層的にスケジューリングを行うため，割り当てプロセス数が足りない場合などは，内部のマクロタスクでの使用プロセス数を調節し，最適なプロセス

並列性解析後のタスク情報

else 文を表す。SELECT ブロックの実行時間には IF，#pragma acpt TASK ( 1 JOB() BASIC 1 ) ( 0 )a=9;#pragma acpt TASK ( 2 JOB() BASIC 1 ) ( 0 )b=0;#pragma acpt TASK ( 3 JOB() BASIC 1 ) ( 0 )c=3;#pragma acpt TASK ( 4 JOB() BASIC 1 )( 2 ( 2 … ) ( 3 …. ) )d=b*c;

ELSE_IF，ELSE ブロックそれぞれの実行時間を比較

粒度解析後のタスク情報

し，実行時間がもっとも大きい値をとる。図 3.6 のよ#pragma acpt TASK ( 1 JOB() BASIC 1 ) ( 0 )#pragma acpt +Block Start Merge#pragma acpt TASK ( 1-1 4 BASIC 1 ) ( 0 ) Ignore
a=9;#pragma acpt TASK ( 1-2 4 BASIC 1 ) ( 0 ) Ignore
b=0;#pragma acpt TASK ( 1-3 4 BASIC 1 ) ( 0 ) Ignore
c=3;#pragma acpt TASK ( 1-4 4 BASIC 1 )( 2 ( 1-2 … ) (1- 3 …. ) ) Ignore
d=b*c;#pragma acpt + Block Endの割り当て数を解析するために使用される。
(1-2)

SELECT ブロックの変更点

制御文全体を SELECT ブロックとし，内部に IF，

ELSE_IF，ELSE ブロックとして，それぞれ if, else if,

うに SELECT ブロック内部のタスクである，タスク
1-1 とタスク 1-2 を比較したとき，大きい値がタスク１の実行時間に置き換えられる。これは部分的には最長の処理を行うケースでの最短の並列処理時間を求めるためである。
if ( i == 2 ){…
} else{…
}#pragma acpt TASK ( 1 300… SELECT… 1) ( … )

図 3.7
(2)

融合されたタスク情報例

通信情報インタフェースと変更点
通信情報インタフェースとは，並列化を考える際に#pragma acpt + Block Start

必要となるデータの流れを表すものであり，タスク間#pragma acpt TASK ( 1-1 10… IF … 1) ( … )の先行制約を通るデータの流れが表現されている。記#pragma acpt + Block Start

述される具体的な内容は以下の通りである。

if( i == 2 ){データパック通信を行うデータ情報…

送信タスクブロック識別子}

通信のタイプ#pragma acpt + Block End

通信されるデータの詳細#pragma acpt TASK ( 1-2 300… ELSE …1) ( … )並列性解析時に見出された依存元タスクブロック#pragma acpt + Block Start

識別子と依存先タスクブロック識別子

else{

図 3.8 は通信情報のフォーマットを表している。

…

“ ( SendBid … )”は PackDataCount 分だけ記述}“（ CommSet ）…”は CommSetCount のされる。

#pragma acpt + Block End

個数分だけ列挙されることを意味している。
このインタフェースは送受信を行うタスクブロック

図 3. 6(1-3)

新しい SELECT タイプのブロック表現例

識別子と並列性解析時に見出されたタスクブロック識
別子の両方を表現している。例えば LOOP タイプのマ融合されたタスク表現の追加

図 3.7 はタスク粒度解析によってタスクを融合してクロタスクブロックのように，その内部へ依存が存在いく様子を表わしている。融合されたタスクは新たなする場合，実際にデータ通信を行うのはそのループ文

タスク番号が割り振られ階層が深くなる。融合後のタが開始される直前でなければならない。もし，そのル

－39－

がある。
フォーマット

通信データ情報とは，ある先行制約を流れるデータの詳細な情報を持つもので，変数名やその個数，配列#pragma acpt DATA( PackDataCount ( SendBid
CommType

データ中の参照開始位置，ポインタの情報などを含ん

DataInfo

でいる。

CommSetCount （ CommSet ）… ）… )#pragma acpt DATA (…

従来は別ファイルとして扱われていた通信情報インタ)

フェースは，タスク情報インタフェースからどのタス…

クの情報かを識別できるため，受信側のタスク識別子
情報は不要となった。また，通信データの数は連続し各要素の説明て記述することでその個数が分かり，通信データが存

PackDataCount : パックを行う通信データの個数
SendBid: 送信側タスクブロック識別子

CommType: 通信のタイプ

DataInfo: 通信データ情報

DataName :DataType

在しない場合には“０”が記述される。
なお，データパック通信を考慮できるように変更を行ったため，複数のデータをパックして送受信を行う
データの情報の数を PackDataCount が示している。

変数名

PackDataCount の数が２以上であればパックを行っ: 変数の型（C 言語と同じ変数の型）

PointerDim :ポインタの次元数

DataCount :通信データの個数

DataIndex

通信データ DataName からの位置:て通信を行う。
(3)

詳細情報インタフェース
並列化の際に必要となるタスクに関する詳細な情報を含み，それはタスクタイプごとに異なる情報が記述(スカラ変数は0)

CommSetCount: CommSet の個数される。現在，詳細な情報を持つ LOOP タイプのタス

CommSet : 並列性解析時のタスクブロック情報

クにのみ記述される。LOOP タイプのタスクには，ル: 依存元タスク識別子

ープ回転インデックス，初期値，終了値，増減幅など

DestBid : 依存先タスク識別子が記述される。特に，DOALL タイプのループを並列

SrcBid化する際に使用される。
図 3. 8

通信情報インタフェースのフォーマット

(4)

リダクション情報インタフェース
リダクション操作を望むループに，どのようなリダープ文の内部で受信操作を行ってしまうと，ループのクションを行うかを指示する情報が含まれる。簡単な

回転数分だけ受信操作を繰り返してしまうことになり

リダクションループであれば並列性解析によって解析

並列コードとして正しくない。同様に，マクロタスクされる。また，ユーザによる指示も可能であるようなブロック内部から外部に向かって依存が存在する場合

フォーマットを意識し，“（ 演算子 : 変数名 : 変数デにはそのマクロタスクブロックの終了直後にデータのータ型 ）”で表される。
現在，特に詳細情報がある LOOP にのみ有効であり，送信が行われる。そして，マクロタスクブロックはそ

情報があるときのみ記述可能である。

の処理を複数のプロセスにより並列に実行される可能性が高い。その際にデータの送受信をどのプロセスが3. 2. 2

従来は，タスク融合が行われるタスクグループ情報と行うのかということを明確に表現するためにも並列性解析による依存情報が記述されることになる。

スケジューリング結果情報と変更点処理するプロセス番号，処理順序の情報が記述されてい通信のタイプは 2 つあり，並列性解析時にフロー依た。しかし，3.2.1 節(1-3)で述べたように本論文では，融存(RAW)を持つものは COMM，逆依存(WAR)や出力

合情報はソースコードインタフェース上に記述されるた

依存(WAW)を持つものは BARRIER という分類を行め，含まれないように変更された。

っている。通信タイプが COMM の場合，異なるプロ
セスで処理される場合データ通信が起こる。通信タイ

ここでは部分タスクスケジューリングおよび，全体タ
スクスケジューリング結果が記述される。

プが BARRIER の場合は，異なるプロセスで処理される場合はローカルな情報の変更が起こらないため通信は起こらず，同一プロセス上で実行されるように割り当てられた場合のみ，実行順序を逐次と合わせる必要－40－

４．並列化コード生成フェーズの概要

なるため，データバッファを全通信の中で最大通信デー“MPI_Pack_size”をタサイズだけメモリを割り当てる。
使用するので MPI の初期化処理を行うときにバッファ

従来の並列化コード生成部で行っている処理と，新た領域を確保する。これは図 4.6 のように，MPI の初期化に追加したコード生成処理について説明する。

を行う関数内で最初に１回だけ処理される。
4. 1

従来の並列化コード生成

P0

P1

P2

は，各タスクブロックが処理する実行プログラムコード

1

2

3

を MPI を用いて SPMD 型プログラムモデルとして記述

COMM

通信命令には，処理プロセスが複数あるため，通信情報

if( MyRank==0 ){…… /* タスクブロック 1*/
MPI_Send( &X, … … 1 … … );}if( MyRank==1 ){……/* タスクブロック 2*/}if( MyRank==2 ){……/* タスクブロック 3*/
MPI_Send( &Y, … … 1 … … );MPI_Send( &Z, … … 1 … … );}if( MyRank==1 ){MPI_Irecv(&X,..0 ,reQuest );MPI_Irecv(&Y,..2,reQuest+1 );MPI_Irecv(&Z,..2, reQuest+2 );MPI_Waitall( 3 , reQuest, ….);……/* タスクブロック 4*/

インタフェース上に記述された依存関係から適切なプロ}

従来のプロセスランク別の処理コード生成フェーズで

COMM

COMM

するには，プロセス識別子であるランク番号を用いて各タスクブロックの割り当て制御を行えるように処理コー

4ドを記述される。
また，１対１通信命令には，送信側はブロッキング命令である“MPI_Send”命令，受信側はノンブロッキン(a)

グ命令である“MPI_Irecv+MPI_Waitall”を使用してデータ通信が行われる。特に，マクロタスクブロック間のセスへと通信がおこなわれるようになっている。

(b)

そして，DOALL ループは配列のブロック分割，リダ

図 4. 4

従来のタスクブロック間通信例

クション演算を行い，可能であれば各イタレーション内部も並列に実行されるようになっている。
if( MyRank==0 ){…… /* タスクブロック 1*/
MPI_Send( &X, … … 1 … … );}if( MyRank==1 ){……/* タスクブロック 2*/}if( MyRank==2 ){……/* タスクブロック 3*/
MPI_Pack( _static_Pack_buffer,…, );MPI_Pack( _static_Pack_buffer,…, );MPI_Send( _static_Pack_buffer, … … 1 … … );}if( MyRank==1 ){MPI_Irecv( &X,..0 ,.. reQuest );MPI_Irecv( _static_Pack_buffer,..1 ,.. reQuest+1 );MPI_Waitall( 2 , reQuest, ….);
MPI_Unpack(_static_Pack_buffer, … );MPI_Unpack(_static_Pack_buffer, … );……/* タスクブロック 4*/

従来の並列化コード生成部についての詳細は，参考文
献 3)を参照してもらい，ここでは省略する。
4.2

拡張した並列化コード

並列コード生成において新たに，パック・アンパックを使用した通信コード，連続した DOALL ループに関する扱いを加えた。
4. 2. 1

パッキング通信

タスクブロック間で通信するデータが複数ある場合，従来のタスクブロック間 1 対 1 通信は図 4.4 に示すとおりである。(b)のコードセグメントで P2 から P1 への通信が行われているとき，通信するそれぞれのデータに対}して個別に通信処理を行っている。しかし，並列処理に(b’)

図 4. 5 パック・アンパックを使用した１対１通信コード

おいて通信回数の増加はオーバヘッドの増加につながる。
また，タスクスケジューリングでは(a)のタスクグラフを生成するためこのようなコードは正しくない。同一プロセッサ間での複数データの通信には，MPI などの並列化言語で実装されているパック・アンパック処理を使用することで通信回数が最適化される。図 4.6(b’)が新たに，
パック・アンパックを考慮して生成されたコードセグメ
ントである。

void MPI_Initialize_acpt(int argc, char **argv){/* 初期化関数 */MPI_Pack_size( … , …&_Pack_memSize )_Pack_memMax += _Pack_memSize;…
_Pack_buffer = malloc( _Pack_memMax );}図 4. 6

パック・アンパックのためのデータバッファが必要と－41－

初期化関数内に記述されるパッキング
データバッファ領域確保を行うコード

DOALL ループのデータの分散・集約

ここで，評価に使用したプログラムは 48 ノード構成の

従来の並列化コード生成フェーズでは，DOALL ルー

PC クラスタ上で実行した。各ノードはすべて CPU にプ前後ではデータの分散・集約を行っている。ここでは，Pentium4 (3.0 GHz)，メモリに 512MB，LAN に Gigabit

分散・集約を行う通信データが複数ある場合，パッキン

Ether の性能を持つ。各ノードの相互接続にはギガビッ

グ通信を行うように変更した。特に配列データを含む場

トスイッチングハブを用いている。

4. 2. 2

この環境下で，今回評価に使用したプログラムを 8 プ

合は，単一データに加えブロック分割した配列データを
それぞれのプロセスにまとめて分散・集約するようなコロセッサで実行した。

ードとなる。
4. 2. 3

5. 1

連続した DOALL ループの扱い

並列化コード

図 4.7 のように先行制約のタスクブロックも DOALL

図 5.1，5.2 でそれぞれの並列化コード生成によって生ループであり，内部を１プロセスで処理し，同じプロセ成された評価プログラム中のある DOALL ループのデスのグループによって処理されるような DOALL ルー

ータ分散コードを例に示す。

プではデータの集約，分散を行わないように２つのPCG１は美濃本氏によって考えられた並列コード生
３）

DOALL ループを融合する。データの分散・集約は次の成

タスクがどのよう場合でも安全なコードとして動作する

通信を考慮したもの，PCG1.2 は PCG1.1 に加え連続しによるもの，PCG1.1 は PCG1 に加えてパッキング

ためには必要な処理である。しかし，DOALL ループでた DOALL ループ融合を考慮した並列化コードを表わのデータの分散・集約の通信にかかる時間は大きく，こしている。なお，PCG1.2 では連続した DOALL ループのようなパターンの場合削減できるところは削減すべきと判断されたため，データ分散コードが記述されることと考える。

はなかったため省略する。

なお，タスク融合が現在，BASIC タイプのタスクの融合のみしか考慮していないため，暫定的な融合を並列…

コード生成部で行っている。

if ( _Sub_Rank_000==0 ) {/* X0 と X1 の送信 */MPI_Send( X1+1250000, 1250000, ..., 1, ..., ...);MPI_Send( X1+2500000, 1250000, ..., 2, ..., ...);…
MPI_Send( X0+7500000, 1250000, ..., 6, ..., ...);MPI_Send( X0+8750000, 1250000, ..., 7, ..., ...);}
if ( _Sub_Rank_000!=0 ) {/* X0 と X1 の受信

タスク

MPI_Irecv( X1+(_Sub_Rank_000/1)*1250000,...,…);

通信

MPI_Irecv( X0+(_Sub_Rank_000/1)*1250000,…,…);

依存

図 4. 7*/

MPI_Waitall( 2, _mPi_request, _mPi_status );}連続した DOALL ループの例_LpStart_000=(_Sub_Rank_000/1)*1250000,_LpEnd_000=(_Sub_Rank_000/1)*1250000+1250000;

５. 評 価for( i=_LpStart_000; i<_LpEnd_000; i=i+1 ) {DATA[i] = X0[i]*X0[i];評価対象として台形法を用いた積分計算プログラムの自動並列化コードを生成した。最終的な積分値が解析対...

象コードを逐次実行した結果と同じになっていることか

DATA[i] = DATA[i] + 2.0*X1[i];ら正しく並列化されたことが確認できた。その上で，並DATA[i] = DATA[i]*h/2;} 図 5. 1

列化コード生成部で考えた並列化コードを生成し，それぞれの実並列処理時間を計測した。

－42－

PCG1 によるデータ分散コード

６．終わりに…
if ( _Sub_Rank_000==0 ) {/* X0 と X1 のパック */6. 1

MPI_Pack(X0+1250000*0, 1250000,…,…);

マクロタスクを考慮した流れへと変更したことで，精MPI_Pack(X1+1250000*0, 1250000,…,…);

度の高いタスク粒度に関する情報が表わされるようにな…

った。また，今回のように，共有リソースを一元管理す}ることで解析間での情報の交換がスムーズにいくと考え/*パッキング通信*/られる。

MPI_Scatter(static_Pack_buffer,…, …);
if ( _Sub_Rank_000!=0 ) {並列化コード生成部では，このステージでしか解析で/* X0 と X1 のアンパック */きないような DOALL ループの融合処理を行うことで

MPI_Unpack(static_Pack_buffer, …, …);

大幅な処理時間の向上をすることができた。パッキング

MPI_Unpack(static_Pack_buffer, …, …);

通信は残念ながら期待した効果を得ることはできなかっ}たが，パッキング通信の必要性は明らかなので必要な機_LpStart_000=(_Sub_Rank_000/1)*1250000,

能であると考えられる。

_LpEnd_000=(_Sub_Rank_000/1)*1250000+1250000;
for( i=_LpStart_000; i<_LpEnd_000; i=i+1 ) {6. 2

DATA[i] = X0[i]*X0[i];●...

今後に向けて効率のよい通信コードの生成

MPI の関数にはその汎用性や移植性から，内在するソ

DATA[i] = DATA[i] + 2.0*X1[i];フトウエアオーバヘッドが大きいことが分かっている。4)DATA[i] = DATA[i]*h/2;

従って，同じ動作をする通信コードではなるべく関数の}呼び出しを少なくする必要がある。

図 5.2 PCG1.1 によるデータ分散コード
5. 2

まとめ

●

処理時間

ユーザの知識を利用する方法の検討 2)

共有リソースの一元化をした結果，一方でタスクの情表 5.1 並列化コード処理時間

（sec）

逐 次

P C G １P C G １ ． １

P C G １ ． ２

0 .4 2 0

3 5 .73 6 .10 .0 5 7 5報を開発ユーザが読解するには情報が多すぎるため可読性が低い。今後，より詳細な並列化情報をソースコード
上に記述しかつ，その情報を開発ユーザがわかりやすい形で表現することは困難である。
また，実際には最適な並列化コードの候補がいくつも

各並列プログラムを実行した処理時間を表 5.1 に示す。

ある場合がある。また，開発ユーザが目的とした環境にPCG1.1 では，パッキング通信による高速化がみられよっても意図するコードが異なる。生成コードの候補をなかった。すなわち予想した通信回数の減少による通信選択できるようにすることも重要である。

を行う際のオーバヘッド時間の減少効果が得られなかっ今後は，開発ユーザと，システム全体とのインタラク

た。これは今回使用した PC クラスタ環境のスイッチのティブな関係を構築するためのツールが必要と考える。

性能がよかったためではないかと考える。従って，パッ

これは，共有リソースを基にしたコード生成に開発ユー

キングによる処理時間の向上はマシン環境によっては十ザからのアプローチを並列化コードに反映させるもので分効果的と考えられる。

あり，例えば，最適な通信コードの候補からの生成されPCG1.2 では，DOALL ループの融合によるデータのる通信の選択，また，タスク粒度・スケジューリング結

分散・集約の通信時間削減によって逐次処理に比べて果の手動での調整を可能にする機能などが考えられる。

13%の処理時間まで減少した。これは，いくつかある

DOALL ループのうち開始と終了時に行っていたデータ●の分散・集約のための通信命令が削除されたためである。

並列性の強化，特に制御依存による曖昧性の削減
制御依存の曖昧性により通信のパスを一意に決めることが出来ない現状となっている。より並列性解析時の動的解析などにより制御依存への対応を強化していくべき
だろう。

－43－

●

3) 美濃本

ポインタ変数に対する並列化

宗徳. 「C 言語自動並列化トランスレータの開発」. 成蹊大学理工学研究報告, Vol.42,

分散メモリアーキテクチャ上で通信処理をする以上各No.1, pp.41-49，2005 年 6 月

プロセス内でのメモリアドレス空間は異なるものとなる。
このようなアーキテクチャに対応したより詳細なポイン

一浩, 甲斐

4) Hirotaka Ogawa : “OMPI: Optimizing MPI programs

using Partial Evaluation”, ACM/IEEE Supercomputing

タ解析を行う必要がある。

Conference , 1996 年
より多くの DOALL ループタイプの並列化●

5) “Message Passing Interface Forum -MPI2-” ,DOALL ループの並列化に関しては単純に DOALL 処

http://www.mpi-forum.org/ ,2007 年 03 月現在参照可

理可能であるからといって単にループのイタレーション

6) “The Message Passing Interface (MPI) standard” ,を分割すればよいだけではない場合も多々ある。このよ

http://www-unix.mcs.anl.gov/mpi/ ,2007 年 03 月現在

うな場合に備え，ループ文の持つ固有の情報の取得，内参照可

部で使用される配列のアクセスパターンなどの詳細な解

7) Gropp, Lusk, and Skjellum : “Using MPI second

Edition” , MIT Press , 1999 年

析が必要となるだろう。

8) Gropp, Lusk, Thakur : “Using MPI2”, MIT Press ,参考文献

1999 年
9) 平林雅英 : “ANSI C 言語辞典”, 技術評論社, 1997 年

1) TOP500, http://www.top500.org/ , 2007 年 03 月現在参照可2) 平成 13 年度 アドバンスト並列化コンパイラ技術報
告書（概要編）, 財団法人日本情報処理開発協会－44－