成蹊大学理工学研究報告
J. Fac. Sci. Tech., Seikei Univ.
Vol.42 No.1 (2005) pp.41-49

C 言語自動並列化トランスレータの開発
美濃本 一浩＊1，甲斐 宗徳＊2

Implementation of Automatic Translator from C Programs to Parallel Programs using MPI
Kazuhiro MINOMOTO＊1, Munenori KAI＊2
ABSTRACT : The work of automatic parallelization can be divided and considered on each stage, that is,
the parallelism analysis of a source program, execution-time analysis, task grain-size analysis, taskscheduling, and parallelized code generation. Although there was the result of research individual about
each stage, unifying and treating them to one was not realized. Then, in developing an automaticparallelization translator, we proposed and implemented the common resource for summarizing all theanalysis stages as a series of flows. A common resource plays the role which tells the result of eachanalysis stage of a C automatic parallelization translator as an input of the next analysis stage. A
parallelized code can be automatically generated now from a source program using this common
resource. As a parallelized code, MPI, which is a message communication library of the present industry
standard, is used. The contents of the common resource were changed into the suitable communicationcommand using MPI, and parallelization in a DOALL loop and a block were performed. Moreover, theanalysis stage which takes the lead for fully improving parallel processing performance, and the tuning
method in parallel code conversion, etc. are clarified.
Keywords : Parallelism Analysis, Parallelized Translator, Task Scheduling, Parallel Processing, MPI(Received March 25, 2005)

１．はじめにのスケジューリング作業などを行わなければならない。
ところが，その作業にはアプリケーションの内部構造お

1. 1

背景

よび処理システムのアーキテクチャなどの知識が要求さコンピュータの性能向上の手段としてマルチプロセッ
サシステムが有効であることは，近年のスーパーコンピ
ュータの多くに利用され，高い性能を実現しているれるため，マルチプロセッサシステムの有効利用という点で大きな障害になっている。

1)

ことからも明らかである。そして，プロセッサ単独での速

1. 2

研究目的

度向上も限界に近づきつつあることを考えると，マルチ

上記のような問題点を解決するための手段として，自プロセッサシステムは今後もより一層重要な基盤技術に

動並列化コンパイラの利用が挙げられる。しかし，マル

なっていくであろう。

チプロセッサシステムの性能を十分に発揮させることがしかし，マルチプロセッサシステムには，並列性と効できず，プログラムの実行性能をかえって低下させてし率を考慮したプログラムでないとその優れた性能を十分まう傾向を示している 2 )，というのが現状である。そこに引き出せないという側面もある。故に，プログラムをで，プログラム内にある単純なループの並列性のみを抽

並列処理向きに作成する必要があり，それには並列性の出するような単一粒度を対象とした並列化を行うのでは抽出作業や，処理すべきタスクの実行順序を決めるためなく，関数や関数を含んだループ及びループ間などの粗＊1

情報処理専攻大学院生＊2
情報処理専攻助教授(kai@st.seikei.ac.jp)
Associate Professor, Dept. of Information Sciences

粒度の並列性や，細粒度であるステートメントレベルの並列性を引き出すことも，今後の自動並列化コンパイラには望まれている 3 )。

−41−

本研究では，実用的な自動並列化コンパイラが存在しいた C 言語プログラムの自動並列化トランスレータの開ていない C 言語に対してそのような複数粒度の並列化を発を行う。ここでのトランスレータとは C 言語で書かれ行うことで，プログラムの実行性能の向上を図る自動並

たソースプログラムを MPI を用いた C 言語ベースのプロ

列化 C コンパイラの完成を最終目的としている。

グラムへと変換することである。実行時には生成された
ソースプログラムを MPI ライブラリと合わせてコンパ

２．自動並列化 C コンパイラ

イルし，実行ファイルに直してから実行する。MPI を用いることでより汎用性・移植性の高いコード生成が出来

自動並列化 C コンパイラとは，C 言語で記述されたソる。動作環境としては分散メモリアーキテクチャ上を想ースプログラム内に存在する並列性を抽出し，それを活定している。プログラムモデルとしては Single Program

用することで自動的に並列実行コードを生成するものでMultiple Data(SPMD)型での自動生成を行う。

ある。本研究で開発する自動並列化 C コンパイラの全体

MPI は，現在の業界標準のメッセージ交換用のライブ
ラリである。マルチプロセッサ上で並列に実行することに伴い，シングルプロセッサでは必要のなかったデータ

ソースプログラム

通信処理を加えなければ正しい答を導き出せなくなる。
この不足分を補うために必要最小限度，通信を介してプ

