スライド 1

共有メモリマシン上での
並列計算プログラミング
金田憲二
背景

速く計算ができると色々うれしいはず
一つ一つのプロセッサはまだまだ遅い

並列に計算することで高速化


1個のプロセッサで1000時間かかる計算を、
1000個のプロセッサを使って1時間で!!!
どうやって並列計算をするのか
並列計算機を手に入れなければいけない
 プログラムを記述しなければいけない
※当然、実現したい計算の種類によって
最適な手段は異なる

並列計算機の種類

共有メモリマシン
例）SunFire15K

クラスタ
ネットワークでつながった数百～数千台の計算機
例）IBM BladeCenter
例）Sun V210 x 128

並列計算を記述する方法

普通の言語
例）C/Java + スレッド/通信ライブラリ
 とても大変

自動並列化コンパイラ



ユーザは並列計算を意識しないで済む
性能などの面で問題がある
並列プログラミング言語
例）Cilk、 Linda、KLIC、Stackthreads、…
 簡便に高性能な並列計算を実現可能
今回取りあげるのは

Cilk言語




90年代後半にMITで研究・開発
C言語にいくつかのキーワードを追加
共有メモリマシン上で動作
再帰関数などは結構簡単に並列化
例）チェスの次手の探索
発表の概要
～Cilk言語のチュートリアル～



フィボナッチの並列化
言語の詳細
実装の概要
フィボナッチの並列化
フィボナッチ数を計算する
Cプログラム
#include <stdlib.h>
int main (int args, char *argv[]) {
#include <stdio.h>
int n, result;
int fib (int n) {
n = atoi(argv[1]);
if (n<2) return (n)
result = fib (n);
int x, y;
printf(“Result: %d\n”, result);
x = fib (n-1);
return 0;
y = fib (n-2);
return (x+y);
}
}
並列に計算できる箇所は？
fib (4);
fib (5);
fib (3);
fib (6);
fib (3);
fib (4);
fib (2);
fib (3);
fib (2);
fib (2);
fib (1);
fib (2);
fib (1);
fib (1);
fib (0);
並列に計算できる箇所は？
#include <stdlib.h>
int main (int args, char *argv[]) {
#include <stdio.h>
int n, result;
int fib (int n) {
n = atoi(argv[1]);
if (n<2) return (n)
result = fib (n);
int x, y;
printf(“Result: %d\n”, result);
x = fib (n-1);
return 0;
y = fib (n-2);
return (x+y);
}
}
この2つの関数の呼び出しは
並列に実行できる
Cilkで記述された
並列フィボナッチ
#include <stdlib.h>
cilk int main (int args, char *argv[]) {
#include <stdio.h>
int n, result;
#include <cilk.h>
n = atoi(argv[1]);
cilk int fib (int n) {
result = spawn fib (n);
if (n<2) return (n)
sync;
else {
printf(“Result: %d\n”, result);
int x, y;
x = spawn fib (n-1);
y = spawn fib (n-2);
sync;
return (x+y); } }
return 0;
}
プログラム中に現れる
キーワード



cilk
spawn
sync
cilk

spawnやsyncを呼び出す関数の先頭に
つける識別子
cilk int f() {
…
}
※以降この識別子のついた関数をcilk procedureと呼ぶ
spawn

並列関数呼び出し

関数の終了を待たずに呼び出し元が実行を
続ける
spawn f (x);
g ();
f (x)の終了を待たずにg ()も実行する
sync

spawnした関数の終了を待つ
y = spawn f (x);
…
sync;
f (x)の終了を待つ
printf (“%d”, y);
コンパイル

コマンド名：cilk
$ cilk filename

gccと同じコンパイルオプションが使える
$ cilk -g -Wall -O2 fib.cilk -o cilk
実行

--nprocで計算機のプロセッサ数を指定
$ filename --nproc n args

例）64プロセッサ上でのfib (32)の計算
$ ./fib --nproc 64 32
※fib (32)の計算はSunFire 15K上で
約55倍のスピードアップ
プロファイリング (1/2)

以下のオプションをつけてコンパイル



