成蹊大学理工学研究報告
J. Fac. Sci. Tech., Seikei Univ.
Vol.45 No.１ (2008) pp.13-19

マルチコアクラスタ向け並列言語－スレッド/プロセス並列機構の実装－
小山浩生*1，緑川博子*2，甲斐 宗徳*3

The Parallel Processing Language for Multicore Clusters- The Implementation of a Thread/Process-Parallel Mechanism Hiroki KOYAMA＊1, Hiroko MIDORIKAWA＊2, Munenori KAI＊3,
ABSTRACT： We already proposed a new parallel programming model called “meta process model” anddesigned a new language MpC and its compiler to realize the model. The MpC compiler converts a MpC program toone of the two different programs according to a target machine’s memory architecture. For distributed memorymachines such as clusters, the compiler converts a MpC program to a software DSM program which employs
process-level parallelism. For shared memory machines such as SMP, the compiler converts a MpC program into apthread program which employs thread-level parallelism. This paper presents three topics, 1) Optimization of code
generation in the MpC compiler for SMP, 2) Incorporation of a thread parallel mechanism into the in the MpC
compiler for clusters, and 3) Implementation of DLM Compiler, new compiler for sequential programs using large
data, which is based on the MpC compiler.

Keywords：parallel language, compiler, cluster computing, software DSM, pthread（Received March 21, 2008）

１．はじめにMemory)の研究開発[2]をもとに，ロ－カリティに着目したメタプロセスモデル[3]という階層型共有メモリプログ

現在，分散メモリ並列システムにおける並列プログララミングモデルを提案し，これに基づくポータブルなミングで，最も広く用いられている移植性のあるソフト

API として MpC 言語を開発してきた。すでに，MpC がウエアインタフェースといえば，MPI(Message Passing

コモディティクラスタや共有メモリ型 SMP マシンにおInterface)であろう。高性能並列コンピュータシステムのいて，UPC や OpenMP と比較し，性能上の優位性があるほとんどにおいて，各ベンダーにより高性能な MPI が実ことを示した。さらに，NPB(NAS Parallel Benchmark)ベ装され，並列プログラミングの事実上の標準ンチマークセットを MpC と他の言語で記述したプログAPI(Application Programming Interface)となっている状況

ラムの有効行数の比較では，逐次コードに対し，MPI がにおいて，最近，MPI 以外のプログラミングモデルや言平均 1.74 倍に増大するのに比べ，MpC は平均 1.07 倍に語にも少し目が向けられるようになってきた。その一つ

とどまっており，プログラムの可読性，生産性の上で優が，GAS 言語とよばれるもので，UPC(Unified Parallel C)[1]れていることを明らかにした[4][5]。などがある。これらは，従来のデータをフラットに扱う

本報告ではこの MpC 言語への機能の追加，性能向上と純粋な共有メモリプログラミングモデルとは異なり，区して『共有メモリマシン向けコンパイラの生成コードの分化大域アドレス空間モデル(PGAS：Partitioned Global最適化』，『クラスタ向けコンパイラへのスレッド機構のAddress Space)に基づいている。

