近年,コンピュータシステムにおけるプログラムの実行に関して種々の最適化が強く求められてきているが,とりわけ実行時における最適化の重要性が増してきている.一般に実行時(動的)における最適化手法の,静的な最適化手法と比べた場合の利点は,データセットの違いや,ハードウェア構成などの違いからくる動的な振る舞いに対処することが可能であり,効率的な実行を提供できるという点にある.ここで,静的に予測できない挙動とは,例えば最適化の対象として適切な周波数・電源電圧の選択や,キャッシュや命令キューのサイズ,マルチコア・マルチスレッドプロセッサにおける実行スレッド数の選択などが挙げられる.アプローチの手段も様々であり,ハードウェア的なアプローチから,コンパイラ・OSなどのソフトウェア的なものまでと多岐にわたっている.

OSによる手法やハードウェアによる手法では,一般的に実行時の情報を用いるため,キャッシュミスなどの動的な振る舞いにも対応できる.しかし,フェーズの変化などのプログラムの情報を明示的に利用することはできないため,最適化が困難な場合がある.また,コンパイラによる手法は,主としてプロファイリングを用いオフラインで分析を行うというものである.これらの手法の問題点として,例えばデータセットが異なっていた場合に,プロファイリング時と実際のプログラム実行時における振る舞いが異なっていると有効に最適化が行えないことが挙げられる.このように,ハードウェアやOSなどによる動的な手法と,コンパイラによる静的な手法にはそれぞれ一長一短がある.近年ではお互いの良い点を用いるハイブリッドな手法が提案されており,より優れた実行時における最適化を行うことが可能であると考えられている.

このように実行時における最適化が重要になってきている一方で,最適化を行うためには計算機の振る舞いを解析・理解し,どのような場合にどういった最適化を行うかというモデルを立てることが必要である.しかし,計算機システムは年々加速的に複雑化してきている.例えば命令実行においては,スーパーパイプラインや高度な分岐予測によるアウト・オブ・オーダー実行などが行われている.また,SMTやCMPといったワンチップ上でリソースを共有しつつ複数のスレッドを実行可能なプロセッサも登場し,多階層のキャッシュメモリを有している.こういった事情から,計算機の振る舞いを定性的に理解することが非常に困難になってきている.今後,さらに複雑化していく計算機システムにおいて,定性的な解析によるモデルを用いた最適化手法を生み出していくための時間およびコストは増大する一方である.

例えば従来の手法では,プロセッサ内のあるイベント情報を指標として性能モデルを作成し,周波数・電源電圧を制御するDVFS手法が提案されているが,プラットフォームが異なり,当該イベント情報を取得することができない場合は,新たに性能モデルを作成し直す必要がある.また,取得可能な場合であっても,性能モデルに用いられている数式のパラメータなどは,プラットフォーム毎に異なるため,再探索する必要があり,定性的にそれらを構築する手法には限界があると考えられる.

そこで我々は,このような問題に対処しつつ種々の最適化を可能にするために,計算機システムの振る舞いを定量的に解析し最適化のためのモデルを構築し,実行時に得られたモデルに基づいて最適化を行う手法を提案する.具体的には,まず計算機の振る舞いを示す様々なハードウェアイベントの定量的な値から統計的な学習を行い最適化実行のためのモデル(予測式および,着目すべきハードウェアイベントの決定)を作成する.その上で,実行時にはそれらハードウェアイベントにおける値を指標として最適化を行う.ハードウェアイベントの定量的な測定には,最近の大半のプロセッサに搭載されているパフォーマンスカウンタと呼ばれる機構を用いる。パフォーマンスカウンタにより,キャッシュのヒット/ミス回数や,分岐予測ミス回数などがソフトウェアから計測可能となっている.

本論文では以下の二種類の最適化問題について,実機のプラットフォーム上で提案手法を用いて最適化のためのモデルを統計的に構築した上で,実行時に最適化を実現し,評価を行う,

1.動的電源電圧制御による低消費電力化

・2.CMPにおけるリソース競合に着目したプロセススケジューリング

一つめの動的電源電圧制御を用いた低消費電力化は,実行時の情報をもとに電圧・周波数変更時の性能を予測し,性能低下を決められた範囲内に抑えた上でなるべく低周波数でプログラムを実行し消費電力を削減するものである.プロセッサの周波数を変更したときの性能変化の割合は}実行しているプログラムがどの程度メモリバウンドであるかによって大きく異なる.また}プログラムがどの程度メモリバウンドかというのは,データセットのサイズと実行しているプロセッサのキャッシュサイズとの兼ね合いなどによって動的に変化するため,静的な予測は困難そあり,動的に性能を予測することが重要となる。

二つめのCMPにおけるリソース競合に着目したプロセススケジューリングは,実行時の情報をもとにCMP上で実行している複数のプロセス同士のリソース競合による性能低下の割合を予測し,性能低下の割合の公平性(Fairness)の改善や,トータルスループットの向上などの最適化を行うものである.あるプロセスがリソース競合によってどの程度性能低下を起こしているかを予測するためには,そのプロセスの共有リソースに対するアクセス頻度とともに,同時に実行している他のプロセスのアクセス頻度を観測する必要があるため,一つめの最適化問題と同じく動的な予測が重要になる.

これら二つの評価結果より,統計的な学習を用いた最適化モデルの構築による実行時最適化手法が実機のプラットフォーム上で有効に働くことがわかった.これは,実行時における最適化が重要な問題に対して,最適化の指針を与えるための効果的なモデルが,プロセッサ内のハードウェア情報を用いることによって統計的に構築することができたことを意味している.これらの評価結果から,複雑化していく計算機システムにおいて,統計的な学習を用いたモデル化による実行時最適化手法が有効であると結論づけることができる.

