マイクロプロセッサは1971年に発表された4004の誕生以来,デバイス技術の進歩とアーキテクチャの進歩により発展を続けてきた.デバイス技術に関してはムーアの法則として知られるように,3年間でチップに集積するトランジスタ数が4倍になるというペースが続いており,これらのハードウェア資源を利用してVLIW方式,スーパーパイプライン方式,スーパースカラ方式などのプロセッサが開発されている.

　プロセッサ市場に視点を移すと,スーパースカラ方式が高性能プロセッサ・アーキテクチャの主流となっている.スーパースカラ方式は,従来のスカラプロセッサとのコード互換性を維持しながら,分岐予測を用いた投機実行やアウトオブオーダ実行といったアーキテクチャの改良により,命令レベルの並列性を抽出し,サイクル当たりの処理命令数を増加させることで性能を向上させている.また,2次キャッシュがチップ上に実装されるようになってきており,プロセッサの処理能力に対するデータ供給システムの処理能力不足を緩和しており,この点もプロセッサの性能向上に寄与している.

　このように,順調に性能を向上させてきたスーパースカラ方式だが,次のような問題点が指摘されている.

　・分岐予測に成功すれば制御依存関係による性能低下を排除できるが,予測ミスが発生した場合には正しい制御流の再投入が必要となり,投機的に処理した命令を破棄しなければならない.分岐予測の精度は95%程度に向上しているが,残りの約5%の分岐予測ミスによりプロセッサ内の命令列が分断され,並列性を抽出するためのウィンドウを拡大することによる十分な利得が得られない.

　・ロード命令の実行を開始するためには,先行してフェッチされたストア命令のメモリ参照アドレスが計算されている必要があり,データ依存関係を持たないストア命令であっても,そのアドレス計算が終了するまで,ロード命令の実行を遅らせる必要がある.この制約を曖昧なメモリ依存関係と呼び,並列性の抽出を制限する要因となっている.

　前者の制御依存関係の解消を目指して,条件付実行を用いた分岐命令の削除や,分岐成立と不成立の両方のパスにおいて投機的に処理を進める複数パス実行の可能性が議論されている,また,後者の曖昧なメモリ依存関係の解消を目指して,ストアセットを用いた依存関係予測が提案されている.これらの予測手法を用いて,制御依存関係と曖昧なメモリ依存関係の多くを解消できるとすれば,真のデータ依存関係が命令レベル並列性を制限する大きな要因となる.従来,真のデータ依存関係を解消することは困難と考えられていたが,近年,真のデータ依存関係を解消する技術として,値予測を用いた投機処理の手法が提案された.これは,実際に計算をおこなってデータ値を得る代わりに,生成されるデータの値を予測することで処理を進めておくという投機処理技術である.

　チップに集積するトランジスタ数の急激な増加が追い風となり,これらの投機技術の利用は性能向上のための現実的な選択肢となっている.本研究では,既存のRISCプロセッサとのコード互換性を維持しながら,命令レベル並列性10をもたらす投機技術の確立を目的とする.この高い命令レベル並列性を達成するために,制御依存関係を解消する複数パス実行,曖昧なメモリ依存関係を解消する依存関係予測,真のデータ依存関係を解消する値予測の手法を議論し,以下の知見を得た.

　一つ目の投機技術として複数パス実行を議論した.従来からおこなわれている単一パスの実行は分岐の結果(分岐成立または不成立)を予測し,予測先の命令を投機的に実行する.一方,Eager Executionとして知られる全パスの実行では,多くの分岐命令を跨いで投機的に実行するに従って,爆発的にパスの数が増加してしまう.このため,現実的なハードウェア量を考慮した場合には,プロセッサが利用できるパスの数を考慮して,パスを複製する分岐命令を選択するパス割付け戦略の性能が必要となる.提案されている幾つかのパス割付け戦略を比較検討した上で,各手法の利点を組み合わせるJRS-PM方式を提案した.シミュレーションによる評価により,命令レベル並列性,各パイプライン・ステージで処理される命令トラフィック,データキャッシュのヒット率を測定し,利用できるパスの数を16に設定した場合に59%の分岐ミスペナルティを削減できることがわかった.この時,各パイプラインステージで処理される命令数の増加は,単一パス実行の数倍に抑えられることを確認した.これらの評価により複数パス実行の可能性が一部確認された.

　二つ目の投機技術として,曖昧なメモリ依存関係を解消する依存関係予測を議論した.まず,曖昧なメモリ依存関係がプロセッサ性能に与える影響を測定し,曖昧なメモリ依存関係を解消することで13%から18%の性能向上を達成できることを示した.これまでに提案されているストアセットを用いた依存関係予測は,実行中のストア命令にデータ依存関係を持たないロード命令を予測する.しかし,32%のロード命令は実行中のストア命令にデータ依存関係を持ち,ストアセットだけでは曖昧なメモリ依存関係の78%しか解消することはできない.このため,ロード命令が実行中のストア命令にデータ依存関係を持つ場合に,複数のストア命令から,データ依存関係を持つストア命令を特定するストア特定予測を提案した.シミュレーションによる評価により,ストアセットを用いた予測手法と,ストア特定予測を同時に利用することで,予測ミスの回数を抑えつつ,85%の曖昧なメモリ依存関係を解消できることが判明した.