導入』の 2 項目，また，MpC コンパイラの応用として『逐筆 者 ら は ， ソ フ ト ウ ェ ア DSM(Distributed Shared*1：工学研究科情報処理専攻修士学生*2：情報処理専攻助手(midori@is.seikei.ac.jp)*3：情報処理専攻教授(kai@st.seikei.ac.jp)

次大容量データ処理向け DLM コンパイラの構築』の 1
項目，以上の 3 項目についてそれぞれ 3，4，5 で述べる。

－13－

２．メタプロセスモデルと MpC 言語
2．1 メタプロセスモデル

CPUCPU

CPU

メモリ

メモリ

メモリ

CPU

メタプロセスモデル(図 2-1)とは，従来の共有メモリモメモリ

ネットワーク結合

デルに，NUMA マシンなどにも対応できるような各プロセスへの共有分散データの階層構造（スコープ）を取りCPU

図 2-2 クラスタ

CPU

バス結合

図 2-3 共有メモリマシ入れたプログラミングモデルである。メタプロセスとは，
1 つのアプリケーションを協力して並列処理する複数のMpCプログラム
MpC

プロセス全体を指し，ユーザにとっての実行単位である。
プリプロセッサ

メタプロセス
トランスレータ

sharedプロセス０

プロセス１

globalglobal

local

local

実装系ライブラリｃコンパイラ

実行ファイル

図 2-4 MpC コンパイラ

３． 共有メモリマシン向けコンパイラの生成コー

図 2-1 メタプロセスモデル

ドの最適化
2．2

MpC 言語MpC 言語は，メタプロセスモデルをクラスタや共有メ

MpC コンパイラは共有メモリマシンでは pthread プロ

モ リ マシ ン上 で実 現 するため に 共有 デー タ型 修飾子グラムに変換をしている。その際に，グローバル変数のshared と共有データ分散マッピング指定子を新しく導入

数，ユーザ定義関数の数に比例してオーバーヘッドが大して，C 言語を拡張したものである。UPC も MpC と同様きくなってしまう変換をしていたので生成コードの効率に共有変数に shared(型修飾子)を使用しており，C 言語の化を図った。

拡張であるが，共有データの分散マッピング方式は全スレッドへの均一サイズのマッピングに固定されており，3．1 共有メモリマシンへの対応

これを前提に CPU アーキテクチャ毎のコンパイラによる

図 2-1 に示したメタプロセスモデルを pthread プログラ最適化を行うことを指向した言語である。これに対し，ムに対応させるために，図 3-1 のように shared はグロー

MpC 言語の共有データの分散マッピング宣言は，スカラ，バル変数へ，local はローカル変数に対応させている。

ベクタを問わず任意のプロセスへ割り付けることが出来

global についてはスコープがスレッド局所になるように，る[5]。特に配列データに関しては柔軟性のある割り付け

global に対応する変数をユーザプログラムから抽出し，が可能である。MpC 言語ではコンパイル時よりも実行時スレッド局所変数(thread specific data)に置き換える。に割り付け処理を行うことで柔軟性を高めている。また，プロセス特定のコンパイラや実装系を前提とせず，アーキテクチャによらず移植性が高いことが特徴である。
現在，MpC コンパイラは 2 通りあり，図 2-2 のようなコモディティクラスタなどの分散メモリマシンではソフ
トウェア DSM プログラムへ変換しプロセスレベルで並列化し，図 2-3 のような共有メモリマシンでは pthread プ

グローバル変数
スレッド0

スレッド１

thread specificdatathread specificdata

ローカル変数

ローカル変数ログラムへ変換しスレッドで並列実行できるようにして対応している。クラスタ向け MpC コンパイラの例を図2-4 に示す。MpC コンパイラ内のトランスレータでは Cプログラムに変換をしている。

図 3-1 メタプロセスモデルの pthread 向け実装

－14－

int a, b;
void funcA(){a++;}void funcB(){b++;}int main(int argc, char *argv[]){
mpc_init(argc, argv);
a = 0;
b = 0;
funcA(); funcB();
printf("%d %d¥n", a, b);
mpc_exit();}

例として示した図 3-3 のプログラムにあるように，
sub_main 関数内で a に key[0]を，b に key[1]を関連付けしている。そして，main 関数を除くすべての関数の先頭で a には key[0]から，b には key[1]から関連付けされたスレッド固有のデータを返すことでスレッド局所の変数にしている。
3．2 生成コードの改善点
図 3-2 の funcA 関数では a のみ，funcB 関数では b のみを使用しているので，変換後 funcA では b，funcB では aを pthread_getspecific する必要はないが，従来の変換では

図 3-2 ソースプログラムすべての変数について pthread_getspecific していたためそのために pthread_create された関数で pthread_setspecificオーバーヘッドになっていた。関数のコール数が増える

関数を使い，スレッド固有にする変数を各 key に関連付と pthread_getspecific のためのオーバーヘッドも増える

けをしておき，main 以外のユーザ定義関数の先頭においのでその関数で使用している global 変数についてのみて pthread_getspecific 関数により key からスレッド固有デ

pthread_getspecific するように改良した。

ータを代入して使用する。MpC コンパイラでは，図 3-2のソースプログラムを図 3-3 のコードに変換をしている。

pthread_key_t key[512];
void funcA(){
int *a, *b;
a = pthread_getspecific(key[0]);b = pthread_getspecific(key[1]);(*a)++;}
void funcB(){
int *a, *b;
a = pthread_getspecific(key[0]);b = pthread_getspecific(key[1]);(*b)++;}
void sub_main(){int *a, *b;a = (int *)malloc(…);
b = (int *)malloc(…);
pthread_setspecific(key[0], a);pthread_setspecific(key[1], b);
a = pthread_getspecific(key[0]);b = pthread_getspecific(key[1]);(*a) = 0; (*b) = 0;
funcA(); funcB();
printf("%d %d¥n", *a, *b);}
int main(int argc, char *argv[]){…
pthread_create(…,sub_main, …);…
}

3．3 改善前後での性能比較評価に使用した 2 種類の TSP のプログラムは繰り返し回数の多いヒューリスティックを用いたアルゴリズムである。改善法を用いて，初期値を変えて複数回実行している。for 文を並列処理する Parfor 型と複数回行う実行を並列処理する Trial 型[6][7]を用いてスレッド数を増加させたときの実行時間について改善前後を比べた。実行環境としては，表 4-1 に示す Intel SMP と SunFire の 2 つのマ シ ン で 評 価 を 行 っ た 。 TSP の 評 価 デ ー タ に は
TSPLIB[11]の pr1002 を用いた。図 3-4，図 3-5 は各マシンでの実行時間を示したものである。また，図 3-4，図3-5 の実線は改善前，点線は改善後を示している。
両マシンで改善前に 1 スレッドで 2 つのマシンともにParfor 型，Trial 型の間に大きな差がある。Trial 型，Parfor型ともに関数コールの総数は約 112 億回とほぼ同じだが，グローバル変数を Trial 型が 13 変数使用しているのに対して、Parfor 型が 8 変数使用と 5 つ差がある。 1 回
pthread_getspecific を 実 行 す る と Intel SMP で は 約0.008µsec、SunFire では約 0.0015µsec かかる。このため，改善前は関数の先頭で毎回 pthread_getspecific を実行していたので Intel SMP では 112 億×5×0.008µsec≒450sec の差となった。不要な pthread_getspecific のコールを削減したので改善後は改善前と比べて両方式の差が減り，どち

図 3-3 スレッド変換での問題点

らの方式でも処理時間が 40％～70％削減される成果が得られた。

－15－

表 3-1 実行環境
Intel SMP

SunFireV40Z SMPCPUIntel Xeon E5310 1.6Ghz

AMD デュアルコアCPU 数

Quad コア×2 チップ

Dual コア×2 チップ

OS

Linux FC5 kernel 2.6.19

SunOS 10メモリ

8GB16GBCPU CPUCPU CPUCPU CPUメモリメモリメモリ

ネットワーク結合
図 4-1 マルチコアクラスタ

2400

メタプロセス

Parfor(旧)Trial(旧)
Parfor(新)Trial(新)2000

sharedTime[S]

1600

プロセス０

プロセス１

globalglobalスレッド スレッド

スレッド スレッド

1200

800

400

図 4-2 プログラミングモデル

01

2

Num of Thread

48

4．1 実

図 3-4 改善前後の実行時間（Intel SMP）

今回の実装では，プロセスローカルデータにアクセス

3600
Parfor(旧)Trial(旧)
Parfor(新)Trial(新)

3200
2800
2400
Time[S]装する for 文を対象にしたスレッド並列構文 thread_for 文をMpC 文法に追加し，この区間に限ってスレッド並列を行う。あらかじめ MpC コンパイラにより，fork-join 方式で2000スレッド生成し，for 文におけるイテレーション区間を実1600

行時に指定したスレッド数で等分して並列処理するコー

1200

ドに書き換えておく。

800
400

4．2

0124thread_for 文

8

Num of Thread

現在のところ，thread_for の指定はユーザの責任で行い，図 3-5 改善前後の実行時間（Sun Fire SMP）

for 文内のデータ，フローの依存性はコンパイラは関知しない。MpC プログラムでは thread_for 文以外のスコープ

４．クラスタ向けコンパイラへのスレッド機構の導入で従来通りプロセス共有データ（shared）にアクセスすることが可能であるが，現段階では SDSM(SMS)がスレッド並列に対応していないので thread_for スコープで最近ではコア数の多いマルチコアクラスタ（図 4-1)が個々のスレッドが直接 shared データにアクセスすること広く普及し始めている。そこで，マルチコアの特性を生は禁止している。shared データを global の変数に代入し

