・ディジタル回路とクロック ・プロセッサアーキテクチャ ・例外処理 ・パイプライン ・ハザード

Presentation on theme: "・ディジタル回路とクロック ・プロセッサアーキテクチャ ・例外処理 ・パイプライン ・ハザード"— Presentation transcript:

1 ・ディジタル回路とクロック ・プロセッサアーキテクチャ ・例外処理 ・パイプライン ・ハザード
情報システム基盤学基礎１ 勉強会その４ 2016/05/25 ・ディジタル回路とクロック ・プロセッサアーキテクチャ ・例外処理 ・パイプライン ・ハザード

2 情報システム基盤学基礎１ プロセッサの概念的な 構造と動作（復習）

3 コンピュータの概念的な構造 プロセッサ メモリ プログラムカウンタ（PC） レジスタファイル 演算器 命令やデータを格納する領域
情報システム基盤学基礎１ コンピュータの概念的な構造 プロセッサ プログラムカウンタ（PC） 実行中の命令のアドレスを格納する小さなメモリ レジスタファイル レジスタ（小容量のメモリ）の集合 演算に必要なデータを格納 演算器 演算を行うハードウェア （例： ALU，浮動小数点演算器） メモリ 命令やデータを格納する領域 命令用とデータ用で分かれていてもよい メモリ プロセッサ 命令１ PC 命令２ 命令３ レジスタ ファイル データ１ データ２ データ３ 演算器 [ コンピュータの概念的な構成 ]

4 コンピュータの動作例 アドレス メモリ プロセッサ $s2 = M [1024 + 4] $s1 = M [1024 + 0] 4
情報システム基盤学基礎１ コンピュータの動作例 アドレス メモリ プロセッサ $s2 = M [ ] $s1 = M [ ] lw $s1, 0($t0) lw $s1, 0($t0) 実行中 の命令 PC 4 4 lw $s2, 4($t0) lw $s2, 4($t0) 8 lw $s3, 8($t0) lw $s3, 8($t0) レジスタファイル 12 lw $s4, 16($t0) lw $s4, 16($t0) 16 add $t1, $s1, $s2 add $t1, $s1, $s2 20 add $t2, $s3, $s4 add $t2, $s3, $s4 8 ($t0) 1024 24 sub $s0, $t1, $t2 sub $s0, $t1, $t2 9 ($t1) 28 sw $s0, 16($t0) sw $s0, 20($t0) 10 ($t2) 16 ($s0) 17 ($s1) 1024 100 100 ALU 18 ($s2) 1028 10 10 19 ($s3) 1032 42 42 20 ($s4) 1036 3 3 1040

5 コンピュータの動作例 アドレス メモリ プロセッサ $t1 = $s1 + $s2 $t2 = $s3 + $s4 20 16 12 100
情報システム基盤学基礎１ コンピュータの動作例 アドレス メモリ プロセッサ $t1 = $s1 + $s2 $t2 = $s3 + $s4 lw $s1, 0($t0) lw $s1, 0($t0) 実行中 の命令 PC 20 16 12 lw $s4, 16($t0) 4 lw $s2, 4($t0) lw $s2, 4($t0) 8 lw $s3, 8($t0) lw $s3, 8($t0) レジスタファイル 12 lw $s4, 16($t0) lw $s4, 16($t0) 16 add $t1, $s1, $s2 add $t1, $s1, $s2 20 add $t2, $s3, $s4 add $t2, $s3, $s4 8 ($t0) 1024 24 sub $s0, $t1, $t2 sub $s0, $t1, $t2 9 ($t1) 28 sw $s0, 16($t0) sw $s0, 20($t0) 10 ($t2) 16 ($s0) 17 ($s1) 100 100 1024 100 100 ALU 18 ($s2) 10 10 1028 10 10 19 ($s3) 42 42 1032 42 42 20 ($s4) 3 3 1036 3 3 110 45 1040

6 コンピュータの動作例 アドレス メモリ プロセッサ $s0 = $t1 - $t2 20 24 110 110 45 45 100 100
情報システム基盤学基礎１ コンピュータの動作例 アドレス メモリ プロセッサ $s0 = $t1 - $t2 lw $s1, 0($t0) lw $s1, 0($t0) 実行中 の命令 PC 20 24 add $t2, $s3, $s4 4 lw $s2, 4($t0) lw $s2, 4($t0) 8 lw $s3, 8($t0) lw $s3, 8($t0) レジスタファイル 12 lw $s4, 16($t0) lw $s4, 16($t0) 16 add $t1, $s1, $s2 add $t1, $s1, $s2 20 add $t2, $s3, $s4 add $t2, $s3, $s4 8 ($t0) 1024 24 sub $s0, $t1, $t2 sub $s0, $t1, $t2 9 ($t1) 110 110 28 sw $s0, 20($t0) sw $s0, 16($t0) 10 ($t2) 45 45 16 ($s0) 17 ($s1) 100 100 1024 100 100 ALU 18 ($s2) 10 10 1028 10 10 19 ($s3) 42 42 1032 42 42 20 ($s4) 3 3 1036 3 3 65 1040

