Microsoft PowerPoint - t-kubo07PN-LAMBDA-slide.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - t-kubo07PN-LAMBDA-slide.ppt"

ひろとひろなが
4 years ago
Views:

リングネットワークにおける λコンピューティング環境に適した共有メモリアーキテクチャの設計と設計と評価大阪大学大学院情報科学研究科大学院情報科学研究科村田研究室久保貴司発表内容研究の背景と目的 λコンピューティング環境共有メモリアーキテクチャの設計と評価設計トポロジメモリアクセスモデルキャッシュとメモリの一貫性制御モデル化と解析評価まとめ 2007/6/14 PN 研究会

1 リングネットワークにおける λコンピューティング環境に適した共有メモリアーキテクチャの設計と設計と評価大阪大学大学院情報科学研究科大学院情報科学研究科村田研究室久保貴司発表内容研究の背景と目的 λコンピューティング環境共有メモリアーキテクチャの設計と評価設計トポロジメモリアクセスモデルキャッシュとメモリの一貫性制御モデル化と解析評価まとめ 2007/6/14 PN 研究会 /6/14 PN 研究会 2 背景グリッドコンピューティング技術への期待の高まり TP/IP は分散並列計算には不向きパケット処理や再送制御による遅延などのオーバヘッドが発生大量のデータ交換を行う大規模計算への応用では十分な計算性能を達成することは困難 λコンピューティング環境を提案高速高信頼なネットワークを基盤とした計算環境ノード計算機間に波長パスを設定し, 専用の通信路として用いる従来の研究関連研究 [1-3] における λコンピューティング環境の実現 NTT フォトニクス研究所が開発した情報共有システム (AWG( AWG-STAR システム ) を利用並列計算アプリケーションの実行時間に基づいて評価分散計算を行う MPI やOpenMPI の設計と実装を行い, 実際のアプリケーションを用いてその性能を評価システムの各処理にどれだけ時間がかかっているのか不明 AWG-STAR システム PI バス光リング共有メモリボード 2007/6/14 PN 研究会 /6/14 PN 研究会 4 研究の目的 λコンピューティング環境のシステムの定量的な評価 λコンピューティング環境における計算性能ネットワーク特性や共有メモリシステムにより影響 λコンピューティング環境に適した適した共有メモリアーキテクチャの設計と評価設計ハードウェア制約の考慮共有メモリアーキテクチャの特徴を決定する要因の検討キャッシュ一貫性制御に焦点を当てた動作の検討評価ノード計算機のモデル化と解析計算スループットを指標として評価共有メモリアーキテクチャの設計 A. トポロジリングトポロジメッシュトポロジ. メモリアクセスモデル Uniform Memory Access (UMA) Non Uniform Memory Access (NUMA). キャッシュ一貫性制御スヌープ法ディレクトリ法キャッシュとメモリ間の一貫性制御無効型と更新型ライトスルーとライトバック 2007/6/14 PN 研究会 /6/14 PN 研究会 6 1

2 A. トポロジメモリアクセスモデルトポロジリングトポロジ少数の波長で作成実現可能ブロードキャスト時にデータの複製が不要データ共有における伝播遅延ノードの処理遅延は大メッシュトポロジ多数の波長が必要ブロードキャスト時にデータの複製が必要データ共有における伝播遅延ノードの処理遅延は小ハードウェア制約の考慮 WDM 技術の発達により 1つの物理回線に複数の波長を多重化することが可能多数の波長を利用するには多数のインターフェースが必要制御の複雑化システムのコストが高 UMA モデル全ての PU が同じ共有メモリを持つ共有メモリへ共有バスを介してアクセス任意のアドレスに対して PU のメモリアクセス時間が同じ共有バスの競合 NUMA モデル各 PU はキャッシュと共有メモリを持つそれぞれの共有メモリは異なるアドレスを持つ他の PU が持つ共有メモリへ相互接続網を介してアクセスアドレスによって PU のアクセス時間が異なる共有メモリ共有バス相互接続網共有メモリへは相互接続網を介してアクセスされるキャッシュ PU 共有メモリキャッシュ PU 2007/6/14 PN 研究会 /6/14 PN 研究会 8 キャッシュ一貫性制御 (1) スヌープ法共有メディアを監視システムの挙動を把握ディレクトリ法どのキャッシュがどのキャッシュラインを保持するかという情報を各ノードのディレクトリに記憶キャッシュとメモリ間の一貫性制御キャッシュを一致させる方法書き込み時に該当キャッシュを無効化する無効化型書き込み時に該当キャッシュを更新する更新型キャッシュを一致させるタイミング更新されたキャッシュに対して読み込みアクセスがあった場合に書き戻しを行うライトバックキャッシュが更新されるたびに書き戻しを行うライトスルーキャッシュ一貫性制御 (2) 本研究では : スヌープ法リングトポロジを取るため, ネットワーク上のデータを監視することにより制御が簡単トークンリングとし, トークンを監視することにより実現キャッシュ一貫性制御 : 無効化型ライトバック書き込みが行われたキャッシュを無効化するため, 最新の情報を保持するキャッシュを記憶する必要がない書き込みが行われても, すぐに共有メモリへ書き戻しを行わず, 読み込みが発生したときのみ共有メモリへ書き戻しを行う為, ネットワークの使用頻度が低い 2007/6/14 PN 研究会 /6/14 PN 研究会キャッシュ一貫性制御の内部キャッシュの lean 共有メモリと PU のキャッシュが一致 Dirty 共有メモリと PU のキャッシュが不一致 Invalid PU のキャッシュが無効 2007/6/14 PN 研究会 11 : ローカル読み込み : ローカル書き込み : 他ノードの読み込み : 他ノードの書き込み I D リング UMA アーキテクチャコントロールトークン共有キャッシュメモリメモリ #0 トポロジとしてはリングトポロジ共有メモリの書き戻し方法各ノードには共有メモリとキャッシュメコントロールトークンを待つ G モリコントロールトークンにロック信号をつけてリング上に送信同一の共有メモリアドレスコントロールトークンに更新一貫性制御を行うコントロールトークンデータをつけてリング上に送信 #1 #2 0 無効 A A G A 0: ロック A H 2007/6/14 PN 研究会 12 #4 F L #3 V 2

3 複数の波長パスの利用リングトポロジでは, 全ノードを経由するため処理遅延が大きくなる複数の波長を用いてノードをカットスルーし, 処理遅延を小さく抑える 2007/6/14 PN 研究会 13 送信元波長パスの設定送信先通信経路の例波長 λ11 が全てのノードを経由す左上のノードからるように張る左下のノードへの通信方法 2 波長扱うことのできるノードを決波長 2 を使用し, ノードをカットス定するルーすることにより処理遅延が減分割するノード少する数が均等になるように配置波長 1, 及び波長 2波長のどちらを使用 λ22 を 2 波長扱うことのできるするかは, 送信先ノードに張るアドレスによって決定される 2007/6/14 PN 研究会 14 λ1 λ2 モデル化と解析共有メモリアーキテクチャの動作に基づき遷移図を作成ノード計算機の PU のに着目計算処理を行っているローカルメモリにアクセスしているキャッシュ一貫性制御を行っているなど解析にはセミマルコフ過程を利用の滞在時間を任意に設定可能各の定常確率を導出 s 2007/6/14 PN 研究会 15 UMA モデル :2: 波長の遷移図他ノードの 25 書き戻し要求ブロードキャスト後の Pd D キャッシュのトークン待ち調査 Pc キャッシュの容量確保 1-Pc-Pd ローカルメモリへ読み込み I 28 ブロック 1-P アクセス (1-s)/(1+Pq) P r ブロック w 制御トークン待ち h*r*(1-p) r*p (1-h)*r*(1-P) 33 Pq/(1+Pq) 1 s/(1+pq) 2 書き戻し共有メモリへ計算処理アクセス (1-h)*w*(1-P) 8 h*w*(1-p) 制御トークン待ち P 5 9 D w*p w 3 ブロック w ブロック P 他ノードの他ノードの 6 自ノードの r キャッシュラインの書き込みキャッシュ更新キャッシュの他ノードのロック解除調査キャッシュの 1- r 調査 Pc-Pd Pc+Pd キャッシュの容量確保 35 ブロードキャスト後のトークン待ち Pc キャッシュラインの更新制御トークン待ち I 11 Pd 他ノードのキャッシュをI D P 1-1-P 18 ブロックキャッシュの16 容量確保 τ 共有メモリへのリードアクセス 3 3τ/ 2 + 時に通過する T/2 21 T 4 t τ 共有メモリへのライトアクセス 6 t1時に通過する 24 3τ/ 2 + T/ τ キャッシュ一貫性制御を行って τ/ 2 + いる T/ T 11 0 共有メモリへ書き戻しを行って 29 2τ 12 t2 いる 30 t ローカルで処理を行っている 32 h*t1+(1-h)(t1+t2) τ 33 t1+t2 16 t2 19 τ 22 3τ/ 2 + T/2 25 T t1 34 2τ 他ノードの 1- 書き戻し要求 τ 35 τ-t キャッシュラインをロック 2007/6/14 PN 研究会 18 3τ/ 2 + T/2 36 τ-t16 評価のための数値例計算機ノードのスペック PU- -キャッシュ間の遅延 ns キャッシュ - メモリ間の遅延 1us キャッシュ容量 24 K キャッシュラインサイズ 4 K ネットワークインターフェイスでの処理遅延 3us 帯域 Gbps 伝播遅延 5 us/km その他, 必要となるパラメータキャッシュヒット率 0.95 PU が発行する命令頻度 LAD 命令 15%,STORE 命令 5%,, その他 ( レジストリ間計算 ) 80% 解析のパラメータノード数 N (4 ~ 64) 光リングの長さ L km (0.01km ~ 0km) 共有メモリへのアクセス頻度 S (^(-1) 1) ~ ^(-6)) 2007/6/14 PN 研究会 17 State probability State Number 確率の分布リング UMA モデル :N=32,L=1,S=3 の場合全体としてローカルメモリへのアクセスと一貫性制御を行っている確率が大波長が増加するとローカルメモリアクセス確率が増加データ待ち, 一貫性制御の確率が減少 1wavelength 2wavelengths 一貫性制御をローカルメモリへデータ待ちの行っているアクセスしている 2007/6/