かし MpC プログラムの性能をさらに引き出すために，ておき使用することは可能である。また，thread_for スコ

図 4-2 のように，クラスタノードにまたがるプロセスとープでの typedef，enum 変数の使用も禁止している。

ノード内にあるスレッドを組み合わせ，２レベルの並列処理機構を取り入れた共有メモリ型並列プログラミング

4．3 性能評価モデルを新たに提案する．[8]
実行環境を表 4-1 に示す。性能評価として mandelbrot－16－を使用し，プロセス，スレッド数を増やして実行したときについての実行時間を比べた。mandelbrot はメモリア

表 4-2 実行時間比較 [クラスタ 1]

クセスに比べ計算量が多く，ノード数，プロセス数，ス(a)従来のプロセス並列のみの MpC〔sec〕
ノード数 x プロセス数

レッド数に階層的にそれぞれ自由に分け易いアプリケーションになっている。
表 4-1 実行環境
クラスタ 2

クラスタ１4x1

4x2

4x4

4x8

Init

0.376

0.549

1.077

23.355

Calc

4.219

2.199

1.488

1.420

Total

4.595

2.748

2.565

24.7744x16SMS 対応無ノード数

411

CPU type

Dual CPUQuad core

Dual core(b)スレッド＋プロセス並列の MpC〔sec〕