7 コンピュータの動作例 アドレス メモリ プロセッサ M[1024+16] = $s0 24 28 110 110 45 45 65 65
情報システム基盤学基礎１ コンピュータの動作例 アドレス メモリ プロセッサ M[ ] = $s0 lw $s1, 0($t0) lw $s1, 0($t0) 実行中 の命令 PC 24 28 sub $s0, $t1, $t2 4 lw $s2, 4($t0) lw $s2, 4($t0) 8 lw $s3, 8($t0) lw $s3, 8($t0) レジスタファイル 12 lw $s4, 16($t0) lw $s4, 16($t0) 16 add $t1, $s1, $s2 add $t1, $s1, $s2 20 add $t2, $s3, $s4 add $t2, $s3, $s4 8 ($t0) 1024 24 sub $s0, $t1, $t2 sub $s0, $t1, $t2 9 ($t1) 110 110 28 sw $s0, 16($t0) sw $s0, 16($t0) 10 ($t2) 45 45 16 ($s0) 65 65 17 ($s1) 100 100 1024 100 100 ALU 18 ($s2) 10 10 1028 10 10 19 ($s3) 42 42 1032 42 42 20 ($s4) 3 3 1036 3 3 1040

8 情報システム基盤学基礎１ ディジタル回路とクロック

9 ディジタル回路の種類 組み合わせ回路 順序回路 状態を持たない回路 入力から出力が一意に決まる 例）加算器 状態を有する回路
00111 と を入力すると出力は常に 01101 順序回路 状態を有する回路 出力は入力と記憶素子の保持内容 によって決まる 記憶素子： レジスタ，ラッチなど 例）プロセッサ 入力「add $t1, $s1, $s2」の出力はレジスタ $s1, $s2 が記憶している内容によって異なる 組み合わせ回路 入力 出力 記憶素子 入力 組み合わせ回路 出力

10 クロック信号 記憶素子に対して入力を記憶するタイミングを指示する信号 L（Low）と H（High）を繰り返す周期信号
情報システム基盤学基礎１ クロック信号 記憶素子に対して入力を記憶するタイミングを指示する信号 L（Low）と H（High）を繰り返す周期信号 各記憶素子は信号の立ち上がり（PE: Positive Edge）または立ち下がり（NE: Negative Edge）において入力を記憶 time クロック 信号 H L H 記憶素子 の入力 L H PE型の 出力 L H NE型の 出力 L

11 クロック周波数と回路遅延 クロック周波数 回路遅延 クロック信号の周波数（単位は Hz） 1 / クロックサイクル
情報システム基盤学基礎１ クロック周波数と回路遅延 クロック周波数 クロック信号の周波数（単位は Hz） 1 / クロックサイクル 回路遅延 組み合わせ回路部分の最長パスの遅延 回路に入力できる最大のクロック周波数を決定 「回路遅延 ＜ クロックサイクル」でないと回路が正常動作しない クロックサイクル1 クロックサイクルN 1秒間 [ N Hz のクロック信号 ] 回路遅延 回路 A time x clk c X y y z s z c clk s

12 情報システム基盤学基礎１ プロセッサの 単純な実装方式

13 情報システム基盤学基礎１ 実装の説明に入る前に 参考書ではボトムアップに説明 この講義ではトップダウンに説明 （その方がわかりやすいため）

14 プロセッサ全体の構成 4 PC 加算 加算 制御 ALU 命令フェッチ 命令メモリ データメモリ 実行 メモリアクセス 符号 拡張
情報システム基盤学基礎１ プロセッサ全体の構成 命令フェッチ 実行 加算 加算 4 2ビット 左シフト 命令デコード＆ レジスタ読み出し Branch MemtoReg 制御 MemRead MemWrite ALUSrc ALUOp RegWrite レジスタファイル RegDst レジスタ書き込み Read Reg 1 Read データ1 Zero PC Read アドレス メモリアクセス Read Reg 2 ALU Read データ2 アドレス Read データ Read データ Write Reg Write データ Write データ 命令メモリ データメモリ 符号 拡張 ALU 制御

15 命令フェッチ 命令の読み出し PC の更新 PC を使用して（命令）メモリにアクセス 読み出した命令を後続の回路に送る
情報システム基盤学基礎１ 命令フェッチ 命令の読み出し PC を使用して（命令）メモリにアクセス 読み出した命令を後続の回路に送る PC の更新 次の命令フェッチのために PC に 4 を加算 命令は 4B おきに配置されていることに注意 分岐命令の結果によっては上書きが発生 加算 PC+4 4 32 32 PC Read アドレス 32 32 Read データ 命令 32 命令メモリ

16 命令デコードとレジスタ読み出し 命令デコード レジスタ読み出し 符号拡張 命令形式に応じて命令をフィールドに分解
情報システム基盤学基礎１ 命令デコードとレジスタ読み出し 命令デコード 命令形式に応じて命令をフィールドに分解 各フィールドの信号を適切な回路に送る オペコードを解析し，制御信号を生成 レジスタ読み出し 読み出しに用いる信号（レジスタ番号を表す信号）は命令から該当するフィールドを抽出することにより生成 同時に 2 つまでのレジスタアクセスが可能 2 つのレジスタを参照して行う演算があるため 符号拡張 I 形式の命令用 16 ビットの即値フィールドを 32 ビットに変換 命令 [31-26] （全形式） Branch MemtoReg MemWrite 制御 MemRead 6 ALUOp 命令 [25-21]（R/I 形式） ALUSrc RegWrite レジスタファイル 命令 [20-16]（R/I 形式） レジスタ値1 RegDst Read Reg 1 Read データ1 5 32 Read Reg 2 Read データ2 命令 [31-0] 5 32 レジスタ値2 Write Reg 32 Write データ 命令 [15-11] （R形式） 符号 拡張 16 命令 [15-0] 32 （I 形式）

