Microsoft PowerPoint - Lec ppt [互換モード]

(1)

1 計算機アーキテクチャ第二

(O)

アウトオブオーダ実行プロセッサとバックエンド

2012年後学期

アウトオブオーダ実行プロセッサの構成

命令キャッシュ，

分岐予測など

命令

ウィンドウ

・

レジスタ

ファイル

・

スケジューラ

等

命令ウィンドウ

：

命令を格納するバッファ

命令フェッチ，デコード，リネーミング

Instruction

Fetch

Instruction

Decode

Register

Renaming

Dispatch

パイプライン

レジスタ

命令フェッチユニット

OoO実行コア

（データの処理）

ALU0

ALU1

ALU2

フロントエンド

バックエンド

2 アウトオブオーダ実行プロセッサの構成

命令キャッシュ，

分岐予測など

命令

ウィンドウ

・

レジスタ

ファイル

・

スケジューラ

等

Instruction

Fetch

Instruction

Decode

Register

Renaming

Dis

p

atch

パイプライン

レジスタ

命令フェッチユニット

OoO実行コア

（データの処理）

ALU0

ALU1

ALU2

3



ディスパッチ

(dispatch)

: 命令ウィンドウに命令を格納する動作

アウトオブオーダ実行プロセッサの構成

命令キャッシュ，

分岐予測など

命令

ウィンドウ

・

レジスタ

ファイル

・

スケジューラ

等

Instruction

Fetch

Instruction

Decode

Register

Renaming

Issue

パイプライン

レジスタ

命令フェッチユニット

OoO実行コア

（データの処理）

ALU0

ALU1

ALU2

4



発行

(issue, fire)

: 命令ウィンドウから，データ依存が解消された命

令を機能ユニットに送り出す動作

Dispatch

アウトオブオーダ実行プロセッサの命令パイプライン

Instruction

Fetch

Decode

Rename

Dispatch

Issue

Register

_Read

Execute

Commit

The Alpha 21264 Microprocessor Architecture

R. E. Kessler, E. J. McLellan, and D. A. Webb, Compaq Computer Corporation

5 命令発行機構：

Tomasuloのアプローチ

1967



IBM 360/91 の

浮動小数点ユニット

では、アウトオブオー

ダ実行のための洗練された方式が採用されていた．



Robert Tomasulo によって発明されたこの手法では



(1) レジスタリネーミングを導入してWAWハザードとWAR

ハザード（偽のデータ依存）を排除



(2) 命令が必要とするオペランドがいつ利用できるかを探

知し，RAWハザードを最少化



近年のプロセッサでは，この手法のさまざまなバリエー

ションが採用されているが，これら２つの重要な概念は共

通の特徴

6

(2)

命令発行機構：

Tomasuloのアプローチ



IBM 360/91 の浮動小数点ユニットでは、アウトオブオー

ダ実行を行う洗練された方式が採用されていた。



Robert Tomasulo によって発明されたこの手法では



命令が必要とするオペランドがいつ利用できるかを探知し、

RAWハザードを最少化



レジスタリネーミングを導入してWAWハザードとWARハ

ザードを回避



近年のプロセッサでは、この手法のさまざまなバリエー

ションが採用されているが、これら２つの重要な概念は共

通の特徴

7 Tomasuloのアプローチ

DIV.D

F0

,F2,F4

ADD.D

F6

,F0,

F8

S.D

F6,0(R1)

SUB.D

F8

,F10,F14

MUL.D

F6

,F10,F8



（1）レジスタリネーミングを導入してWAWハザードと

WARハザードを回避



S

と

T

という

2つの一時レジスタが利用できると仮定

DIV.D F0,F2,F4

ADD.D

S

,F0,F8

S.D

S

,0(R1)

SUB.D

T

,F10,F14

MUL.D F6,F10,

T

8 真のデータ依存

(true data dependence)

R3 := R3 x R5 (1)

R4 := R3 + 1 (2)

R3 := R5 + 1 (3)

R7 := R3 x R4 (4)

If R3=20, R5=3

60 := 20 x 3 (1)

61 := 60 + 1 (2)

4 := 3 + 1 (3)

244:=

60 x 61 (4)

3番目の命令が完了する前に，4番目の命令を実行してはいけない．

RAW (read after write)

9 出力依存

(output dependence)

R3 := R3 x R5 (1)

R4 := R3 + 1 (2)

R3 := R5 + 1 (3)

R7 := R3 x R4 (4)

If R3=20, R5=3

60 := 20 x 3 (1)

61 := 60 + 1 (2)

4 := 3 + 1 (3)

XXX:=

60 x 61 (4)

１番目の命令の代入が３番目の命令の代入より後に完了してはいけない．

WAW (write after write)

10 逆依存

(antidependence)

R3 := R3 x R5 (1)

R4 := R3 + 1 (2)

R3 := R5 + 1 (3)

R7 := R3 x R4 (4)

If R3=20, R5=3

60 := 20 x 3 (1)

XX :=

4 + 1 (2)