Intel Xeon

Intel Xeon

Intel Xeon

ノード数 x プロセス数 x スレッド数

2.8GHzE5310 1.6GHz

E5110 1.6GHz

CPU 数/Single コア

Quad コア

Dual コア

ノード数

×2 チップ×2 チップ×2 チップLinux FC5

Linux FC5

Linux FC7

kernelkernelkernel

2.6.202.6.202.6.23

gcc

4.1.1

4.1.1

4.1.2

表 4-3 実行時間比較 [クラスタ 2]

メモリ

１GB

8GB

4GB(a)従来のプロセス並列のみの MpC〔sec〕

CPU SpecOS

4x1x1

4x1x2

4x1x4

4x1x8

4x1x16

Init

0.368

0.365

0.363

0.359

0.355

Calc

3.642

1.996

1.394

1.277

1.256

Mcpy

0.573

0.183

0.288

0.196

0.181

Total

4.582

2.544

2.045

1.832

1.792

ノード数 x プロセス数
表 4-2(a)はクラスタ 1 で従来のプロセス並列のみ MpC，

2x1

2x2

2x42x8

表 4-2(b)はクラスタ 1 でスレッド機構を組み込んだ MpC，

Init

0.409

0.431

0.816

2.232

表 4-3(a)はクラスタ 2 で従来のプロセス並列のみ MpC，

Calc

6.315

3.679

1.895

1.910

表 4-3(b)はクラスタ 2 でスレッド機構を組み込んだ MpC

Total

6.724

4.111

2.711

4.142

2x16

エラーを使用した mandelbrot プログラムの実行時間である。各(a)はノード内をプロセスで並列に，各(b)はノード内をス(b)スレッド＋プロセス並列の MpC〔sec〕レッドで並列に処理している。

ノード数 x プロセス数 x スレッド数

表 4-2，表 4-3 は上の欄から Init はプロセスの fork や通信経路の確立などの時間，Calc は計算時間，Mcpy はthread_for スコープでは shared データにアクセスできないのでローカルに必要なデータをコピーしたり，計算した結果を shared データに書き戻したりする時間，Total

2x1x1

2x1x2

2x1x4

2x1x8

2x1x16

Init

0.398

0.428

0.390

0.390

0.389

Calc6.306

3.194

1.746

0.928

0.900

Mcpy0.015

0.501

0.174

0.468

0.334

Total

6.719

4.124

2.310

1.786

1.624

はプログラムの総実行時間を示す。また，各表の網掛けした値はクラスタ 1，2 においての Total の最小値を示し

表 4-3 の(a)従来のプロセス並列のみの MpC 内の 2x16ている。なお，時間の単位は全て〔sec〕である。

は原因の特定はできていないがエラーが発生し，実行結

図 4-3，図 4-4 はプロセス並列の 1 プロセスでの Total果が取れなかった。

を 1 としたときの各部割合を示したものである。図 4-3