17 実行 演算の実行 次の PC の計算 レジスタ値または符号拡張された値を入力として ALU が演算を実行
情報システム基盤学基礎１ 実行 演算の実行 レジスタ値または符号拡張された値を入力として ALU が演算を実行 算術/論理演算だけでなくメモリアクセス命令のアドレス計算にもこの ALU を使用 演算に用いる値をマルチプレクサにより制御 命令デコードの結果および命令の下位ビット（機能コード）に応じて ALU を制御 次の PC の計算 PC＋４ に符号拡張された値を加算 （分岐命令用） 命令デコードの結果と ALU によるレジスタ比較の結果に応じて次の PC を決定 Next PC PC＋４ 32 加算 32 2ビット 左シフト Branch ALUSrc レジスタ値1 Zero 32 ALU 演算結果 32 32 レジスタ値2 ALUOp マルチ プレクサ 符号拡張 ALU 制御 32 命令 [5-0] （=機能コード）

18 メモリアクセス データの読み出し データの書き込み 読み書きの制御 演算結果（アドレス計算の結果）を入力として（データ）メモリにアクセス
情報システム基盤学基礎１ メモリアクセス データの読み出し 演算結果（アドレス計算の結果）を入力として（データ）メモリにアクセス 読み出したデータを後続の回路へ転送 データの書き込み レジスタファイルから読み出したレジスタ２の値を書き込み 読み書きの制御 命令デコード時に２つの制御信号（MemRead, MemWrite）を生成 制御信号が H の時，対応する操作をメモリに対して行う MemRead MemWrite メモリ データ 演算結果 アドレス Read データ 32 32 Write データ レジスタ値2 32 データメモリ

19 レジスタ書き込み レジスタ書き込み 演算結果または（データ）メモリから 読み出した値を書き込み マルチプレクサにより書き込む値を制御
情報システム基盤学基礎１ レジスタ書き込み レジスタ書き込み 演算結果または（データ）メモリから 読み出した値を書き込み マルチプレクサにより書き込む値を制御 マルチプレクサを制御するための信号は命令デコード時に生成 書き込みを行うレジスタの番号も命令 デコード時に生成 命令 [31-26] （全形式） Branch MemtoReg MemWrite 制御 MemRead 5 ALUOp 命令 [25-21]（R/I 形式） ALUSrc RegWrite レジスタファイル 命令 [20-16]（R/I 形式） レジスタ値1 RegDst Read Reg 1 Read データ1 5 32 Read Reg 2 Read データ2 命令 [31-0] 5 32 レジスタ値2 Write Reg 32 Write データ 命令 [15-11] （R形式） 32 符号 拡張 16 命令 [15-0] 32 （I 形式） 32 32 メモリ データ 演算 結果

20 動作例（加算命令） 4 4 20 PC 16 ALU 制御 加算 加算 加算 制御 ALU ALU 制御 命令メモリ 命令メモリ
情報システム基盤学基礎１ 動作例（加算命令） MemtoReg ALU ALU 制御 ALUOp 制御 レジスタファイル RegDst RegWrite ALUSrc 4 加算 命令メモリ 加算 加算 4 2ビット 左シフト Branch MemtoReg “ALU” 制御 MemRead MemWrite ALUSrc ALUOp RegWrite レジスタファイル RegDst Read Reg 1 Read データ1 100 10 17 18 9 “17(s1)” Zero 20 PC 16 Read アドレス “18(s2)” Read Reg 2 ALU Read データ2 アドレス Read データ “110” add $t1, $s1, $s2 Read データ 16 Write Reg “9(t1)” Write データ Write データ 110 命令メモリ “110” データメモリ “add” 符号 拡張 ALU 制御

21 動作例（ロード命令） 4 4 ４ ８ PC ALU 制御 加算 加算 加算 制御 ALU ALU 制御 符号 拡張 命令メモリ データメモリ
情報システム基盤学基礎１ 動作例（ロード命令） MemtoReg ALU ALU 制御 ALUOp 制御 レジスタファイル RegDst RegWrite ALUSrc “4” “18(s2)” “8(t0)” “lw” 符号 拡張 4 加算 命令メモリ 加算 加算 4 2ビット 左シフト Branch MemtoReg MemRead データメモリ 制御 MemRead MemWrite ALUSrc ALUOp RegWrite レジスタファイル RegDst Read Reg 1 Read データ1 1024 8 18 Zero ４ ８ PC Read アドレス Read Reg 2 ALU Read データ2 アドレス 10 Read データ “1028” 4 lw $s2, 4($t0) Read データ Write Reg Write データ Write データ 10 命令メモリ “10” データメモリ 符号 拡張 ALU 制御

22 動作例（ストア命令） 4 4 28 PC 32 ALU 制御 加算 加算 加算 制御 ALU ALU 制御 符号 拡張 命令メモリ
情報システム基盤学基礎１ 動作例（ストア命令） ALU ALU 制御 ALUOp 制御 レジスタファイル RegWrite ALUSrc “16” “16(s0)” “8(t0)” “sw” 符号 拡張 4 加算 命令メモリ 加算 加算 4 2ビット 左シフト Branch MemtoReg 制御 MemWrite データメモリ MemRead MemWrite ALUSrc ALUOp RegWrite レジスタファイル RegDst Read Reg 1 Read データ1 1024 65 8 16 Zero 28 PC 32 Read アドレス Read Reg 2 ALU Read データ2 アドレス Read データ “1040” Read データ 28 sw $s0, 16($t0) Write Reg Write データ Write データ 65 命令メモリ データメモリ 符号 拡張 ALU 制御

