ハイエンドコンピューティング技術に関する調査研究� ―　高性能プラットフォーム技術を中心とする　―

　ハイエンド・コンピュータのアーキテクチャは進化途上にあり、様々なアイデアが次々と提案されている。このようなアイデアを特に性能面で評価するためには、アーキテクチャレベル（または命令セットレベル）のシミュレータは不可欠のツールである。一方、並列マシンのPE（Processor Element）数増加などシステムの大規模化や、マルチスレッド・プロセッサなどプロセッサの複雑化により、シミュレーションに要する時間は増加の一途をたどっている。したがってシミュレータの高速化技術は緊急の課題であり、様々な提案がなされている。
　本節では共有メモリ・マルチプロセッサをターゲットとするシミュレータを中心に、以下の観点から代表的なシミュレータの高速化技術や、最近の研究動向について概観する。

●     高速化の基本技術
●      プロセッサの複雑化への対応
●      統合的シミュレーション
●      シミュレータの分散・並列化

1．高速化の基本技術
　これまでに提案されている多くの並列マシン・シミュレータは、単一プロセッサの上で動作する。したがって１プロセッサあたりの実機／シミュレータの実行時間比であるslowdown factor（SF）をSとすると、Nプロセッサから成る並列マシンに対するSFはS×Nとなる。たとえばS=50のシミュレータは比較的高速な部類に属するが、N =16であればSFは800となり、実機が１分で実行するワークロードに13時間以上を要することとなる。したがって高速化技術の基本的な目的は、いかにSを小さくするかにある。
　共有メモリ・マルチプロセッサの多くは図１に示すように、トレース駆動型と実行駆動型のいずれかの形態であり、いずれの場合もプロセッサの挙動をシミュレートするメモリ参照履歴を生成するフロントエンドと、それを消費しながらメモリシステムをシミュレートするバックエンドに二分される。各々の形態に固有の高速化技法はもちろんあるが、多くの研究の主眼はいかにフロントエンドのSFを小さくするかにある。逆にいえばバックエンドの高速化はユーザ（アーキテクト）任せであり、研究されていない多くの課題が存在すると思われる。

　フロントエンドでのプロセッサ・シミュレーションの方式は、図2に示すようにAugmentation方式とEmulation方式に大別される。前者はワークロード・プログラムのソースあるいはオブジェクトに、メモリ参照履歴生成などのためのコードを付加し、それをシミュレータ・ライブラリとリンクして得られる実行形式を直接実行する。これに対しEmulation方式ではワークロードの実行形式を入力し、命令の解釈実行あるいは等価な命令列の実行によりシミュレーションを行なう。

	T/E	Seq/Para	Mem Sim.	SF
MPTrace [2]	T:aug	P:9～12/9～12	No	1.9～2.6 1000～ (w/ backend)
Cerberus [3]	E:aug	Seq	No Yes
SimICS [4]	E:int	Seq	Yes	50～200
MINT [6]	E:int+bt	Seq	No Yes	18～65 60～200
SimOS [5] (DE) (BT) (DC) (DS)	E:de E:bt E:int E:int	Seq Seq P:4/4 Seq Seq	No L2C L2C Yes Yes	1.1～1.9 9～11 10～36 180～230 3900～6400
RSIM [8]	E:int	Seq	Yes	5000～10000
DirectRSIM [9]	E:aug+int	Seq	Yes	1500～3000
FastILP [10]	T::aug+int	Seq	No	50～100
TDS-NF [11]	T:int	Seq	Yes	1500～3000
SIMCA [12]	E:int	Seq	Yes	40000～50000
WWT [16]	E:de	P:4～64/4～64	Yes	52～250
WWT-II [17]	E:aug	Seq P:32/2～8	Yes Yes	114～241 132～468×16～4
T/E: T … トレース駆動、E … 実行駆動、de … direct execution、 aug … augmentation、 int … interpretation、 bt … binary translation P:n/m … nプロセッサの対象システムをmプロセッサのホストでシミュレート SimOS: DE … direct execution、 BT … binary translation、 DC … Detailed CPU DS … DC + dynamic scheduling

