情報理工学系研究科 コンピュータ科学専攻 上嶋裕樹

Presentation on theme: "情報理工学系研究科 コンピュータ科学専攻 上嶋裕樹"— Presentation transcript:

1 情報理工学系研究科 コンピュータ科学専攻 上嶋裕樹 uejima@is.s.u-tokyo.ac.jp
Exploring the Benefits of Multiple Hardware Contexts in a Multiprocessor Architecture: Preliminary Results 情報理工学系研究科 コンピュータ科学専攻 上嶋裕樹

2 概要 multiple hardware contextsにより， メモリー操作の高いlatencyの悪影響を抑えることが出来るかの探求。
効果はアプリケーションの性質，context switch overhead，latencyに依存する。 context switch overheadが小さいとき，２, ４ contextsで1 contextより効果があった。

3 アーキテクチャ(1/2)

4 アーキテクチャ(2/2) direct-map方式でline size 16 bytesのキャッシュ・メモリーは64 Kbytes。
context switchの基準 キャッシュ・ミスの発生 共有読み込みデータへの書き込みの発生 contextはround-robin schedulingで選択。

5 アプリケーション LocusRoute (standard cellのglobal router): 荒い粒度のタスク，細かい粒度のデータ構造共有。 MP3D (３次元の粒子シミュレーション): 並列のための分散ループを使った，典型的な科学計算。 P-Thor (並列論理シミュレーション): Chandy-Misraの分散シミュレーションアルゴリズム。

6 予備実験の結果 Application Run Length Read Latency Write Latency MP3D 16 (16)
32 (44) 42 (57) P-Thor 50 (50) 25 (33) 55 (72) Locus Route 156 (154) 22 (29) 99 (128) 4プロセッサで，各プロセッサに1 context ネットワーク遅延が1の場合(5の場合)

7 いくつかの論点 contextはいくつがいいか？ context switch overheadの影響は？ ネットワーク遅延の影響は？
キャッシュ干渉の影響は？ いつcontext switchをするべきか？ アプリケーションによってパフォーマンスはどう変わるか？ processor efficiency: 全cycle数のうち，意味のある仕事に費やされたcycle数の割合。

8 Contextの数 contextを増やすことによって得られる利益は，contextの数が大きくなると少なくなる。
contextが少ない方がハードウェアを簡単化でき，overheadも小さくできる。 overheadが大きい場合にcontextを増やすと，かえってパフォーマンスが落ちる。(キャッシュ干渉のため) 数contextで十分効果をあげることができる。

9 Context switch overhead
overheadが大きくなるとmultiple contextsによる効果が少なくなる。 overheadは数cycleのオーダーにしておくことが望ましい。

10 ネットワークのlatency 複数のcontextを設けることにより，ネットワークのlatencyの悪影響を少なくすることができる。
ネットワークのlatencyはアーキテクチャ(crossbar switch, grid network)や プロセッサの数に依存する。

11 キャッシュの干渉 複数のcontextが１つのキャッシュを使うことによる正の干渉，負の干渉。
複数contextを持つプロセッサのキャッシュが少なすぎると，極端にパフォーマンスが落ちることがある。(P-Thor, 4 contexts, cache size 16Kbytes)

12 Context switchのタイミング switchのoverheadがlatencyより小さいときにswitchするのが理想。
watchdog counterによるswitch

13 アプリケーションによる違い MP3D (Global traffic　大): contextを増やすことによる効果が大きい。ただしキャッシュ干渉も大きいのでネットワーク遅延の悪影響を受けやすい。 P-Thor (Global traffic　中): 複数contextによる効果があり，latencyの増加による影響も受けにくくなる。 LocusRoute (Global traffic　小): キャッシュも効いているのでcontextを増やすことによる効果が小さい。

14 他のプロセッサの multiple hardware contexts
Alto: time criticalな入出力処理を行えるように。 HEP: latencyを克服できているが，最低８プロセスでパイプラインを満たす必要がある。 Hybrid data-flow/von Neumann machine: registerがcontext switchの際に保存されない。多くのcontextを保持する。次にどのcontextを実行するかの決定が複雑。 MASA: １つのプロセスについて，前の命令が完了しない限り次の命令を発行できない。

15 議論 multiple contextsの意義は？ multiple contextsをどう実装すべきか？
高価なプロセッサとlatencyの大きいネットワークを複数のcontextで共有する。 multiple contextsをどう実装すべきか？ １つのchipにするより複数chipにした方がいい。 ある１つのプロセッサに対してどのプロセスを割り当てるか？ 重要な問題である。

16 結論(1/2) 1 contextのプロセッサと比べると，一定の少数のcontextでも十分大きな効果を上げることがでる。
以下の状況で最良の効果をあげる。 読み書きのlatencyが大きい。(大規模なmultiprocessor) context switch overheadが小さい。(contextの数が固定で少なく，context switchの基準が単純) multiple contextsによるキャッシュ干渉が少ない。(大きなキャッシュ)

17 結論(2/2) context switchの仕組みがsubtask管理の仕組みと分離している。 単純で高速なハードウェアを実現。
高い柔軟性を持ち，アプリケーションに依存したパフォーマンスのチューニングが可能。

18 参考文献 W.-D. Weber and A. Gupta, “Exploring the Benefits of Multiple Hardware Contexts in a Multiprocessor Architecture: Preliminary Results,” Proc. 16th Int. Symp. on Computer Architecture, pp , 1989.