本論文は「Run-time Optimization for Computer Systems based on Statistical Analysis」と題し、7つの章から構成されている。近年、コンピュータシステムにおけるプログラムの実行に関して、性能や消費電力などの観点からさまざまな最適化が強く求められてきているが、とりわけ実行時における最適化の重要性が増してきている。実行時の最適化を行うためには計算機の実行状況を解析・理解し、実行状況に応じて目標とする最適化を実現するためのモデル構築が必要となる。このモデルは、実行状況が与えられた時に、最適化可能な事項と、目標とする性能や消費電力などの対象とする指標との関係を表すものである。これまでの研究では一般的に定性的な知見によりモデルを構築する手法が用いられてきた。しかし、コンピュータシステムは年々加速的に複雑化してきているためコンピュータシステムの定性的な理解が非常に困難であり、モデルの構築に要する時間およびコストは増大する一方となっている。本論文は、このような問題を解決するために、コンピュータシステムの実行状況を定量的に解析することによってモデルを構築し、実行時にそのモデルに基づいた最適化を行う手法を提案している。また、提案手法を複数の最適化に適用し、その評価を実機のプラットフォーム上で行うことでその有効性を示している。

第1章「Introduction」では、本論文の背景と目的を述べ、本論文の構成を述べている。まず、本論文で焦点をあてている実行時最適化手法について、その特徴と利点を述べている。また、本論文における提案手法の概要を述べた上で、提案手法を用いた最適化について簡単に述べている。

第2章「Run-time Optimization Technique based on Statistical Analysis」では、提案手法である、コンピュータシステムの統計的なモデリング手法について述べている。プロセッサ内のハードウェアイベントの値は、パフォーマンスモニタリングカウンタと呼ばれる機構を用いることによって取得する。これらの値をオフラインで取得し、統計的な学習を行うことによってモデル化を行う。学習のための統計手法としては独立変数同士の交互作用を考慮した多変数の重回帰分析、およびRestricted Cubic Splines(RCS)と呼ばれるスプライン関数による非線形なモデルを用いている。

第3章「Applications of the Proposed Technique」では、提案手法を複数の最適化へ適用する手法を論じている。具体的には、提案手法は(1)動的電源電圧制御(DVFS)による低消費電力化、(2)チップマルチプロセッサ(CMP)における効率的な実行制御、の2つの最適化に適用されている。前者の動的電源電圧制御を用いた低消費電力化は、実行時の情報をもとに電圧・周波数変更時の性能を予測し、性能低下を決められた範囲内に抑えた上でなるべく低い周波数でプログラムを実行し消費電力を削減するものである。また、後者のCMPにおける効率的な実行制御は、実行時の情報をもとにCMP上で実行している複数のプロセス同士のリソース競合による性能低下の割合を予測し、性能低下の割合の公平性(Fairness)の改善や、トータルスループットの向上などの最適化を行うものである。CMPの実行制御に関しては、実行時に各プロセッサの速度を独立に制御することによって競合の影響を緩和する手法と、前もって実行するプログラムが複数与えられたときになるべく競合が発生しないような組み合わせを選択するタスクスケジューリング手法の提案を行っている。

第4章「Evaluation」では、第3章で述べた各種最適化について、それらを実際に適用するハードウェアのプラットフォームおよびソフトウェアを示し、モデル化の手段およびモデルを用いた評価の概要について述べている。

第5章「Evaluation Results」では、構築されたモデル式、変数としてモデルに組み込まれたパフォーマンスモニタリングカウンタの種類、およびそれらのモデルの寄与率などを提示している。また、導出したモデルの評価をLeave-one-out cross validation法によって行い、高い予測精度を有していることを明らかにしている。次に、得られたモデルを適用し実際に最適化手法の評価を行っている。DVFSによる低消費電力化手法に関しては、与えられた性能閾値を満たしつつ、大幅な消費電力を削減している。また、CMPにおける実行制御では、動的にプロセッサの速度を調整することにより、Fairnessとトータルスループットを大きく改善できることを示している。タスクスケジューリング手法では、競合の生じにくい組み合わせを選択することにより性能の低下を抑制できることを示している。さらに、得られたモデルおよび最適化手法の評価結果に関して議論を行い、統計的な学習を用いた最適化モデルの構築による実行時最適化手法が実機のプラットフォーム上で有効であることを論じている。これは、実行時における最適化が重要な問題に対して、最適化のための効果的なモデルが、プロセッサ内のハードウェア情報を用いることによって統計的に構築することができたことを意味している。以上より、複雑化していくコンピュータシステムにおいて、統計的な学習を用いたモデル化による実行時最適化手法が有効であることを論じている。

第6章「Related Work」では、本論文で対象とした2つの最適化に関して関連する研究について述べ、提案手法との得失利害を論じている。

第7章「Conclusions and Future Work」では、以上の成果を要約した上で、今後の課題を展望している。

以上を要するに、本論文はコンピュータシステムの実行時最適化手法の確立を目的とし、プロセッサ内のハードウェアイベントの値を用いた定量的なモデルの構築手法と、モデルに基づく実行時最適化手法の有用性を、実際のコンピュータシステム上で複数の最適化に適用することで明らかにしたものであり、非常に意義がある研究であり、その成果は工学的に貢献するところが大きいと考えられる。

よって本論文は博士(工学)の学位請求論文として合格と認められる。