Graph-based Critical Path Analysis on Out-of-Order Processors

 コンピュータ・システムの主要構成要素であるプロセッサは，CMOS半導体の微細化を背景に目覚ましい発展を遂げてきた．その代表として，さまざまな分野で実用化されているアウトオブオーダ（OoO: Out-of-Order）プロセッサが挙げられる．OoOプロセッサでは，プログラム実行中に正しい結果を保証する範囲内で順序を入替え，命令レベル並列性を積極的に活用する．また，メモリ参照と計算のオーバラップ実行や分岐予測に基づく投機実行をサポートしており，高いシングルスレッド性能を達成できる．その反面，プロセッサ内部における命令実行の挙動は複雑であり，詳細な性能ボトルネックの解析が極めて難しい．近年，コンピュータ・システムの高性能化にはハードウェアとソフトウェアの協調設計がより重要性を増しており，プロセッサの内部構造を反映した詳細なプログラム実効性能解析法の確立が喫緊の課題となっている．

 このような技術的課題を解決すべく，本研究では，OoOプロセッサに着目した新しい性能解析手法を提案し，その有効性ならびに実用可能性を示している．本研究の第一の貢献は，近年の最新OoOプロセッサ構造を反映した命令実行モデル化手法の提案である．先行研究として，事前取得したプログラム実行トレースを基に，命令間依存関係と処理に要する遅延情報を抽出し，プログラム実行をグラフ表現するモデル化手法が知られている．プロセッサの複雑化に伴い従来モデルでは近年のプロセッサに適用できない問題があるため，考慮できないアーキテクチャ構造を特定し，モデルの改良により考慮可能とした．本技術を性能推定に用いる場合を想定した評価実験の結果，従来技術では最大97%の推定誤差を0.22%に削減（全ベンチマーク平均では22%の誤差を2.1%に削減）した．第二の貢献は，プログラム実行時間の内訳をより正確に表現する指標としてCPCI（Cycles per Critical Instruction）スタックを提案し，依存グラフ性能解析により自動抽出可能とした点である．プログラム実行時間を決定する命令実行のクリティカルパスを考慮した解析により，既存の性能解析指標であるCPI（Cycles per Instruction）スタックが内包する曖昧さを取り除いた厳密な解析が可能となった．ベンチマークを用いた適用実験を行い，従来方式では発見できなかった性能ボトルネックの検出とその可視化が可能であることを確認した．第三の貢献は，上述の性能解析手法の拡張による，命令チェーン（依存関係にある複数命令）に基づく性能ボトルネック解析手法の提案である．本提案は，依存グラフの解析によりプログラム中の命令列の実行時間に対する影響度を数値化し，実行時間に大きな影響を与える命令チェーンを自動抽出する．ベンチマークを用いた適用実験を行った結果，従来技術では検出できなかった性能ボトルネック命令チェーンの検出が可能であることを確認した．この結果は，当該命令チェーン特化ハードウェアの導入など設計最適化に活用可能である．