23 動作例（条件分岐命令） 4 4 132 PC 48 ALU 加算 制御 加算 加算 加算 制御 ALU ALU 制御 符号 拡張 命令メモリ
情報システム基盤学基礎１ 動作例（条件分岐命令） ALU ALU 制御 ALUOp 加算 2ビット 左シフト Zero “80” “true” “52” “132” 制御 レジスタファイル RegWrite ALUSrc “20” “20(s4)” “19(s3)” “beq” 符号 拡張 Branch 4 加算 命令メモリ 加算 加算 4 2ビット 左シフト Branch MemtoReg 制御 MemRead MemWrite ALUSrc ALUOp RegWrite レジスタファイル RegDst Read Reg 1 Read データ1 5 19 20 Zero 132 PC 48 Read アドレス Read Reg 2 ALU Read データ2 アドレス Read データ Read データ 48 beq $s3, $s4, 20 Write Reg Write データ Write データ 命令メモリ データメモリ 符号 拡張 ALU 制御

24 単純な実装方式のクロックサイクル 単純な実装方式は回路遅延が大きい 長いクロックサイクルが必要
情報システム基盤学基礎１ 単純な実装方式のクロックサイクル 単純な実装方式は回路遅延が大きい 最長パスは，命令フェッチ ⇒ 命令デコード ⇒ 実行 ⇒ メモリアクセス ⇒ レジスタ書き込み （ロード命令実行時） 上記のパスの遅延 ＝ 単純な実装方式の遅延 長いクロックサイクルが必要 PC ALU 加算 制御 符号 拡張 ALU 制御 Read アドレス Read データ アドレス Write データ Read データ1 Read データ2 Read Reg 1 Read Reg 2 Write Reg Branch Zero ４ [ 単純な実装方式の最長パス ]

25 情報システム基盤学基礎１ 例外処理

26 例外と割込み 例外 割込み プログラムの実行を妨げる予定外の事象
情報システム基盤学基礎１ 例外と割込み 例外 プログラムの実行を妨げる予定外の事象 例： 算術演算におけるオーバーフローの発生，ゼロ除算の実行， 　　 未定義命令の実行，入出力装置からのリクエストなど 実行をただちに中断し，OS が用意している例外処理用のルーチン （割込みハンドラ）の実行を開始 その後の振る舞いは発生した例外の種類や OS に依存 プログラムの実行を再開 or 実行を完全に停止してエラーを通知 割込み プロセッサの外部から発生した例外 例： 入出力装置からのリクエスト 実際には例外と同じ意味で使われることが多い

27 プロセッサ側の処理 （例外発生～割込みハンドラの呼び出し）
情報システム基盤学基礎１ プロセッサ側の処理 （例外発生～割込みハンドラの呼び出し） 手順 例外の発生を検出 例外を起こした命令のアドレスを例外プログラムカウンタ（EPC）に記録 例外処理を行った後でプログラムの実行を再開するため 発生した例外の種類を OS に通知した上で，PC を割込みハンドラの先頭アドレスに変更 ③ 割込みハンドラ 　　の実行を開始 0x メモリ プロセッサ 命令１ PC 0x 命令２ 0x ② PC 退避 EPC 命令３ レジスタ ファイル データ１ 例外発生 ① 例外検出 データ２ データ３ 演算器

28 例外の種類の通知方法 状態レジスタを使用する方法 ベクタ割込みを使用する方法 プロセッサが発生した例外の種類を状態 レジスタに記録
情報システム基盤学基礎１ 例外の種類の通知方法 メモリ プロセッサ 命令１ PC 0x 命令２ 未定義 命令 1 オーバー フロー EPC 命令３ 状態レジスタを使用する方法 プロセッサが発生した例外の種類を状態 レジスタに記録 OS は状態レジスタを参照することにより，発生した例外の種類を把握 ベクタ割込みを使用する方法 発生した例外の種類に応じて，呼び出す割込みハンドラを変更 例： 未定義命令 ⇒ 0x 　　 算術オーバーフロー ⇒ 0x OS は呼び出された割込みハンドラの種類によって例外の種類を認識 状態レジスタ レジスタ ファイル データ１ データ２ データ３ 演算器 [ 状態レジスタを使用する方法 ] 0x 未定義 命令 オーバー フロー 0x メモリ プロセッサ 命令１ PC 0x 命令２ EPC 命令３ レジスタ ファイル データ１ データ２ データ３ 演算器 [ ベクタ割込みを使用する方法 ]

29 OS 側の処理 割込みハンドラの実行を開始 割込みハンドラの終了 例外の種類を解析して各例外に対応するルーチンを選択
情報システム基盤学基礎１ OS 側の処理 割込みハンドラの実行を開始 例外の種類を解析して各例外に対応するルーチンを選択 各例外に対応するルーチンを実行するために，例外を起こしたプロセスの実行状態（レジスタやスタックの内容など）をメモリへ退避 各例外に対応するルーチンの実行を開始 割込みハンドラの終了 プロセスの実行を中断する場合 プロセスの実行を中断し，ユーザにエラーを通知 プロセスの実行を継続する場合 メモリに退避したプロセスの実行状態を復帰 例外プログラムカウンタの値にジャンプする命令を実行