並列性解析

ロセッサにローカルなメモリにあるデータのやり取りをする。この通信の機能とその呼び出し方法を規定してい実行時間解析

るのが MPI である。MPI は規格であり，MPI フォーラムという会議によって規格されている。
メッセージパッシングによるプログラミングは基本的

タスク粒度解析に分散メモリアーキテクチャのためのモデルである。
並列計算でのモデルには図 2.2 に示されるように
タスクスケジューリングSPMD( Single Program Multiple Data ) 型 と MPMD
( Multiple Program Multiple Data )型が存在する。SPMD 型
プログラミングモデルというのは図 2.2(a)で表されてい並列コード生成るように一つのプログラムで並列処理を記述するもので
図 2.1

自動並列化 C コンパイラの処理の流れある。MPMD 型プログラミングモデルは図 2.2(b)で表されるように複数のプログラムを協調的に動作させて並列的な処理の流れを図 2.1 に示す。

処理を行うものである。また MPI を用いた並列処理では初期段階の作業として，解析対象となるソースプログ

各プロセッサ上にプロセスを生成し処理を並列に行う。

ラムの実行時間解析と並列性解析を行う。並列性解析でその際には各プロセスを識別する必要がある。MPI ではは，プログラム内に存在するプログラムの一行(以下，ス

各プロセスの識別を行うためにランクという番号が 0 番

テートメント)レベルでの並列性を抽出する。実行時間解

より順々に割り振られる。

析では，ステートメントごとの実行時間を求める。
次の段階の作業として，タスク粒度解析とタスクスケ

exe
file

ジューリングを行う。タスク粒度解析では，実行時間解

実行ファイルexe
file1

析と並列性解析から得られた結果に基づき，各タスクを異なる実行ファイルexe
file2

どのような大きさでプロセッサに割り当てれば効率のよい並列処理を行えるのかを考慮してタスク粒度を決める。
タスクスケジューリングでは，それら処理すべきタスク

exe
file

exe
file

exe
file

集合をどのように各プロセッサに割り当て，どのような

CPU0

CPU1

CPU2

順序で実行すればよいのかを決める。
(a) SPMD 型

最終段階の作業として，ターゲットマシンにおいて優図 2.2

れた実行性能を実現するような並列実行コードの自動生成を行う。
本研究では，Message Passing Interface(以下，MPI)を用

−42−

exe
file1

exe
file2

exe
file2

マスタ

スレーブ

スレーブ

(b) MPMD 型

プログラミングモデルの例

３．共有リソースとインタフェース

3. 1. 1

ソースコードインタフェース

ソースコードインタフェースの内部ではタスクブロッ
昨年度までは図 2.1 に示した各解析フェーズにおいて，

クと呼ばれる単位で情報が表現されている。タスクブロ

各々の解析結果は後の解析に対して適した形とは言えなックとは並列コード生成時に各プロセスが実行する最小

かった。そこで各解析間に連携を持たせ，一つの流れと単位であり，最小の粒度としてはプログラムのステート

して仕上げることを考えた。そのためには，全ての解析

メントと等価な物である。このタスクブロックは解析対間で使用できるリソースの共有が必要である。その共有

象のソースコードに#pragma ディレクティブを挿入する

可能なリソースをインタフェースとして，各解析は情報ことで表現される。#pragma ディレクティブとはプリプを追加していく。そして本年度の最終形である MPI コー

ロセス命令であり，処理系の実装に依存した方法で指示ドの自動生成を行う。以下に共有リソースの詳細とそのを出すことが出来る。#pragma ディレクティブは各ベン共有リソースを使用する各解析間でのインタフェースとダにおいても独自の形で多々利用されている。本年度のしての使われ方について説明する

研究では

3. 1

である C 言語並列化トランスレータの略称である。

#pragma acpt で始まる #pragma ディレクテ

ィブを用いている。#pragma に続く acpt は本研究の題目
共有リソース

共有リソースは 2 つあり，一つはソースコードインタ

ソースコードインタフェースを用いることにより表現

フェースであり，もう一つは通信情報インタフェースですることが出来る情報は以下の通りである。

ある。この 2 つのリソースは並列性解析の結果により生l

タスクブロックの区間情報成される。そして実行時間解析，タスクスケジューリンl

タスクブロックの識別子

グやタスク粒度解析時に読み込まれ，解析された情報をl

タスクブロックのタイプ

順々に追加していくことになる。最終的には全ての情報

l

タスクブロックの大きさを並列コード生成部で読み込み並列化のコードを生成すl