4 := 3 + 1 (3)

XXX:= 4 x XX (4)

スキャネットシート

氏名，学籍番号，

学籍番号マーク欄(右詰で)

年月日

Arch II

(3)

13 Tomasuloのアプローチ

DIV.D

F0

,F2,F4

ADD.D

F6

,F0,

F8

S.D

F6,0(R1)

SUB.D

F8

,F10,F14

MUL.D

F6

,F10,F8



（1）レジスタリネーミングを導入してWAWハザードと

WARハザードを回避



S

と

T

という

2つの一時レジスタが利用できると仮定

DIV.D F0,F2,F4

ADD.D

S

,F0,F8

S.D

S

,0(R1)

SUB.D

T

,F10,F14

MUL.D F6,F10,

T

14 Tomasuloのアプローチ

15 Tomasuloのアプローチ



それぞれの演算器（FP加算器，FP乗算器など）は，そこで実行される命

令のみを蓄える，分散化された命令ウィンドウを持つ．

これを

リザベーションステーション

と呼ぶ．



リザベーションステーションに，オペランドの値を格納することで，レジスタ

ファイルを経由しないオペランドの受け渡しを実現．



保留中の命令は，その入力を提供するリザベーションステーションの情報

を持つ．



命令が

ディスパッチ（リザベーションステーションに格納）

される時，保留中

のオペランド用のレジスタ指示子をリザベーションステーションの名前にリ

ネームする．



複数の同じレジスタへの書き込みが生じる場合には最後のデータのみをレ

ジスタに書き込む．

16 Tomasuloのアプローチ



集中化された構成ではなく、リザベーションステーションを使用することに

よる2つの重要な利点



（１）ハザード検出および実行制御の分散化



各機能ユニットはリザベーションステーションに保持された情報によって，その

ユニットでいつ命令が実行を始めるかを決める．



（２）実行結果がレジスタを経由するオーバヘッドを隠蔽



実行結果（オペランド）が格納されているリザベーションステーションから機能

ユニットにオペランドが直接渡され，レジスタを経由する必要がない．



実行結果は，共通の結果バスでバイパスされ，オペランドを待つ全てのリザ

ベーションステーションが同時に値を取得する．



このバスは，IBM 360/91 で

共通データバス（CDB： common data bus）

と呼

ばれる．



複数の実行ユニットを備えたパイプラインでは2つ以上のバスが必要

17 Tomasuloのアプローチ



ロードバッファの3つの機能



計算されるまでの間，実効アドレスの要素を保持



メモリからデータが到着するのを待っている処理中のロード命令を探知



完了してCDBの利用を待っているロードの結果を保持



ストアバッファの3つの機能



計算されるまでの間，実効アドレスの要素を保持



データ値がストアされるのを待っている処理中のストア命令の書き込み

先メモリアドレスを保持



メモリユニットが利用可能になるまで格納するアドレスおよび値を保持



浮動小数点機能ユニットとロードユニットの結果はすべてCDBを経

由して，レジスタファイル，リザベーションステーション，ストアバッ

ファに送られる．

18

(4)

Tomasuloのアプローチ

19 Tomasuloのアプローチ



1. リザベーションステーションへの命令格納



命令キュー（正確なデータフローを保証するためにFIFO で命令を格納

している）のヘッド（先頭）から命令を取り出す．