30 単純な実装方式＋例外処理機構 0x80000180 4 EPC 4 PC 加算 ALU 制御 ALU 状態レジスタ 命令メモリ データメモリ
情報システム基盤学基礎１ 単純な実装方式＋例外処理機構 0x 4 加算 ALU EPC 4 2ビット 左シフト 制御 状態レジスタ Branch MemtoReg 制御 MemRead MemWrite ALUSrc ALUOp RegWrite レジスタファイル Overflow RegDst Read Reg 1 Read データ1 Zero PC Read アドレス Read Reg 2 ALU Read データ2 アドレス Read データ Read データ Write Reg Write データ Write データ 命令メモリ データメモリ 符号 拡張 ALU 制御

31 情報システム基盤学基礎１ パイプライン処理

32 単純な実装方式における処理の流れ 命令を逐次的に処理 まず命令1のフェッチ，デコード，…，レジスタ書き込みを順に実行
情報システム基盤学基礎１ 単純な実装方式における処理の流れ 命令を逐次的に処理 まず命令1のフェッチ，デコード，…，レジスタ書き込みを順に実行 命令1のすべての処理が完了したら命令2の処理を開始 clk time 命令1 IF ID EX MEM WB 命令2 IF ID EX MEM WB 命令3 IF ID EX MEM WB IF： ID： EX： MEM： WB： 命令フェッチ 命令デコード＆レジスタ読み出し 実行 メモリアクセス レジスタ書き込み

33 レストランに置き換えてみると… 単純な実装方式における処理 処理効率を上げるには？ オーダーから会計まで1人でこなす 非常に効率が悪い
情報システム基盤学基礎１ レストランに置き換えてみると… 単純な実装方式における処理 オーダーから会計まで1人でこなす 非常に効率が悪い 処理効率を上げるには？ 人を雇って作業分担 流れ作業（オーダー担当，調理担当，給仕担当，会計担当など） レストランA レストランB

34 流れ作業が上手くいくためには… 全員の処理速度を等しくする 1人でも遅い人がいると全体の足を引っ張ってしまうため 全員が常に仕事をしている
情報システム基盤学基礎１ 流れ作業が上手くいくためには… 全員の処理速度を等しくする 1人でも遅い人がいると全体の足を引っ張ってしまうため 全員が常に仕事をしている 次々に仕事が溜まっていく [ 遅い人に配慮せずに仕事を進めた場合 ] 暇な人が生まれる [ 全員が同じ速さで仕事する場合 ] [ 遅い人に合わせて仕事を進めた場合 ]

35 パイプライン処理 処理を複数のパイプラインステージに分割 流れ作業によってプログラムを実行 機能的に分割しやすい部分で分割
情報システム基盤学基礎１ パイプライン処理 処理を複数のパイプラインステージに分割 機能的に分割しやすい部分で分割 各ステージの回路遅延がなるべく等しくなるように分割 例： IF, ID, EX, MEM, WD の 5 つのステージに分割 流れ作業によってプログラムを実行 clk time 命令1 IF ID EX MEM WB IF： ID： EX： MEM： WB： 命令フェッチ 命令デコード＆レジスタ読み出し 実行 メモリアクセス レジスタ書き込み 命令2 IF ID EX MEM WB 命令3 IF ID EX MEM WB 命令4 IF ID EX MEM WB 命令5 IF ID EX MEM WB

36 非パイプライン vs パイプライン 非パイプライン処理 パイプライン処理 実行時間 ＝ n × s 約1/s
情報システム基盤学基礎１ 非パイプライン vs パイプライン 非パイプライン処理 パイプライン処理 time 命令1 IF ID EX MEM WB 実行時間 ＝ n × s 命令2 IF ID EX MEM WB 命令3 IF ID EX MEM WB 約1/s time 命令1 IF ID EX MEM WB 実行時間 ＝ n + s - 1 命令2 IF ID EX MEM WB 命令3 IF ID EX MEM WB n： s： 命令数 ステージ数 命令4 IF ID EX MEM WB 命令5 IF ID EX MEM WB

37 パイプラインレジスタ 各ステージの足並みをクロックサイクルに合わせる HW ステージをまたぐ全ての信号線に挿入 ステージ内 ＆ ステージ間
情報システム基盤学基礎１ パイプラインレジスタ 回路 A 各ステージの足並みをクロックサイクルに合わせる HW ステージ内 ＆ ステージ間 ステージをまたぐ全ての信号線に挿入 x c y s z clk サイクル1 サイクル2 サイクル3 time パイプライン レジスタ パイプライン化 clk X ステージ1 ステージ2 x y a a’ c c’ a y b b’ b a’ s z b’ c clk c’ 遅延が異なる

38 パイプライン処理を行うプロセッサ 4 制御 ALU 命令フェッチ 命令デコード＆ レジスタ読み出し メモリアクセス レジスタ 書き込み 実行
情報システム基盤学基礎１ パイプライン処理を行うプロセッサ 命令フェッチ 命令デコード＆ レジスタ読み出し メモリアクセス レジスタ 書き込み 実行 加算 4 加算 2ビット 左シフト RegWrite Branch 制御 ALUOp MemtoReg Zero レジスタファイル MemRead MemWrite ALUSrc Read Reg 1 Read データ1 Read Reg 2 ALU Read データ2 アドレス Read データ PC Read アドレス Read データ Write Reg Write データ Write データ 命令メモリ データメモリ 符号 拡張 RegDst ALU 制御