タスクブロックの実行時間

ることになる。図 3.1 は各解析フェーズが共有リソースl

タスクブロック間の先行制約

l

タスクブロック間のデータ通信時間

である 2 つのインタフェースを読み込んで解析を行い，その結果を共有リソースに戻している状態を表している。

これらの情報を表現する#pragma ディレクティブのフォーマットは図 3.2 で示すとおりである。 図 3.2 のフォーマットで記述されている“[*]” は，“Dct”の個数分だけ

ソースプログラム“( Src CT )” が繰り返されることを意味している。最初
共有リソース

並列性解析の小括弧で表されるのが，この#pragma ディレクティブ
により表される個々のタスクブロック情報である。そのソースコードインタフェース

実行時間解析

通信情報
インタフェース

タスク粒度解析

次に記述される小括弧はそのタスクブロックへの先行制
約情報を表している。各要素の詳細は以下で説明する。
BT で表されるタスクブロックのタイプには BASIC・
LOOP・SELECT・SELECT_ELSE・FUNC などがある。

タスクスケジューリング

フォーマット#pragma acpt ( Bid ET BT Op ) ( Dct ( Src CT )[*] )並列コード生成

各要素の説明図 3.1

共有リソースの利用

またタスク粒度解析・タスクスケジューリングフェーズ
では，共有リソースに対してコード並列生成になくてはならない重要なスケジュールや各タスクに対するプロセスの割り当ての情報が求められる。
次に共有リソースの 2 つのインタフェースについて説l

Bid : タスクブロック識別子lET : 実行時間lBT : タスクブロックのタイプ

l

Op : オプションl

Dct : 直接先行ブロック数l

Src : 直接先行ブロック識別子lCT : 直接先行ブロックとの通信時間明する。
図 3.2 ソースコードインタフェースのフォーマット

−43−

BASIC タイプは基本タイプであり，C プログラム内のfor( i=0; i<100; i++ ){array[i] = array[i] + 2;
Data[i] = array[i] * 5;}