　Augmentation方式で最高速のトレース駆動型のフロントエンドであるMPTrace [2] は、road mapと呼ぶ独特の解析情報を用いて、履歴生成のみであれば2～3、履歴のファイル書込みを含めても10程度という、驚異的に小さなSFを達成している。すなわち通常のフロントエンドがメモリアドレスやアクセスタイプの完全な列を直接生成するのに対し、MPTraceでは完全な列を得るために必要な最小限の情報（たとえばベース・レジスタの値）のみを生成する。road mapはこの最小限の情報に基づく補完方法を指示する一種の命令列であり、たとえば履歴中のレジスタ値を参照してメモリアドレスを求める方法が示されている。またワークロードのデータ依存解析を行なうことにより、履歴生成やそのために必要なレジスタ等の退避／復帰を最小限に抑えている。この結果前述のようにフロントエンドのSFは極めて小さいが、逆に履歴を消費するバックエンドではroad mapを用いた一種のinterpretationが必要となり、バックエンドを含めたSFは（おそらく）1000以上の大きな値となる。
　Augmentation方式で通常の履歴を生成する高速フロントエンドとしては、Cerberus [3] が挙げられる。Cerberusは実行駆動型であり、MIPS R3000の１命令を8命令に展開したコードを直接実行する。この8命令の中にはシミュレータ・ライブラリ中の関数呼出が少なくとも一つは存在し、並行実行している対象プロセッサのスケジューリング、キャッシュ・シミュレータの呼出、浮動小数点演算などを行なう。CerberusのフロントエンドのみのSFは、対象が単一プロセッサの場合は20～40、マルチプロセッサの場合はプロセッサあたり40～50と、比較的高速である。しかし簡単なコヒーレント・キャッシュを付加した場合のSFは1000～2000となり、バックエンドあるいはフロントエンドとバックエンドのインタフェースに大きなオーバヘッドがあると思われる。
　Emulation方式の基本的な実行方法は、命令フェッチ、デコード、実行をソフトウェアでシミュレートするinterpretationである。この方法は対象プロセッサの動作を最も正確に再現する方法であるが、Augmentation方式に比べてやや性能が劣るのが普通である。しかしMMUやOS機能も含めた詳細なシミュレーションが可能なSimICS [4]やSimOS [5]（詳細実行モード）のSFは、コヒーレント・キャッシュのシミュレーションも含め50～200であり、Cerberusよりも高速である。
　より高速な方式はbinary translationと呼ばれ、簡単にいえばAugmentation方式で静的に展開されたコードを、シミュレーション実行時に動的に展開して実行する方式である。SimOSのbinary translationモードでは基本ブロックごとにコード展開を行ない、展開結果を一種のキャッシュに保存する。したがってこの展開コードキャッシュにヒットした基本ブロックは直接実行することができ、簡単なキャッシュのシミュレーションを含めても10程度の小さなSFが達成されている。
　また、代表的なシミュレータの一つであるMINT [6]は、基本ブロック中のメモリ参照を含まない一定の長さ以上の部分命令列に対してbinary translationを行ない、それ以外はinterpretationを行なうという、二つの方式を混在させた手法を用いている。MINTのSFは履歴生成のみであれば20～70、コヒーレント・キャッシュのシミュレーションを行なった場合は100～200であり、前者はCerberusと、後者はSimICSやSimOSとほぼ同等である。

