チップマルチプロセッサ（CMP）は次世代マイクロプロセッサアーキテクチャとして注目され実用化されつつある。CMPでは複数のスレッドを並列実行することができ、スレッドレベル並列性の多いサーバ用途においては、非常に高いスループットを発揮できる。しかし、デスクトップ用途においては、同時に稼働されているスレッドの数が普段は少ないため、CMPの資源の利用率があまり良くない。さらに、単一スレッドだけを実行する場合、同量の資源を使ったスーパースカラプロセッサよりも一般的に性能が低い。このような問題で、CMPはデスクトップマイクロプロセッサとしては受け入れられがたい。

上記の問題を解決するためにスレッド投機実行という手法が提案された。スレッド投機実行では、単一スレッドプログラムを複数のスレッドに分割し、投機的に並列実行する。数値計算プログラムによく使われている従来の並列化手法と違い、スレッド投機実行ではスレッドの間で制御依存やデータ依存が許されている。実行結果の正しさを保証するために、ハードウェア及びソフトウェアのサポートが追加される。

本研究は、効率的なスレッド投機実行を行うCMPを設計することを目的とし、NEKO アーキテクチャを提案する。NEKO アーキテクチャはまずコンパイラが単一スレッドプログラムに対してスレッド分割を行う。実行時にはプログラムオーダーに従いスレッドを動的に予測しCMP のプロセッシングユニット（PU）に割り当てる。割り当てられたスレッドはそれぞれ各PU上で並列に実行することで、従来の実行方式に比べてより高い性能を目指す。

既存のスレッド投機実行アーキテクチャに比べて、NEKO アーキテクチャには以下の性能向上手法が提案され組み込まれている。

Dual-length パスベーススレッド予測手法

この手法はスレッド予測精度を向上させる手法である。我々が行った解析によれば無限サイズの予測テーブル（エイリアスなし）を仮定しパスベース予測でスレッドを予測する場合、充分長いパス情報を利用すれば、高いヒット率で予測できることがわかった。しかし、予測テーブルサイズを有限にするとパス情報が長くなるほどエイリアスが起りやすくなる。プログラムによってヒット率が悪化するケースが出てきた。そこで、我々は Dual-length パスベース予測手法を提案する。この手法ではパスの長さの長いものと短いもの、2つの予測器を組み合わせハイブリッド構成にする。この構成では、スレッドの数が少なくエイリアスが起りにくいプログラムはパスの長い予測器の高い予測性を活用することができる。また、スレッドの数が多くエイリアスが起りやすいプログラムの場合には、パスの長さが短いものでヒット率悪化を抑制する。さらにこの構成では、テーブルの更新アルゴリズムを工夫することによって、片方のテーブルで予測できるものは他方のテーブルを干渉しないようにすることができ、全体のエイリアスの影響を抑制することができる。

スレッドマージとスレッド予測の早期検証手法

手法1がスレッド予測精度を向上させるのに対し、ここで提案する2つの手法は予測がミスした時に発生するペナルティを削減する。一般的な手法ではスレッド予測ミスが発生した場合、そのスレッドの実行を破棄し、新しいスレッドを同じPUに割り当て実行を再開する。スレッドマージでは、ミスになったスレッドと同じPUではなく、その前のスレッドのあるPUに新しいスレッドの実行をマージする。これは、新しいスレッドの命令の一部はすでにフェッチされ（場合によっては実行もされ）、このPUのパイプラインにすでに入っているということを利用する。新しいスレッドの実行をこのPU上にマージすることによってPUのパイプラインに命令をフェッチするオーバヘッドを削減することができる。もう一つの手法、早期検証では予測がヒットかミスかをできるだけ早く検証できるようにコンパイラが支援を行う手法である。コンパイル時には各後続スレッドの制御等価位置を解析し、その位置に後続スレッドのアドレスが実行時にわかるように特別な命令を入れる。プログラムの制御フローがこの命令に至ったら、PU は後続スレッドのアドレスを確定し、CMPのスレッド管理ユニットに通知する。スレッド管理ユニットは予測の検証を行い、予測がミスした場合より早期にスレッドを破棄し新しいスレッドの実行を再開できる。

低レイテンシレジスタ通信機構

NEKO アーキテクチャはスレッド間のレジスタ依存を許している。従って、あるスレッドが生成した値を、それに依存する後続スレッドが使用する場合、正しい値が伝わるようにしなければならない。我々はスレッド間のレジスタ依存解析を行い、依存関係の大部分はプログラムオーダで隣接している二つのスレッドに存在していることがわかった。また、通信バンド幅よりも通信レイテンシの方が性能に大きく影響することがわかった。これらの解析結果を踏まえて、NEKOアーキテクチャにはリングトポロジの通信データパスを採用した。また、生成したレジスタの値を実際通信するかどうかがまだ確定していない時点でもできるだけ次のPUの近くに送れるようにしている。通信プロトコルにはProducer-initiated 型を採用し、通信手続きによるオーバヘッドを最低限にする。また、提案するデータパスはレジスタファイルやリネームマップに追加するポート数が少ない。このように我々は低レイテンシレジスタ通信機構を実現し、高い性能を目指している。

更新型・リードブロードキャスト コヒーレンス プロトコル