39 動作例（0サイクル目） 4 制御 ALU PC データメモリ 命令メモリ プログラム 情報システム基盤学基礎１ 加算 加算 符号 拡張
2ビット 左シフト RegWrite Branch 制御 ALUOp MemtoReg Zero レジスタファイル MemRead MemWrite ALUSrc ALU PC 命令メモリ データメモリ 符号 拡張 RegDst プログラム ALU 制御 lw $s2, 4($t0) add $t1,$s0,$s1 sub $t2,$s3,$s4 sw $s5, 16($t0) beq $s6,$s7,20 4 8 12 16

40 動作例（1サイクル目） 4 4 制御 ALU PC データメモリ 命令メモリ 命令メモリ プログラム 情報システム基盤学基礎１ 加算 加算
lw $s2, 4($t0) 4 加算 命令メモリ 加算 4 加算 2ビット 左シフト RegWrite Branch 制御 ALUOp MemtoReg Zero レジスタファイル MemRead MemWrite ALUSrc “4” ALU PC lw $s2, 4($t0) “0” 命令メモリ データメモリ 符号 拡張 RegDst プログラム ALU 制御 lw $s2, 4($t0) add $t1,$s0,$s1 sub $t2,$s3,$s4 sw $s5, 16($t0) beq $s6,$s7,20 4 8 12 16

41 動作例（2サイクル目） 4 4 制御 制御 ALU 命令メモリ 4 命令メモリ PC 命令メモリ データメモリ プログラム
情報システム基盤学基礎１ 動作例（2サイクル目） add $t1,$s0,$s1 lw $s2, 4($t0) lw $s2, 4($t0) “1024” “18(s2)” 4 加算 命令メモリ 4 加算 命令メモリ 加算 4 加算 2ビット 左シフト RegWrite レジスタファイル 制御 符号 拡張 “lw” “4” “18(s2)” “8(t0)” Branch 制御 ALUOp MemtoReg Zero レジスタファイル MemRead MemWrite ALUSrc “8” “4” 1024 8 ALU PC lw $s2, 4($t0) “0” add $t1,$s0,$s1 “4” 命令メモリ データメモリ 符号 拡張 RegDst プログラム ALU 制御 lw $s2, 4($t0) add $t1,$s0,$s1 sub $t2,$s3,$s4 sw $s5, 16($t0) beq $s6,$s7,20 4 8 12 16

42 動作例（3サイクル目） 4 4 4 ALU 制御 制御 制御 ALU 8 命令メモリ 8 命令メモリ PC 命令メモリ データメモリ
情報システム基盤学基礎１ 動作例（3サイクル目） lw $s2, 4($t0) sub $t2,$s3,$s4 add $t1,$s0,$s1 add $t1,$s0,$s1 lw $s2, 4($t0) “100” “10” lw $s2, 4($t0) “1028” 8 4 加算 命令メモリ 8 4 加算 命令メモリ 加算 4 加算 ALU ALU 制御 ALUSrc ALUOp “1024” “4” 2ビット 左シフト RegWrite レジスタファイル 制御 “ALU” “9($t1)” “17(s1)” “16(s0)” “add” レジスタファイル 制御 符号 拡張 Branch “1024” “lw” “4” “18(s2)” “8(t0)” add $t1,$s0,$s1 “8” 制御 ALUOp MemtoReg Zero レジスタファイル MemRead MemWrite ALUSrc “12” 100 16 10 17 1024 8 ALU PC sub $t2,$s3,$s4 “8” 命令メモリ データメモリ 符号 拡張 RegDst プログラム ALU 制御 lw $s2, 4($t0) add $t1,$s0,$s1 sub $t2,$s3,$s4 sw $s5, 16($t0) beq $s6,$s7,20 4 “18(s2)” 8 12 16 “18(s2)”

43 動作例（4サイクル目） 4 制御 4 ALU 4 ALU 制御 制御 ALU 12 命令メモリ 8 命令メモリ データメモリ PC
情報システム基盤学基礎１ 動作例（4サイクル目） add $t1,$s0,$s1 sw $s5, 16($t0) lw $s2, 4($t0) sub $t2,$s3,$s4 sub $t2,$s3,$s4 add $t1,$s0,$s1 lw $s2, 4($t0) “320” “80” add $t1,$s0,$s1 lw $s2, 4($t0) “110” lw $s2, 4($t0) “16384” 12 4 加算 命令メモリ “100” “10” レジスタファイル 制御 “ALU” “9($t1)” “17(s1)” “16(s0)” 100 16 10 17 8 4 加算 命令メモリ sub $t2,$s3,$s4 “8” ALU ALU 制御 ALUSrc ALUOp “1024” “4” “1028” 加算 4 加算 ALU ALU 制御 ALUSrc ALUOp “100” “10” 2ビット 左シフト RegWrite レジスタファイル 制御 “ALU” “10($t2)” “20(s4)” “19(s3)” Branch 制御 データメモリ MemRead ALUOp MemtoReg Zero レジスタファイル MemRead MemWrite ALUSrc “12” “16” 320 19 80 20 ALU PC 16384 “1028” sw $s5, 16($t0) “12” 命令メモリ データメモリ 符号 拡張 RegDst プログラム ALU 制御 “add” “sub” lw $s2, 4($t0) add $t1,$s0,$s1 sub $t2,$s3,$s4 sw $s5, 16($t0) beq $s6,$s7,20 4 “18(s2)” “9(t1)” “18(s2)” 8 12 16

