A parallelizing compiler cooperative acceleration technique of multicore architecture simulation using a statistical method
Gakuho Taguchi, Keiji Richard Kimura, Hironori Kasahara · IEICE technical report. Computer systems · 2014
A parallelizing compiler cooperative acceleration technique for multicore architecture simulation is proposed in this paper. Profile data of a sequential execution of a target application on a real machine is decomposed into multiple clusters by x-means clustering. Then, sampling points for a detail simulation mode in each cluster are calculated. In addition, a parallelizing compiler generates a parallelized code by taking both of the clustering information and the source code of the target application. The evaluation results show, in the case of the simulation for 16 cores, 437 times speedup is achieved with 0.04% error for equake, and 28 times speedup is achieved with 0.04% error for mpeg2 encoder. Keyword Parallelized application, Multicore architecture simulator, Statistical method, Acceleration technique 1. はじめに コンピュータアーキテクチャの研究及び開発にお いて,アーキテクチャシミュレータは様々なアーキテ クチャの初期評価で大きな役割を果たしてきた.しか しながら,シミュレーションには実機での実行の 10000~15000 倍という膨大な実行時間を要し,これが 大きな問題となっている.その為,高速で精度の高いシミュ レーション手法の研究が注目されている. 単一コア CPU のマイクロアーキテクチャの研究で は,これまでプログラムのある一定区間の IPC を測定 するといった形式で多くの評価が行われてきた.しか しながら,この方式では並列化アプリケーションをマ ルチコア上で実行するときのシミュレーションに対し て単純には適用できないといった問題,及びプログラ ムの特徴的な部分を測定できているか不明であるとい う問題があった. これらの問題のうち,プログラムの測定部分の絞り 込みに関して,プログラムのある一部分のみを詳細に 実行するサンプリング実行による高速化が提案されて いる.例えば,SimPoint[1]はアプリケーションのベー シックブロックごとの実行回数を計測した情報である BBV を基に詳細実行部分を絞り込む.BBV に対しク ラスタリングを施すことでプログラムの特徴を表す部 分を見つけ出し,クラスタごとの適切なサンプリング ポイントを設定する.SimFlex[2]は,命令数を基準とし たプロファイルに対して統計を用いたサンプリングを 施し,サンプルを算出する.しかし,マルチコアアー キテクチャにおいては,コア間のリソース競合や同期 により,それぞれのスレッドにおいてアイドルやスピ ニングが起こる為,依然としてマルチコアのシミュレ ーションに対してこれらの方法を単純に適用すること は出来ない. マルチコアに対応したサンプリング高速化手法とし て,Carlson 等の手法がある [3].これは,SimPoint と同 様に BBV の解析によりアプリケーションの周期性を 解析しサンプル対象を設定する手法だが,スレッドご とのアプリケーションの挙動に着目し,機能シミュレ ーション時にも詳細な同期を行うことでマルチコアア ーキテテクチャのシミュレーションに対応している. この手法では,事前アプリケーション解析にシミュレ ーション対象アーキテクチャと同じコア数のプロファ イルが必要となり,また SimPoint 同様 BBV のまとめ 方やクラスタリングのパラメータを手動で適宜設定し なければならないといった問題がある.サンプリング 実行以外のマルチコアに対する高速化手法としては, Bryan らの手法がある [5].バリア同期間隔をスレッド ごとの進捗の差異のない独立した単位として扱い,シ ミュレーション自体を並列化するものである. 本稿で提案する高速化手法は,並列化されたベンチ マークアプリケーションのマルチコア上での実行を対 象とし,これらアプリケーションのメインループをイ タレーション単位でサンプリングするものである.本 手法では,このような粒度では実行サイクル数等の計 測対象の計測値の変動が,アーキテクチャの差異によ る寄与よりも,アプリケーションそのものの演算ステ ップ数の変動による寄与が大きいと考え,任意のアー キテクチャによる対象アプリケーションの逐次実行の プロファイル結果によりサンプリング対象をクラスタ リングする.クラスタリング後,各クラスタのサンプ ル数を決定し,これらのサンプルのみを詳細シミュレ ーションする.対象アプリケーションでは,メインル ープそのものが並列化される,あるいはメインループ 内部が並列化されているため,同期やコア間のリソー ス競合といった並列化特有のプロセスを考慮にいれた 評価が可能となる. 先行研究に対して,本手法は以下の様な特徴を持つ. 1) 同期やコア間のリソース競合を含む粒度でのサン プリングにより,全コアで統一した単位のサンプ ルを得ることができ,マルチコアアーキテクチャ への対応が可能となる. 2) 本手法で対象とする粒度でのアプリケーションの コスト変動は並列化後も同じ傾向であるという仮 定から,事前アプリケーション分析に用いるプロ ファイルは逐次実行のみとすることができる. 3) プロファイルの解析には x-means クラスタリング と統計手法を用いることで,手動によるパラメー タの設定を必要とせず,自動的に最適なサンプル を算出することができる. さらに本稿では,並列化コンパイラとの連携によるプ ロファイル部分特定及びサンプリング用ランタイム生 成自動化フレームワークについても提案する. 以下,第 2 章で本稿で提案するシミュレーション 高速化の手法,第 3 章でコンパイラと協調した高速化 のフレームワーク,第 4 章で精度切り替え機能,第 5 章で性能評価,第 6 章でまとめについて述べる. 2. シミュレーション高速化の手法 本章では,本稿で提案するシミュレーション高速化 手法について述べる. 2.1. シミュレーション高速化の概要 本稿で提案する高速化手法は,ベンチマークアプリ ケーションにおける,並列化可能ループまたは並列化 可能ブロックを内包するメインループに着目してイタ レーション単位でサンプリングを行う.サンプリング とは,ある母集団の部分集合である標本(サンプル) から,その母集団の性質を推定する手法である.本手 法では,任意のループのイタレーション毎の実行サイ クル数のプロファイルに対してサンプリングを行い, 一部のイタレーションの実行サイクル数(サンプル) からループ全体の実行サイクル数(母集団)を推定す る.この時,サンプルイタレーションのみ詳細なシミ ュレーションを行い,その他のイタレーションは簡易 で高速なシミュレーションを行う.すなわち,シミュ レーション速度の非常に遅い詳細シミュレーションを 行う部分をサンプル部分に限定することで,シミュレ ーション時間の短縮を図る. 2.2. シミュレーションモード 本高速化手法では,次の 2 種類のシミュレーション モード(精度)を適宜切り替えながらシミュレーショ ンを行う. 詳細シミュレーション キャッシュやパイプライン,相互結合網などの アーキテクチャ構造を詳細に再現しクロック サイクルレベルでシミュレーションを行うモ ード.サンプルイタレーションに対して行う. 機能シミュレーション 命令実行のみの機能レベルでの簡易で高速な シミュレーションを行うモード.サンプル以外 のイタレーションに対して行う. 2.3. サンプル算出の手法 本手法におけるサンプルとは,サンプリング対象ル ープの全てのイタレーションを母集団とし,その母集 団の実行サイクル数を推定するのに必要なイタレーシ ョンの数である.この時,精度を高く,より少ないサ ンプル数でループ全体の実行サイクル数を推定できる サンプルの算出が求められる. 2.3.1. 任意の実機での実行プロファイル取得 メインループのイタレーション毎の大局的な挙動は, プログラム構造と入力に依存するという前提から,ベ ンチマークアプリケーションを任意の実機で実行して 取得したプロファイル情報に,シミュレーション対象 アーキテクチャにおけるベンチマークプログラムのコ スト変動の挙動も従うと仮定する. そこでまず,ベンチマークアプリケーションを任意 の実機で逐次実行し,イタレーション毎の実行サイク ル数を計測する.このプロファイルに統計手法を用い たサンプリングを施し,得たサンプルをシミュレーシ ョンに用いる. 2.3.2. クラスタリング手法 任意の実機での逐次実行から得たプロファイルに対 して統計処理を施す前に,クラスタリングによるプロ ファイルの分割を行う.母集団を偏差の小さい集合に 分割することで,統計手法を施した際のサンプル数を 減少させることができる.ここでは,クラスタリング 法として x-means 法 [5]を用いる.x-means 法とは,まず 小さなクラスタ数 k0による k0-means クラスタリングを行い,分 割後の各集合に対して,分割が適当でないと判断されるま で 2-means クラスタリングを再帰的に行う手法である.ここで は分割停止基準をサンプル数の和とし,この値が改善す るか否かにより分割停止の判断を行う.この x-means 法を用いることにより,入力集合に対して最適なクラ スタ数の決定が自動化できる.イタレーションごとの 実行サイクル数のプロファイルに対してクラスタリン グを施した例を図 1 に示す.図では横軸がイタレーシ ョンの番号,縦軸が実行サイクル数をそれぞれ表し, イタレーションが実行サイクル数に応じて 4 クラスタ に分割されていることを示す. 図 1 実行サイクル数によるクラスタリングの例 2.3.3. 統計的手法によるサンプル算出 サンプルはそれぞれのクラスタに対して,推定する 全体の実行サイクル数が許容する誤差に収まるように 統計手法によって決定する.クラスタリングによって 得られた集合を C1, C2, ... , Ck とする.C i (i=1,2,... ,k)に ついて,次の式に 1よってサンプル数 n iを計算する [6]. サンプル数ni ≥ ⌈( 上側P%点 許容誤差率 e × 標準偏差σi 相加平均μi ) 2