スレッド投機実行アーキテクチャではスレッドレベルメモリ投機を行うものが一般的である。スレッドレベルメモリ投機では、投機スレッドは前のスレッドの全てのメモリアクセスが解決できなくても、メモリロードを積極的に行う。その後、前のスレッドが同じところにメモリストアをした場合はバイオレーションが発生し、バイオレーションが生じたスレッドを破棄し再実行させる。このような機能を実現するキャッシュ機構は関連研究ですでにいくつか提案されているが、これらは全て無効化型コヒーレンスプロトコルを使っている。しかし、我々の解析では無効化型プロトコルでスレッド投機実行を行うと高い共有ミス(sharing miss)が発生することがわかった。また、スレッド投機実行ではスレッドの実行が分散され、キャッシュの空間的・時間的局所性が低くなり、ミス率が著しく上がることもわかった。これらの問題を解決するために更新型・リードブロードキャスト コヒーレンス プロトコル を提案する。このプロトコルはスレッドがストアしキャッシュを更新した場合、その更新を同じラインのコピーを持つキャッシュにも通信し更新させる。これによって無効化型プロトコルに多発する共有ミスを抑制する。また、リードブロードキャスト機能を使って、あるキャッシュにミスが発生し新しいラインを持ってくる場合、他のキャッシュもそのラインをスヌープし自分のところにも入れる。これによってバンド幅を無駄にすることなくプリフェッチに近い機能を実現し、局所性の低下によるキャッシュミス率の増加も押さえる。

本論文は NEKO アーキテクチャの設計についての解析及び提案手法を述べている。まず既存の問題点を洗いだし定量的に解析をする。その結果に基づいて提案を行い、その提案手法を NEKO アーキテクチャに組み込む。さらに、詳細なシミュレーションを行い提案した手法及び NEKO アーキテクチャ全体を評価する。評価結果から我々が提案した手法がそれぞれの問題に対し効果的であること、また NEKO アーキテクチャを用いることで従来の実行方式より高い性能が得られることを確認し、NEKO アーキテクチャの有効性を示す。

本論文は、Designing NEKO: A Speculative Multithreading Chip Multiprocessor（スレッド投機実行チップマルチプロセッサＮＥＫＯの設計と評価）と題し、全体で8章から成る。本論文は、近未来のＣＰＵの主流をなすと考えられるチップマルチプロセッサシステムについて、そのアーキテクチャと処理方式を提案し、シミュレーション評価を行ってこれを検証したものである。チップマルチプロセッサは複数のスレッドを並列実行することができるために潜在的に高い性能をあげることが期待されるが、汎用用途においては、並列性の不足からこれが果たされていなかった。本論文は、以下に示す要素技術・システム技術によってこれを解決し、真に有用なチップマルチプロセッサを提案するものである。

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

第2章「Related work」は、本論文の下敷きとなる先行研究を紹介し、これを検討することでチップマルチプロセッサの課題を明らかにするものである。先行研究としては、動的マルチスレッディング（ＤＭＴ），ＮＥＣ　ＭＰ98、名古屋大学ＳＫＹ、ウィスコンシン大学Multiscalar、スタンフォード大学Hydra、イリノイ大学IACOMA、ミネソタ大学スーパスレッディング、投機的マルチスレッディングなどがとりあげられている。これらの研究開発について紹介したあと、本章では先行研究の限界として、集中型のハードウェア資源が多く競合による性能低下が避けられないこと、投機の正確さだけを問題にして投機に失敗したときのペナルティを軽減する方法について検討していないこと、の2点をあげている。

第3章「Overview of NEKO architecture」は、本論文で提案するチップマルチプロセッサアーキテクチャであるＮＥＫＯの概要を述べている。ＮＥＫＯ アーキテクチャにおいては、まずコンパイラが単一スレッドプログラムに対してスレッド分割を行う。実行時にはプログラムの順序に従いスレッドを動的に予測しプロセッシングユニットに割り当てる。割り当てられたスレッドはそれぞれ各プロセッシングユニット上で並列に実行することで、従来の実行方式に比べてより高い性能を目指す。

第4章「Thread-level control speculation」では、スレッドレベルの投機処理を効果的に行う手法が提案・評価されている。具体的には、「Dual-length パスベース・スレッド予測手法」、「スレッドマージ」、「スレッド予測の早期検証手法」の3つの手法が示されている。「Dual-length パスベース・スレッド予測手法」は、パスの長さの長いものと短いもののそれぞれに予測器を設け、両者を組み合わせてハイブリッド構成にすることで、スレッド予測率をあげるものである。「スレッドマージ」は、スレッドを動的にマージして起動オーバヘッドを軽減する方式である。「スレッド予測の早期検証手法」では予測がヒットかミスかをできるだけ早く検証できるようにコンパイラが支援する手法である。

第5章「Register synchronization」は、低レイテンシのレジスタ通信・データ同期機構を提案・評価するものである。ＮＥＫＯ アーキテクチャはスレッド間のレジスタ依存を許しているため、あるスレッドが生成した値を、それに依存する後続スレッドが使用する場合、正しい値が伝わるようにしなければならない。ここではリングトポロジの通信データパスを用い、ハードウェア量を抑えながら通信オーバヘッドを最小化する方式を提案し、シミュレーション評価によってその有効性を示した。

第6章「Cache design」は、ＮＥＫＯのキャッシュプロトコルとして、「更新型・リードブロードキャスト コヒーレンス プロトコル」の採用を提案し、評価した。これによって無効化型プロトコルでは多発していた共有ミスを抑制できることなどが確認された。

第7章「Evaluations」は、以上の提案を総合し、ＮＥＫＯシステムの全体評価を行ったものである。ＮＥＫＯで提案・提唱された方式により、従来では得られなかった大きな性能向上が達成されることが示された。

第8章「Conclusion」は、結論である。

以上、これを要するに本論文は、近未来のＣＰＵの主流と目されるチップマルチプロセッサについて、スレッド投機方式、レジスタデータ転送方式、キャッシュ方式などにおいて新規性に富む優れた方式提案を行い、綿密なシミュレーション評価によってその有用性を検証しており、電子情報学の発展に寄与するところが小さくない。

よって本論文は博士（情報理工学）の学位請求論文として合格と認められる。