2．プロセッサの複雑化への対応
　前節で示したSFの値は、いずれも1クロック／命令や単純なパイプライン構造を前提としたシミュレータの性能である。一方、スーパスカラーなどの複雑な構造をもったプロセッサの挙動を忠実にシミュレートしようとすると、より大きなSFとなってしまう。実際、SimICSの動的スケジューリング・モードでは5000程度、代表的なILPプロセッサ・シミュレータであるSimpleScalar [7]では10000程度、また共有メモリ・マルチプロセッサ用のRSIM [8]では20KIPSという性能値[9]から換算して5000～10000という大きな値になっている。
　このような低い性能はシミュレーションの精度とのトレードオフであり、精度をある程度犠牲にすればより高い性能を得ることができる。たとえばRSIMを開発したRice大学のグループの報告[9]によれば、スーパスカラー・プロセッサの命令発行レートのピーク値に合わせてプロセッサとL1キャッシュのクロック速度を加速した単純なプロセッサを用いれば、シミュレーション速度を1桁程度改善できる。ただし精度はさほど高くなく、RSIMの結果に対して対象システムの実行時間に30～70%程度の誤差が生じる（増加する）と報告されている。
　シミュレーション精度を高めるアプローチのいくつかは、やはりRice大学のグループから提案されている。一つはAugmentationとEmulationを組み合わせたDirectRSIM [9]である。このシミュレータでは命令の「論理的な実行」、すなわち各命令が行なう演算などの操作とそれにより定まる実行パスのトレースをAugmentation方式により行い、「物理的な実行」すなわちメモリ参照命令の実行タイミングを定めるためのILP機構のシミュレーションをEmulation方式により行なう。また後者のタイミング管理を一部簡略化するなどの工夫も行い、誤差を1～2%に留めつつRSIMの3倍程度の高速化を達成している。
　もう一つの提案は、シミュレータをシステムの性能モデルへの入力パラメータ生成ツールと考え、モデルを用いた解析に必要なだけの精度のシミュレーションを高速に行なうというものである[10]。この提案の中で用いられているシミュレータFastILPは、DirectRSIMをさらに簡略化し、かつ1プロセッサ分のメモリ参照履歴だけを用いることにより、RSIMの100倍程度（すなわちSFが50～100）の高速化を達成している。また解析の精度は比較的高く、誤差は10%程度と報告されている。
　RSIMをベースとした別のグループの提案として、特定の構成によるRSIMの実行結果を用いたトレース駆動シミュレーションを行なうTDS-NF [11]がある。このシミュレータではネットワークの構造だけを変化させることができ、RSIMの3～4倍の高速化と10%以下の誤差が報告されている。
　この他、マルチスレッド・プロセッサのシミュレータの性能も大きな問題であり、スーパスカラー用のシミュレータをベースにマルチスレッド化するような方法では、極めて大きなSFとなることが容易に推測できる。たとえばSIMCA [12]の性能はSimpleScalarの1/4～1/5であり、SFは40000から50000という非常に大きな値となっている。

3．統合的シミュレーション
　多くのシミュレータは、SPECやSPLASH-2といったベンチマークなど、単一のアプリケーションを実行した際のシステム性能を示すことを目的としている。したがってOS機能はシミュレータ内部で直接シミュレートすることが多く、OSの性能やOS機能がアプリケーションに与える性能上の影響については、一般に高い精度が得られない。
　このような状況の中で例外的なものはSimOSであり、IRIXをほぼ完全にシミュレートする機能を持っている。また、SimOSには前述のbinary translation、詳細実行、動的スケジューリングの他に、OSの動作の再現だけを目的としたdirect executionというモードがあり、単一プロセッサの場合には2以下という極めて小さなSFを達成している。このモードは割込やトラップをsignalで模倣しつつ、単にOSのコードをユーザ・プログラムとして実行するだけであるので、SFが小さいのは当然ではあるが、性能を細かく解析したいアプリケーションの実行環境設定などの高速化への貢献は大きい。
　また、MINT（あるいは他のシミュレータ）をフロントエンドとして用い、共有メモリ・マルチプロセッサの性能と密接に関係するOS機能である、スレッド・マイグレーション[13]やマルチプロセス環境でのスケジューリング[14]を対象とするシミュレータ構築に関する報告もある。しかし、これらはいずれも対象システムの性能のみを報告しており、シミュレータ自体の性能は明らかにされていない。

