1
計算機構成論II パイプラン,記憶階層編
第8回以降(全15回）
電気情報系学科
横田孝義
2019年11月28日（木）3 10/3 10/10 10/24 10/31 11/7 11/14 11/21 11/28 12/5 12/12 12/19 12/26 1/9 1/23 1/30
授業計画
休講 （補講12・4）７ パイプライン処理
5
７ パイプライン処理
コンピュータの世界でのパイプラインとは？
フォンノイマン型コンピュータの性能向上策
性能：スループットともいう throughput,単位時間あたりの処理能力
パイプライン処理 命令パイプライン処理 演算パイプライン処理７ パイプライン処理
処 理 の 流 れ 盆 皿 金 箸 盆 皿 金 箸 盆 皿 金 箸 盆 皿 金 箸 母 娘 息子 父 時間の流れ 0 16 カフェテリア：お盆をとる、皿をとる、 お金を払う、箸をとるの時間を すべて１と仮定 つまり、各ステージの所要時間が直列処理だと。。
7
７ パイプライン処理
パイプライン処理だと。。（出来るだけ並列化）
処 理 の 流 れ 盆 皿 金 箸 盆 皿 金 箸 盆 皿 金 箸 盆 皿 金 箸 母 娘 息子 父 時間の流れ 0 7 カフェテリア：お盆をとる、皿をとる、 お金を払う、箸をとるの時間を すべて１と仮定 つまり、各ステージの所要時間が 等しいと仮定７ パイプライン処理
客処理能力の向上
直列処理では１６単位時間
パイプライン処理では7単位時間
9
７ パイプライン処理
人数が増えた場合は？
N人の場合
直列処理だと。。
客１ 盆 皿 金 箸 盆 皿 金 箸 盆 皿 金 箸 盆 皿 金 箸 客２ 客３ 客N 時間の流れ 04N
処 理 の 流 れ７ パイプライン処理
人数が増えた場合は？
N人の場合
パイプライン処理だと。。
客１ 盆 皿 金 箸 盆 皿 金 箸 盆 皿 金 箸 客２ 客３ 時間の流れ 0N+3
処 理 の 流 れ N 311
７ パイプライン処理
客の数がN人の場合の直列処理とパイプライン処理のスループット比は 直列処理の処理時間 パイプライン処理の処理時間 ＝ 4N/(N+3) 各ステージの所要時間が 等しい場合は スループットの向上率は ステージ数に漸近する。７ パイプライン処理
RISC型CPU
各機械語命令の実行時間に基づきパイプライン処理を説明する。
RISC型CPU は１命令を１クロックサイクルで実行する。
命令実行のステージは以下の５ステージで構成されるとする。
①命令フェッチ(IF: instruction fetch ステージ)
➁命令デコードとレジスタフェッチ(ID:insruction decode ステージ)
③ALUでの演算とアドレス計算(EX:excutionステージ)
④メモリアクセス(MA:memory access ステージ)
⑤レジスタへの書き込み(WB:write backステージ)
13
７ パイプライン処理
RISC型CPU
①命令フェッチ(IF: instruction fetch ステージ)
➁命令デコードとレジスタフェッチ(ID:insruction decode ステージ)
③ALUでの演算とアドレス計算(EX:excutionステージ)
④メモリアクセス(MA:memory access ステージ)
⑤レジスタへの書き込み(WB:write backステージ)
基本的命令と各ステージの実行時間 nsec この時間を基本とする。７ パイプライン処理
RISC型CPU
直列処理ではこの時間を基本とする。 IF ID EX MA WB IF ID EX MA WB 時間の流れ (ns) 処 理 の 流 0 直列処理 7 1415
７ パイプライン処理
RISC型CPU
パイプライン処理の場合、各ステージの処理時間は同一でないといけないので 各ステージの最大処理時間の2nsecとする必要がある。 15 IF ID EX MA WB 時間の流れ (ns) 処 理 の 流 れ 0 10 14 パイプライン処理 IF ID EX MA WB IF ID EX MA WB IF ID EX MA WB 8 6 4 2 12７ パイプライン処理
RISC型CPU
実効命令数n個の時の スループット向上率は処理時間 2N+8 ns
処理時間 7N ns
7 ns 2ns17
７ パイプライン処理
パイプライン処理によるスループット比は直列処理のクロックサイクル７nsと
パイプライン処理のクロックサイクル２ns
の比率である3.5に漸近する。
７ パイプライン処理
パイプラインの流れを乱すもの
次の命令の実行開始を阻害するもの。
ハザード hazard,競合 conflict などと呼ぶ。
パイプライン処理は停止してしまう。
命令を実行できないステージが発生。 Stall, bubble
19
構造ハザード….. ハードウエアが競合する場合
19 IF ID EX MA WB 時間の流れ (ns) 処 理 の 流 れ 0 10 14 パイプライン処理 IF ID EX MA WB IF ID EX MA WB IF ID EX MA WB 8 6 4 2 12 メモリへの同時アクセスになり競合する制御ハザード….. 分岐命令によって予測が外れる場合
IF ID EX MA WB 処 理 の 流 れ IF ID EX MA WB 次命令 分岐先計算と分岐条件の判定 対処法3： 次命令アドレスが確定する演算結果を待つ。（ストールする） この分の遅れが生じる。これを分岐遅延と呼ぶ。 分岐遅延スロット 分岐遅延スロット21
データハザード…..演算結果待ちが生じる場合
IF ID EX MA WB 処 理 の 流 れ 減算 R3-R4->R5 IF ID EX MA WB R1+R2 R3の値が確定 するまでストール R1+R2の結果をR3に書込み 加算 R1+R2->R3 R3の読み出し R3-R4７ パイプライン処理
ハザードの種類は３種類
構造ハザード….. ハードウエアが競合する場合
制御ハザード….. 分岐命令によって予測が外れる場合
データハザード…演算結果待ちが生じる場合
23 データの流れ 制御の流れ 命令レジスタ プログラム カウンタ 命令デコーダ ＡＬＵ 算術論理 演算 ユニット レ ジ ス タ 群 メモリ部 入出力部 制御部 演算部
CPU
基本的演算とその拡張
R1レジ(32bit) R2 レジ(32bit) ALU（加算） c R3レジ(32bit) ALU（減算） R４レジ(32bit)
データハザード…..演算結果待ちが生じる場合
加算
R1+R2->R3
減算
R3-R4->R5
25 IF ID EX MA WB 処 理 の 流 れ IF ID EX MA WB R1+R2 加算 R1+R2->R3 R3-R4
データハザード…..演算結果待ちが生じる場合の対策
フォワーディング、バイパス 演算結果R1+R2を次のサイクルでALUの入力に直接入れてしまう。R1レジ(32bit) R2 レジ(32bit) ALU（加算） c R3レジ(32bit) ALU（減算） R４レジ(32bit)
データハザード…..演算結果待ちが生じる場合の対策
加算
R1+R2->R3
減算
R3-R4->R5
バイパス27
8. 記憶階層
フォン・ノイマンボトルネック １プロセッサ、１メモリ構造、逐次性 ＣＰＵとメモリ間が命令とデータで渋滞してしまう。 CPUとメモリのパイプを太く、かつ遠くまで届くようにするための 工夫が記憶階層8.1 局所性原理と階層構造
(1) アクセス時間 メモリからの読み出し、書き込みにかかる時間 ①ストア命令、ロード命令などのメモリへのアクセス命令（メモリ命令）により、 アドレス指定され、データや命令の読み出し、書き込みが開始される まで（先頭語をアクセスするまで）の時間． 通常はこの規定． ２つの規定 ②アクセス命令によりアドレスが指定され、そこからの命令やデータの読み出し、 あるいは書き込みが完了するまでの時間． この場合はアクセスレイテンシ ともいわれる． サイクル時間：メモリに対して繰り返しアクセス可能な最少時間29
8.1 局所性原理と階層構造
時間的局所性と空間的局所性
時間的局所性：最近アクセスされた命令やデータのほうが再度アクセスされる 可能性が高い． 空間的局所性：アクセスされた命令やデータに、アドレス空間（メモリ空間）上 接近した命令やデータが引き続きアクセスされる可能性が高い． メモリ内の隣接したアドレスの命令が順次実行されていく． 繰り返し実行が多い． 同一データの読み書きが多い． メモリ内の隣接したデータ（配列要素など）が逐次アクセスされることが多い． プログラムの性質8.1 局所性原理と階層構造
アクセスされる可能性のより高いデータや命令を
ＣＰＵにより近く、より高速なメモリに収納すればデータや命令への
アクセス時間を短縮できる．
31
8.1 局所性原理と階層構造
CPU レジ スタ 群 キ ャ ッ シ ュ 主 記 憶 二 次 記 憶 より高速 より小容量 より低速 より大容量8.2 キャッシュ方式
アクセス キャッシュメモリ 主記憶（メモリ） 命令やデータ キャッシュ にあるか？ 無ければ主記憶に取りに行く キャッシュに コピー キャッシュに該当する命令やデータがあった場合をヒット， 無かった場合をミスという． ヒット率＋ミス率＝１33
8.2 キャッシュ方式
キャッシュへのアクセス時間：1単位時間 主記憶へのアクセス時間： 20単位時間 ヒット率：90％ だったとすると、 キャッシュ方式による平均アクセス時間は 1 × 0.9 + 20 + 1 × 0.1 = 3 単位時間 すなわち、 20/3＝6.67 倍の高速化 となる。 ヒット率が95%だと何倍の高速化になるか？8.2 .2 セットアソシアティブ方式 (set associative mapping)
キャッシュ容量 65kB(216B) 主記憶容量:256MB(228 B) 1語32bit (4B)とする． ディレクトリ メモリ タグ タグ ブロックフレーム（2語） 0 1 12 13 25 タグ セット（インデックス） ブロックフレーム（2語） 0 1 i 212-1 比較一致検出回路 比較一致検出回路 セット 13bit (block k) 32bit 32bit セレクタ セレクタ 32bit セレクタ35
8.2 .2 セットアソシアティブ方式 (set associative mapping) 具体例
37
例えるならば
鳥取県鳥取市湖山町南4-101 比較一致検出回路 セレクタ OFF 鳥取県鳥取市湖山町南 出力せず キャッシュ ミスの場合例えるならば
鳥取県鳥取市湖山町南4-101
比較一致検出回路 セレクタ
39
8.3 仮想記憶方式
仮想アドレスと物理アドレス 仮想アドレス空間 物理アドレス空間 主記憶8.3 仮想記憶方式
主記憶と2次記憶のデータの入れ替え単位
ページ方式
セグメント方式
41
8.3 仮想記憶方式
ページ方式
仮想アドレス 物理アドレス 仮想ページ番号 i ページ内オフセット 物理ページ番号 j ページ内オフセット 同bit数 ページ表 vは有効bit v 物理ページ番号 0 1 i 0 1 1 0 k j ページサイズは4kB～256kB8.3 仮想記憶方式
セグメント方式
大きさが可変のブロック（ページ）をセグメントと呼ぶ． 物理アドレス セグメント番号 i セグメント内オフセット セグメント内オフセット 同bit数 セグメント表 vは有効bit v 0 1 i 0 1 1 0 先頭物理アドレス 物理先頭アドレス セグメントサイズ 仮想アドレス43 仮想アドレス 仮想ページ番号 i ページ内オフセット TLB tag 物理ページ番号 0 1 i
TLB:translation look-aside buffer
