Explorations in Symbiosis on two Multithreaded Architectures 輪講担当：上嶋　裕樹(16001) uejima@is.s.u-tokyo.ac.jp

概要 複数のアプリケーションをマルチスレッド計算機で並行に実行したときのスループット増加をsymbiosisと定義して探求した。 その性質の考察 実験結果 Tera MTA SMT machine (via simulation)

symbiosisの定義 Throughput rate Symbiosis TM is a measure of how good symbiosis could possibly be. If TR=TM, symbiosis is 1. Symbiosis is between 0 and 1, or arbitrarily negative.

symbiosisの性質 複数の資源を独立に並行にスケジュールし，互いのlatencyをカバーしあうことによる。 プログラムの資源の要求がどれくらい相補的か。 共有資源で助け合うことによりsymbiosisが1より大きくなる例(実験では扱っていない) データのprepageをする キャッシュを埋める

使用したbenchmark 5つのNAS 2.3 Parallel Benchmark kernel Conjugate Gradient Embarrassingly Parallel Fourier Transform Integer Sort Multigrid grind section: benchmarkが計測している部分(←→initialization section) phantom: プログラムによって使われていないissue slot

Tera MTAでのSymbiosisの測定 5つのNAS 2.3 Parallel Benchmark kernelの15通りの組み合わせ。(同じもの同士もあり) MTAのコンパイラーで自動的に並列化。 メモリーの参照頻度が重要である。

Symbiosis of Vanilla Class W NPB on MTA

Symbiosis of Tuned Class W NPB on MTA

Symbiosis of Tuned “long run” NPB on MTA

Tera MTA実験結果 tuningをして(ILPを高めて)phantomを少なくすると，symbiosisは全般的に低下した。 grind sectionの割合を長くすると，symbiosisはさらに低下した。 parallel sectionとserial sectionの重なっている部分でのsymbiosisの影響が小さくなったため。 高いphantomの割合，低いメモリー参照頻度，長いinitialization sectionで高いsymbiosis。

SMTでのSymbiosisの測定 5つのNAS 2.3 Parallel Benchmark kernelの15通りの組み合わせ。(同じもの同士もあり) 各ベンチマークはシングルスレッド。(マルチスレッドは今後の課題) キャッシュはdirect-mappedの場合と2-way set associativeの場合で行った。 (MTAの場合と異なり)キャッシュ内のデータ再利用パターンが重要になってくるかもしれない。

Symbiosis of Vanilla Class W NPB on SMT (2 way assoc. I-cache)

SMTの実験結果 CG+CG: 2-way assoc. キャッシュのヒット率が上がったが，floating-point queueがボトルネックに。 IS+IS: integer registerがボトルネックに。 MG: キャッシュのヒット率も上がらず，floating-point registerがボトルネックに。 EP: ILPが低いため，大変よいsymbiosisを示す。 CG+MG: floating-point registerがボトルネックに。 FT+MG: floating-point register, floating-point issue slotがボトルネック。 ILP = Instruction Level Prallelism ISは他のfloating-point intensiveなものとのSymbiosisが高い。

まとめと今後の課題 マルチスレッド計算機での複数プログラムの同時実行で，symbiosisがあることが示せた。 symbiosisに従ったバッチスケジューリングができれば，マルチスレッド計算機でsuperlinearなthroughputを実現できるかもしれない。 parallel section同士，またはparallel sectionとserial sectionが重なっている部分でのsymbiosisを正確に特徴付けたい。 throughputとsymbiosisは短い時間間隔で計算できるような定義になっている。

参考文献 A. Snavely, N. Mitchell, L. Carter, J. Ferrante and D. Tullsen, “Explorations in Symbiosis on two Multithreaded Architectures”, Proc. MTEAC 99, Jan. 1999.