4．シミュレータの分散・並列化
　マルチプロセッサを対象とするシミュレータの場合、問題には明らかに並列性が内在している。しかしこの並列性を活用して実際にシミュレータを分散・並列化した例は少なく、成功例もごく限られている。この理由の一つは、対象システムの論理構造、特にプロセッサの論理構造が複雑であるため、Time Warp [15]のような一般的な分散・並列離散シミュレーションの技術が適用困難なことにある。Time Warpではシミュレータ・ノード間の局所時刻のずれにより生じる因果関係の逆転を解消するための巻き戻し処理のためには、クロックごとにプロセッサの状態（あるいはその変化）を保存する必要がある。したがって、ノード間の通信遅延が大きなシステム、たとえばPCクラスタなどでノードあたりのSFを小さくしようとすると、膨大な状態保存が必要となってしまう。また共有メモリ・マルチプロセッサではプロセッサ間通信の頻度が高く、これをノード間通信に直接マッピングすると、致命的な通信オーバヘッドが生じる。たとえば1GIPSのプロセッサからなる対象システムを、同じ性能のプロセッサを用いてSFが100となるようにシミュレーションしようとすると、キャッシュ・ミス率を10%、メモリ参照命令の出現頻度を25%とした場合、4μsに１回の細粒度通信が生じてしまう。
　これまで述べたシミュレータのいくつかは、時刻管理の簡略化と共有メモリ・マルチプロセッサの利用により、上記のような問題を回避しながら並列化を行なっている。たとえばMPTraceでは、共有メモリ機構の実現をシミュレータ・ホストである共有メモリ・マルチプロセッサに完全に委任し、メモリ参照履歴の生成と保存のみを行なう。したがって対象システムの結合網やメモリでの競合による遅延を考慮したタイミング・シミュレーションは、履歴を解析するバックエンドに委ねられる。またSimOSのbinary translationモードは、コヒーレントな2次キャッシュの並列シミュレーションが可能であるが、キャッシュミス時の遅延は固定としており、false sharingなど複数プロセッサのアクセス競合に起因するキャッシュ動作の非決定性も考慮していない。
　厳密な時刻管理を行ないながら分散メモリマシンを用いて共有メモリ・マルチプロセッサ・シミュレータの成功例は、Wisconsin Wind Tunnel (WWT) [16]にほぼ限定される。WWTでは、並列離散シミュレーション技法の一つであるconservative法に基づく同期的時刻管理を行なっている。この方法では、対象システムのプロセッサ間（キャッシュ間）の通信遅延の最小値Qを時刻管理のquantumとして用い、シミュレータの時刻がQだけ進むごとに全てのシミュレータ・ノードで同期を取りつつプロセッサ間通信事象の授受を行なう。この方法はQが比較的大きく、全ノードでのバリア同期の性能がよい場合には有効であり、WWTでは64PEのCM-5を用いて64PEのDASH （Q=100）のシミュレーションをSF=50～100で実現している。このような高い性能は、CM-5のバリア同期が高速であることのほかに、対象システムのコードを直接実行すること（direct execution）や、キャッシュミスの検出にECCトラップを用いていることに負っている。
　また、WWTの後継システムであるWWT-II [17]は、Augmentation方式を用いることによりWSクラスタを含めた広範囲のホストに実装可能としている。WWT-IIを67MHzのSuperSPARCをMyrinetで結合したクラスタに実装した例では、32PEのCOMA（Qはやはり100程度と思われる）の8ノードでのシミュレーションにおいて1200～1500（対象を8PEとすれば300程度）のSFを達成している。しかしWWT(-II)の手法はQが小さいシステム、たとえばバス結合されたSMPを対象とした場合にオーバヘッドが大きく、適用範囲が限定される。
　WWTとは全く違うアプローチとして、本報告の筆者らによるShaman [18]があげられる。ShamanはPCクラスタへの実装を想定し、フロントエンドに複数ノードを、バックエンドには別のノード（当面は単一ノード）を割り当てる。したがってフロントエンドからバックエンドへ、LANなどを介して供給するメモリ参照履歴の量をいかに小さくするかが研究の主題である。ShamanのフロントエンドはLazy Release Consistencyの技法を用いたソフトウェア分散共有メモリにより、対象システムの共有メモリをシミュレートする。その際、対象システムのキャッシュを部分的にシミュレートし、対象システムで確実にヒットするメモリ参照を履歴から除去することによって、履歴の大幅な圧縮を行なっている。Shamanは開発途上であるのでSFの値は未測定であるが（ノードあたりで100程度と予想している）、履歴の削減率が95%以上であることが確かめられており、高効率の分散シミュレーションが実現できると考えている。

参考文献
[1] R. A. Uhlig and T. N. Mudge. Trace-Driven Memory Simulation: A Survey. ACM Computing Surveys, Vol. 29, No. 2, pp. 128--170, June 1997.