図 4-3，図 4-4 にあるように，横軸各左欄の(a)従来のはクラスタ 1，図 4-4 はクラスタ 2 での結果である。横軸は，ノード内のスレッドとプロセスの数を示している。
表 4-2 の(a)従来のプロセス並列のみの MpC 内の 4x16の欄が空いているのは，今回使用している SDSM のバージョン(sms0.0.5)の最大指定プロセス数が 32 になっていることにより実行結果が取れなかったためである。

プロセス並列のみの MpC では，プロセス数を増やすとCalc は減少しているが，Init に時間がかかっている。ノード内の実 CPU 数をこえるプロセス数(クラスタ 1 では4，クラスタ 2 では 8)を指定するとさらに多くの時間がかかる。そのため，プロセス並列の MpC の実行は計算時間を減らすために実 CPU 数をこえるプロセス数での実行は適していない。

－17－

横軸各右欄の(b)スレッド機構を組み込んだ MpC では，５．

1 ノードに 1 プロセスずつしか fork していないので，そ逐次大容量データ処理向け DLM コンパイラのプロセス fork や，プロセス同士のコネクションを行っ大容量のメモリを必要とする逐次プログラムのために，て い る Init は 最 小 限 の 時 間 し か か か っ て い な い 。
thread_for 文の最後で thread 並列の計算結果を shared デクラスタの各ノードの遠隔メモリを集めて仮想的に大容ータに戻す際に多少の時間はかかっているが，実 CPU 数量メモリとする分散大容量メモリシステム DLM（図 5-1）をこえてもスレッドの起動にはプロセスほどのオーバー[9][10]を構築した。DLM システムは一般ユーザが手軽にヘッドはなく，Calc も減少していっている。そのため，使えるように，swap システムなどを変更することを必要

各ノードに 1 プロセスずつ fork しその中でスレッド展開としないユーザーレベルのソフトウェアになっている。

をしたほうが Total で見るといい結果が得られた。

その DLM システムを用いる際に，ユーザの C プログラたメモリを大容量メモリとして用いられるように DLM

6

コンパイラを構築した。

5
Mcpy
Calc
Init

4

Memserv process

Cal process

32

CalCom1

threadthreadmemhost1
Memserv process

12

4
ノード内の並列性

8(b)スレッド(a)プロセス(b)スレッド(a)プロセス(b)スレッド(a)プロセス(b)スレッド(b)スレッド(a)プロセス0(a)プロセス

プロセス並列の1プロセスの実行時間との割合

ムに dlm 宣言を加えるだけで，容易にクラスタに分散しcalhostmemhost2
Memserv process16

図 4-3 プロセス並列での 1 プロセス使用に対する割合[クラスタ 1]

memhost3：
図 5-1 DLM システム構成図
McpyCalcInit

1calhost0.832768 //32GB

memhost1 32768 //32GB
0.6

memhost2 65536 //64GB

0.4

memhost3 16384 //16GB：

0.2

248

ノード内の並列性

図 4-4 プロセス並列での 1 プロセス使用に対する割合[クラスタ 2]

図 5-2 DLM 設定ファイル例(b)スレッド(a)プロセス(b)スレッド(a)プロセス(b)スレッド(a)プロセス(b)スレッド(b)スレッド
1(a)プロセス

0(a)プロセス

プロセス並列の1プロセスの実行時間との割合

1.2

DLM システムは起動時に図 5-2 に示す DLM 設定ファ16イルを読み込む。設定ファイルの先頭行は計算ノードホ
ストと，計算ホストでローカルメモリとしてどの程度のメモリを DLM システムに使用させるかということを示す。２行目以降は，メモリサーバとして提供できるホスト名と提供メモリ容量を記述する（メモリ容量は現在，MB 単位で記述）。そして，実行時にメモリ動的割り当てやメモリサーバへの swap 要求を処理する。このため，－18－

DLM コンパイラは，まずメモリサーバプロセスの遠隔起の最適化により，今回使用した評価プログラムでは，改動や計算プロセスの初期設定などを行う初期化関数

善後は改善前と比べておよそ 1.5～3 倍の性能向上が得ら

dlm_init()をプログラムの開始部分に挿入する。さらに，れた。また，クラスタ向けコンパイラへのスレッド機構

