1971年にintelによる最初のマイクロプロセッサ4004が誕生して以降、マイクロプロセッサはその製造技術、設計技術とも絶間なく改良され、急激な性能向上を続けてきた。マイクロプロセッサの性能向上は、半導体デバイス技術とアーキテクチャ技術の双方によって支えられてきた。デバイス技術の進歩によって高密度の集積が可能になり、利用できるトランジスタ数はより多く、トランジスタのスイッチング時間はより短くなってきた。スイッチング時間の短縮はプロセッサの動作速度の向上に貢献する一方、トランジスタ数の増加は新しいアーキテクチャ技術の導入を可能にする。この結果、パイプライン実行によるクロック速度の向上、分岐予測による投機的実行、レジスタ・リネーミング、オウトオブオーダ実行による動的な命令間並列度の抽出など、さまざまなアーキテクチャ技術が開発、実装された。現在でも半導体の集積度と性能は18ヶ月で2倍になるというMooreの法則を維持しており、米国半導体工業会によって今後もMooreの法則に従った性能向上が続くと予想されている。

　しかし、クロック速度の向上による性能向上は限界に達しつつある。消費電力はクロック速度に比例して増大するため、数年のうちにプロセッサコアの単位面積当たりの発熱量は核反応炉の温度を越えると予想されている。また、アーキテクチャ技術による性能向上は停滞している。現在主流のスーバスカラプロセッサでは、実行時にプログラムから命令レベル並列性を動的に抽出することで1サイクルに処理できる命令数を増加し、実行速度の向上を図っている。多数のトランジスタを使用して1サイクルに処理できる命令を更に増やそうとすると処理機構の複雑さが増大し、動作速度の低下を引き起こす。更に、プログラム中にはデータ依存関係(真の依存関係)が存在しており、それらの関係を守りつつ実行を行わなければ正しい結果は得られない。そのため、従来のデータ順序関係を守りつつ、1サイクルに同時実行可能な命令を抽出することで処理速度を向上させるという手法には理論的な限界がある。

　通常のプログラムをプロセッサで実行する場合、制御依存や種々のデータ依存関係の制約が存在するため、実行ユニットをフルに使用しているのはまれである。従って、何らかの方法で従来のデータ順序関係を破って命令の実行を行うことができれば、クロック速度を向上させずとも性能を向上させることができる。この真の依存関係を解決して実行する方法は困難であるとされてきたが、近年、これを解決するための投機手法として、命令が生成する値を予測する値予測が考案されている。

　値予測は実際に演算を行って結果を得る代わりに、生成されるデータを演算の実行前に予測することで仮想的に命令間の真の依存関係を解消する手法である。パイプライン処理で性能向上を得るためには欠かせない分岐予測は、実行前に分岐方向を予測するのに対して、値予測は演算命令の実行前に演算を予測する。分岐予測では予測精度が高いほど速度向上が得られるように、値予測でも、予測精度が高く、かつ予測可能な命令が多いほど実行速度が向上する。値予測で予測可能な命令数を増やし、予測精度を向上させるために、種々の複雑な予測機構が提案されている。また、予測値を格納しておく値履歴テーブル(Value History Table,VHT)の(1)エントリ数を増加させる、(2)連想度を増加させる、とVHTにヒットする命令が多くなり、予測精度も向上するまた、(3)ポート数を増加させると複数命令が同時に予測可能になり、(1)〜(3)を全て実現させることによっても、高精度な予測命令数を増加させることができる。

　だが、このような方法で予測命令数を増大させると、予測機構を実装するためのハードウェア量が膨大なものになり、予測値を取り出すまでのレイテンシが大きくなり、予測機構がネックとなり高クロックで動作させることが難しくなる。そのため、現在でも値予測機構を搭載し数GHzという高クロックで動作するプロセッサはまだ出現していない。本論文では、この値予測機構の問題点を解決し、Compaq AlphaやIntelPentium4のように、数GHzという高クロックで動作するスーパーパイプラインプロセッサに値予測を適用可能にする方式を提案する。具体的には、2001年版SIAの2003年の予測より、90nmプロセス、4GHzで動作する4wayのスーパースカラプロセッサを仮定し、その上に高クロックで動作する値予測を実装する。

　値予測機構を高クロックで動作させるにはレイテンシに気をつけなければならない。レイテンシが大きいと、クリティカルパスが増大しクロック周波数を高めることが困難になる。この問題は値予測機構を多くのパイプラインステージに分割することによって解決できるが、今度は予測結果が出力される前に当該命令の実行が完了し、正しい値が生成されてしまう可能性が高くなり、値予測を行う意味が薄れる。従って値予測を搭載し高クロック動作可能なプロセッサを実現させるにはレイテンシを抑えることが重要な鍵となる。

　レイテンシを抑えるためには、単純な予測機構を用い、VHTのエントリ数やポート数を削減する等してハードウェア量を削減しなければならない。そのため本論文では最初に(i)値予測機構として一番単純な予測機構であるLastValue予測を用い、VHTのサイズも最小限に抑えて軽量化を図り、低レイテンシで動作する機構を提案する。