[2] D. K. Keppel, E. J. Koldinger, S. J. Eggers, and H. M. Levy. Techniques for Efficient Inline Tracing on a Shared-Memory Multiprocessor. In Proc. ACM SIGMETRICS Conf. Measurement and Modeling of Computer Systems, 1990.

[3] J. B. Rothman and A. J. Smith. Multiprocessor Memory Reference Generator Using Cerberus. In Proc. MASCOTS'99, pp. 278--287, October 1999.

[4] P. Magnusson and B. Werner. Efficient Memory Simulation in SimICS. In Proc. 28th Annual Simulation Symp., 1995.

[5] M. Rosenblum, S. A. Herrod, E. Witchel, and A. Gupta. Complete Computer System Simulation: The SimOS Approach. IEEE Parallel & Distributed Technology, Vol. 3, No. 4, pp. 34--43, 1995.

[6] J. E. Veenstra and R. J. Fowler. MINT: A Front End for Efficient Simulation of Shared-Memory Multiprocessors. In Proc. MASCOTS'94, pp. 201--207, February 1994.

[8] V. S. Pai, P. Ranganathan, and S. V. Adve. RSIM: An Execution-Driven Simulator for ILP-Based Shared-Memory Multiprocessors and Uniprocessors. In Proc. WS. Computer Architecture Education, February 1997.

[9] M. Durbhakula, V. S. Pai, and S. Adve. Improving the Accuracy vs. Speed Tradeoff for Simulating Shared-Memory Multiprocessors with ILP Processors. In Proc. 5th IEEE Symp. High-Performance Computer Architecture, January 1999.

[10] D. J. Sorin, V. S. Pai, S. V. Adve, M. K. Vernon, and D. A. Wood. Analytic Evaluation of Shared-Memory Systems with ILP Processors. In Proc. 25th Intl. Symp. Computer Architecture, June 1998.

[11] V. Puente, J. M. Prellezo, C. Izu, J. A. Gregorio, and R. Beivide. A Case Study of Trace-Driven Simulation for Analyzing Interconnection Networks: cc-NUMAs with ILP Processors. In Proc. 8th Euromicro Workshop on Parallel and Distributed Processing, January 2000.

[12] J. Huang and D. J. Lilja. An Efficient Strategy for Developing a Simulator for a Novel Concurrent Multithreaded Processor Architecture. In Proc. MASCOTS'98, July 1998.

[13] F. Gabbay and A. Mendelson. Smart: An Advanced Shared-Memory Simulator --- Towards a System-Level Simulation Environment. In Proc. MASCOTS'97, January 1997.

[14] H. J. Choi, H. J. Suh, S. T. Jhang, and C. S. Jhon. A Method for an Integrated Simulation Linked with Scheduling Policies on a Program-Driven Simulator. In Proc. MASCOTS'00, August 2000.

[15] D. R. Jefferson. Virtual Time. ACM Trans. Programming Languages and Systems, Vol. 7, No. 3, pp. 404--425, July 1985.

[16] S. K. Reinhardt, M. D. Hill, J. R. Larus, A. R. Lebeck, J. C. Lewis, and D. A. Wood. The Wisconsin Wind Tunnel: Virtual Prototyping of Parallel Computers. In Proc. ACM SIGMETRICS Conf. Measurement and Modeling of Computer Systems, pp. 48--60, May 1993.

[17] S. S. Mukherjee, S. K. Reinhardt, B. Falsafi, M. Litzkow, S. Huss-Lederman, M. D. Hill, J. R. Larus, and D. A. Wood. Wisconsin Wind Tunnel II: A Fast and Portable Parallel Architecture Simulator. In Proc. Workshop on Performance Analysis and Its Impact on Design, June 1997.

[18] S. Imafuku, K. Ohno, and H. Nakashima. Reference Filtering for Distributed Simulation of Shared Memory Multiprocessors. In Proc. 34th Annual Simulation Symp., May 2001. (to appear).

3.5.2 ハイエンド・コンピュータ研究のためのシミュレーション技術

3.5.2　ハイエンド・コンピュータ研究のためのシミュレーション技術