--cilk-profile
--cilk-critical-path
以下のオプションをつけて実行

--stats level
プロファイリング (2/2)
$ cilk -cilk-profile -cilk-critical-path -O2 fib.cilk -o fib
$ ./fib --nproc 4 --stats 1 30
Result: 832040
RUNTIME SYSTEM STATISTICS
Wall-clock running time on 4 processors: 2.593270 s
Total work = 10.341069 s
Total work (accumulated) = 7.746886 s
Critical path = 779.588000 us
Parallelism = 9937.154003
言語の詳細
言語の詳細






Storage allocation
Locking
Inlets
Aborting
Timer
（プログラム例：n-queens）
Storage Allocation (1/2)

Stack memoryへの割り当て

Cilk procedure内では

ptr = Cilk_alloca(size)；
C関数内では
ptr = alloca(size)；
※関数がreturnする時に自動的に開放される
Storage Allocation (2/2)

Heap memoryへの割り当て

通常のCと同じ
ptr = malloc(size)；
free(ptr)；
Locking

Cilkは相互排他ロックを提供する

スレッド間で共有されるデータへのatomicな
アクセスを可能にする
Data raceの例 (1/2)

foo()が2を返す（ことを意図した）プログラム
cilk int foo (void) {
int x = 0;
{
spawn bar(&x);
*px = *px + 1;
x = x + 1;
return;
sync;
return (x);
}
cilk void bar (int *px)
}
Data raceの例 (2/2)

実行によっては、値が正しく更新されない
cilk int foo (void) {
int x = 0;
(1)
xをread
(= 0)
spawn
bar(&x);
cilk void bar (int *px)
(2) xをread (= 0)
{
*px = *px + 1;
x = x + 1;
return;
(3)
xへwrite (= 1)
sync;
(4) xへwrite
(= 1)
return (x);
}
}
(5) 1をreturn
API (1/2)

型
Cilk_lockvar

ロックを初期化する関数
Cilk_lock_init(ｌ)

ロックを取得する関数
Cilk_lock (ｌ)

ロックを開放する関数
Cilk_unlock(ｌ)
API (2/2)


ロックを取得できるのは同時に一つの
スレッド
ロックを取得できなかったスレッドは
そのロックが開放されるまで待機
プログラム例1
#include <cilk-lib.h>
Cilk_lockvar mylock;
{
Cilk_lock_init(mylock);
Cilk_lock(mylock);
/* critical section
(atomicに実行したいコード) */
Cilk_unlock(mylock);
}
プログラム例2
#include <cilk-lib.h>
Cilk_lockvar mylock;
cilk void bar (int *px)
cilk int foo (void) {
{
int x = 0;
Cilk_lock (mylock);
Cilk_lock_init(mylock);
*px = *px + 1;
spawn bar(&x);
Cilk_unlock(mylock);
Cilk_lock(mylock);
return;
x = x + 1;
Cilk_unlock(mylock);
sync;
return (x); }
}
Inlets


spawnの返り値に使える操作というもの
が制限されている
そのためにspawnの返り値を操作するた
めの特殊な機構
spawnに対する制限 (1/2)

spawnの返り値に対して許されている操作は
=
*=
/= %=
+=
-=
&=
^= |= <<= >>=
のみ
y += spawn f (x);
spawnに対する制限 (2/2)

以下のような操作は許されていない
z = spawn f (x) + spawn g (y)
h (spawn f (x));
ただしhはCの関数
Inlet

spawnの返り値を処理する特殊な関数


Cilk procedure内で定義される
spawnの返り値を渡すことができる
cilk int f (int x) {
inlet int g (int y) {
…
}
z = g (spawn h())
}
プログラム例
cilk int fib (int n) {
int x = 0;
inlet void summer (int result) {
x += result;
}
if (n < 2) return n;
summer (spawn fib (n-1));
summer (spawn fib (n-2));
sync;
return (x);
}
注意点 (1/2)

inlet中でspawnやsyncを呼び出すこと
はできない
cilk int f (int x) {
inlet int g (int y) {
z = spawn h();
}
z = g (spawn h())
}
注意点 (2/2)