44 動作例（5サイクル目） 制御 4 ALU 4 4 ALU 制御 制御 ALU 12 命令メモリ データメモリ 16 命令メモリ PC
情報システム基盤学基礎１ 動作例（5サイクル目） add $t1,$s0,$s1 beq $s6,$s7,20 lw $s2, 4($t0) sub $t2,$s3,$s4 add $t1,$s0,$s1 lw $s2, 4($t0) sw $s5, 16($t0) “1024” sub $t2,$s3,$s4 lw $s2, 4($t0) “240” add $t1,$s0,$s1 “110” lw $s2, 4($t0) “320” “80” レジスタファイル 制御 “ALU” “10($t2)” “20(s4)” “19(s3)” 12 4 加算 命令メモリ ALU ALU 制御 ALUSrc ALUOp “100” “10” “110” 320 19 80 20 sw $s5, 16($t0) “12” “16” “sub” “16384” データメモリ MemRead “9(t1)” “18(s2)” 16384 “1028” 16 4 加算 命令メモリ RegWrite MemtoReg 加算 4 “20” 加算 ALU ALU 制御 ALUSrc ALUOp “320” “80” 2ビット 左シフト RegWrite レジスタファイル 制御 符号 拡張 “sw” “16” “21(s5)” “8(t0)” Branch 制御 ALUOp MemtoReg Zero レジスタファイル MemRead MemWrite ALUSrc 1024 8 ALU PC “18(s2)” beq $s6,$s7,20 “16” “16384” 16384 18 命令メモリ データメモリ 符号 拡張 RegDst プログラム ALU 制御 lw $s2, 4($t0) add $t1,$s0,$s1 sub $t2,$s3,$s4 sw $s5, 16($t0) beq $s6,$s7,20 4 “10(t2)” “9(t1)” 8 12 16 “20(s5)”

45 PC/サーバ用プロセッサの命令パイプライン
情報システム基盤学基礎１ PC/サーバ用プロセッサの命令パイプライン 以前： ステージ数がとても多かった 例： Intel Pentium 4 （2000年頃）の命令パイプライン 31 ステージのプロセッサが発売されていたこともあった クロック周波数を上げることが最善と考えられていたため 現在： 14 ステージ前後 周波数を上げても思ったほど性能向上には繋がらなかった 消費電力の問題が深刻になった 周波数の増加　　　　消費電力の大幅な増加

46 その他のプロセッサの命令パイプライン パーソナルモバイルデバイス 組込みプロセッサ
情報システム基盤学基礎１ その他のプロセッサの命令パイプライン パーソナルモバイルデバイス 高性能なものでは 10 ステージ以上に分割して数 GHz で稼働 かつての PC 並 組込みプロセッサ 性能と消費電力のレンジが広いためプロセッサによって大きく異なる パイプライン化されていないもの～数段のパイプラインを持つもの

47 情報システム基盤学基礎１ ハザード

48 ハザード（パイプラインハザード） 命令をパイプライン処理できない状況 パイプラインの停止や処理のやり直しが必要
情報システム基盤学基礎１ ハザード（パイプラインハザード） 命令をパイプライン処理できない状況 パイプラインの停止や処理のやり直しが必要 「本日のデザート」は 品切れだよ すいませんお客様 「本日のデザート」は品切れでして… 最後の「本日のデザート」 「本日のデザート」をください！ [ パイプラインハザード ]

49 情報システム基盤学基礎１ ハザードの種類 構造ハザード データハザード 制御ハザード

50 構造ハザード ハードウェア資源の不足によって命令が実行できなくなること 十分な資源があれば発生しない
情報システム基盤学基礎１ 構造ハザード ハードウェア資源の不足によって命令が実行できなくなること 例： 命令とデータが同じメモリに格納されており，同時にはどちらか一方 　　　しか読み出すことができない場合 十分な資源があれば発生しない 例： 命令とデータを同時に読み出すことができるメモリにすればよい IF IF MEM メモリアクセス IF IF time lw $s2, 4($t0) IF ID IF EX ID IF MEM EX ID add $t1,$s0,$s1 sub $t2,$s3,$s4 sw $s5, 16($t0) IF

51 データハザード データの依存関係によって命令が実行できなくなること 例： 直前の命令が書き込んだレジスタを後続の命令が読み出す場合
情報システム基盤学基礎１ データハザード データの依存関係によって命令が実行できなくなること 例： 直前の命令が書き込んだレジスタを後続の命令が読み出す場合 $s0の中身 IF ID EX 10 100 110 10 100 $t1へ格納 IF ID 110 10 100 $s2の中身 $t1の中身 time add $t1,$s0,$s2 WB MEM データ依存 $t1の読み出し add $t2,$t1,$s3 「$s0+$s2」の実行 [ パイプライン処理を行わない場合 ] $s0の中身 10 100 110 10 100 $s2の中身 $t1の中身 「110」を$t1に書き込む前に読み出し time add $t1,$s0,$s2 IF ID EX MEM EX WB add $t2,$t1,$s3 [ パイプライン処理を行う場合 ]