全ての情報を表現することが出来る。LOOP タイプはそのブロックが C プログラム内の for や while 文であることを意味する。そして SELECT・SELECT_ELSE タイプ#pragma acpt ( 5 JOB() LOOP DOALL 100 … ) ( 1 ( 1 …) )#pragma acpt + Block Start
for( i=0; i<100; i++ ){#pragma acpt ( 5-1 JOB() BASIC ) ( 0 )array[i] = array[i] + 2;
#pragma acpt ( 5-1 JOB() BASIC ) ( 1 ( 5-1 COMM() ) )Data[i] = array[i] * 5;}#pragma acpt + Block End

はそれが if-then-else 文であることを示している。そして
FUNC タイプはそのステートメントが解析対象プログラム内にユーザが定義した関数の呼び出しであることを意味している。つまりライブラリ関数の呼び出し時にFUNC タイプを持つことはない。
次に，オプション情報である OP はこのブロックタイ
プ別に必要な情報が追加されることになる。特に LOOP

図 3.4 ソースコードインタフェース例 2タイプのタスクブロック時にはその LOOP のタイプをDOALL，DOACROSS といった情報や，イタレーション

図 3.4 はループ文である for 文のソースコードインタフの繰り返し回数，ループを並列実行する時の１イタレー

ェースである。タスクブロック 5 を見ると，LOOP タイ

ションに費やされるプロセス数，このプロセス数はタス

プとして表現されていることが分かる。その後このルー

ク粒度解析・スケジューリング時に追加される，が記述

プ文が DOALL 処理可能でありループのサイクル数がされる。また FUNC タイプでは呼び出される関数名が記

100 回であると記述されている。

述される。そして ET(実行時間)や CT(先行制約のブロッ

そして，図 3.3，図 3.4 両方にて表現されている#pragma

クとの通信時間)は実行時間解析時に情報が追加される。

acpt + Block Start と#pragma acpt + Block End は複数のス

具体的なソースコードインタフェース例を図 3.3 と図 3.4

テートメントを囲む場合や内部に複数のタスクブロックで示す。この図では各タスクブロックの実行時間と通信を持つ場合に利用される。

時間をそれぞれ JOB()と COMM()と表現しているがこの

3. 1. 2

通信情報インタフェース

部分には実行時間解析時に各タスクブロックの実行時間

通信情報インタフェースとは，並列化を考える際に必とタスクブロック間の通信時間として自動的に置換され要となるデータの流れを一元的に管理するものであり，ることになる。

ソースコードインタフェース上で表現される先行制約区

図 3.3 は先ほど示した BASIC タイプのタスクブロック

間を通るデータの流れが表現されている。記述される具のみで表現されるソースコードインタフェースである。

体的な内容は以下の通りである。

この例ではタスクブロック 3 が 2 つの先行するタスクブl

送/受信を行うタスクブロック識別子

ロック 1 と 2 を持つ事が読み取ることが出来る。この場

l

通信のタイプ合は，タスクブロック１で書き込まれた変数ｂとタスクl

通信されるデータの詳細

ブロック 2 で書き込まれた変数 c をタスクブロックが読l

実際に並列性解析時に見出された依存元タスクブ

み込むため，このような形で先行制約が表されている。

ロック識別子と依存先タスクブロック識別子
特に注意したいのは送受信を行うタスクブロック識別

a=9;
b=0;
c=3;
d=b*c;#pragma acpt ( 1 JOB()BASIC ) ( 0 )#pragma acpt + Block Start
a=9;
b=0;
#pragma acpt + Block End#pragma acpt ( 2 JOB()BASIC ) ( 0 )c=3;#pragma acpt ( 3 JOB()BASIC ) ( 2 ( 1 … ) ( 2 …. ) )d=b*c;

図 3.3 ソースコードインタフェース例 1子と並列性解析時に見出されたタスクブロック識別子の両方を表現しているところである。この情報は時に異なる。例えば LOOP タイプのタスクブロックのように内部にネストした形で内部にタスクブロックを持つものをこ
こではマクロタスクブロックと呼び，その内部へ依存のパスが張られる場合，実際にデータ通信を行うのはそのループ文が開始される直前でなければならない。もし，
そのループ文の内部で受信操作を行ってしまうと，ループの回転数分だけ受信操作を繰り返してしまうことにな
り並列コードとして正しくない。このことと同じ理由で，マクロタスクブロック内部から外部に向かって依存のパスが張られる場合ではそのマクロタスクブロックの終了直後にデータの送信が行われる。そして，マクロタスク−44−

４．並列コード生成

ブロックはその処理を複数のプロセスにより並列に実行される可能性が高い。その際にデータの送受信をどのプ
ロセスが行うのかということを明確に表現するためにも

並列コード生成は図 3.1 で示したように共有リソース

並列性解析による依存情報も記述されることになる。

を入力として並列コード生成が行われる。ここでは並列通信のタイプには 2 種類あり，一つは COMM であり，

コード生成フェーズについて順を追って説明する。

もう一つは BARRIER である。図 3.5 で表されるように
4. 1

この 2 つの通信のタイプには特徴があり，基本的には並タスクブロック融合とスケジューリングの決定

列性解析時に FLOW 依存(RAW)を持つものには COMM。

タスク粒度解析・タスクスケジューリングからの情報

逆 依 存 (WAR) や 出 力 依 存 (WAW) を 持 つ も の に はは MPI を用いた並列コード生成時になくてはならない

BARRIER というタイプで区別を行っている。通信タイ

必須の情報である。この情報がなければ解析したソース

プが COMM の場合，図 3.5(a)を例に取ると，タスクブロ

プログラムを最適なスケジューリングにより並列コード

ック１とタスクブロック 3 が仮に異なるプロセス上で実として生成することが出来ない。図 4.1 はタスク粒度解行されるのであるならばタスクブロック 1 はタスクブロ

析とタスクスケジューリングにより各タスクのスケジュック 3 へ変数 X を送らなければならない。もし同一のプーリングとタスク融合，プロセスへの割り当てが決定さロセス上であればその必要はない。通信タイプがれている状態を示している。図 4.1 は，(a)がタスクスケ

BARRIER の場合，基本的に MPI のように，分散メモリ

ジューリング・粒度解析前，(b)がタスクスケジューリン

アーキテクチャ上で動作する場合においてはそれが異な

グ・粒度解析後である。図 4.1 ではスクスケジューリン

るプロセス上で実行されたとしてもデータ通信や，プロ

グ・粒度解析の際にタスクが融合され，各タスクを処理

セス間での同期は起こらない。なぜならばタスクブロッ

するプロセスの識別子，P0,P1 など，が決定されている

ク 3 では新しく変数 X への書き込みを行うのであり，そことが分かる。図 4.1(b)で示されているどのタスクが融れまでに更新された変数 X の値を必要としないためであ合されたのかという情報や各タスクをどのプロセスで実る。また同一のプロセスで実行されるのであればタスク行すればよいのかという情報を並列コード生成は受け取

ブロック１はタスクブロック 3 の後に実行されることがり，その情報を用いてソースコードレベルでタスクブロ保証される。しかし，異なるプロセス上で実行されるのックの融合や処理プロセスの割り当てを行う。図 4.2 はであるならばタスクブロック 3 が先に実行される可能性

図 4.1 の(b)で示された結果から各タスクをスケジューリがある。タスクブロック 3 以降に変数 X への読み込み命

ング結果のままプロセスへ割り当てたものである。並列

令が発行されるとその読み込み命令先へタスクブロック

コード生成では図 4.2 に示しているような各プロセスへ

3 からのデータ通信が起こる。

のタスクの割り当てやプロセス間通信処理などを MPI通信されるデータの詳細はこの先行制約区間を流れる
データの詳細な情報を持つもので，内部には変数名やそを用いて記述する。この際 SPMD 型プログラムモデルで表現する。

の個数，配列データなどに備えた先頭の位置，ポインタ
0の情報などを含んでいる。

タスク
0,1,2 が融合

0’
1

Write(X) 1

タスク
ブロック

2

図 3.5

P0
P3

4

5

6

4

5

P0

2

6

P1, P2,P3. P4

7

Write(X)(a) COMM

3

3

Write(X)
1
orRead (X)

X

3
Read (X)

2

7

3
8

(b) BARRIER

P4
8

通信のタイプ

P４
(a)

図 4.1

−45−

(b)

タスクスケジューリング・粒度解析事例

プロセスが同じ事から，通信コードが(b)では挿入されて

プロセス

P0

時間の流れ
0’

いないことが分かる。送受信する際には送信時には相手

4

P1のランクを指定し，受信時には送信側のランクを指定す

5P2る。ここでは書かれていないがそのほかにも送受信時にはタグと呼ばれる各メッセージ通信を識別する値を指定5P3することになる。そして全ての通信が確実に行われるよ

6

3

P4

7

6

うに各メッセージに固有のタグを C 言語の列挙子型を用8いて実現している。この例では各タスクブロックが唯一

図 4.2 各プロセスへのタスクの割り当て例

つのプロセスにより処理される例を示した。
P0

P1

先に述べたように各タスクブロックが処理する実行プ

1

2

ログラムコードを MPI を用いて SPMD 型プログラムモデ

COMM

4. 2

プロセスランク別の処理コード生成

P1
3
COMM

COMM

ルとして記述するには，プロセス識別子であるランク番
号を用いて各タスクブロックの制御を行えるように処理

4

コードを記述すればよい。図 4.3 ではその例を示している。マクロタスクブロックのように複数のプロセスによ(a)

り実行される場合はプログラムとして記述する際にはif( my_rank==N || my_rank==M || …… )と制御間で論理和を取るように記述すればよい。

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

1Statement

2Statement

3

Statement

4

Statement

1Statement

2Statement

3

Statement

4}プロセス 3にて実行

