スケーラブルでないモジュールを含む
並列プログラムにおける高性能の達成
Achieving High Performance in Parallel
Programs Containing Unscalable Modules
東京大学 大学院
理学系研究科 情報科学専攻
大山恵弘
満足のいく性能モデル
• プロセッサ増加 ⇒ 実行時間減少 or
実行時間そのまま
すべてのプログラムで成立してほしい
はたして現実は？
Motivating Example
• 各スレッドが独立にfib(10)と共有カウンタの増加
を交互に繰り返し実行するプログラム
– C + Pthreads, Sun Enterprise 10000
– 仕事量の総和はプロセッサ数に非依存
time (msec)
2000
fib
実行のほんの一部が逐次化
fib + counter
↓
(spin)
fib + counter
満足のいく性能モデルが破綻
1500
1000
500
(mutex)
0
0
10
20
30
40
number of processors
50
60
実行を逐次化するモジュール
（ボトルネックモジュール）
広範囲に存在！
• Thread-unsafeライブラリ
– MPICH、GTK+
• 共有資源の操作
– I/O、GUI、大域変数、共有バッファ
– 並列ループの誘導変数
• 暗黙に排他処理するライブラリ
– 多くのmallocの実装
現状
多くの並列プログラムで不満足な性能モデル！
並列プログラム
逐次モジュールが
ほとんどないプログラム
行列積
GUI
Fib
暗号破り
自然言語処理
webサーバ
並列分野の既存研究の多く
本研究の目的
• 満足のいく性能モデルを、すべての並列
プログラムで実現する言語
– 共有メモリ計算機が対象
ボトルネックの最大性能ギリギリ
Q: 満足のいく性能モデルを
得ることに意味あるの？
A: ある！
time
このへんで実行したら悲劇
（最高性能の半分）
number of processors
Ｕ字の底のプロセッサ数で
実行すればいいのでは？
• 最適なプロセッサ数は予測困難
– 動的な挙動の予測はときに困難
– 最適な数は入力やプログラムの場面に依存
色々なプロセッサ数で何回も同じ計算をするのは
処理系実装者やベンチマーク屋だけ！
我々の怒り
多くの並列プログラマが
唯々諾々と従っている啓示
「並列化の恩恵受けたければ、
ボトルネックを皆無にすべし」
こんな高飛車で、
万人に並列処理が普及するか？
「最高性能を出すプロセッサ数は
プログラマが自分で見つけるべし」
そんな苦労をプログラマに
負わせておいていいのか？
並列処理を大きく
discourage！
我々が取り組んだ問題
• ボトルネック存在下でも高性能を出すには
– 排他処理
– スレッドスケジューリング
– 言語設計
はどうあるべきか？
３つの本質的な部分問題
•
ボトルネック部分の実行コストの削減
– ボトルネック担当プロセッサの動的導入で達成
•
ボトルネック部分の実行回数の削減
– 複数の呼び出しの「融合」で達成
•
ボトルネック部分での過大なメモリ消費の抑制
– プロセッサ数の動的制御で達成
３つのポイントがもたらすもの
time
１
２
number of processors
３つのポイントがもたらすもの
メ
モ
リ
消
費
量
limit
３
number of processors
Part 0
我々の言語
我々の言語Amdahl
• C++
+ 軽量スレッド
+ 排他メソッド
単純なプログラミングモデルを提供
スレッド
• API:
athread_create(f, arg, thr_id);
• Lazy Task Creation [Mohr et al. 91]に
もとづくスレッド管理
– 低コストで多数のスレッドを生成可
• 「並列単位1つ ⇔ スレッド1つ」のプログラミング
– ランタイムが自動的に動的負荷分散
• Task stealing
排他機構
• 排他メソッド
– ≒ synchronized methods in Java
– １つのオブジェクト上で排他的に実行されるメソッド
class Counter {
int value;
…
sync inc(int n) {
value += n;
}
}
Part 1
ボトルネック部分の実行における
メモリ通信コストの最小化
情報処理学会論文誌に掲載
その拡張版を国際学会PDSIA ’99で発表
既存の逐次化モジュールの実装法
• ロックを付加し呼び出しを逐次化
ＣＰＵ１
ＣＰＵ２
ボ
ＣＰＵ３
既存の方法の問題 （1）
• ロック操作で大きなメモリアクセス遅延
– 同じアドレスへのアクセスの衝突
→アクセスコストの飛躍的増加
ＣＰＵ２
ＣＰＵ１
ＣＰＵ３
既存の方法の問題 （2）
• 更新された情報の読出でキャッシュミス
– 異なるプロセッサが交代で実行するため
ＣＰＵ１
ＣＰＵ２
ボ
a, b
ＣＰＵ３
Amdahlのランタイム技術
• アクセス衝突
→ 呼び出しデータ（タスク）のリスト作成
• 複数の呼び出しを１プロセッサが連続実行
ＣＰＵ２
f(5)
担当するぞ！
ＣＰＵ１
ボ
a, b
f(3)
ＣＰＵ３
f(7)
Amdahlのランタイム技術
• アクセス衝突
→ 呼び出しデータ（タスク）のリスト作成
• 複数の呼び出しを１プロセッサが連続実行
f(5)
f(3)
ＣＰＵ１
ＣＰＵ２
f(7)
ボ
a, b
ＣＰＵ３
この方法がもたらす利益
• ロック操作の大幅減少
– 例： １回ロック操作して、３０個メソッド実行
– 全部消えはしない
• 連続実行中：
オブジェクトの読出と更新
⇔ キャッシュの読出と更新
• ボトルネックに常にプロセッサ
Amdahlのコンパイル時最適化
• メモリ読出コストをさらに削減
– Prefetch 命令の挿入
– 手続き間 register promotion
これの実行中
この情報をprefetch
f(5)
ＣＰＵ１
f(3)
ボ
f(7)
a, b
連続実行中はa,b
をレジスタに置く
実験
• アプリケーション
– N body, RNA
• 比較したもの
– C + Solaris threads + task queue
• Spin locks, mutex locks
– Amdahl
• Spin locks, mutex locks, 我々の提案する方法
• Sun Enterprise 10000 （64 CPU）
RNA
20000
C + Solaris threads
(spin)
C + Solaris threads
(mutex)
Amdahl (spin)
time (msec)
15000
10000
Amdahl (mutex)
5000
Amdahl (detach)
0
0
10
20
30
40
number of processors
50
60
N body, 木作成フェーズ
8000
C + Solaris threads
(spin)
C + Solaris threads
(mutex)
Amdahl (spin)
time (msec)
6000
4000
Amdahl (mutex)
2000
Amdahl (detach)
0
0
10
20
30
40
number of processors
50
60
N body, 全フェーズ合計
15000
time (msec)
C + Solaris threads
(spin)
C + Solaris threads
(mutex)
Amdahl (spin)
Amdahl (mutex)
Amdahl (detach)
0
0
10
20
30
40
number of processors
50
60
非衝突時の性能
Cで書いたマイクロベンチマーク
no lock
roundrobin
spin
ticket
MCS
Solaris mutex
block
Amdahl
1200
time (msec)
1000
800
600
400
200
0
•Amdahlの方法の実行時間：
•単純なblocking lockの0.92倍
•単純なspin lockの1.32倍
Part 2
複数の排他的な操作を
融合する機構
情報処理学会論文誌に掲載
既存の枠組みの問題
• プログラムの動的挙動に適応する効率化支援
機構が少ない
– 我々の観測： アクセス衝突時に生じる効率化の機会を
有効利用できていない
重複して呼び出し
ＣＰＵ１
window
repaint
ＣＰＵ２
repaint
ＣＰＵ３
repaint
Amdahlのアプローチ
• 排他メソッドの複数の呼び出しの融合
– 動的に逐次化された２つの呼び出しを融合
– プログラマが融合規則を記述
プログラム例 （１/２）
class Window {
…
sync repaint() {
…
}
融合規則
fusion repaint() & repaint() {
repaint();
}
}
repaintを「まびき」
プログラム例 （２/２）
class Buffer {
int len;
double elements[...];
...
sync void put(double v) { elements[len++] = v; }
sync double get() { return elements[--len]; }
fusion put(v) & get() {
return v;
}
}
融合規則
putとgetを「バイパス処理」
融合処理の実装
タスクリストの操作で実現
専念！
ＣＰＵ２
♪
repaint
ＣＰＵ１
window
repaint
ＣＰＵ３
repaint
この融合の研究の広い見方
• 並列言語ならではの効率化の機会を指摘した
– 逐次言語:
x = y-2;
x += 3;
x = y+1;
– 並列言語: 文面に現れない制御フロー
• 既存研究の盲点
val
+=1;
val
+=2;
val
+=3;
実験
• ImageViewer
– repaint & repaint → repaint
• FileWriter
– write & write → strcat + write
• RNA
– inc & inc → inc
ImageViewer
no fusion
fusion
time (msec)
20000
15000
10000
5000
0
0
2
4
6
8
number of processors
10
12
FileWriter
no fusion
fusion
time (msec)
5000
2500
0
0
10
20
30
40
number of processors
50
60
RNA
no fusion
fusion
time (msec)
6000
4000
2000
0
0
10
20
30
40
number of processors
50
60
Part 3
プロセッサ数の動的調節による
メモリ消費量の制御
単純な実装における問題
• ボトルネックにおける大きなメモリ消費量
ＣＰＵ２
f()
f()
ＣＰＵ３
...
f()
…..
ＣＰＵ１
ボ
生産者消費者アプリケーション一般が共有
ＣＰＵｎ
メモリ消費量拡大による悪影響
• Cache miss, page faultの増加
– Working setの増加による
• 他ジョブで使えるメモリが減少
– １つの邪悪なプログラムが、その計算機上の
全プログラムを凍らせうる
Motivating Example
ボトルネックに付加されるタスク数： 数百のオーダ
←
タ
ス
ク
数
我々の目標
• １つのオブジェクト（モジュール）に付加
されるタスク数の最大値を小さく抑える
– 例：各オブジェクトに最大６４個
– 「メモリ消費量の制限⇔タスク数の制限」
と問題を限定
目標達成のための単純な方法
• タスク数 ＝ 閾値
→タスクを入れようとするＣＰＵはスピンして待つ
64
…..
f()
ＣＰＵ１
ボ
f()
ＣＰＵ３
デッドロック発生！
（詳細は論文を参照）
f()
我々はより緩い目標をめざす
• Soft limitをほとんどの場合に越えない
soft limit
タ
ス
ク
数
時間
我々のアプローチの概要
• プロセッサ数の動的調節でタスク数を制御
– タスク数がsoft limitを越えそう
→プロセッサ減らす
タスク生成ペースを遅らせる
– タスク数がsoft limitを越える気配なし
→減らしたプロセッサを復活させる
Amdahlの実装
生存可能プロセッサ数カウンタ
現プロセッサ数カウンタ
２８
５０
定期的に更新
f()
ＣＰＵ１
ボ
脱退！
ＣＰＵ３
...
f() …..
ＣＰＵ２
ＣＰＵ５０
プロセッサの脱退
thread
thread
thread
thread
thread
thread
thread
ＣＰＵ１５
ＣＰＵ３７
プロセッサの増加
生存可能プロセッサ数カウンタ
４８
現プロセッサ数カウンタ
３１
ＣＰＵ１
ＣＰＵ３３
ＣＰＵ２
定期的にチェック
...
ＣＰＵ３２
ＣＰＵ３１
生存可能プロセッサ数の決定法
• 次のカウンタ更新時のタスク数を予測
– 過去の履歴からタスクが入るペース、出るペースを予測
• その数がsoft limitを越えないよう、入るペースを調節
– 仮定： 入るペース∝プロセッサ数
soft limit = 64
...
...
20
プロセッサ数を 20/60＝1/3 に
...
ボ
44
60
実験結果
• ほとんどの時間でsoft limit以下
• タスク数小 → プロセッサ数増
•最大タスク数 ＜ ２×soft limit
実行時間 (６０プロセッサ上）
numprocessors fixed
numprocessors varied
normalized execution time
2
1.5
1
0.5
0
Fib&Memwrite
RNA
N body
（Part 4）
クリティカルパスの実行時計算
国際学会 HIPS 2000 で発表
（LNCS vol. 1800）
クリティカルパスの実行時計算
• プログラムにコードを挿入
• クリティカルパスを求めつつプログラムを実行
• Cilk [Blumofe et al. 95],
Paradyn [Hollingsworth 98]
• クリティカルパスの利益
– 性能モデルの調査と検証を
助ける
– チューニングすべき場所の
発見に役立つ
我々がやったこと
• 既存の方法を改良
– メモリ通信コストを考慮
– 第一級通信データ構造の導入
• 改良した方法を並列言語Schematicに実装
– 実験で有効性を確認
関連研究 （１/３）
• 互いに干渉しない排他処理間の並行性抽出
– ICC++ [Chien et al. 96], OPA [Yasugi et al. 98],
Schematic [Taura et al. 96], Reader-writer locks
• Associativeな操作の並行実行
– CA [Chien 91], Reduction [Fisher et al. 94],
Adaptive object replication [Rinard et al. 99]
衝突した複数の排他操作
干渉しない
Associative
関連研究 （２/３）
• Locality-Enhanced Staged Server [Larus 00]
– 似た操作を固めて実行して局所性向上
– まだアイデア段階。実験結果なし
• Network combining [Gottlieb et al. 83]
– ネットワークスイッチによる複数の命令の融合
• プログラム変換による複数の処理の融合
– Bird-Meertens Formalism [Bird 89], Loop fusion,
Deforestation [Wadler 90], Parallel scans,
プログラム融合変換 [Onoue et al. 97]
– 静的に検出できる連続した操作を静的に融合
関連研究 （３/３）
• プロセッサ数の動的調節
– [Hall et al. 97], [Thitikamol et al. 99], [Yue et al. 96], [WernerKytölä et al. 00], [Nguyen et al. 96], [Severance 96]
– 過去の性能を基にイテレーションの切れ目や
並列ループの直前のみで調節
• Congestion avoidance for TCP
– [Jacobson 88], [Jain et al. 97], [Brakmo et al 95]
– データ生成ペースの動的調節という点で共通
• Ninja [Welsh et al. 2000]
– サーバの要求キューの長さの制限
– まだアイデア段階。実験結果なし
今後の課題
• 各排他処理実装の性能のよりよい理解
– 「なぜ我々の方式が速いか」を形式的に議論
• 正しい融合規則の記述の支援
– 明らかに誤った融合規則を静的に検出
• 性能向上を強く志向したプロセッサ数制御
まとめ
• 満足のいく性能モデルの実現に大きく
近づける並列言語実装技術を提案
極限まで近づけた！
全体性能
最低性能のモジュールの性能
（GUI, I/O, mem. allocator, counter…）
• プロセッサを投入しすぎたときの悲劇を最小化
• 「軽いスレッド ＋ 排他メソッド」による
快適な並列プログラミングモデルを維持
Amdahlがもたらすもの
単純でないプログラム
資産
Amdahlによる
並列実行
値下がりしない
株
低
高 リスク
高リターン
逐次実行維持
タンス預金
低リスク
低リターン
並列処理がより広く普及！
並列プログラマは待望のエル・ドラドを獲得！
おわり
• Visit
http://www.yl.is.s.u-tokyo.ac.jp/~oyama/publications/
© Copyright 2024 ExpyDoc
