潜在的なボトルネックが存在する 並列プログラムの効率的実行 東京大学 大学院 理学系研究科 情報科学専攻 米澤研究室 大山 恵弘 田浦健次朗 米澤明憲 ボトルネック 仮定： （分散）共有メモリ並列計算機 上への 並列オブジェクト指向言語 の実装 排他的メソッド 排他的メソッド …….. 排他的メソッド 排他的メソッド 同時に多数起動 例： Java の synchronized メソッド オブジェクト （例：共有カウンタ） ここでの実行時間が 全実行時間を支配 目指すもの ボトルネックを持つプログラムの効率的実行 プログラム全体を 並列実行した時間 ボトルネックだけを 逐次実行した時間 近づけたい 迷信： 台数効果はある台数で止まる 以降はプロセッサを増やしても実行時間は一定 観測事実： 実行時間は一定を保てない。性能は着々と悪化 カウンタプログラムを用いた 予備実験 • C と Solaris threads で記述 • 単純なスピンロックを使用 • 各プロセッサが並列に一つの 共有カウンタを100000まで増やす 台数増加につれ 実行時間は 横ばいどころか 劇的に増加 3000 time (msec) 2500 2000 1500 1000 500 0 0 10 20 30 40 # of PEs 50 60 70 Local-based 実行と owner-based 実行 Local-based 実行 （例：スピンロックによる実装） – 各プロセッサが自らメソッドを実行 – オブジェクト参照時にキャッシュミスが頻発 Owner-based 実行 （例：ブロッキングロックによる実装） – 単一プロセッサ（owner）がメソッドを実行 – 待ちスレッドのコンテキストのキュー操作に関し オーバヘッド キューの排他処理 他プロセッサのキュー操作中の待ち時間 単純なブロッキングロックによる オブジェクトの実装 • コンテキストを格納するキューを用意 • キューをスピンロックで排他処理 • キュー操作の前に必ずスピンロックを獲得 • Owner がコンテキストを一つずつ取り出して実行 スピンロック オブジェクトデータ メソッドのコンテキスト 我々の方式 (1/2) たった１ワードの追加 オブジェクトデータ 非 owner オブジェクトデータ 追加！ Owner オブジェクトデータ 切り離し！ そして逐次的に順に実行！ Owner に高い優先度 → 切り離しは定数時間で成功 （owner は swap を、非 owner は compare-and-swap を使用） 我々の方式 (2/2) コンテキストのプリフェッチ – 他プロセッサが作ったコンテキストの読み出しに伴う キャッシュミスを減らす オブジェクトデータのレジスタへの割り当て このメソッド実行中に このコンテキストのプリフェッチ オブジェクトデータをレジスタで受け渡し これらの処理は並列オブジェクト指向言語 Schematic の コンパイラとランタイムが暗黙に行う 性能評価 (1/3) Ultra Enterprise 10000 上での RNA プログラム(統計情報つき)の実行時間 spinlock block spinblock our scheme time (msec) 5000 4000 3000 2000 1000 0 0 10 20 30 40 # of PEs 50 60 70 性能評価 (2/3) Origin 2000 上での RNA プログラム(統計情報つき)の実行時間 spinlock block spinblock our scheme 20000 time (msec) 16000 12000 8000 4000 0 0 10 20 30 40 50 60 # of PEs 70 80 90 100 110 性能評価 (3/3) Ultra Enterprise 10000 上 RNA での 全 PE の二次キャッシュミス数の総和 spinlock block spinblock our scheme time (msec) 50000 40000 30000 20000 10000 0 0 10 20 30 40 # of PEs 50 60 70 今後の展望 Java への適用 – 同一スレッドのロック再獲得を許す拡張が必要 コンテキスト領域用に大量のメモリを 消費する問題の解決 – 使用メモリが一定量を越えたら local-based 実行に 切り替えるなどの工夫が必要 依然少しずつ性能低下していく問題の解決 除去が面倒なボトルネックの例 MT-unsafe ライブラリ – 逐次環境仮定のライブラリが膨大数存在 入出力 – printf などの呼び出し 分散システムのスタブオブジェクト – サイト間の通信を一手に引き受け 共有変数 – 統計取得用に事象の発生を数えるカウンタ 低級言語（例：Ｃ言語）による 同様の効果の実現 典型的なプログラマの挙動 – ボトルネックでないオブジェクト： local-based 実行 – ボトルネックであるオブジェクト： owner-based 実行 欠点 • ボトルネック部分が動的に決定するプログラムの存在 （プロセッサ数、実行時パラメタの影響） • owner-based 実行の実装そのものが大変 （オブジェクトごとにコンテキストのデータ構造が異なるため ライブラリ化が困難、もしくは非効率的）
© Copyright 2024 ExpyDoc