　しかしながら、これの機構は(1)〜(3)に相反することであるため、値予測による性能向上率は低下してしまう。そのような環境においても値予測による性能向上を可能な限り得るために、(ii)コンパイラやバイナリの逆アセンブラでプログラムのデータフローグラフを解析し、予測候補となる命令を選択することでVHTのエントリ数が少ない場合でも極力性能向上が得られるような静的解析法を提案する。そして(i)(ii)の提案の下に評価を行う。その結果、エントリ数が64エントリ以下と少ない場合において、予測命令を選択することで平均の性能向上率が向上することを確認した。

　本論文は、「値予測の軽量効率化方式の提案と評価」と題し、7章と付録からなる。プロセッサ処理性能の向上に対する要求は、応用の拡大につれてますます大きくなり、とどまるところを知らない。今後ともその傾向は続くであろう。プロセッサの性能向上は、半導体デバイス技術とアーキテクチャ技術とにより支えられてきた。しかし、クロック速度の向上による性能向上は特に、消費電力によって抑えられる傾向が現れている他、アーキテクチャ技術に関しては命令間の処理依存性のために性能改善が難しい状況にある。本論文は、処理の結果を値予測という形で推定し、その処理依存性を解決しながら高クロックでの処理性能を向上させる方式について論じたものである。

　第1章「序論」は、研究の背景、目的を述べるとともに、本論文の構成についてまとめたものである。

　第2章「投機実行」は、プロセッサの性能向上を抑えているアーキテクチャ上の問題点である処理の依存性を論じ、それを解決するための投機実行方式の現状について述べたもので、制御投機とデータ投機とに分けて論じ、本論文ではデータ投機方式の一つである値予測を扱っているが、他の投機実行方式がロードやストア命令のように限られた命令に対してのみ可能であるのに比して、値予測は値を生成する全命令を対象とすることができると述べている。

　第3章「値予測機構」は、従来提案されている様々な値予測機構について論じ、それらを実際にプロセッサに実装する場合を考察して速度向上が得られるための条件を分析し、従来の提案の問題点を明らかにしている。

　第4章「低レイテンシで動作可能な値予測機構の検討」は、3章で述べた分析結果と今後のプロセッサ動向に鑑み、高速プロセッサに用いても値予測が有効に機能するための実現性の高いハードウエア構成について考察したものである。その結果、クロック4GHz、4wayスーパースカラ方式を想定した場合は、値予測に用いるテーブルVHTは、エントリサイズ256以下、ダイレクトマップ方式、レイテンシ2クロック以下である必要があり、予測機構はLast Value方式で、パイプライン構成を値予測に適した形にして、予測ミス発生時はそれ以降の実行をフラッシュし次の命令から再実行する方式を用いるのが現実的であることを示している。

　第5章「静的な予測命令選択法の提案」は、4章で考察したハードウエア構造ではエントリ数が小さいことによる容量性ミスが発生しやすく、またタグが無いことから別名問題によって予測ミスが発生しやすくなることを指摘し、その解決手法を提案している。すなわち、静的に命令の種類やデータフローを解析し、予測対象命令を限定することでVHTに登録されるエントリを精選してミスの可能性を抑え、タグを除いてVHTを単純化したことによる性能低下を抑える方式であり、実行バイナリの各命令には、予測を行うかどうかを判断するために1ビットの付加情報をコンパイラが付けるものである。具体的には、バイナリ命令を逆アセンブルして、値を生成する全命令を6種類に分類し、それらの内、どの種類の命令を予測対象からはずすかを定性的に考察し、新たに有望な3つの方式を提案している。また、これらを用いると、平均45%の命令は予測対象外となることを示している。

　第6章「評価」は、5章で提案した方式を評価したもので、まず、想定するプロセッサの現実的なモデルを与え、次に評価環境としてトレースベースのシミュレータを用いたこと、ベンチマークにはSPECint95の8プログラムと、MediaBenchの11プログラム、合わせて19のプログラムを用いたことを述べている。また、5章で与えた値予測限定方式に加え、VHTの各エントリに飽和カウンタを設けて、その対応命令の生成値が前回の実行時の値と等しいときにカウンタを増やし、カウンタ値が飽和しているときにのみ当該命令の値予測を行うという確信度方式を導入して、このカウンタとしては4ビットが最適であることを示している。次いで総合的な性能評価をおこない、VHTエントリ数が大きい場合は、予測命令を限定することによって予測ヒット率が向上するが、総合性能については限定しない方が高い。しかしながら、エントリ数がそのように大きな構成でレイテンシが2という構成を高クロックプロセッサで実現することは困難であり、現実的なVHTエントリ数が256以下の場合は、値予測をする命令を精選する方が総合性能が向上することを示している。

　第7章は「結論」である。

　以上、これを要するに本論文は、プロセッサの性能向上を阻害する主要なアーキテクチャ要因である処理依存性を解決する方式として値予測に着目し、それを今後の高速プロセッサに導入する現実的な手法を考察して、コンパイラとの協調により性能を向上させる手法を与えたもので、情報工学上貢献するところ少なくない。

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