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

标签：

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

Author

Yu, 祭音Myyura

Description

【問 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 ⇒ 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 ⇒ 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)

1. 並⾏性の向上: パイプライン技術を使⽤することで、各ステージが同時に異なる命令を処理できます。これにより、プロセッサは複数の命令を同時に実⾏できるようになり、全体的なスループットが向上します。
2. タスクの分割: パイプラインは、命令の実⾏をいくつかのステージに分割します。これにより、各ステージは特定のタスクに特化し、そのタスクを効率的に実⾏できます。これにより、命令の実⾏時間が短縮され、性能が向上します。
3. クロックサイクルの短縮: 各ステージが独⽴して動作するため、クロックサイクルは各ステージの最も遅い部分に合わせる必要があります。これにより、クロックサイクルが短くなり、プロセッサの性能が向上します。

(2)

1. ストール（Stall）: ストールは、RAW ハザードが解消されるまで次の命令の実⾏を⼀時停止する方法です。これは、データが前の命令から利⽤可能になるまで待つことで、RAW ハザードを回避します。ただし、ストールはプロセッサの性能に悪影響を与える可能性があります。

• 実現方法：ハードウェアは、RAW ハザードが検出された場合、次の命令の実⾏を⼀時停止し、前の命令が書き込みを完了するのを待ちます。書き込みが完了したら、次の命令が再開され、ハザードが解消されます。

2. フォワードィング（Forwarding）またはバイパス（Bypass）: フォワードィングは、前の命令が書き込むデータを、次の命令がそれを読む前に直接転送する方法です。これにより、次の命令が待つことなくデータを読むことができ、RAW ハザードが解消されます。

• 実現方法：ハードウェアは、前の命令が書き込むデータを、次の命令がそれを必要とするステージに直接送信します。これにより、次の命令はデータを待たずに読むことができ、RAW ハザードが解消されます。

(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}$$

である。従ってミス率は

$$\frac{6}{9}=\frac{2}{3}.$$