52 制御ハザード 制御依存関係によって命令が実行できなくなること 例： 条件分岐命令の結果によって実行される後続命令が異なる場合
情報システム基盤学基礎１ 制御ハザード 制御依存関係によって命令が実行できなくなること 例： 条件分岐命令の結果によって実行される後続命令が異なる場合 「sub $t2,$s3,$s4」の命令フェッチ開始 time プログラム beq $s6,$s7,label IF ID EX WB MEM beq $s6,$s7,label add $t1,$s0,$s1 sub $t2,$s3,$s4 制御依存 sub $t2,$s3,$s4 IF 分岐成立 label: [ パイプライン処理を行わない場合 ] 分岐の成立/不成立が判明する前に後続命令のフェッチを開始 time beq $s6,$s7,label IF ID ID EX ??? [ パイプライン処理を行う場合 ]

53 ハザードへの対処 一般的な対処法 ハードウェアやプログラムの変更により解決 保守的な方法： ストール（パイプラインストール）
情報システム基盤学基礎１ ハザードへの対処 一般的な対処法 保守的な方法： ストール（パイプラインストール） 積極的な方法： 投機的に処理を行い，投機が間違っていたら再実行 ハードウェアやプログラムの変更により解決 バイパシング（フォワーディング）　　　データハザードの一部 遅延分岐　　　制御ハザードの一部

54 ストール ハザードが解消されるまで後続命令の処理を停止 ハザードが解消されたら停止していた命令の処理を再開 データハザード解消
情報システム基盤学基礎１ ストール ハザードが解消されるまで後続命令の処理を停止 ハザードが解消されたら停止していた命令の処理を再開 $s0の中身 10 100 110 10 100 110 10 100 $s2の中身 $t1の中身 time IF ID EX ID MEM WB データハザード解消 add $t1,$s0,$s2 add $t2,$t1,$s3 ID ID 後続命令の処理再開 データハザード発生 後続命令の処理停止 [ データハザード時にストールを行った場合 ]

55 投機実行 予測にもとづき，後続命令の処理を投機的に実行開始 投機成功/失敗を評価し，結果に応じて適切な処理を施す
情報システム基盤学基礎１ 投機実行 予測にもとづき，後続命令の処理を投機的に実行開始 投機成功/失敗を評価し，結果に応じて適切な処理を施す 投機成功　　　何もしない 投機失敗　　　アーキテクチャ状態を回復し，正しい結果を用いて再実行 投機に成功した場合は，命令パイプラインはハザードがない時と同様の振る舞いを示す 詳細は「高性能コンピューティング論２」で 分岐成立 time プログラム beq $s6,$s7,label IF ID IF EX ID IF WB MEM EX ID IF beq $s6,$s7,label add $t1,$s0,$s1 sub $t2,$s3,$s4 lw $t3, 4($t0) add $s5, $t3, $t1 sub $t2,$s3,$s4 label: lw $t3, 4($t0) add $s5, $t3, $t1 分岐成立と予測し label 以降の命令フェッチ開始 [ 投機実行（分岐予測）を行った場合 ]

56 バイパシング レジスタ書き込み前のデータを必要なステージに直接供給 演算命令間のデータハザードを解消
情報システム基盤学基礎１ バイパシング レジスタ書き込み前のデータを必要なステージに直接供給 演算命令間のデータハザードを解消 メモリ命令⇒演算命令のデータハザードを緩和 バイパス 「$s0+$s2」の結果判明 time add $t1,$s0,$s2 IF ID EX MEM EX バイパスされたデータを使って演算実行 add $t2,$t1,$s3 100 ($s0) 110 ($t1) [ EX⇒EXバイパシング ] ALU 110 ($t1) 310 ($t2) 512 (4(t0)) 292 ($t2) 182 ($s3) 「4($t0)」のロード完了 time データメモリ lw $s3, 4($t0) EX MEM IF ID EX WB バイパスされたデータを使って 演算実行 200 ($s3) 10 ($s2) add $t2,$t1,$s3 EX MEM [ MEM⇒EXバイパシング ]

57 結果が判明してから分岐先の 命令フェッチ開始
情報システム基盤学基礎１ 遅延分岐 分岐結果の影響を受けない命令をコンパイラが検出 分岐の成立/不成立によらず実行される命令 かつ，分岐の成立/不成立によらず結果が同じ命令 上記命令を分岐命令の直後に挿入することで制御ハザードの発生を防ぐ 欠点： 挿入できる命令が十分な数存在しない場合はストール 分岐成立 プログラム A 変換 beq $s6,$s7,label add $s0,$s0,$s2 lw $s4, 4($t0) add $s0,$s0,$s1 sub $s3,$s0,$s2 add $s5, $s3, $s4 label: プログラム A’ time beq $s6,$s7,label IF ID IF EX ID IF MEM EX ID IF add $s0,$s0,$s2 beq $s6,$s7,label add $s0,$s0,$s1 sub $s3,$s0,$s2 lw $s4, 4($t0) add $s5, $s3, $s4 add $s0,$s0,$s2 beq $s6,$s7,label add $s0,$s0,$s1 sub $s3,$s0,$s2 lw $s4, 4($t0) add $s5, $s3, $s4 分岐結果 の影響を 受けない add $s0,$s0,$s2 label: lw $t4, 4($t0) sub $s3,$s0,$s2 結果が判明してから分岐先の 命令フェッチ開始 [ 遅延分岐 ]