潜在的なボトルネックが存在する 並列プログラムの効率的実行 東京大学 大学院 理学系研究科 情報科学専攻 大山恵弘 田浦健次朗 米澤明憲 対象とするプログラム 排他処理をしつつ共有データを頻繁に更新するプログラム 研究の文脈: 共有・分散共有メモリ並列計算機 並列オブジェクト指向言語 の実装 上への 排他的メソッド 排他的メソッド …….. 排他的メソッド 排他的メソッド 更新! 更新! 更新! ボトルネック オブジェクト (例:共有カウンタ) 例: 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な実行の実現 オーナ = そのオブジェクトのメソッドを実行中のプロセッサ オーナが存在 → リクエストを作成、挿入 オーナが不在 → 自分がオーナになりメソッドを実行 • 一個ずつ • 排他処理しつつ デキュー データ オブジェクト 1プロセッサが複数メソッドを続けて実行する可能性が高い Owner baseな実行の利害得失 利点: オブジェクトの参照でキャッシュミスが少ない 欠点: “計算” を移動させるオーバヘッド • キュー操作の排他処理そのもの • キューの排他処理のオーナの待ち時間 • リクエスト読み出し時のキャッシュミス (クリティカル・パスを決定するオーナの実行に注目) 軽減できないか? 我々の方法の概要 • 単純なブロッキングロックを改良 – リクエスト集合の切り離し • リクエスト操作の排他処理の回数を削減 – オーナに高い優先度 • オーナのリクエスト操作1回あたりの時間を削減 – コンテキストデータのプリフェッチ • コンテキストデータ読み出し時のキャッシュミスを削減 我々の方法は並列オブジェクト指向言語 Schematicの コンパイラとランタイムが暗黙に実現する データ構造 • リクエストをリストで管理 – 各オブジェクトに1ワードのポインタ領域を付加 オブジェクト – 非オーナ: リクエストを作成、リストに挿入 – オーナ: リスト内のリクエストを取り出し、実行 アルゴリズム設計方針 • オーナの挙動がクリティカルパスを決定 – とにかくオーナの実行を速くする – 非オーナの実行が少々遅くなってもよい – とにかくリクエストの取り出しを効率的にする – リクエストの挿入は少々非効率的でもよい 非オーナによる リクエストの挿入 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) • オブジェクトデータをレジスタ上に保持 – 切り離したリクエストの処理中、非オーナが オブジェクトを参照、更新しないことを利用 レジスタで受け渡し オブジェクト 1つのメソッドにコードを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 % • 我々の方法は1プロセッサ上でも高性能 – スピンロック: 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 2024 ExpyDoc