slides

並行計算に基づく
並列プログラミング言語のための
効率的なコンパイルの枠組
大山恵弘
東京大学大学院理学系研究科
情報科学専攻米澤研究室
今日の並列プログラミング
ポピュラーな方法
+ 並列拡張ライブラリ
C, Fortran, ...
メモリ管理
同期、通信
スレッド（プロセス）の生成と終了
プログラマ
の責任
なぜポピュラーか？
Cで書けば速いよ！
しかし、、、多くの開発時間、人員、能力
記述が楽
かつ
実行が速い
言語がほしい
細粒度スレッドをサポートする言語
（1/2）

例
– 並列オブジェクト指向言語
– 並行論理型言語
– 関数型言語＋並列拡張

特徴
– 動的スレッド生成で並列性抽出
（Fibの例: 2つの子をスレッド生成して計算）
– 多数のスレッドを生成可能（何十万、何百万）
細粒度スレッドをサポートする言語
（2/2）

利点
– 均等な負荷分散
– プロセッサ効率の向上
– アルゴリズムの自然な記述

実装上の問題
– 動的スレッド生成オーバヘッド
– 同期、通信オーバヘッド
細粒度スレッドをサポートする言語
（2/2）
London
Moscow
Los Angeles
Hong Kong
Dakar
New York
細粒度スレッド技術
97年度輸出状況（推定）
Singapore
Salvador
Cape Town
Sydney
Antarctic
細粒度マルチスレッドが有効な例
（1/2）
•例題１: 枝刈りつき並列木探索（RNA）
仕事の単位を
細かく分ける必要
負荷の不均衡
特徴: 部分木の計算量予測困難
64台CPU使用時に65個の
スレッドができたら困る
細粒度マルチスレッド言語:
言語が細かい仕事を管理
細粒度マルチスレッドが有効な例
（2/2）
•例題2: 並列文法解析（CKY）
Cによる単純な記述:
スピンロックで待つ
長時間無駄仕事する可能性
特徴: 同期待ち時間
予測困難
細粒度マルチスレッド言語:
CPUを無駄にせず
別の仕事を実行
貢献

細粒度スレッドの効率的なコンパイルの枠組み
– 並行計算を利用
– スレッドスケジューリングの回数を減らす技法
– スレッド間通信をレジスタで行う技法

並列オブジェクト指向言語Schematicの実装
– 単一プロセッサWS & SMP
– Lazy Task Creation 方式による動的負荷分散を実装

現実的なアプリケーションで性能評価
– Cと比較
以降の発表の流れ



我々の使用する言語
ナイーブなコンパイル技法
提案するコンパイル技法
– コンパイル時スケジューリング
– Unboxed チャネル



動的負荷分散
性能評価
関連研究
我々の言語の概要

表層言語: Schematic [田浦ら 96]
– Scheme ＋非同期呼び出し拡張
– 高効率なスレッド生成
•
呼び出しコスト: 同期呼び出し ≒ 非同期呼び出し
– 1st-class の通信媒体（チャネル）

中間言語: 並行計算HACL [小林ら 95]
– プロセスがチャネル通信によって計算
– ごく少数の本質的なプリミティブ
– 単純で解析や最適化の platform に適する
細粒度マルチスレッド言語の
ナイーブな実行方式
スレッド生成＝タスクキューへのエンキュー
タスクキュー内の各仕事はメモリで通信
受信成功:
を実行可能な仕事として
タスクキューにエンキュー
受信失敗:
を待ちキューにエンキューし
タスクキューから仕事を取り出して実行
提案するコンパイル技法
[大山ら Euro-Par 97]

最適化1: コンパイル時スケジューリング
– 複数のスレッドのコードを並べて生成
– タスクキュー操作の回数を削減

最適化2: unboxed チャネル
– レジスタにチャネルの内容と状態を持たせる
– メモリを使用しないスレッド間通信
変換規則による
コンパイルアルゴリズムの記述
Parallel
Receive
F (r(v)=>P) U k =
if (r has a value) then
let val v = get_value(r)
Send
in F (P::U) k end
F (r<=v) U k =
else
if (r has a process) then
let fun s(l, v) = F [P] l
let val p = get_value(r) in
fun s(k) = p(k, v)
put_process(r, s);
in F U (s::k) end
FUk
else
end
put_value(r, s);
Process instantiation
FUk
F ( f(x1, ..., xn)) U k =
Conditional
let fun s(k) = F U k
F (if x then P1 else P2) U k
in f((s::k), x1, ..., xn) end
= if x then F (P1::U) k
else F (P2::U) k
F (P1 | P2) U k
= F (P1::(P2::U)) k
.....
コンパイル時スケジューリング
（1/2）
受信
if （受信成功） then
else
を待ちキューに格納
no
スレッド
コンパイル時スケジューリング（2/2）
no
タスクキューが不要なわけではない
をスタックにプッシュ
f (r,1,2)
f (r,1,2)の本体へ飛ぶ
unknownな関数
スタック: 実行可能なクロージャの集合を保持
コード複製戦略
else
複製を行わずコード生成
全く複製しないコードサイズ
×
プログラマが与えた定数
≦
if （受信成功） then
生成されるコードサイズ
Unboxed チャネル
• [田浦ら94]で最初に提案
• レジスタ上にチャネルの状態と内容を保持
• 必要に応じメモリにチャネルを作成
unboxed
チャネル
unboxed
チャネル
レジスタ上で値通信
スタック
動的負荷分散

