九州大学 システム情報科学府 情報理工学専攻 2018年8月実施 計算機アーキテクチャ

标签：

• Kyushu-University
• Boolean-Function-Minimization
• Pipelining
• Data-Hazard
• Data-Forwarding
• Cache
• Cache-Address-Mapping

Author

Yu, 祭音Myyura

Description

出典：公式問題（保存版、33–34頁）。

【問 1】

以下の真理値表で与えられた論理関数 $F(a, b, c, d)$ を図で示されるように関数 $G(a, b, c, d)$ および NAND ゲートを使って実現することを考える。 関数 $G$ の最簡積和形を示せ。

【問 2】

5 つのステージからなるパイプライン式データパスを有するマイクロプロセッサについて考える。 実装されたパイプラインステージは、IF（命令取得）、ID（命令デコード）、EX（実行）、MEM（メモリアクセス）、ならびに、WB（ライトバック）である。 以下の各問いに答えよ。

(1) パイプラインの導入によりプロセッサ性能が向上する理由を説明せよ。

(2) このパイプライン構造で発生する RAW（Read After Write）ハザードを解消する方法を少なくとも 2 つ挙げ、それぞれの実現法を簡潔に説明せよ。

(3) プログラム実行時間は、「実行命令数」「CPI（Clock cycles Per Instruction）」「クロックサイクル時間」の積で近似できる。このパイプラインのステージ数を増加した場合、改善を期待できる項目を選択し、その理由を説明せよ。

(4) 一般に、パイプライン段数を増加し続けた場合、プロセッサ性能向上の度合いは次第に小さくなる傾向にある。その理由を述べよ。

【問 3】

16 ビットのアドレス（adr[15:0]）を入力とするダイレクトマップキャッシュの設計について考える。 バイトアドレッシング方式であり 1 語は 4 バイトとする。 各キャッシュアクセスにおいて、adr[15:8]、adr[7:4] ならびに adr[3:0] は、それぞれ、タグフィールド、インデックスフィールド、オフセットフィールドとして参照される。 以下の問いに答えよ。

(1) キャッシュブロックサイズを答えよ。

(2) キャッシュブロックの総数を答えよ。

(3) キャッシュの初期状態は空であるとする。以下の 16 進表現されたバイトアドレスに対してメモリアクセスが順次発生した場合のキャッシュ・ミス率を答えよ。

• 0x0000 ⇒ 0x0004 ⇒ 0x0020 ⇒ 0x1120 ⇒ 0x1104 ⇒ 0x0004 ⇒ 0x1120 ⇒ 0x0020 ⇒ 0x0024 ⇒ 0x0020

题目描述

【问题 1】逻辑函数 $F(a,b,c,d)$ 的真值表及实现结构见原题图。要求按图使用函数 $G(a,b,c,d)$ 和 NAND 门实现 $F$，求 $G$ 的最简与项之和形式（最简积和式）。

【问题 2】考虑具有 IF（取指）、ID（译码）、EX（执行）、MEM（访存）和 WB（写回）五级流水数据通路的微处理器。回答：

1. 说明引入流水线能够提高处理器性能的原因。
2. 至少列出两种消除该流水结构中 RAW（写后读）冒险的方法，并分别简要说明其实现方式。
3. 程序执行时间可近似为“执行指令数 × CPI（每条指令的时钟周期数）× 时钟周期时间”。增加流水级数时，指出其中哪一项有望改善，并说明原因。
4. 一般而言，持续增加流水级数所带来的处理器性能增益会逐渐减小，说明其原因。

【问题 3】设计一个输入为 $16$ 位地址 adr[15:0] 的直接映射缓存。系统按字节寻址，每字为 $4$ 字节；每次访问时，以 adr[15:8] 为标记字段、adr[7:4] 为索引字段、adr[3:0] 为块内偏移字段。回答：

1. 求缓存块大小。

2. 求缓存块总数。

3. 假设缓存初始为空，依次访问下列十六进制字节地址时，求缓存缺失率：

   0x0000 ⇒ 0x0004 ⇒ 0x0020 ⇒ 0x1120 ⇒ 0x1104 ⇒ 0x0004 ⇒ 0x1120 ⇒ 0x0020 ⇒ 0x0024 ⇒ 0x0020

Kai

【問 1】

$$F = \overline{\overline{\overline{ab}c}G}$$

a	b	c	d	G
0	0	0	0	1
0	0	0	1	1
0	0	1	0	x
0	0	1	1	x
0	1	0	0	1
0	1	0	1	0
0	1	1	0	x
0	1	1	1	x
1	0	0	0	1
1	0	0	1	1
1	0	1	0	x
1	0	1	1	x
1	1	0	0	1
1	1	0	1	0
1	1	1	0	1
1	1	1	1	0

ab\cd	00	01	11	10
00	1	1	x	x
01	1		x	x
11	1			1
10	1	1	x	x

$$G = \overline{b} + \overline{d}$$

【問 2】

(1)

命令処理を複数の段階に分割し、各段階で異なる命令を同時に処理することで、命令の完了間隔を短くできる。理想的にはパイプラインが満たされた後、毎クロック一命令を完了できる。組合せ回路を分割すればクロック周期も短縮できるが、一命令が IF から WB まで進む遅延が短縮されるとは限らない。

(2)

• ストール：依存する入力値が使えるまで PC と IF/ID レジスタを保持し、EX にバブルを挿入する。先行命令の WB 後にレジスタを読み直せば正しい値を使える。
• フォワーディング：先行命令の結果を EX/MEM または MEM/WB レジスタから、後続命令の入力へ直接送る。レジスタファイルへの書戻しを待つ必要がなくなる。ただし、ロード直後にその結果を使う場合など、必要な時刻までに結果が得られない依存では、フォワーディングとストールを併用する。

(3)

パイプラインのステージ数を増加させた場合、改善を期待できる項⽬は 「クロックサイクル時間」である。

各ステージで⾏う組合せ回路処理が減るため、クロックサイクル時間を短くできる。 実行命令数は変わらず、命令発行幅が同じなら理想 CPI は既にほぼ $1$ である。 むしろ段数の増加によりハザードのペナルティが増え、平均 CPI は悪化し得る。

(4)

パイプラインレジスタの遅延やクロックスキューなど、段を細分化しても減らない時間がクロック周期の下限となる。さらに以下の要因がある。

1. 分岐予測ミスのペナルティが増加する: パイプラインが深くなると、分岐予測ミス時に破棄する命令と回復までのサイクル数が増えるため、性能向上が抑制される。
2. パイプラインのバランスが悪化する: パイプライン段数が増加すると、各ステージの処理時間が異なる場合、最も遅いステージに従属することがあります。これにより、全体の性能が低下する可能性があります。
3. プロセッサの複雑さが増加する: パイプライン段数が増加すると、プロセッサの設計や実装がより複雑になり、デバッグや最適化が困難になることがあります。また、消費電⼒やチップ⾯積も増加する可能性があります。
4. 指令レベルの並列性 (ILP) の限界: プロセッサが同時に実⾏できる命令数には⾃然な限界があります。パイプライン段数を増加させても、その限界を超えることはできません。したがって、性能向上の度合いは次第に小さくなります。

【問 3】

(1)

$16$ バイト

(2)

$16$

(3)

アクセス結果は順に

$$\mathrm{M,H,M,M,M,M,H,M,H,H}$$

である。従ってミス率は

$$\frac{6}{10}=60\%.$$