Implicit atomicity

spawnの呼び出したスレッドと同じスレッドが
inlet内を処理する
cilk int fib (int n) {
inlet void summer (int result) {
x += result;
}
xへのアクセスはatomicで
あることが保障されている
summer (spawn fib (n-1));
summer (spawn fib (n-2));
}
Aborting

spawnしたCilk procedureを中断させる
機構

探索の枝狩りなどの目的に使用する
Abort

inlet内にabortプリミティンブをいれる
cilk int f (int n) {
inlet void g (int x) {
...
abort;
}
…
}
プログラム例
cilk void search(int n) {
inlet void catch() {
if (解が発見された) { abort; }
…
}
for (x in 探索空間) {
catch (spawn search (x));
}
}
注意点

abortが呼ばれた時点でまだspawnされ
ていないタスクは中断されない
cilk void foo(int n) {
(3) abortを呼び出す
inlet void bar() {
abort;
}
bar (spawn baz(17));
spawn baz(28);
}
(1) baz(17)をspawn
(2) baz(17)が終了
(4) baz(28)をspawn
Timer

型
Cilk_time

wall-clock timeを返す関数
t = Cilk_get_wall_time()

Cilk_timeを秒に変換する関数
sec = Cilk_time_sec(t)
プログラム例：n-queens
(1/8)

N×Nのチェスボード上で以下の条件を満
たすN個のQueenの配置を求める
[条件]Queen同士は互いを取れない
Q
Q
Q
Q
Q
Q
Q
Q
プログラム例：n-queens
(2/8)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <cilk.h>
#include <cilk-lib.h>
…
プログラム例：n-queens
(3/8)
…
int safe(char *config, int i, int j) {
int r, s;
for (r = 0; r < i; r++) {
s = config[r];
if (j==s || i-r==j-s || i-r==s-j) {
return 0;
}
}
return 1;
}
…
プログラム例：n-queens
(4/8)
…
cilk char *nqueens(char *config, int n, int i) {
char *new_config;
char *done = NULL;
int j;
inlet void catch(char *res) {
if (res != NULL) {
if (done == NULL) { done = res; }
abort;
}
}
…
プログラム例：n-queens
(5/8)
…
if (i==n) {
char *result;
}
/* put this good solution in heap,
and return a pointer to it */
result = malloc(n*sizeof(char));
memcpy(result, config, n*sizeof(char));
return result;
…
プログラム例：n-queens
(6/8)
…
/* try each possible position for queen <i> */
for (j=0; j<n; j++) {
new_config = Cilk_alloca((i + 1) * sizeof(char));
memcpy(new_config, config, i*sizeof(char));
if (safe(new_config, i, j)) {
new_config[i] = j;
catch(spawn nqueens(new_config, n, i+1));
}
if (done != NULL) { break; }
}
sync;
return done; }
…
プログラム例：n-queens
(7/8)
…
cilk int main(int argc, char *argv[]) {
int n;
char *config;
char *result;
n = atoi(argv[1]);
config = Cilk_alloca(n*sizeof(char));
result = spawn nqueens(config, n, 0);
sync;
…
プログラム例：n-queens
(8/8)
…
}
if (result != NULL) {
int i;
printf("Solution: ");
for (i=0; i<n; i++) {
printf(“%2d\n”, result[i]); }
} else {
printf(“No solutions!¥n”);
}
return 0;
実装の概要
実装の概要

work-stealingによる負荷分散

idleなプロセッサはランダムに選んだプロセッ
サからタスクを盗む
実装の概要

work-stealingによる負荷分散

idleなプロセッサはランダムに選んだプロセッ
サからタスクを盗む
実装の概要

work-stealingによる負荷分散

idleなプロセッサはランダムに選んだプロセッ
サからタスクを盗む
参考文献

Cilk 5.3.2 Reference Manual



Supercomputing Technologies Group
MIT Laboratory for Computer Science
http://supertech.lcs.mit.edu/cilk
2001
コンパイル方法
foo.cilk
cilk2c
foo.c
gcc
foo.o
ld
foo
Cilk runtime system

Download Report