タスクブロックの持つコードセグメント

図 4.3 プロセスランク別のコード生成例

図 4.4 タスクブロック間通信例 1
次に送受信時のタスクブロックがマクロタスクブロッ
クの場合の例を図 4.5 で示す。この場合あるタスクブロ
ックを処理するプロセスが複数個存在することになるため，実際の通信を行うプロセスはその中のいずれかとなる。特にこの例では送信側，受信側共にマクロタスクブ
ロックではあるが，いずれか一方がマクロタスクブロッ
クである場合も同様に，実際の依存関係を元にして，処理するプロセスが適切な場所でデータ通信を行う。通信

4. 3

タスクブロック間通信

タスクスケジューリングにより各タスクブロックを処理するプロセッサが決定される。この時，処理プロセッ

情報インタフェースにはこのための情報として通信を行うタスクブロック以外に実際にデータが依存しているタ
スクブロック間に関する情報が記述されている。

サが異なるタスクブロック間に COMM タイプの依存が実際のP0, P2
依存関係
タスクブロック１

あるならば，その区間に通信が発生することになる。本
年度は通信を MPI が定義している MPI_Send 命令によるデータ送信操作と MPI_Irecv 命令によるデータ受信操作

P0により実現した。図 4.4 はその具体的な様子を表していP0

P0, P2
タスクブロック１
P0

P2

P0

P2

る。
図 4.4 は(a)で表現されるタスクブロック間の通信情報

P1, P4,

を元にデータ通信命令を挟んだコードを(b)で表現してP1いる。(a)はタスクブロック 1,2,3 がタスクブロック 4 へ

P4,

P4,
タスクブロック２