適切な(当該命令を処理する演算器の）リザベーションステーションに

空きがある場合は，そこに命令を送る．



レジスタファイルがオペランド値を持つ場合，その値も同時にリザベー

ションステーションに送られる．

空のリザベーションステーションがない場合，構造ハザードとなり，リザ

ベーションステーションやバッファが解放されるまでストール．



オペランド値がレジスタファイルにない場合（その値はまだ生成されて

いない），オペランド値を生成する命令が格納されているリザベーション

ステーションを検出する．

このステップがレジスタリネーミングに対応し，WARとWAWハザードを

除去する。

20 Tomasuloのアプローチ



2. 命令実行の開始と実行（execute）



1つ以上のオペランドがまだ利用できない場合は，値が送られてくるのを待ちながら

共通データバスを監視する．

オペランドが利用可能になった時に，それを待つリザベーションステーションに格納

する．すべてのオペランドが利用可能になった時に，そのオペレーションは対応する

機能ユニットで実行できる．



すなわち，オペランドが利用可能になるまで命令の実行を遅らせることによって，

RAWハザードを回避する．



同じ機能ユニットを利用する複数の命令が同一のクロックサイクルにおいて実行可

能になるかもしれない点に注意する．同じクロックサイクルにおいて，個々の機能ユ

ニットは異なる命令の実行を開始することができるが，1つの機能ユニットに対して2

つ以上の命令が実行可能であれば，ユニットはそれらの中から1つを選択する．



整数演算，浮動小数点演算のリザベーションステーションについては，この選択は任意の

方式で行うことができる．ロードとストアの場合には制約を考慮する必要がある．

21 Tomasuloのアプローチ



2. 実行（execute）の続き



ロードとストアは2 段階の実行過程を必要とする．第1 段階では，ベースレジ

スタが利用可能な場合に実効アドレスを計算する．また，得られた実効アドレ

スをロード・ストアバッファに格納する．

第2 段階では，メモリユニットが利用可能になるとすぐに，ロードバッファの

ロード命令を実行する．



ストアバッファのストア命令は，メモリユニットに送られる前に，ストアすべき値

を待たなければならない．ロードとストアは実効アドレス計算を通じてプログラ

ム順序を維持する．それによって、メモリを経由するハザードに対処できる．



例外の振る舞いを維持するために，命令は，プログラム順序において先行す

る分岐がすべて完了するまで実行を始めてはいけない．この制約により、実行

中に例外を引き起こす命令が実際に実行を完了するということが保証される．



分岐予測を利用するプロセッサ（動的スケジューリングのすべてのプロセッサがそう

であるが）では，分岐に続く命令の実行を始める前に，分岐予測が正しいことをプロ

セッサが知らなければならないことを意味する．

22 Tomasuloのアプローチ



3. 結果書き込み（Write Result）



結果が利用可能になったら，CDBに結果を流し，そこからレジス

タ、およびこの結果を待っているすべてのリザベーションステー

ション（ストアバッファを含む）に書き込む．



ストアされる値およびストアするメモリのアドレスの両方が利用可

能になるまで，ストア命令はストアバッファの中に保存され，メモ

リユニットが利用可能になるとすぐに結果が格納される．

Tomasuloのアプローチ



リザベーションステーションが保有する

7つのフィールド



Op

：ソースオペランドS1 およびS2 に対して行うオペレーション



Qj、Qk

：対応するソースオペランド値を生成するリザベーションス

テーションの番号．値が0 の場合は，ソースオペランドがVj また

はVkとしてすでに利用可能であるか，不必要であることを示す．



Vj、Vk

：ソースオペランドの値．各オペランドについては，Vフィー

ルドあるいはQフィールドのどちらかが常に有効となる．ロード命

令については，Vkフィールドはオフセットフィールドを保持するた

めに利用される．



A

：ロードあるいはストア命令がメモリアドレス計算の情報を保持

するために利用する．最初に，命令の即値のフィールドがここに

格納される．アドレス計算の後には，実効アドレスが格納される．



Busy

：当該リザベーションステーション，および，対応する機能

(5)

Tomasuloのアプローチ



レジスタファイルの各エントリにはQi フィールドを追加



Qi

：このレジスタへ実行結果を格納する操作を含んでいるリザ

ベーションステーションの番号．

Qi の値がブランク（すなわち0）の場合は，現在，このレジスタに

格納すべき結果を計算する命令が実行中でない．このため，この

レジスタに格納されている内容がその値となる．

25 Tomasuloのアプローチ

26 動的スケジューリングの例題



最初のロードだけが完了してその結果が書き戻されている時，次の

命令列に対するスケジューリングの状態はどのようになっているか？

1. L.D

F6,32(R2)

2. L.D

F2,44(R3)

3. MUL.D

F0,F2,F4

4. SUB.D

F8,F2,F6

5. DIV.D

F10,F0,F6

6. ADD.D

F6,F8,F2

27

44 Mem[32 + Regs[R2]] Mem[32 + Regs[R2]]

28

1

2

3

4

5

6

1

2

4

6

3

5

dispatch

動的スケジューリングの例題



例題2.5 と同じコードセグメントを利用して，MUL.D がその結果を

書く準備ができている場合，状態テーブルがどのようになっている

Microsoft PowerPoint - Lec ppt [互換モード]

1

計算機アーキテクチャ 第二

(O)

アウトオブオーダ実行プロセッサとバックエンド

2012年 後学期

アウトオブオーダ実行プロセッサの構成

命令キャッシュ，

分岐予測など

命令

ウィンドウ

・

レジスタ

ファイル

・

スケジューラ

等

命令ウィンドウ

：

命令を格納するバッファ

命令フェッチ，デコード，リネーミング

Instruction

Fetch

Instruction

Decode

Register

Renaming

Dispatch

パイプライン

レジスタ

命令フェッチユニット

OoO実行コア

（データの処理）

ALU0

ALU1

ALU2

フロントエンド

バックエンド

2

アウトオブオーダ実行プロセッサの構成

命令キャッシュ，

分岐予測など

命令

ウィンドウ

・

レジスタ

ファイル

・

スケジューラ

等

Instruction

Fetch

Instruction

Decode

Register

Renaming

Dis

p

atch

パイプライン

レジスタ

命令フェッチユニット

OoO実行コア

（データの処理）

ALU0

ALU1

ALU2

3

ディスパッチ

(dispatch)

: 命令ウィンドウに命令を格納する動作

アウトオブオーダ実行プロセッサの構成

命令キャッシュ，

分岐予測など

命令

ウィンドウ

・

レジスタ

ファイル

・

計算機アーキテクチャ第二

2012年後学期

_Read