Lazy Task Creation [Mohr et al. 91] に基づく
レジスタ上
通信
メモリ上通信
仕事を盗む
性能測定





同じアルゴリズムのCプログラムと比較
逐次版: SS20 (HyperSparc 150MHz)
並列版: Sun Enterprise 10000
(UltraSparc 250 MHz × 64)
Schematicの動的型チェックは除いている
並列版SchematicのGC時間は除いている
逐次版性能測定結果
（各最適化の効果）
Normalized Elapsed Time
Schematic
Schematic
Schematic
Schematic
(コンパイル時スケジューリングあり
(コンパイル時スケジューリングなし
(コンパイル時スケジューリングあり
(コンパイル時スケジューリングなし
unboxed チャネルあり)
unboxed チャネルあり)
unboxed チャネルなし)
unboxed チャネルなし)
10.0
9.0
8.0
7.0
6.0
5.0
4.0
3.0
2.0
1.0
0.0
Fib
k
Ta
t
or
s
Q
e
m
i
Pr
P
A
Q
Gr
o
r
e
n
b
逐次版性能測定結果
（Cとの比較）
C
Schematic (with both optimizations)
Normalized Elapsed Time
5.0
4.0
3.0
2.0
1.0
0.0
Fib
k
Ta
Q
t
r
o
s
e
m
i
Pr
P
A
Q
G
r
e
n
rob
並列版性能測定結果
（単純な並列性を持つ問題）
Schematic's Scalability
Linear
Fib
Tak
Nqueen
QAP
60
SpeedUp
50
40
30
20
10
0
0
10
20
30
40
Number of PEs
50
60
並列版性能測定結果（RNA）
Scalability
Solaris thread C
task queue C
Schematic
50
SpeedUp
40
30
20
10
0
0
10
20
30
40
Number of PEs
50
60
並列版性能測定結果（CKY）
Scalability
C
Schematic
50
SpeedUp
40
30
20
10
0
0
10
20
30
40
Number of PEs
50
60
関連研究（1/3）

Id [Schauser et al. 95], Fleng [荒木ら 97]
– 依存関係解析によるスレッドの静的融合
– 我々は同様の効果をコード複製によって実現

Pict [Turner 96]
– 我々と同じく並行計算のコンパイルを扱う
– すべてのチャネル操作にメモリ操作が必要
– 受信前と後の実行を同一スレッド内で行えない
関連研究（2/3）

StackThreads [田浦ら 94, 97]
– Unboxed チャネルを最初に提案
– 我々は unboxed チャネルを、一般的な
並行計算のコンパイルの枠組みの中に導入

リニアチャネル [小林ら 96, 五十嵐ら 97]
– リニアチャネル＝一回だけ使われるチャネル
– リニアチャネルによる通信を静的に除去
– Unboxed チャネルとは直交した方法で、共存可能
関連研究（3/3）

CPS [Appel 92]
– 逐次言語のためのコンパイルの枠組み
– Unboxed チャネルの定式化に
彼らの callee-save レジスタの技術を使用

Cilk [Blumofe et al. 95]
– Cを非同期関数呼び出し拡張
– 我々と同じく細粒度スレッドを効率よく実行
– 我々の言語よりも同期構造が制限されている
•
親が子の終了を待つ以外の同期ができない
結論

並行計算を効率的にコンパイルする枠組み
– コンパイル時スケジューリング (スレッドの融合)
– Unboxed チャネル (レジスタ上スレッド間通信)

並列オブジェクト指向言語Schematicの実装
– 逐次版: 平均してCの 2.5 倍
– 並列版: 高い台数効果
(50台でFib:47倍, RNA:24倍, CKY:15倍)
今後の研究

RNA, CKY の台数効果をさらに向上
– RNA: ビジー時間が伸びる原因の究明
– CKY: アイドル時間を減らす手法の提案

DSMマシン上高性能実装技術の提案
– 外山（四年）の手によってすでに移植は完了

コード複製戦略の改良
– 頻繁に実行される部分を優先的に複製

マルチスレッド拡張Cの実装

Download Report