COMM タイプの通信を持つ状態を示している。各タスク
ブロックを処理するプロセスは示されるとおりであり，

図 4.5

特にタスクブロック 2 とタスクブロック 4 は処理を行う

−46−

通信を行う
ポイント

P1, P4,P1P2 の Send
P4,の Recv
P4,

P4,
タスクブロック２

タスクブロック間通信例 2

またタスクブロックが DOALL 処理を可能とするマク同様にサブグループを生成し並列に実行を行うようにしロタスクブロックである場合は必要なデータを受信した

た。

プロセスがさらに全プロセスに必要なデータを分散し，
4. 5

そして処理後のデータを収集することになる。DOALLの並列化に関しては 4.5 節にて述べる。

DOALL ループの並列化

本年度実現した DOALL ループの並列化では，配列データのブロック分割やリダクション演算(総和・総積)ル

4. 4

通信サブグループの生成

ープの自動並列化を行った。4.4 節にて述べたとおり，

MPI を用いた並列処理ではプロセスの起動の際に，処DOALL ループ全体はサブグループにて実行されること理する全てのプロセスを持つグループ(コミュニケータ)

で DOALL ループを処理するプロセスはそのグループ内が生成される。そして，そのプロセスグループの内部でのみの通信が保障されている。DOALL ループの並列化

のみ通信が行われることを MPI は保障している。更に，においてはループの全イタレーションをブロック分割す

MPI は起動時のグループの内部にサブグループを生成する。そして，その内部のイタレーション自体もスケジュる機能を持っている。本年度はユーザ定義関数部(mainーリングにより複数個のプロセスにより処理される可能関数を除く)や DOALL ループでは MPI の提供するサブグ性があることを考慮し，イタレーション内部でも並列にループを生成する機能を用いて実現した。

処理している。

本年度の C 言語自動並列化トランスレータではユーザ

DOALL ループの並列実行には前処理として各プロセス

定義のプログラムのうち main 関数から呼ばれた先の一にに必要なデータ分配を行う工程がある。その後つ目の関数までを並列化している。特に処理が大きい関

DOALL ループ自体を並列に実行する工程があり，後処

数はマクロタスクブロックとなる可能性が高く，呼び出

理として分散したデータの収集処理を行うことで実現しされるたびにその内部を処理するプロセスの集合が異なている。

る可能性がある。このような場合に対応するため，本年度はサブグループを形成し，その内部のみの通信を保障

５．評

価することにした。図 4.6 はその例を示している。
・プロセス 4 個(P0,P1,P2,P3)で並列処理をすると仮定
void func_1( void ){… Func_1 は…3 つのプロセス…
で実行}

この呼び出し時には P0,P1,P2 で実行し，その 3 つのプロセスでサブグ
ループを形成しfunc_1を並列に処理する