　三つ目の投機技術として,真のデータ依存関係を解消する値予測を議論した.これまでの研究では,予測する命令の前回の演算結果を今回の予測値として利用するLast-value予測や,過去の2回の演算結果の差分と前回の演算結果の和を予測値とするストライド値予測が検討されてきたが,これらの予測機構には予測ミスの回数が多いという欠点が存在する.この欠点の解消を目指した2レベル・ストライド値予測を提案した.2レベル・ストライド値予測では,ストライド値予測でミスした際のグローバルな条件分岐命令の履歴を保存し,同様のミスの発生を抑えることで,予測ミスの削減と正しく予測できる割合の向上を目指す.シミュレーションにより提案手法を評価し,予測をおこなう閾値を8に設定した場合に,最も高い14%の性能向上を確認した.この時,全実行命令の34%の命令の演算結果を正しく予測できることが判明した.

　提案した3つの高レベル投機技術は,制御依存関係,曖昧なメモリ依存関係,真のデータ依存関係,という異なる依存関係を解消する.これらの高レベル投機技術はそれぞれを単体で利用できるが,複数の技術を同時に利用することで,プロセッサ性能の更なる向上が可能となる,本研究では,これらの高レベル投機技術の融合手法を議論した.シミュレーションによる評価により,複数の高レベル投機技術を同時に利用することで,より高い命令レベル並列性の利用が可能となることを示した.

　本論文は、「高レベル投機技術を用いた複数パス実行プロセッサ」と題し、9章からなる。現在の高性能マイクロプロセッサは、スーパースカラー方式によって性能向上をはかっているが、それには限界があり、実効速度向上は2程度である。そこで、この論文では、性能を押えている原因の一つである分岐命令による制御依存性を解消することによってボトルネックを解消すべく、分岐命令から発生する複数のパスを双方とも投機的に効率良く実行する方式や、変数の値やアドレスを予測することによって投機を効率化する方式を提案しそれを詳細に論じたものである。

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

　第2章「プロセッサの動向」は、現在のマイクロプロセッサ技術をサーベイするとともに、次世代のプロセッサとして期待できる技術をまとめている。

　第3章「ペンチマークプログラム」は、本研究でプロセッサの性能を評価するために使用したベンチマークプログラムについてまとめたもので、SPECint95の8本のプログラムを解析し、実行命令数の他、整数演算、分岐命令、ロード命令、ストア命令、浮動小数点演算の割合を与えている。

　第4章「ベースラインプロセッサ」は、本論文で提案する高レベル投機技術による性能向上を明確にするために、比較対象としたプロセッサをベースラインプロセッサと呼び、その定義を与えている。すなわち、アウトオブオーダ実行を行なう理想的なスーパースカラプロセッサであるが、演算ユニット数、リオーダバッファエントリ数、リネームレジスタ数などを無制限に利用可能で、大容量のキャッシュを設けたものである。また、サイクル当たり16命令のフェッチが可能なものとしている。

　第5章「複数パス実行による分岐予測ミスペナルティの削減」は、分岐命令に遭遇したとき、taken/not-takenの両方のパスを同時に実行しておく方式を検討したものである。すなわち、従来、分岐命令によるペナルティの削減を目指して精度の高い分岐予測方式が提案されているが、それでも、なお数%の予測ミスが残り、これは並列性の抽出の大きな制約となっている。それを改良するためには、可能性のあるパスを両方とも投機的に実行し、予測ミス時のロールバックを無くせばよいが、すべての分岐命令のパスを複製すると、余りにもパス数が多くなる。従って、パスを複製する分岐命令の選択手法が重要である。本論文では、様々な手法の性能を評価するとともに、それらを比較検討した結果、JRS確信度評価器と確率モデルとを同時に利用するハイブリッド方式を新たに提案している。これによる分岐予測ペナルティの削減率は50%にもなる。

　第6章は、「メモリ依存予測による曖昧なメモリ依存関係の解消」で、ロード命令とストア命令とのメモリ依存関係を解析することにより、実際の命令実行時点までその依存関係の有無が決定できないというその曖昧性を解消し、先行して実行が可能なロードを増やすことで性能が向上することを定量的に示したものである。また、本章では、そのための予測機構として、ストアセットとストア特定予測のハイブリッド方式を提案しており、それによる性能向上を、サイクル当たりの実行命令数(IPC)で評価すれば、0.7〜1.7になることを示している。

　第7章は、「値予測によるデータ依存関係の解消」で、レジスタの数が無限に多くても、尚存在する真のデータ依存関係を、値を予測することで解消する投機処理について考察したものである。従来、変数の値が、ある一定の差分で変化する状況を予測するストライド方式が提案されているが、その手法では、ストフイド値の変化に対応できない。そこで本論文では、その欠点を補う2レベルストライド方式を提案し、性能が向上することを示している。

　第8章は、「高レベル投機技術を用いた複数パス実行プロセッサ」で、これまでに述べてきた複数パス実行、メモリ依存予測、値予測の3つの投機技術を融合した手法を議論したものであり、精細にその手法を述べるとともに、それによる性能向上を評価している。その結果、融合することによって、大きな総合利得が得られることを示している。

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

　以上、これを要する(本論文は、マイクロプセッサの性能向上を達成するために、複数パス実行、メモリ依存予測、値予測の3つの投機技術の改良や組合せを用いる手法を提案し、それによる性能向上を評価することによって、かなりな性能向上が可能であることを示したもので、情報工学上貢献する所少なくない。

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