潜在的なボトルネックが存在する
並列プログラムの効率的実行
東京大学 大学院
理学系研究科 情報科学専攻
大山恵弘 田浦健次朗 米澤明憲
対象とするプログラム
排他処理をしつつ共有データを頻繁に更新するプログラム
研究の文脈： 共有・分散共有メモリ並列計算機
並列オブジェクト指向言語 の実装
上への
排他的メソッド 排他的メソッド …….. 排他的メソッド 排他的メソッド
更新！
更新！
更新！
ボトルネック
オブジェクト
（例：共有カウンタ）
例： Java の
synchronized メソッド
更新！
ボトルネックを持つプログラムの
台数効果曲線
迷信： 台数効果はある台数で止まる。以降は実行時間は一定
実行時間
現実
理想（かつ目標）
プロセッサ数
「過剰な」プロセッサは投入されうる！
∵ プログラムの動的な挙動の予測はときに困難
∵ 必要な台数はプログラムの「場面」に依存する
予備実験結果
（Cのカウンタプログラム）
• Solaris threads & Sun Ultra Enterprise 10000
• 各プロセッサが並列に一つの共有カウンタを増やす
スピンロック
単純なブロッキングロック
我々の方法
2000
time (msec)
1500
台数増加につれ
実行時間は
横ばいどころか
劇的に増加
1000
500
0
0
10
20
30
# of PEs
40
50
60
70
研究のゴール
• ボトルネックを持つプログラムの効率的実行
– オブジェクトの排他処理 の実装に注目
プログラム全体を
並列実行した時間
近づける
ボトルネックだけを
逐次実行した時間
他の部分
他の部分
ボトルネック部分
ボトルネック部分
1PE
50PE
解くべき問題は何か？
ナイーブな実装
他の部分
他の部分
ボトルネック
部分
理想とする実装
他の部分
ボトルネック部分
ボトルネック部分
1PE
50PE
ボトルネック部分の実行時間増大を食い止める！
発表の概要
• ボトルネックとなりうるオブジェクトの例
• 単純な実装とその問題
– Local baseな方式
– Owner baseな方式
• 我々の実装
– キュー切り離し機構
– compare-and-swap による優先度機構
– コンパイル時最適化
• 性能評価 & 関連研究
ボトルネックとなりうる
オブジェクトの例
• MT-unsafe関数をMT環境で単純に再利用
するために導入されたオブジェクト
• 入出力を仮想化したオブジェクト
• 分散システムのスタブ
– サイト間の通信を一手に引き受け
• 共有変数
– 統計取得用に事象の発生を数えるカウンタ
これらを取り除くプログラムの改良はときに困難
Local baseな実行方式
（例：スピンロックによる実装）
メソッド
メソッド
メソッド
メソッド
メソッド
メソッド
各プロセッサは自分で
メソッドを実行
↓
オブジェクト
各プロセッサは自分で
データ
オブジェクトを参照、更新
オブジェクトデータ
（＝インスタンス変数）
オブジェクト
利点:
“計算” の移動なし
欠点:
オブジェクトの参照でキャッシュミス
（他プロセッサによるキャッシュの無効化、更新のため）
Local baseな実行に存在する
オーバヘッドの確認
empty method
counter
time (msec)
2000
1500
1000
Ultra Enterprise 10000 上の
Cプログラム
500
0
0
10
20
30
40
50
# of PEs
オブジェクトの参照、更新オーバヘッド
• 台数の増加とともに増加
• 60PE上では実行時間の 1/3
60
70
Owner baseな実行方式
他プロセッサ（オーナ）に、自分のメソッドの実行を「依頼」
→ リクエスト（＝ メソッドの情報を含むデータ構造）を作成
オーナ
非オーナ
オブジェクト
単純なブロッキングロックによる
owner baseな実行の実現
オーナ ＝ そのオブジェクトのメソッドを実行中のプロセッサ
オーナが存在 → リクエストを作成、挿入
オーナが不在 → 自分がオーナになりメソッドを実行
• 一個ずつ
• 排他処理しつつ
デキュー
データ
オブジェクト
１プロセッサが複数メソッドを続けて実行する可能性が高い
Owner baseな実行の利害得失
利点:
オブジェクトの参照でキャッシュミスが少ない
欠点:
“計算” を移動させるオーバヘッド
• キュー操作の排他処理そのもの
• キューの排他処理のオーナの待ち時間
• リクエスト読み出し時のキャッシュミス
（クリティカル･パスを決定するオーナの実行に注目）
軽減できないか？
我々の方法の概要
• 単純なブロッキングロックを改良
– リクエスト集合の切り離し
• リクエスト操作の排他処理の回数を削減
– オーナに高い優先度
• オーナのリクエスト操作１回あたりの時間を削減
– コンテキストデータのプリフェッチ
• コンテキストデータ読み出し時のキャッシュミスを削減
我々の方法は並列オブジェクト指向言語 Schematicの
コンパイラとランタイムが暗黙に実現する
データ構造
• リクエストをリストで管理
– 各オブジェクトに１ワードのポインタ領域を付加
オブジェクト
– 非オーナ： リクエストを作成、リストに挿入
– オーナ：
リスト内のリクエストを取り出し、実行
アルゴリズム設計方針
• オーナの挙動がクリティカルパスを決定
– とにかくオーナの実行を速くする
– 非オーナの実行が少々遅くなってもよい
– とにかくリクエストの取り出しを効率的にする
– リクエストの挿入は少々非効率的でもよい
非オーナによる
リクエストの挿入
X
オブジェクト
Y
A
B
Z
C
非オーナによる
リクエストの挿入
X
オブジェクト
Y
A
B
Z
C
compare-and-swapで更新
割り込まれたら再試行
非オーナによる
リクエストの挿入
X
オブジェクト
Y
A
B
Z
C
compare-and-swapで更新
割り込まれたら再試行
オーナによる
リクエストの切り離し
オブジェクト
Y
A
B
C
ポイント
• リストを丸ごと切り離す
• swapで更新： ポインタ領域がどこを指していても成功
→ オーナは他プロセッサに干渉されない
オーナによる
リクエストの切り離し
オブジェクト
Y
A
B
C
ポイント
• リストを丸ごと切り離す
• swapで更新： ポインタ領域がどこを指していても成功
→ オーナは他プロセッサに干渉されない
オーナによる
切り離したリクエストの実行
排他処理なしで
順番に実行
Y
A
B
C
オブジェクト
X
Z
オーナを干渉せず
リクエスト挿入
1. オーナが行っていた多数の排他操作を除去
オーナに有利な優先度機構
• リストの操作：
– 非オーナによる挿入 （compare-and-swap） :
多数回失敗しうる
– オーナによる切り離し （swap） :
常に定数命令ステップで成功
2. オーナの排他処理の待ち時間のオーバヘッドを大幅に削減
コンパイル時の最適化 （1/2）
• リクエストのプリフェッチ
このリクエスト処理中
このリクエストをプリフェッチ
...
while (req != NULL) {
PREFETCH(req->next);
EXECUTE(req);
req = req->next;
}
...
3. リクエスト読み出し時のキャッシュミス数を削減
コンパイル時の最適化 （2/2）
• オブジェクトデータをレジスタ上に保持
– 切り離したリクエストの処理中、非オーナが
オブジェクトを参照、更新しないことを利用
レジスタで受け渡し
オブジェクト
１つのメソッドにコードを２バージョン用意
自ら実行する時使うコード：
メモリ上のデータを操作
オーナが実行する時使うコード： レジスタ上のデータを操作
低級言語（例：C言語）による
同様の効果の実現
• 「ボトルネック発見→コード書き換え」アプローチ
– ボトルネック： local baseな実行を実装
– 非ボトルネック： owner baseな実行を実装
• 「高級言語の協調」アプローチよりずっと面倒
– Owner baseな実行の実装そのものが大変
• オブジェクト、メソッドごとにリクエストのデータ構造が異なる
• ライブラリ化が困難、もしくは非効率的
– ボトルネックが動的に出現するプログラムが存在
• プロセッサ数、実行時パラメタ、プログラムの「場面」の影響
実験結果 （1/2）
RNA二次構造予測 (統計情報つき)
in Schematic on Ultra Enterprise 10000
time (msec)
spin
block
spinblock
our scheme
7000
6000
5000
4000
3000
2000
1000
0
0
10
20
30
40
# of PEs
50
60
70
実験結果 （2/2）
RNA二次構造予測 (統計情報つき)
in Schematic on Origin 2000
spin
block
spinblock
our scheme
time (msec)
16000
12000
8000
4000
0
0
10
20
30
40
50
60
# of PEs
70
80
90
100
110
Cのカウンタプログラムを
用いた興味深い実験結果
• 単純なブロッキングロック：
キュー排他処理待ち時間が最大オーバヘッド
– オーナの全実行時間の70 %
• 我々の方法は１プロセッサ上でも高性能
– スピンロック:
641 msec
– 単純なブロッキングロック: 1025 msec
– 我々の方法:
810 msec
（実行時間）
関連研究 （1/3）
- 並列に起動されたメソッドの効率的実行 • ICC++ [Chien et al. 96]
– 静的解析で排他的でないメソッドの組を検出
• Concurrent Aggregates [Chien 91]
– プログラマの明示的記述を通じた並列実行
• Cooperative Technique [Barnes 93]
– 後に排他区間に入ったプロセッサが
先に入ったプロセッサを「手伝う」
どれも非排他的メソッド間の並列性抽出が主眼
どれも排他的メソッド衝突時の性能低下対策なし
関連研究 （2/3）
- アクセス競合時に高性能なスピンロック • MCSロック [Mellor-Crummey et al. 91]
– スピン領域をプロセッサごとに用意
• Exponential Backoff [Anderson 90]
– ロックが獲得できないプロセッサをうまく
「休ませる」ためのヒューリスティクス
これらはlocal baseな実行を与える
オブジェクト参照の局所性低下の問題が依然残る
関連研究 （3/3）
- その他 • スタック交換 [外山ら 98]
– 非オーナによるlocal baseなメソッド実行の
低いメモリ局所性の問題を解決
– 一般（＝非ボトルネック）の計算移動を効率化
• Bimodal object-locking algorithm [小野寺ら 98],
Thin Lock [Bacon et al. 98]
– Javaのモニタの文脈
– 低レベル実装は彼らの方法を参考に作成
– オブジェクト参照の局所性の考察なし
まとめ
• ボトルネックを持ちうる並列プログラムを
効率的に実行する方法を示した
– 問題の明確化
• 既存の実装ではボトルネックで悲劇的に性能低下
– 解決法の提案
• ボトルネックの処理を劇的に高速化する実装
– 実用プログラムによる有効性の確認
• UE 10K （SMP）、Origin 2K （DSM） で実験
• 単純な方法の数倍の性能 （数百％の性能向上）
今後の課題
• 場合により膨大なメモリを使いうる問題の解決
– リクエストの長大なリストができる可能性がある
– Owner baseな実行に共通の問題
– 本研究は速度面の解決。メモリ面には注目していない
– 単純な解法: リクエストが占めるメモリ ＞ ある閾値
⇒ local baseな実行に動的に切り替え
• 実行状況に応じたプロセッサ数の増減
– 言語処理系が各場面で「最適な」プロセッサ数を決定
– プロセッサ過剰状態そのものを除去
© Copyright 2025 ExpyDoc
