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

标签：

• Kyushu-University
• Boolean-Function-Minimization
• Pipelining
• Data-Hazard
• Data-Forwarding
• Cache
• Cache-Address-Mapping
• Average-Memory-Access-Time

Author

Yu

Description

【問 1】

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

【問 2】

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

(1) プログラム実行時間は，「実行命令数」「平均 CPI(Clock cycles Per Instruction)」「クロックサイクル時間」の積で近似できる．シングルサイクル・データパス方式（$1$ 命令の実行を $1$ クロックサイクルで実行する方式）と比較した場合，パイプライン処理がプログラム実行時間に与える影響を説明せよ．

(2) パイプライン式データパスで発生する RAW (Read After Write) ハザードを解消する代表的な実装として「パイプラインストール」と「データフォワーディング」がある．これらの実装法の利点と欠点を説明せよ．

(3) 命令発行幅は $1$ と仮定する．このパイプラインで達成できる IPC (Instructions Per Clock cycle) の上限を答えよ．

【問 3】

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

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

(2) キャッシュサイズを答えよ．

(3) レベル $1$ キャッシュと主記憶からなるメモリシステムを想定した場合，平均メモリアクセス時間（AMAT: Average Memory Access Time）は下の式で表される． ここで，キャッシュヒット時間はキャッシュアクセス時間と同義と考えて良い． より高いキャッシュ連想度を採用することの利点と欠点を AMAT を用いて説明せよ．

AMAT = キャッシュヒット時間 + キャッシュミス率 × キャッシュミスペナルティ

题目描述

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

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

1. 程序执行时间可近似为“执行指令数 × 平均 CPI（每条指令的时钟周期数）× 时钟周期时间”。与单周期数据通路（每条指令在一个时钟周期内完成）相比，说明流水处理会如何影响这三个因素及程序执行时间。
2. 流水数据通路中处理 RAW（写后读）冒险的典型实现包括“流水线停顿”和“数据前递”，分别说明两者的优点与缺点。
3. 假设指令发射宽度为 $1$，求该流水线可达到的 IPC（每时钟周期完成的指令数）上限。

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

1. 求缓存块大小。

2. 求缓存总容量。

3. 对仅由一级缓存和主存组成的存储系统，平均存储访问时间定义为

   $$\mathrm{AMAT} =\text{缓存命中时间} +\text{缓存缺失率}\times\text{缓存缺失代价},$$

   其中缓存命中时间与缓存访问时间同义。结合该公式说明采用更高缓存相联度的优点与缺点。

考点

• 布尔函数化简：依据与非门组合结构和两个已知真值表反求中间函数，并写成最简积和式。
• 流水线性能与吞吐率：用指令数、CPI、周期时间及发射宽度分析流水相对单周期实现的影响和 IPC 上限。
• 流水线停顿与数据前递：比较两种写后读冒险处理机制在硬件复杂度、等待周期和性能上的取舍。
• 二路组相联缓存地址映射：由偏移位、索引位和路数计算缓存块大小、组数及总容量。
• 平均存储访问时间：用平均访问时间公式权衡更高相联度降低冲突缺失与增加命中延迟、硬件成本的影响。

Kai

【問 1】

$$H = \overline{FG}$$

a	b	c	d	F
0	0	0	0	1
0	0	0	1	0
0	0	1	0	x
0	0	1	1	0
0	1	0	0	x
0	1	0	1	0
0	1	1	0	x
0	1	1	1	x
1	0	0	0	x
1	0	0	1	0
1	0	1	0	1
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0
1	1	1	0	x
1	1	1	1	x

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

【問 2】

(1)

1. クロックサイクル時間の短縮：パイプライン処理では、各ステージが短いクロックサイクル時間で実行できるため、全体のクロックサイクル時間が短くなります。
2. 並行性の向上：パイプライン処理では、複数の命令が同時に実行されるため、全体の実行速度が向上します。
3. パイプラインハザードの影響：パイプライン処理では、パイプラインハザードが発生することでCPIが増加し、実行時間が長くなる可能性があります。

(2)

パイプラインストール：

利点：

• シンプルな実装で、ハードウェアの複雑さが比較的少ない。
• データ依存性が発生した場合に、後続の命令を一時停止してデータが利⽤可能になるのを待つため、ハザードが解消される。

欠点：

• 後続の命令がストールされるため、パイプラインの効率が低下し、IPC（Instructions Per Cycle）が減少する可能性がある。
• パイプラインストールが頻繁に発生すると、プロセッサの性能が大幅に低下する。

データフォワーディング：

利点：

• 後続の命令がデータを待つことなく実行できるため、パイプラインの効率が向上し、IPCが向上する可能性がある。
• データ依存性がある場合でも、パイプラインストールが発生しにくくなるため、プロセッサの性能が向上する。

欠点：

• ハードウェアの複雑さが増すため、実装が難しくなる。
• すべてのRAWハザードがデータフォワーディングで解消できるわけではなく、場合によってはパイプラインストールが必要になることがある（例：ロード命令の結果がすぐに利⽤可能でない場合）。

(3)

$1$

【問 3】

(1)

$16$ バイト

(2)

$512$ バイト

(3)

利点:

1. キャッシュミス率の低下: キャッシュ連想度が高いと、キャッシュ内でのデータの配置が柔軟になるため、キャッシュミスが発生しにくくなります。これにより、キャッシュミス率が低下し、AMATが短くなります。
2. ローカリティの向上: キャッシュ連想度が高いと、データのローカリティが向上し、特定のデータに対するアクセスが高速化されます。これもAMATを短くする要因となります。

欠点：

1. キャッシュヒット時間の増加: キャッシュ連想度が高いと、キャッシュ内でのデータの検索に時間がかかる可能性があります。これにより、キャッシュヒット時間が増加し、AMATが⻑くなることがあります。
2. ハードウェアの複雑さとコスト: 高いキャッシュ連想度を実現するには、より複雑なハードウェアが必要となり、コストが増加します。このコスト増加は、性能向上のためのトレードオフとして考慮されるべきです。