4 スライド 16 t3 UMA NUMA で 2 波長の場合の遷移図である. 1 波長の場合の遷移図である. t-kubo, 2007/06/03

5 計算スループットによる評価全体としてリング長が短く, 共有メモリへのアクセス頻度が低い場合, 高計算スループットリング長が長い, 又は共有メモリへのアクセス頻度が高い場合, 低計算スループット波長数による性能差リング長が短い場合 : ノード数が増加すると性能が向上リング長が長い場合 : 性能差がない Throughput (MIPS) Throughput (MIPS) 1 wavelength 1 wavelength 2 wavelengths 2 wavelengths Number of nodes Number of nodes 約 15% リングUMAモデルリングUMAモデル性能が向上 L=1km, N=32, S=3の場合 L=0km, N=32, S=3の場合 2007/6/ まとめと今後の課題まとめ共有メモリアーキテクチャの設計リング UMA アーキテクチャ (1( 波長, 及び 2 波長 ) リング NUMA アーキテクチャ (1( 波長, 及び 2 波長 ) 計算スループットを指標とした共有メモリアーキテクチャの評価 UMA NUMA 共にほぼ同じ性能リング長が短く共有メモリへのアクセス頻度が低い場合, 高計算スループットリング長が長い, 又は共有メモリへのアクセス頻度が高い場合, 低計算スループット波長数による性能の違い UMA NUMA 共に同じ傾向リング長が短い場合共有メモリへのアクセス頻度が高いと性能差が生じるノード数が多いほど複数波長を用いたアーキテクチャの方が性能はよくなるリング長が長い場合共有メモリへのアクセス頻度, ノード数によらず性能の差がないノードの処理遅延に比べ, 伝播遅延が大きいためと考えられる今後の課題メッシュトポロジにおける共有メモリアーキテクチャの性能評価 2007/6/14 伝播遅延が小さいため, 高計算スループットが期待 PN 研究会 20 4

この方法では, 複数のアドレスが同じインデックスに対応づけられる可能性があるため, キャッシュラインのコピーと書き戻しが交互に起きる性のミスが発生する可能性がある. これを回避するために考案されたのが, 連想メモリアクセスができる形キャッシュである. この方式は, キャッシュに余裕がある限り主記憶の

この方法では, 複数のアドレスが同じインデックスに対応づけられる可能性があるため, キャッシュラインのコピーと書き戻しが交互に起きる性のミスが発生する可能性がある. これを回避するために考案されたのが, 連想メモリアクセスができる形キャッシュである. この方式は, キャッシュに余裕がある限り主記憶の計算機システム Ⅱ 演習問題学科学籍番号氏名 1. 以下の分の空白を埋めなさい. CPUは, 命令フェッチ (F), 命令デコード (D), 実行 (E), 計算結果の書き戻し (W), の異なるステージの処理を反復実行するが, ある命令の計算結果の書き戻しをするまで, 次の命令のフェッチをしない場合, ( 単位時間当たりに実行できる命令数 ) が低くなる. これを解決するために考案されたのがパイプライン処理である.