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

标签：

• Kyushu-University
• Boolean-Function-Minimization
• Pipelining
• Superscalar-Execution
• Performance-Analysis
• Cache
• Cache-Miss-Types

Author

Yu

Description

【問 1】

下図の様にいくつかの論理ゲートと部分回路 $H$ から構成される論理回路の出力の論理関数 $F(a, b, c, d)$ が以下の様な真理値表で表される時， 部分回路 $H$ の論理関数 $H(s,t, u, v)$の最簡積和形を示せ． ただし，論理関数の最簡積和形とはその論理関数を表す積和形論理式のうち，積項数が最小のものを指す． 積項数が等しい積和形論理式が複数ある場合にはそのなかでリテラル数が最小のものを指す．

【問 2】

パイプライン式データパスを有するマイクロプロセッサについて考える． 以下の式で示すように，プログラム実行時間 $ET$ は，プログラム実行のために処理される総命令数 $IC$， クロックサイクル当り実行命令数 $IPC$，ならびに，動作周波数 $F$，の $3$ つのパラメータを用いて表現できる．

$$ET = \frac{IC}{IPC \times F}$$

以下の各問いに答えよ．

(1) 命令発行幅が $1$ のインオーダマイクロプロセッサを考える． シングルサイクル・データパス方式（ $1$ 命令の実行を $1$ クロックサイクルで処理する方式）と比較した場合， パイプライン式データパスの実装が $IC，IPC，F$ に与える影響をそれぞれ説明せよ． なお，各パラメータにおいて影響がない場合は「影響なし」と答えること．

(2) このパイプライン式データパスにおいて命令発行幅を $2$ へ増加し， インオーダ命令実行のスーパスカラ方式へと拡張した（依存関係のない命令を最大で $2$ 個同時に実行できる）． この拡張が $IC，IPC，F$ に与える影響をそれぞれ説明せよ． なお，各パラメータにおいて影響がない場合は「影響なし」と答えること．

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

【問 3】

コンピュータのメモリシステムについて考える． マイクロプロセッサにダイレクトマップ・キャッシュが搭載されているものとする． ワードアドレッシング方式を採用しており，ワードサイズは $4$ バイト，キャッシュ・サイズは $16$ バイト，ブロックサイズは $4$ バイト，アドレス長は $4$ ビットである． キャッシュの初期状態は空であったが，これまでに $1101 \Rightarrow 1010 \Rightarrow 1111 \Rightarrow 1101$ のワードアドレス (2 進表現) に対してメモリアクセスが順次発生している． このとき，メモリアクセス (i) ～ (v) が順次発生したとする．

メモリアクセス	ワードアドレス (2 進表現)
(i)	1010
(ii)	1001
(iii)	1000
(iv)	0011
(v)	1111

以下の各問いに答えよ．

(1) メモリアクセス (i) ～ (v) のうち，キャッシュ・ヒットとなるメモリアクセスをすべて答えよ． 該当するメモリアクセスがない場合は「該当なし」と答えること．

(2) メモリアクセス (i) ～ (v) のうち，初期参照ミスとなるメモリアクセスをすべて答えよ． 該当するメモリアクセスがない場合は「該当なし」と答えること．

(3) 競合ミスを削減するためにはこのキャッシュをどのように改良すれば良いか説明せよ． また，改良によるデメリットがあればあわせて説明せよ.

题目描述

【问题 1】一个由若干逻辑门和子电路 $H$ 构成的组合逻辑电路，其输出函数 $F(a,b,c,d)$ 的真值表及连接方式见原题图。求子电路的逻辑函数 $H(s,t,u,v)$ 的最简积和式。“最简”首先要求积项数最少；若有多个积项数相同的表达式，则取文字总数最少者。

【问题 2】考虑具有流水数据通路的微处理器。程序执行时间 $ET$ 可由总执行指令数 $IC$、每时钟周期执行指令数 $IPC$ 和工作频率 $F$ 表示为

