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

标签：

• Kyushu-University
• Boolean-Function-Minimization
• Pipelining
• Performance-Analysis
• Cache
• Cache-Address-Mapping

Author

Yu

Description

出典：九州大学令和3年度公式問題。

【問 1】

与えられた真理値表で表される論理関数 $F(a, b, c, d)$ が以下の論理式を満たす時，論理関数 $G(X,Y,Z,W)$ の最簡積和形を示せ．ただし，最簡積和形とは積和形論理式のうち，積項数が最小のものを指す．積項数が等しい積和形論理式が複数ある場合にはそのなかでリテラル数が最小のものを指す．

【問 2】

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

(1) IF，ID，EX，MEM，WB の遅延時間は，それぞれ，240 ps，400 ps，200 ps，250 ps，180 ps である．このデータパスの最大動作周波数を答えよ（単位は GHz）．

(2) IF，ID，EX，MEM，WB のいずれか $1$ つを $2$ つのステージに分割し，パイプラインステージ数を $5$ から $6$ へと増加することを考える． ここで，分割された各パイプラインステージの遅延時間は，分割前のパイプラインステージの遅延時間の半分になると仮定する． パイプラインの動作周波数を最大にするために分割すべきパイプラインステージを選択せよ．また，この設計最適化により達成できる最大動作周波数を答えよ（単位は GHz）．

(3) あるプログラムの実行において，上記 (2) のパイプラインステージの分割により CPI（Clock cycles Per Instruction）が 10% 増加した． ここで，パイプラインステージ分割は CPI の増加以外の悪影響は生じないと仮定する． このパイプラインステージ分割によって得られた性能向上比を答えよ．

(4) パイプライン段数を増加することの利点と欠点を説明せよ．

【問 3】

キャッシュタグ・フィールド，キャッシュインデックス・フィールド，キャッシュブロッ クオフセット・フィールドからなる $32$ ビットのメモリアドレスを入力とするダイレク トマップ・キャッシュメモリについて考える．バイトアドレッシング方式を採用してお り， $1$ 語は $4$ バイト，キャッシュサイズは $16$ キロバイト，キャッシュブロックサイズは 32 バイトとする．キャッシュタグ・フィールドのビット幅を答えよ．

题目描述

【问题 1】已知逻辑函数 $F(a,b,c,d)$ 的真值表，以及 $F$ 与 $G(X,Y,Z,W)$ 之间的逻辑表达式，均见原题图。求 $G$ 的最简积和式。这里“最简积和式”首先指积项数最少；若有多个积项数相同的表达式，则取文字总数最少者。

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

1. 五级的延迟依次为 $240\,\mathrm{ps}$、$400\,\mathrm{ps}$、$200\,\mathrm{ps}$、$250\,\mathrm{ps}$、$180\,\mathrm{ps}$，求该数据通路的最高工作频率，单位为 GHz。
2. 从五级中任选一级拆成两级，使总级数由 $5$ 增至 $6$；假设拆分后每一级的延迟均为拆分前的一半。为使工作频率最大，应拆分哪一级？并求优化后的最高工作频率，单位为 GHz。
3. 某程序采用上述拆分后，CPI（每条指令的时钟周期数）增加 $10\%$；假设拆分不产生 CPI 增加以外的负面影响，求本次拆分带来的性能提升比。
4. 说明增加流水级数的优点与缺点。

【问题 3】某直接映射缓存输入 $32$ 位存储器地址，地址由标记、索引和块内偏移字段组成。系统按字节寻址，每字 $4$ 字节，缓存容量为 $16\,\mathrm{KiB}$，缓存块大小为 $32$ 字节。求缓存标记字段的位宽。

Kai

【問 1】

a	b	c	d	X	Y	Z	W	F
0	0	0	0	1	0	0	0	0
0	0	0	1	1	0	1	0	0
0	0	1	0	0	1	0	1	0
0	0	1	1	1	0	1	1	1
0	1	0	0	0	0	1	1	0
0	1	0	1	0	0	1	0	1
0	1	1	0	0	1	0	1	0
0	1	1	1	0	1	0	1	0
1	0	0	0	0	1	0	0	1
1	0	0	1	1	1	1	0	1
1	0	1	0	0	0	0	0	1
1	0	1	1	1	1	1	1	0
1	1	0	0	1	1	0	0	1
1	1	0	1	0	0	1	1	0
1	1	1	0	1	0	0	0	0
1	1	1	1	0	1	0	1	0

X	Y	Z	W	G
0	0	0	0	1
0	0	0	1	x
0	0	1	0	1
0	0	1	1	0
0	1	0	0	1
0	1	0	1	0
0	1	1	0	x
0	1	1	1	x
1	0	0	0	0
1	0	0	1	x
1	0	1	0	0
1	0	1	1	1
1	1	0	0	1
1	1	0	1	x
1	1	1	0	1
1	1	1	1	0

XY\ZW	00	01	11	10
00	1	X		1
01	1		X	X
11	1	X		1
10		X	1

$$G = \overline{X} \overline{W} + Y\overline{W} + X\overline{Y}W$$

【問 2】

(1)

$$F_1 = \frac{1}{400 \times 10^{-12}}\text{ Hz} = 2.5\text{ GHz}$$

(2)

最長の $\mathrm{ID}$ ステージを二分割する。分割後の各段の遅延は $240,200,200,200,250,180\,\mathrm{ps}$ となり、最大は $250\,\mathrm{ps}$ である。

$$F_2=\frac{1}{250\times10^{-12}}\,\mathrm{Hz}=4\,\mathrm{GHz}.$$

(3)

同じ命令数で CPI が $1.1$ 倍になるので、性能向上比は

$$\frac{T_{\rm before}}{T_{\rm after}} =\frac{400}{1.1\times250} =\frac{16}{11}\approx1.45.$$

(4)

各段の組合せ回路を短くすることで、クロック周期を短縮し、単位時間当たりの命令処理数を増やせる。 一方、データ依存による待ち時間や分岐予測ミスからの回復に必要なサイクル数が増える場合がある。 パイプラインレジスタとクロック配線の増加は面積・消費電力を増やし、レジスタ遅延などの固定費用は周期短縮の下限になる。 したがって、段数を増やし続けても性能が比例して向上するわけではない。

【問 3】

$18$