void main( …, …){

P0

func_1( );.......
.....
func_1( );P2

本年度は評価の対象として数値演算プログラムに対して自動並列コード生成を試みた。プログラムの詳細は台形法を用いた数値積分プログラムである。コードとしては小規模であるが本年度開発した C 言語自動並列化トランスレータに備わった並列化手法の数々の評価を行うことが出来るものとなっている。また並列コード生成の評

P1

サブグループ

価を優先したため，タスク粒度，タスクスケジューリン
グは相当無駄があると考えられるものを採用している。
図 5.1 で示されているのは外部関数の呼び出しが行われた際に自動的に通信グループの生成を行い，処理を行っ

この呼び出し時には P1,P2,P3 で実行する，
この際にはその3つのプロセスでグループ化
し実行

図 4.6 サブグループの生成例ている例を示している。本システムでは自動並列化を行うと自動的にグループの生成と解放を集中的に行う関数が生成されるこれが図 4.6 では同一の関数が複数回呼ばれ，呼ばれるごと

・

MPI_CreateSubComm_acpt(…)

・

MPI_FreeSubComm_acpt( … )にその関数を処理するプロセスの要素が異なる場合の例である。前者がグループの生成，後者がグループの解放を示している。この場合では関数が呼ばれるごとに，まを行う関数となっている。この関数を用いて DOALL ル

ず呼び出し時のプロセスグループでサブグループの生成

ープや関数コール時のグループ生成が行われる。図 5.1を行う。次に関数を処理する。最後に生成したグループ

では 2 つのグループを生成しているが，一つは関数用のの解放を行う。こうすることで複数回同一の関数呼び出

グループ，もう一つは関数内のループ文を実行するのにしが起こってもソースプログラム上では一つの関数の並必要となるグループ生成である。その後 init 関数の実行

列コードの記述で，複数回の呼び出しに対応した処理を後生成されたグループの解放を行っているのが分かる。

行うことが可能となる。また DOALL ループに関しても−47−

図 5.2 では DOALL ループ文に対してリダクション演は逐次実行に比べ 26%の処理時間となった。この最適な算を用いて総和を求めることが出来るようになった例をスケジューリングは，DOALL ループ内の各イタレーシ示している。この例では特に分割されたイタレーション
毎の和を MPI が提供する集団メッセージパッシング命

void init( ){令である MPI_Reduce を用いてまとめることで総和を求

h = END-START;h = h/DISB;
ans1 = 0;
for( ii=0; ii<DISB; ii++ ){X0[ii] = START + ii*h;…..

めている。最終的な解が解析対象コードを逐次実行した
際の結果と同じになっていることからも正しく並列化がans1 = ans1+DATA[i];ans1 内に Data[]配列内の全データを総和を求める
ループ文

オリジナル C ソース

MPI の提供している
Reduce 命令にて総和を求めているfor( i=0; i<DISB; i++ ){}}int main( int argc, char** argv ){……
init();
オリジナル C ソースコード
void MPI_CreateSubComm_acpt( …… ……){if ( _Sub_Rank_001!=0 )ans1=0;

サブグループを生成・初期化}
void MPI_FreeSubComm_acpt( …. ,…., ….){

_LpStart_001=_Sub_Rank_001*…..,_LpEnd_001=_Sub_Rank_001*……………

サブグループの解放}

for( i=_LpStart_001; i<_LpEnd_001; i=i+1 ) {ans1 = ans1+DATA[i];}MPI_Reduce(&ans1,&ans1_mpi_reduct001,..MPI_SUM,.. );int main( int argc, char** argv ){……

MPI_CreateSubComm_acpt(,….&_Sub_func_group_002,… );MPI_CreateSubComm_acpt(…..&_Sub_loop_group_003,…..);init(); /*生成されたサブグループで関数の内部を処理*/
MPI_FreeSubComm_acpt(&_Sub_loop_group_003,…
. );MPI_FreeSubComm_acpt(&_Sub_func_group_002,…
. );ans1 = ans1_mpi_reduct001 ; /* -- swap return -- */…. …. …
自動並列化後の MPI コード(リダクション総和部)

図 5.2

自動並列化後の MPI コード (関数コール部)

MPI による自動並列化 例 2

行われていることが確認できたと言える。

init()関数のコールが起こり，関数が処理される。内部では
比較的処理の大き
いループの処理が

図 5.1

MPI による自動並列化 例 1

ョン内の細かい並列性を無視し大きなまとまりとして各

また，評価に利用したプログラムを成蹊大学学園情報プロセスに割付けることを行い，そして各 DOALL ルー

センターに設置してある HPC クラスタマシンにて計測

プで必要となるデータ分配と収集作業を削減できる箇所した。そこではＰＣ48 台＋専用管理マシン１台を使用しを探したことによるものである。このことは，より精度て，2 つのクラスタ環境を構成している。今回はそのうの高い並列性解析や実行時間解析と通信時間の算出を元

ちの 32 台ノードで構成される環境を利用した。各ノードにしたタスクスケジューリング・粒度解析によるところ

全てに CPU に Pentium4 (2.4GHz)，2 次キャッシュにが大きい。並列コード生成に関してもタスクブロック間

512KB，メモリに 512MB，LAN に Gigabit LAN の性能

通信を最適化するような新しい方法が必要と考えられる。

を持つ。各ノードの相互接続にはギガビットスイッチン
グハブを用いている。

６．最後に

この環境下で今回評価の際に使用した並列化プログラ
ムをプロセッサ 4 台利用して動作させたところ，逐次実

6. 1

まとめ

行に比べて自動並列化プログラムは 225%という実行時

本年度は並列性解析から実行時間解析，タスク粒度解間となった。これは通信時間が全体の 80％を占められて析，タスクスケジューリングの一連の流れを繋ぐ共有リいるためであった。今回評価に利用したプログラムは，

ソースの作成と利用を通して最終的な並列コード生成まDOALL ループが複数個連続するものとなっている。4.5

でを全体を通しておこなってきた。まだまだ考えるべき節で述べたように DOALL ループの実行には必ず前処理

点はあるものの，より実システムとして形のあるものがと後処理として，データの分散と収集作業を行う。その残せる結果になったと考えられる。特に各解析間を結ぶ

ため，このような通信時間の肥大化に繋がったものと考共有リソースである二つのインタフェースを通すことでえられる。この自動生成されたプログラムに対して，個各解析間を結ぶことが出来るようになった，という流れ

人的に最適だと考えられるスケジューリングと最適なデは今後の自動並列化 C コンパイラのために役立つものだータ転送を考慮して変更を加えた並列プログラムの場合と考えられる。そして全自動とはいえないながらも，ス−48−

ケジューリングからの結果を手動で生成した物を用いる

よる最適タスク粒度とスケジューリングの考案ことで自動並列化トランスレータとして MPI を用いた

細かい並列性を無視することにより最適なスケジュ

自動並列コードを生成することが出来るようになった。

ーリングを求めることが出来る場合がある。その逆もあ

結果としては，実行時間が逐次実効に比べて遅くなってると考えられる。より正確な通信時間と実行時間の値をいるが，今後の方針となる明確な考案が出来たことも今

参考とし，そして動作環境に最も適した最適なスケジュ

後に繋がるものだと考えている。

ーリングや粒度の決定を行うべきである。

6. 2

参考文献

今後の課題
並列性の強化，特に制御依存による曖昧性の削減

制御依存の曖昧性により通信のパスを一意に決める

1) TOP500 http://www.top500.org/

ことが出来ない現状となっている。より並列性解析時2) 「アドバンスト並列化コンパイラ技術」産業科学技術の動的解析などにより制御依存への対応を強化してい研究開発基本計画

くべきだろう。

http://www.nedo.go.jp/informations/koubo/120324_4/ad-k

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

ihon.html

分散メモリアーキテクチャ上で通信処理をする以上

3) 平成 13 年度アドバンスト並列化コンパイラ技術報告

各プロセス内でのメモリアドレス空間は異なるものと書（概要編），財団法人日本情報処理開発協会なる。このようなアーキテクチャに対応したより詳細

4) 三木光範. “並列処理入門”. PC クラスタ超入門 講習