ユーザにより dlm 指定された静的データ宣言を，動的割の導入により従来の MpC 言語に比べ，マルチコアの性り当てとポインタ表現に置き換える処理を行う。すなわ能を引き出すことができた。さらに，逐次大容量データち，プログラムスコープを考慮した変数リネーミングを処理向け DLM コンパイラの構築により，dlm 記述のみ行う。図 5-3 にコンパイル実行例と変換例を示す。

で DLM システムが利用可能になった。

この逐次大容量データ処理向けDLMコンパイラによ

参考文献

り，図5-3にあるsample.cのように，逐次CコードにDLM記述を付加するだけでDLMシステムが利用可能になった。

[1]// sample.c#define MAX 1000

Tarek El-Ghazawi UPC: Distributed Shared Memory
Programming, Wiley Series on Parallel and Distributed

dlm int a[MAX];
int main(int argc, char *argv[]){
int i;
for(i = 0; i < MAX; i++)for(i = 0; i < MAX; i++)return 0;

William Carlson, Thomas Sterling, Katherine Yelick,a[i] = i;printf("%d ", a[i]);Computing, 2005
[2]

緑川，飯塚 :“ユーザーレベル・ソフトウエア分散共有メモリ SMS の設計と実装”， 情処論文誌 HPC,
Vol. 42, No.SIG9(HPS 3), pp.170-190[3]}(2001)

緑川，片野，飯塚 :“メタプロセスモデル －明示的並列処理記述のための分散共有メモリプログラミ

コンパイル

ングモデル－”，情報科学技術フォーラム FIT2003,dlmc sample.csample.c -ldlm

情報科学技術レターズ,LB_002, pp. 33-35,（2003, 9）

int (*__dlm_sh_a);[4]
int main(int argc, char *argv[]){
int i;dlm_init(argc, argv);

小山, 緑川, 甲斐 :“並列言語 MpC の高機能化”，情報化学技術フォーラム FIT2006, FIT 論文集, B ｰ 016,
pp.101-103,（2006, 9）[5]

緑川，飯塚 :“メタプロセスモデルに基づくポータブルな並列プログラミングインターフェース MpC”，

if(MYPID == 0){__dlm_dim[0] = 1000;__dlm_dim[1] = -1;__dlm_div[0] = -1;__dlm_sh_a = ( int (*))dlm_mapalloc(__dlm_dim,__dlm_div, sizeof( int ),0, dlm_nproc);
for(i = 0; i < 1000; i++) __dlm_sh_a[i] = i;for(i = 0; i < 1000; i++) printf("%d ", __dlm_sh_a[i]);{ dlm_exit(); return 0; }情処論文誌：ACS, Vol.46 No.SIG4(ACS9), pp.69-85（2005）[6]

小山, 鈴木, 緑川：“階層型共有メモリプログラミン
グ言語 MpC を用いた TSP の並列処理”，情報処理学会第 69 回全国大会論文集,1A-1, pp.1-2,（2007, 3）[7]

小山, 緑川 :“階層型共有メモリプログラミング言
語 MpC による TSP 並列処理”，先進的計算基盤シス
テムシンポジウム 論文集 SACSIS2007 pp.198-199}
dlm_exit();（2007, 5）}[8]

図 5-3 DLM コンパイラによるプログラムの変換例

小山, 緑川 :“マルチコアクラスタ向け並列言語の提案”，HPCS2008（2008, 1）[9]

６．終わりに緑川, 小山, 黒川, 姫野 :“分散大容量メモリシステ
ム DLM の設計と DLM コンパイラの構築”，電子情報通信学会 CPSY 研究会資料, 信学技報 Vol.102,

本研究では，『共有メモリマシン向けコンパイラの生成

No.398, pp.29-34（2007,12）

コードの最適化』，『クラスタ向けコンパイラへのスレッ[10] 緑川, 小山, 黒川, 姫野 :“分散大容量メモリシステ

ド機構の導入』，『逐次大容量データ処理向け DLM コン

ム DLM の初期性能評価”，HPCS2008（2008, 1）

パイラの構築』の 3 項目について研究を行い以下の成果[11] TSPLIB：http://elib.zib.de/pub/Packages/mp-testdata/を得た。共有メモリマシン向けコンパイラの生成コード

tsp/tsplib/tsplib.html－19－