Comments
Description
Transcript
レジスタ・リネーミングと ディスパッチ・ネットワークを
卒業論文 レジスタ・リネーミングと ディスパッチ・ネットワークを不要とする トレース・キャッシュ・アーキテクチャ 平成 23 年 2 月 14 日提出 指導教員 坂井 修一 教授 五島正裕 准教授 電子情報工学科 090442 伊達 三雄 目次 第1章 はじめに 1 第2章 2.1 スーパースカラ・プロセッサのフロントエンド・ロジック レジスタ・リネーミング . . . . . . . . . . . . . . . . . . . 2.1.1 レジスタ・リネーミングの動作 . . . . . . . . . . . 2.1.2 レジスタ・リネーミングの負荷 . . . . . . . . . . . ディスパッチ . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 ディスパッチ・ネットワークの負荷 . . . . . . . . . . . . . 3 3 3 5 6 6 . . . . . . . . 9 9 10 10 10 11 12 13 13 . . . . . 15 16 16 17 19 19 評価 評価モデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . キャッシュ・ミス率と IPC . . . . . . . . . . . . . . . . . . . . 20 20 20 2.2 第3章 3.1 3.2 3.3 3.4 3.5 第4章 4.1 4.2 4.3 4.4 第5章 5.1 5.2 Renamed Trace Cache RTC の基本的な考え方 . . . . . . . . . Dualflow 形式の命令の実行 . . . . . . . 3.2.1 RTC の命令形式 . . . . . . . . 3.2.2 Dualflow 形式の実行 . . . . . . Dualflow 形式への変換 . . . . . . . . . パスの表現 . . . . . . . . . . . . . . . 3.4.1 RTC のインデックス生成とパス RTC の効果 . . . . . . . . . . . . . . . Dispatched Image Cache ディスパッチ情報の再利用 . . . . キャッシュ・ラインの形成モデル キャッシュの利用効率 . . . . . . 4.3.1 キャッシュのヒット論理 . DIC の効果 . . . . . . . . . . . . i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 第6章 おわりに 23 ii 図目次 2.1 2.2 2.3 スーパースカラ・プロセッサの基本構造 . . . . . . . . . . . . レジスタ・リネーミングの例 . . . . . . . . . . . . . . . . . . ディスパッチ・ネットワークの複雑性 . . . . . . . . . . . . . 4 5 7 3.1 3.2 3.3 Dualflow 形式の命令表現 . . . . . . . . . . . . . . . . . . . . . Dualflow 形式の命令の実行 . . . . . . . . . . . . . . . . . . . . 変換結果の変化 . . . . . . . . . . . . . . . . . . . . . . . . . . 10 11 12 4.1 4.2 ディスパッチ・ネットワークの省略 . . . . . . . . . . . . . . . DIC の格納法例 . . . . . . . . . . . . . . . . . . . . . . . . . . 15 18 5.1 5.2 DIC・ミス率 . . . . . . . . . . . . . . . . . . . . . . . . . . . 相対 IPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 22 iii 第1章 はじめに 一般にスーパースカラ・プロセッサにおいて，パイプライン上の各フェーズ で同時に処理することのできる命令数を増やすことで，性能は向上する．しか し一般的なスーパースカラ・プロセッサの制御部 (非演算器) の面積は，同時処 理可能な命令数に対して２乗から３乗に比例する大きさで増加する [2]．これ は，スーパースカラ・プロセッサの制御部の大部分が RAM や CAM で構成さ れており，それらの面積がポート数の２乗に比例するためである．多数の命令 を同時に処理するためには，RAM や CAM に対して，多数のアクセス・ポー トが必要となり，回路面積は非常に大きくなってしまう． 本研究では，このようなスーパースカラ・プロセッサの制御部の中で，レジ スタ・リネーミングとディスパッチのロジックに着目する． レジスタ・リネーミングは命令間の偽の依存を解消する処理である．通常は RMT (Register Map Table) を用いて，命令セット・アーキテクチャに指定さ れる論理レジスタを，実際にレジスタ値を格納する物理レジスタにマッピング する．詳しくは 2.1.2 節で述べるが，RMT を RAM で実装した場合，１命令に つき RMT のポートは 4 つ必要である．同時にリネームを行う命令数 (リネー ム幅) が 4 であればポート数は 16 にもなり，RMT の面積は非常に大きなもの となる．RMT はアクセス頻度が高いため，その消費電力も大きくなり，この ロジックの熱密度は大きくなる． ディスパッチは，各命令を，対応する命令ウィンドウに格納する処理である． 一般的なスーパースカラ・プロセッサでは，命令ウィンドウを整数，ロード/ス トア，浮動小数点といった命令の系統ごとに非集中化し, そこでスケジューリ ングを行う．同時にディスパッチする命令数（ディスパッチ幅）が増えるほど， 命令ウィンドウに分配するためのロジックは複雑化する．この配線網をディス パッチ・ネットワークと呼ぶこととする．2.2.1 節で述べるように，このディス パッチ・ネットワークの配線面積もディスパッチ幅の 2 乗に比例して増加する． 基本的にすべての命令がディスパッチ・ネットワークを通るため，利用頻度も 高く，消費電力も増加する． 本研究では，これらの複雑なロジックを省略する手法として DIC (Dispatched Image Cache) を提案する．DIC はレジスタ・リネーミングを行い，ディスパッ 1 チされた後の命令列を格納するトレース・キャッシュである．レジスタ・リネー ミングとディスパッチ情報を再利用することで，これらのロジックを不要と する． 本研究室ではレジスタ・リネーミング済みの命令をキャッシュし，再利用す る手法として RTC (Renamed Trace Cache) を提案した [1]. RTC では後続の命 令が，どの命令の実行結果をソース・オペランドとして使用するかを指定する 形式に命令を変換する．その指定を，何命令前の実行結果に依存しているか， という相対的な差分情報で表すことによって依存を解析する．毎回異なる物理 レジスタ値を割り当てる通常のレジスタ・リネーミングと異なり，この手法を 用いることで変換情報を再利用できる． DIC でも，RTC と同様の形式でリネーミングを行うことによって，依存解析 結果の再利用を可能とする．さらに，ディスパッチ済みの命令列を，対応する 命令ウィンドウごとに領域を分けてキャッシュすることで，ディスパッチ情報 も再利用可能にする．キャッシュ・ヒット時には DIC からフェッチすると同時 に命令ウィンドウに格納できる．ミス時にのみ少数の命令を，依存解析 及び ディスパッチを行う．そうすることで，レジスタ・リネーミング及び，ディス パッチに要する回路面積，消費電力を最小限に保ちながら，リネーム幅，ディ スパッチ幅が大きいときと同等の性能を得られる． 本稿の構成は以下の通りである．2 章では一般的なスーパースカラ・プロセッ サのフロント・エンドのロジックを簡単に説明する．特に本研究で対象とする， リネーミング及びディスパッチの役割とその負荷を論じる．次に 3 章で，提案 手法の背景となる RTC の実現方を述べる．4 章では，提案手法について述べる． 5 章で提案手法の評価を行う．最後に 6 章で，まとめと今後の方針を述べる． 2 第2章 スーパースカラ・プロセッサ のフロントエンド・ロジック 本章では一般的なスーパースカラ・プロセッサにおけるレジスタ・リネーミ ング とディスパッチ の役割とその負荷を明らかにする． 一般的なスーパースカラ・プロセッサの構成 図 2.1 は基本的なアウト・オブ・ オーダスーパースカラ・プロセッサの構成例である．同図のパイプライン上で フェッチから，ディスパッチまでをフロントエンド，発行以降のステージをバッ クエンドと呼ぶ．本研究で主に着目しているのは，フロントエンドのロジック である． フロントエンドの主な役割は，実行する命令の供給と，依存関係の解析であ る．フェッチ・フェーズで命令キャッシュから命令を取り出す．次にフェッチ する命令を決めるために，分岐予測なども行う．リネーム・フェーズでは依存 解析のためにレジスタ・リネーミングを行う．並列実行可能な命令数を増やす ために，出力依存と逆依存を取り除く．ディスパッチ・フェーズでは命令を， 命令ウィンドウに格納する. 命令ウィンドウは，整数，ロード/ストア，浮動小 数点といった，命令の種類ごとに分けることで，それぞれに専用の実行ユニッ トを，効率よく使うことができる．ディスパッチとは命令列を，対応する命令 ウィンドウに配分することである．ディスパッチされた命令は，命令ウィンド ウ内で，依存関係を満たし，対応する実行ユニットが利用可能になるまで待機 する．実行可能になった命令からアウト・オブ・オーダで実行する． 2.1 レジスタ・リネーミング 2.1.1 レジスタ・リネーミングの動作 レジスタ・リネーミングはレジスタの逆依存と出力依存を回避するための処 理である． 3 レジスタ・ファイル 命令 キャッシュ フェッチ Fetch 命令 ウィンドウ リネーム ロジック リネーム ディスパッチ スケジュール Rename Dispatch Schedule 演算器 発行 Issue 実行 Exec フロントエンド バックエンド front-end back-end 書戻 WB 図 2.1: スーパースカラ・プロセッサの基本構造 これらの依存はレジスタの再利用により生じる．命令セット・アーキテク チャで指定される論理レジスタの数は限られているため，不要になった演算結 果を格納しているレジスタに上書きすることで，新しい実行結果を得る．互い に近い命令順にある命令が，同じデスティネーション・オペランドを指定して いるとき，これらの命令は正しい格納順を保持する必要があり，同時に実行す ることができない． これに対して，レジスタを再利用せずに，命令ごとに違うレジスタを使用す ればこれらの依存は生じない．レジスタ・リネーミングは論理レジスタを，実 行時に値を保持する物理レジスタにマッピングすることで，これらの依存を解 決する． 図 2.2 を用いて変換動作例を示す．左がレジスタ・リネーミングを行う前で， 右が行った後である．変換前の i1 のデスティネーション・オペランドは，i0 の ソース・オペランドと同一であるため並列に実行できない（逆依存）．また i2 のデスティネーション・オペランドと i1 のデスティネーション・オペランドが 同じであるため並列に実行できない（出力依存）．レジスタ・リネーミングに よって，別々の物理レジスタを与えることで，これらの依存が解消されている． 通常，このマッピングは RMT と呼ばれる表を用いて行われる．RMT は，論 理レジスタ番号と物理レジスタ番号との現在のマッピングを保持する．RMT を RAM で実装した場合，この RAM を論理レジスタ番号でアドレッシングし 4 リネーミング前 リネーミング後 i0: add r1 <= r2 + 1 i0: add p10 <= p9 i1: sub r2 <= r3 - 1 i1: sub p12 <= p11 - 1 i2: add r1 <= r4 + 1 i2: add p14 <= p13 + 1 + 1 図 2.2: レジスタ・リネーミングの例 て読み出すことで論理レジスタ番号と物理レジスタ番号の対応を得る． 2.1.2 レジスタ・リネーミングの負荷 ソース・オペランド 2 つ，デスティネーション・オペランド 1 つのアーキテ クチャにおいて，RAM で構成された RMT を用いたレジスタ・リネーミング を考える． 1 つの命令をリネームするには， • デスティネーション論理レジスタに割り当てられていた物理レジスタを 解放するための読み出しに 1 ポート • デスティネーション論理レジスタに新たに割り当てられた物理レジスタ 番号の書き込みに 1 ポート • 2 つのソース論理レジスタに割り当てられている物理レジスタ番号の読 み出しに 2 ポート 必要であり，リネームする命令 1 個につき RMT のポートは 4 個必要である． リネーム幅 4 のスーパースカラ・プロセッサを仮定すると，RMT のポートは 16 個必要であり，16 の 2 乗に比例する非常に大きな面積を必要とする． 回路の面積が非常に大きくなることで，消費電力の面でも，命令処理のス ループットの面でも制約を与えることとなる． 消費電力 RMT のアクセス頻度は，レジスタ・ファイルと比べても非常に高 い．レジスタ・ファイルも，概念的には RMT と同様に，オペランド 1 つごと に 1 回アクセスを行うが，RMT は物理レジスタ解放のための読み出しが必要 5 であること，ソース・オペランドの多くはフォワーディングにより供給される こと，投機ミスのためリネームは行われたが実行はされない命令が存在するこ とが原因である．RMT のような多ポートの RAM に対して，高頻度でアクセ スを繰り返すと消費される電力も非常に大きなものとなる． 処理性能 フロントエンドの幅を増加させることで，1 サイクルに，命令ウィ ンドウに格納される命令数を増加させ，命令ウィンドウを素早く埋めることが できる．そうすることで，命令の並列処理の可能性を増加させスループットが あがる．しかし，リネーム幅を増やすことは RMT の巨大化につながり，実質 不可能である． このように，RMT は多ポート，高遅延，高アクセス頻度であるため，レジ スタ・リネーミングを省略することにより，RMT の面積を大幅に削減し，消 費電力を削減することができる．またフロントエンドの幅を増加させたり，パ イプライン段数を削減することが可能になると考えられる． 2.2 ディスパッチ スーパースカラ・プロセッサにおけるディスパッチとは，フェッチされ，リ ネーミングが完了した命令列を，命令ウィンドウに格納することである．一般 的なスーパースカラ・プロセッサではこの命令ウィンドウを整数 (INT)，ロー ド/ストア (LS)，浮動小数点 (FP) といった命令の系統ごとに非集中化する．命 令ウィンドウを非集中化することで，ロジックの実行サイズの縮小と，クリ ティカルパスの分離の効果が得られる [2]. 以下では，同時にディスパッチ可能とする命令数をディスパッチ幅と呼ぶこ ととする．また，命令ウィンドウは上述のような整数，ロード/ストア，浮動小 数点の 3 つの非集中命令ウィンドウを仮定する． 2.2.1 ディスパッチ・ネットワークの負荷 図 2.3 にディスパッチ幅 4 ，命令ウィンドウ数 3 のスーパースカラ・プロセッ サのディスパッチ回路を示す．フェッチ幅 4 として，バンク分けした命令キャッ シュから命令列をフェッチしている．その後 4 命令同時にレジスタ・リネーミ ングを行う．この時点で命令がプログラム・オーダを乱すと，依存関係が乱れ， 正しい実行結果が得られなくなる可能性がある．フェッチされた命令列は，バ ンクによって命令順が決まっているわけではないので，ローテータによって一 定の命令順を保つ必要がある． 6 命令キャッシュ 0 4 1 5 2 6 3 7 ローテータ リネーム・ロジック セレクタ B ：リネーム後の命令サイズ（～６０） DW :ディスパッチ幅（４） IW ：発行幅（２） B =~60bit幅 B × DW × × 2-read,4-write or 2-read,1-write 4 (1+IW) DW B × 命令ウィンドウ (INT) 命令ウィンドウ (MEM) 命令ウィンドウ (FP) 図 2.3: ディスパッチ・ネットワークの複雑性 リネーム済みの命令は 60 bit 程度になり，図 2.3 のリネーミング・ロジック から出ている 1 本の線は，変換された命令であり，60 本のビット・ラインを 表している． ディスパッチ・ネットワーク リネームされた命令のそれぞれが格納される命 令ウィンドウは命令毎に異なる．各命令を表す，60 ビットのラインは，すべ ての命令ウィンドウにセレクタを通して繋がる必要がある．このロジックは 図 2.3 のように，格子状のネットワークとなる．このディスパッチのためのロ ジックをディスパッチ・ネットワークと呼ぶ． 命令ウィンドウとアクセス・ポート 各命令ウィンドウは，基本的にディスパッ チ幅分の書き込みポートと，発行幅分の読み出しポートを備えた RAM で構成 される． 実際には，命令ウィンドウへの書き込みは連続した領域に書き込まれるた め，ランダム・アクセス可能な書き込みポートを 4 つ増やす必要はない．その 7 ため図 2.3 では，各命令ウィンドウを 1 write，2 read の RAM4 つにバンク分 けを行っている．バンク分けされた各命令ウィンドウに隙間なく書き込みを行 うために，各命令のラインは全てのバンクに繋がらなければならない．そのた めに，ディスパッチ・ネットワークのすべての交点にセレクタが必要であり， 図 2.3 では三角形で表している． 以上のような命令ウィンドウに対するディスパッチ・ネットワークの大き さは，命令ウィンドウの幅の和と，ディスパッチ幅と，リネーム済み命令のサ イズの積で表される．命令ウィンドウの幅もディスパッチ幅に比例するため， ディスパッチ・ネットワークの面積はディスパッチ幅の 2 乗に比例して大きく なる．命令のサイズも 60 程度と大きくなっているので，ディスパッチ・ネッ トワークは非常に大きな回路面積を必要とする．このロジックは，すべての命 令がディスパッチの度に利用する必要があるため，利用頻度も高く，消費電力 も高くなる．それに伴い熱密度も高くなる． このディスパッチ・ネットワークを省略することができれば，レジスタ・リ ネーミングの省略と同様に，回路面積を大幅に削減でき，消費電力，熱密度の 面からも大きな改善が得られる． 8 第 3 章 Renamed Trace Cache 本章では RTC (Renamed Trace Cache)[1] の実現方法について説明する． 2.1.2 節で述べたように，レジスタ・リネーミングの際に用いる RMT の負荷は 高い．RTC は，通常時はレジスタ・リネーミングを行わないことで，RMT を 省略することを目的とする． 3.1 RTC の基本的な考え方 RTC は依存解析を行った後の命令列をトレース・キャッシュ[3] にキャッシュ し，再利用する．キャッシュ・ヒット時には命令は依存解析済みであり，レジ スタ・リネーミングを省略し直接ディスパッチできる．キャッシュ・ミス時にの み小さなリネーム幅で依存解析を行うことで，RMT の負荷を最小限にできる． しかし，通常のレジスタ・リネーミングではリネーミング結果を再利用する ことはできない．これは，同じ命令に対しても，毎回異なるマッピング情報を 得ることとなるからである．通常のレジスタ・リネーミングは，フリーリスト から，そのとき使用可能な物理レジスタ番号を割り当てる．また，命令の実行 経路によって，依存する命令は異なることがある．この方法では，フリーリス トの状態や，実行経路によってリネーミング結果は異なってしまう． 一方で，RTC では依存解析結果を，後続の命令が，依存先の命令が何命令 前に実行されたか，という距離で表す．このように依存先の命令を指定する形 に変換し，経路ごとに区別してキャッシュすることで，依存解析の結果を再利 用可能にする．RTC の基本的な考え方は次の通りである • 命令の実行結果を格納するサイクリックなバッファである物理レジスタ・ ファイルを用意し，in-order にエントリを割り当て，out-of-order で実行 結果を格納する • 物理レジスタ・ファイルとは別に，論理レジスタの値を保持する論理レ ジスタ・ファイルを用意する．リタイア時に，命令の実行結果を，物理 レジスタ・ファイルから論理レジスタ・ファイルに in-order に格納する 9 Opcode DstReg RL SrcL RR SrcR Imm 図 3.1: Dualflow 形式の命令表現 • 初回の実行時に命令を変換し，ソース・オペランドを「n 命令前」の実 行結果として物理レジスタ・ファイル上での変位で指定するようにする． リタイア済みであり実行結果が論理レジスタ・ファイルに格納されてい ることが保証できる命令の実行結果を使用する場合には，ソース・オペ ランドを論理レジスタ番号で指定する • 変換した命令列を，命令の実行履歴をタグとするトレース・キャッシュに キャッシュし，再利用する 以下，RTC が実際にどのように動作するか具体的に述べる． 3.2 Dualflow 形式の命令の実行 3.2.1 RTC の命令形式 RTC では，命令のソース・オペランドを，論理レジスタ番号で指定する通常 の形式から「n 命令前」の命令の実行結果として物理レジスタ・ファイル上の 変位で指定する形式に内部的に変換する．ただし，リタイア済みであることが 保証できる命令の実行結果を使用する場合には，ソース・オペランドを論理レ ジスタ番号のままで指定する．以下，この変換形式を dualflow 形式と呼ぶ． 図 3.1 に dualflow 形式に変換された命令の表現形式を例示する．DstReg でデ スティネーション・オペランドを論理レジスタ番号によって指定する．SrcL/SrcR でソース・オペランドを指定する．RL/RR が 1 のとき SrcL/SrcR は依存命令 への変位を表し，RL/RR が 0 のとき SrcL/SrcR は論理レジスタ番号を表す． 3.2.2 Dualflow 形式の実行 Dualflow 形式の命令の実行方法を，図 3.2 を用いて説明する．[−n] は， 「n 命 令前の命令の実行結果」を表す． まず，各命令に対し，物理レジスタ・ファイルのエントリを in-order に割り 当てる．in-order に割り当てることにより，読み出すべき物理レジスタは，命 令に割り当てられた物理レジスタのインデックスに変位を加算するだけで決定 することができる．物理レジスタ・ファイルのエントリには，対応する命令の 10 変換後の命令列 I1 I2 mov add 変換後の命令列 r1 = a r3 = r1+ r2 I1 I2 mov add r1 = a r3 = [-1] + r2 物理レジスタ・ファイル 論理レジスタ・ファイル I1 I2 a a+b r1 r2 r3 r1 r3 a b a+b 図 3.2: Dualflow 形式の命令の実行 デスティネーション論理レジスタ番号を付随させておく．命令の実行結果は， 実行の終わったものから out-of-order に物理レジスタ・ファイルに格納する．そ の後，最も古い命令に対応する物理レジスタのエントリから順番に，すなわち in-order に実行結果を論理レジスタ・ファイルにコピーする． ここで，ある命令のソース・オペランドが命令ウィンドウサイズ W S 以上前 の命令の実行結果である場合を考える．W S 以上前の命令はリタイアしている ので，実行結果は論理レジスタ・ファイルにコピーされている．そのような命 令の実行結果は論理レジスタ・ファイルから読み出すことができる．よって， ソース・オペランドは，W S 以上前の命令の実行結果を参照する場合論理レジ スタ番号のまま指定する．Dualflow 形式への変換時にそのソース・オペランド が論理レジスタ番号を指定しているのか，差分を表しているのかを示す 1 bit を付け加える (図 3.1)． 物理レジスタ・ファイルは，命令ウィンドウ中の最も古い命令が，変位でオ ペランドを指定する最大の範囲である (W S − 1) 前の命令の実行結果を利用で きるようにするため，(2 × W S) エントリを用意する． 3.3 Dualflow 形式への変換 Dualflow 形式への変換は，レジスタ・リネーミングと同様に行うことができ る．まず，命令にフェッチされた順の通し番号を振る．論理レジスタ番号とそ 11 変換後 変換前 (untaken) (taken) mov r1 = … mov r1 = … mov r1 = … bgt r1 > 0 then L1 bgt [-1] > 0 then L1 bgt [-1] > 0 then L1 neg r1 = -r1 neg r1 = -[-2] L1: add r3 = r2 + r1 L1: add L1: add r3 = r2 + [-2] r3 = r2 + [-1] 図 3.3: 変換結果の変化 のプロデューサの番号の対応表を用意し，命令がフェッチされるたびに更新す る．対応表からソース・オペランド・レジスタに対応する命令の番号を読み出 し，変換対象の命令の番号との差を取れば，何命令前の命令の実行結果をソー ス・オペランドとして用いればよいかが分かる．3.2.2 節で述べたように，W S 以上前の命令の実行結果を参照する場合には論理レジスタ番号で参照する． ここで，同時に多数の命令を変換する場合，結局，この対応表の負荷が RMT と同様に高くなってしまう．しかし，変換は初回の実行時のみ行われ，以後は キャッシュした dualflow 形式の命令を再利用できるので，同時に変換できる命 令が少なくても性能への影響は少ないと考えられる．今回は，1 サイクルに 1 命令を変換できるとした． 3.4 パスの表現 RTC では，命令のソース・オペランドを「n 命令前」と変位で表現する形式 に変換する．しかし，変換中の命令までに実行した命令によって，ソース・オ ペランドのプロデューサとなる命令の位置は変化する．図 3.3 に例を示す．分 岐命令 bgt が untaken であれば，add 命令のソースオペランド r1 は 1 命令前 に依存しているため，変換結果は [−1] となる．taken であれば，neg 命令は実 行されないため，add の参照距離は [−2] となる．add 命令から始まる命令列を キャッシュするとき，bgt の結果によって区別しなければならない． パス 変換結果のトレースを一意に識別できる情報をパス と呼ぶことにする． 変換結果はソース・オペランドのプロデューサとなる命令の位置で変化する のであるから，変換結果を一意に識別するためには，トレースにあるソース・ オペランド全てについて，それらのプロデューサの位置が一意に特定できれ ばよい．特定するためには，トレースにある命令のソース・オペランドのプロ 12 デューサとなる命令のうち，最も遠くの命令からそのトレースまでに実行した 命令履歴が特定できれば十分である． このパス上のすべての命令のアドレスを用いることで，パスは一意に表現す ることができるが，それでは冗長である．パスの表現として • パスの先頭の命令のアドレス H • パスの長さ L • パス内の条件分岐の成否 bf lag • パス内の間接分岐のターゲット jtarget とその数 jumpCount を用いることができる [1]． RTC はこのパス情報をタグとして利用する．このタグを比較することによっ て，同一のアドレスを持つ命令列であっても区別することができる． 3.4.1 RTC のインデックス生成とパス 前述のように RTC では同一アドレスの命令列に対して複数のリネームド・ トレースが区別して格納される．このため，命令列の先頭のアドレスなど，パ ス情報を含まない要素のみを用いてインデックスを行うと，コンフリクト・ミ スが起きやすくなる． これを防ぐために，パスの情報を用いてインデックスを行う．典型的には， 一定の命令数前からの，分岐履歴を用いればよい．トレース内に複数の分岐を 含む RTC を構成する際には，分岐予測の情報を用いることもできる．命令列 のアドレスに加え，条件分岐の履歴，分岐予測などをハッシュ関数に通すこと で効果的なインデックスが行える． また，パス内の間接分岐命令のターゲットを多く保持する場合，タグの容量 は大きくなるため，パスに含めることのできる間接分岐命令の数を制限する必 要がある．制限を超過するトレースは，キャッシュに格納しないなどの対応を とる． WS が 32 のとき，パスに含むことのできる間接分岐命令は 2 個あれば，性 能の低下はほとんどないという結果が得られている [1]． 3.5 RTC の効果 RTC により，レジスタ・リネーミングを省略することができる．レジスタ・ リネーミングを省略することにより: 13 • レジスタ・リネーミングに必要なハードウェア・電力 (特に RMT) が削減 できる • レジスタ・リネーミング・ステージ分だけ，分岐予測ミス・ペナルティ が減少する • RTC は 1 ポートで多くの命令列を取り出せるので，フェッチ幅を大きく することができる 14 第 4 章 Dispatched Image Cache DIC (Dispatched Image Cache) はレジスタ・リネーミングに加え，ディス パッチが完了した後の命令列をトレース・キャッシュに格納し再利用する．そ うすることで，図 2.3 のようなディスパッチ・ネットワークを不要とし，図 4.1 のような構成を実現する． 命令キャッシュ Dispatched Image Cache 0 1 リネーム・ロジック ネットワークの簡 略化 2-read,2-write or 2-read,1-write ×2 命令 命令 ウィンド ウィンド ウ ウ (INT) (INT) 命令 命令 ウィンド ウィンド ウ ウ (MEM) (MEM) 命令 ウィンド ウ (FP) 命令 ウィンド ウ (FP) 図 4.1: ディスパッチ・ネットワークの省略 15 4.1 ディスパッチ情報の再利用 レジスタ・リネーミングに加え，ディスパッチ情報を再利用するための DIC の構成は図 4.1 のようになる．基本的には， • 命令は Dualflow 形式に変換する • キャッシュの領域を各命令ウィンドウに合わせて区切り，対応するキャッ シュ領域にのみ, 変換した命令を格納する • ディスパッチを行った後の命令列をまとめてキャッシュし，再利用する • キャッシュ・インデックスの生成やタグ比較は RTC と同様に行う 整数命令は整数命令用のキャッシュ領域に，ロード/ストア命令はロード/スト ア用の領域に，命令のタイプに合わせてそれぞれ格納する．図 4.1 では，各命 令タイプ用の領域もバンク分けを行い，2 命令ずつフェッチ (ディスパッチ) で きるような DIC の構成をとっている．それに伴い，それぞれの命令ウィンド ウも 2 つにバンク分けを行っている．図 2.3 と同様に，ディスパッチ・ネット ワークの交点はセレクタを表すが，大幅に削減されていることがわかる． このような構成をとることで，DIC・ヒット時には，フェッチを行うと同時 にディスパッチが完了し，命令列は命令ウィンドウに格納されている状態とな る．DIC・ミス時にのみ，少数の命令の依存解析とディスパッチを行う．図 4.1 は DIC・ミス時にフロント・エンドを流れる命令数を 1 としたときの構成図で ある． 4.2 キャッシュ・ラインの形成モデル DIC では，どのような命令列を同一ディスパッチグループにするか自由度が ある．トレース・キャッシュや RTC では，実行順にならんだ命令列 (トレース) をひとまとまりで格納したが，DIC では必ずしもその必要はない． 図 4.2 を用いて最も簡単なキャッシュ・ラインの形成方法の一例を説明する. 図 4.2 の左側の命令列，i0 から i9 が上から順にディスパッチされたと仮定する． 右側の INT，MEM，FP と領域を区切った部分は，DIC のモデルを表しており， それを横一列にまとめたものが，論理的なキャッシュ・ラインである．このラ インの命令列が，同一のタグを持ち，同時にディスパッチするグループである． 4.3 節で述べるように，DIC の内部の命令が，物理的にこのような位置関係で 格納されている必要はない． 今回の手法では以下のようなルールに従ってラインを形成する． 16 • 各キャッシュ領域 の 1 ラインに 2 命令まで格納できるようにする • ラインをまたいで命令を追い越さない．すなわち，1 つのタイプのキャッ シュ領域 のラインが埋まれば，他のタイプのキャッシュ領域の同一ライ ンが空いていてもラインを形成を完了する • 分岐命令の次の命令は，次のラインに格納する．すなわち，分岐命令で 命令列を区切る 分岐命令で区切るとは, 図 4.2 において，i9 は i8 の隣に詰めないという意味 である．トレースの区切り方によっては，一つのループ構造に対して複数のト レースが生成されることがあり [3]，キャッシュの容量を圧迫する．また 3.4 章 で述べたように，Dualflow 形式に変換された命令列は，実行履歴によって区別 してキャッシュされる必要があり，分岐命令でトレースを区切らない場合，DIC も RTC と同様に単一のループに対して，多くのトレースが生じ，さらに DIC の容量を消費する． 命令を追い越さないとは，図 4.2 の i7 は i2 の隣や i4 の隣などに詰めたりし ないということである．これはプログラム・オーダを保ち，格納ロジックを簡 単にするためである． 逆 dualflow アーキテクチャ形式に変換する際に，物理レジスタに対して命令 をシーケンシャルに割り当てた．命令のリタイアもこの割り当てた順番に行う ことで，出力依存や逆依存を防いでいる．通常のトレース・キャッシュや RTC の場合は命令の順序を保ったままキャッシュに格納されているため，一定の順 番でリタイアすればよい．しかし DIC は命令順が崩れることとなる． 図 4.2 の手法でも，同一ライン内の命令順はバラバラである可能性がある． 例えば i0，i1，i2 のラインは左から命令順というわけではない．従って DIC か らフェッチされた命令列が，正しい順序でリタイアするためには元の命令順を 表す情報が必要となる．図 4.2 のモデルは，同一ライン内のみの命令順を管理 すればよい，という点で制御が簡単である． 4.3 キャッシュの利用効率 命令の種類の出現パターンには偏りがある．そのため，DIC の 1 ラインを 物理的に固定して扱うと，INT 系のみ埋まっているなどの偏りが生じ，キャッ シュの利用効率は低下してしまう．図 4.2 を見てもわかるように，使っていな いキャッシュ領域が無駄になってしまう． 17 ・ ・ ・ キャッシュラインの作成 i0 i2 i3 i4 i5 i6 i1 i0: r1 = iALU(r14,r2) i1: r12 = iLD(r2) i2: r2 = iALU(r14,r3) i7 i3: r1 = iALU(r4,r10) i4: r4 = iBYTE(r1) i5: r11 = iBYTE(r1) i8 i9 i6: r2 = iALU(r4,r5) i7: r1 = iLD(r64) i8: iBC(r1) 命令 命令 INT MEM 命令 FP i9: r1 = iALU(r4) ・ ・ ・ 図 4.2: DIC の格納法例 この問題は，DIC を非集中化して，3 つのキャッシュ領域を独立に扱うことで 解消できる．すなわち，3.4 節の方法で生成したインデックスとタグを用いて， 3 つのキャッシュに並列に読み書きを行う．それぞれセット・アソシアティブ で構成するなら，置換も独立に行われる．インデックスも，同一のパス情報か ら形成されていれば，まったく同一である必要もなく，それぞれのキャッシュ 容量も同一である必要はなくなる．このようにすれば，論理的には図 4.2 のよ うに，隙間をもった状態でラインを形成したとしても，物理的なキャッシュ上 では詰めた状態でキャッシュされている． 一方で，DIC を完全に独立して扱うと，それぞれにタグが必要となるため， 余分に容量を消費している面もある．集中化して扱えば，例えば，図 4.2 の一 番上のラインに対して，1 つのタグをつければ良かった．しかし独立にすると， それぞれに同一のタグをつけて別の領域に格納することになる． 18 4.3.1 キャッシュのヒット論理 DIC を独立に扱った際に，どのキャッシュから読み出しが成功すれば，キャッ シュ・ヒットとして扱うか制御する必要がある．例えば，書き込みを行うとき は INT と MEM の両方のキャッシュ領域に書き込んだが，読み出しを行うまで に INT のデータはキャッシュから追い出されて存在しておらず，MEM のキャッ シュでしかヒットしないという状態が起こり得る． これに対して，どのキャッシュに命令が格納されているかを，DIC の読み出 し開始前に得られるようにする手法が考えられる．そのために，どのキャッシュ に命令が格納されているかを表すフラグ情報（3 ビット）を保持するテーブル を別に用意する．このテーブルは DIC 本体とは異なり，パスによって区別する 必要はない．DIC 書き込み時にテーブルにフラグの書き込みを行う．DIC から フェッチする際に，このテーブルを引き，得られたフラグ情報が指定するキャッ シュ領域がすべてヒットであればディスパッチを行う． この方法では，フラグ用のテーブルを追加で用意する必要があるが，キャッ シュ・ミスを早く知ることができる．通常の RTC ではタグ比較が完了してか ら，ヒット/ミスの判定が可能となるのに対して，この方法だとテーブルにミ スした時点でキャッシュ・ミスと判断することができる． 4.4 DIC の効果 キャッシュ・ヒット時は，DIC から命令ウィンドウへ，複雑な論理を一切介 さずにディスパッチできる. DIC ミス時のフェッチ幅を 1 にするならば，命令キャッシュにおけるローテー タも不要となる．RTC の目的であるレジスタ・リネーミングの省略も実現で きる．ヒット時にはリネームやディスパッチに充てられていたパイプラインス テージを省略することができる． 但し，RTC と同様にキャッシュミス時の変換幅，ディスパッチ幅が少数であっ ても性能が落ちないようにするためには，十分なキャッシュヒット率が要求さ れる．RTC と同様にパスによって命令列が区別されるため，キャッシュの容量 を多く消費する．DIC の領域を独立に扱った場合は，タグの重複の分更なる容 量が必要となる可能性がある． さらに，図 4.2 のような方法でディスパッチグループを決めてしまうと，高 いキャッシュ・ヒット率が得られても，ディスパッチ幅の小ささから性能が上 がらない場合もある．より最適なキャッシュ・ラインの生成モデルを考察中で ある． 19 第5章 評価 5.1 評価モデル 本研究室で開発したシミュレータ「鬼斬弐」に DIC を実装して評価を行っ た．ベンチマークには，SPECCPU CINT2006 のプログラムに含まれる全 12 本 のベンチマーク・プログラムを用いた．入力セットには train を用い，最初の 1G 命令をスキップし直後の 100M 命令を実行した． 表 5.1 にベース・モデルの主要なパラメータを示す．今回はフェッチ幅 4 の アウト・オブ・オーダ・スーパースカラ・プロセッサをベース・モデルとした． これに対して，4.2 節で示したような，簡単なキャッシュ・ラインの形成モデ ルに基づいた DIC の評価を行った．DIC ヒット時には，リネームと，ディス パッチのステージを省略し，ミス時には 1 命令ずつフロント・エンドを流れる ものとした．ミス時に行う変換，及びディスパッチはそれぞれ 1 サイクルで実 行できるとした． また，3 つのキャッシュ領域は独立に扱い，十分な容量と思われる，8K エ ントリのフラグテーブルを用意した．DIC のフェッチは 4 サイクルとし，この テーブルミス時には，1 サイクルで DIC ミスと判断でき，タグ比較時にミスを 確認した際は 3 サイクル目に DIC ミスと判断できるとした．DIC にミスした 際には，ミスと判断してから，通常の命令キャッシュからのフェッチを開始す るものとした． 5.2 キャッシュ・ミス率と IPC DIC の容量を変化させて，性能の変化を計測した．図 5.1 に DIC のエントリ 数が 2k，4k，8k のときのキャッシュ・ミス率を，図 5.2 に同じくエントリ数が 2k から 8k に変化させたときのベース・モデルに対する相対 IPC を示す．キャッ シュ・ミス率は read を試みた回数に対して，失敗した回数で計測している．こ れらはすべて，8way のセット・アソシアティブで DIC を構成した． 図 5.1 のように，基本的には，容量が増加すればキャッシュ・ミス率が減少し ている．一方で相対 IPC は，図 5.2 のようになっており，平均すると，2k エン 20 表 5.1: ベース・モデルの主要なパラメータ フェッチ幅 4 発行幅 Int 2，FP 2，Mem 2 命令ウィンドウ Int 32 エントリ,FP 16 エントリ, Mem 16 エントリ 32KB, 4 ウェイ, 3 サイクル，64B ライン L1 命令キャッシュ L1 データ・キャッシュ 32KB, 4 ウェイ, 3 サイクル，64B ライン L2 データ・キャッシュ 4MB, 8 ウェイ, 10 サイクル，64B ライン メイン・メモリ 200 サイクル IntALU × 2, IntMUL × 1, Mem × 2, 演算器 FPADD × 1，FPMUL × 1, FPDIV × 1 BTB: 8K エントリ， gshare: 32K エントリ PHT, 分岐予測 10 ビットグローバル分岐履歴 RAS: 8 エントリ Fetch: 3 サイクル, Rename: 2 サイクル， パイプライン構成 Dispatch: 2 サイクル，Issue：2 サイクル トリのとき 0.83 ，4k エントリのときに，0.94 ，8k エントリのときに，0.97 と なっている．これは，先行研究 [1] で得られている結果から予想されるような 性能が出ていない．この原因は RTC を DIC にすることの構造上の問題ではな く，シミュレータへの実装が不完全であるためと考えられる．容量を十分にと れば base に近い性能を得ることも可能であることから，実装を正確に行えば， より少ないキャッシュ容量で，ベース・モデルに近い性能の DIC を実現できる と考えられる． 一方で，高いキャッシュ・ヒット率を実現しながら，性能が低いベンチマー ク・プログラムは，今回実装した 4.2 節のモデルでは，これ以上の性能向上は望 めないことがわかる．より効果的なディスパッチを可能にするような，キャッ シュ・ライン形成モデルが必要となる． 21 60.0% 50.0% 40.0% DICミス率 30.0% 2k 4k 8k 20.0% 10.0% 0.0% 図 5.1: DIC・ミス率 1.4 1.2 1 相対 IPC 0.8 base 2k 0.6 4k 8k 0.4 0.2 0 図 5.2: 相対 IPC 22 第6章 おわりに 本研究はレジスタ・リネーミングとディスパッチ・ネットワークを不要とす るスーパースカラ・プロセッサの実現手段として，DIC を提案した．これらの ロジックを大幅に省略することによって，スーパースカラ・プロセッサの制御 部の回路面積は小さくなり，高い熱密度を緩和することができることが示さ れた． 今回の実装による計測結果ではキャッシュの利用効率が悪く，大きな容量を 必要とした．キャッシュ・インデックスの作成方法や，余分なトレースを減らす ことで改善が望める．今後はより良い実装の実現を目標とする．さらにキャッ シュ・ラインの形成モデルに関しての最適化が課題となる． 23 謝辞 本研究を進めるにあたり，坂井修一教授には，相談会等を通じ，様々な御指 導を頂きました． 五島正裕准教授には，研究テーマの決定から論文の添削まで，本研究に関す る多くの相談に乗って頂き，御指導頂きました． 塩谷亮太氏，伊藤悠二氏，倉田成己氏には，研究内容や論文執筆について 様々な助言を頂きました． 事務補佐員の八木原晴水さん，伊世知代さん，長谷部環さんには，研究を行 う上での事務などでお世話になりました． また，坂井・五島研究室の皆様にも，論文執筆や研究室での生活のサポート などで大変お世話になりました．心より感謝いたします． 24 参考文献 [1] 一林 宏憲, 塩谷 亮太, 入江 英嗣, 五島 正裕, 坂井 修一: 逆 Dualflow アーキ テクチャ, 先進的計算基盤システムシンポジウム SACSIS2008, pp.245-254 [2] 五島正裕: Out-of-order ILP プロセッサにおける命令スケジューリングの 高速化の研究, 京都大学 (博士論文), March, 2004 [3] Rotenberg, Eric and Bennett, Steve and Smith, James E. Trace cache: a low latency approach to high bandwidth instruction fetching Proceedings of the International Symposium on Microarchitecture,pp.24-35 1996 [4] 堀尾一生，塩谷亮太，五島正裕，坂井修一: 面積効率を指向するプロセッ サの設計, 先進的計算基盤システムシンポジウム SACSIS2010, pp.339-346, 25