$$ET=\frac{IC}{IPC\times F}.$$

回答：

1. 对发射宽度为 $1$ 的顺序执行微处理器，与单周期数据通路（每条指令在一个时钟周期内完成）相比，分别说明实现流水数据通路对 $IC$、$IPC$、$F$ 的影响；若某参数不受影响，明确回答“无影响”。
2. 将该流水线的发射宽度增至 $2$，扩展为顺序发射超标量方式，即最多同时执行两条互不依赖的指令。分别说明扩展对 $IC$、$IPC$、$F$ 的影响；无影响者同样须明确指出。
3. 假设发射宽度为 $4$，求该流水线可达到的 $IPC$ 上限。

【问题 3】某微处理器配有直接映射缓存，按字寻址，字长 $4$ 字节、缓存容量 $16$ 字节、块大小 $4$ 字节、地址长度 $4$ 位。缓存初始为空，之前已依次访问二进制字地址 $1101\Rightarrow1010\Rightarrow1111\Rightarrow1101$。随后按顺序发生以下访问：

存储访问	二进制字地址
(i)	1010
(ii)	1001
(iii)	1000
(iv)	0011
(v)	1111

回答：

1. 列出 (i)～(v) 中所有缓存命中的访问；若没有，回答“无”。
2. 列出 (i)～(v) 中所有首次访问缺失（强制缺失）的访问；若没有，回答“无”。
3. 说明应如何改进该缓存以减少冲突缺失，并同时说明该改进可能带来的缺点。

考点

• 布尔函数最简积和式：由整体真值表和逻辑门连接反求子电路函数，并按积项数、文字数两级标准化简。
• 流水线与超标量性能分析：利用 $ET=IC/(IPC\times F)$ 分析流水化、发射宽度变化对三个参数的作用及 IPC 理论上限。
• 直接映射缓存访问跟踪：根据既往与新增字地址序列维护缓存内容，区分命中、强制缺失和冲突缺失。
• 缓存相联度权衡：说明提高相联度如何减少冲突缺失，以及由此增加的访问延迟、比较硬件和替换复杂度。

Kai

【問 1】

$$\begin{align} s = \overline{ab} \quad t = bc \quad u = c + d \quad v = a \oplus d \end{align}$$

a	b	c	d	s	t	u	v	F
0	0	0	0	1	0	0	0	0
0	0	0	1	1	0	1	1	0
0	0	1	0	1	0	1	0	0
0	0	1	1	1	0	1	1	0
0	1	0	0	1	0	0	0	0
0	1	0	1	1	0	1	1	0
0	1	1	0	1	1	1	0	0
0	1	1	1	1	1	1	1	1
1	0	0	0	1	0	0	1	1
1	0	0	1	1	0	1	0	0
1	0	1	0	1	0	1	1	0
1	0	1	1	1	0	1	0	0
1	1	0	0	0	0	0	1	1
1	1	0	1	0	0	1	0	0
1	1	1	0	0	1	1	1	1
1	1	1	1	0	1	1	0	1

s	t	u	v	F
0	0	0	0	x
0	0	0	1	1
0	0	1	0	0
0	0	1	1	x
0	1	0	0	x
0	1	0	1	x
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	0
1	1	0	0	x
1	1	0	1	x
1	1	1	0	0
1	1	1	1	1

st\uv	00	01	11	10
00	x	1	x	0
01	x	x	1	1
11	x	x	1	0
10	0	1	0	0

$$\begin{align} H = \overline{s}t + \overline{u}v + tv \end{align}$$

【問 2】

(1)

• IC: 影響なし
• IPC: 低下する可能性がある
• F: より⾼い

(2)

• IC: 影響なし
• IPC: より⾼い
• F: より低い

(3)

$$IPC_{\max} = 4$$

【問 3】

(1)

(i)

(2)

(iii)

(3)

• キャッシュサイズの拡張
• セットアソシアティブキャッシュの採⽤

デメリット: ハードウェアコストが上がり