なポインタ解析を行う必要がある。

会資料. pp166-177，超並列計算研究会. 2000.

より多くの DOALL ループタイプの並列化

5) John L. Hennessy and David A.Patterson.

DOALL ループの並列化に関しては単純に DOALL“Computer Architecture A Quantitative Approach, Second

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

Edition”. Morgan Kaufmann Publishers, Inc. 1996.

ョンを分割すればよいだけではない場合も多々ある。

6) 湯淺太一，安村通晃，中田登志之. ”はじめての並列

このような場合に備え，ループ文の持つ固有の情報のプログラミング”. 共立出版. 1999.

取得，内部で使用される配列のアクセスパターンなど

7) Kai Hwang. “Advanced Computer Architecture:の詳細な解析が必要となるだろう。

Parallelism, Scalability, Programmability”. McGraw-Hill,

通信時のデッドロックの考慮とデータの通信の効Inc. 1993.

率化8) 手代木進. “自動並列化 C コンパイラのための並列性

本年度の通信には，ブロッキング命令である解析”. Master’s thesis, 成蹊大学工学部工学研究科情MPI_Send 命令を用いて実装している。ブロッキング

報処理専攻. 2002.

命令を用いている限り，システム側に依存する傾向が

9) 斉藤 義功. “ 動的メモリ確保を含む C プログラムの高まりデッドロックを起こす可能性がある。このこと

自動並列性解析”. Master’s thesis, 成蹊大学工学部工への対応とデータの通信時に変数ごとの Send/Recv を学研究科情報処理専攻. 2003.

行うのではなくデータを一まとめにした Pack 通信を10) Message Passing Interface Forum -MPI2-行うことによる効率化を考えていくべきである。また，
DOALL ループなどに必要となっているデータ分配や

http://www.mpi-forum.org/
11) The Message Passing Interface (MPI) standard

収集時にかかる通信コストの削減方法の考案も考えて

12) 林晴比古. “新 C 言語入門 シニア編”. ソフトバンク.

いくべきである。
ユーザの知識を利用する方法の検討

http://www-unix.mcs.anl.gov/mpi/

3)プログラムの並列性解析には動的情報が必要となる1991.
13) Mark Williams Company. “ANIS C a lexical guide”. 1990場合があるため，静的情報のみに頼る方法に固執する必要はないと考えている。そこで，ユーザの知識を反映させるような指示文の導入も検討する必要があるだ
ろう。しかし，より多くのユーザに利用されることを想定しているため，自動並列化の実現も念頭に入れることを忘れてはならない。
精度の高い通信時間や実行時間を利用することに−49−