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

标签：

• 九州大学
• 布尔函数最小化
• 流水线
• 数据冒险
• 数据前递
• 高速缓存
• 缓存地址映射
• 阿姆达尔定律

Author

Zero, 祭音Myyura

Description

【問 1】

以下の真理値表で与えられた論理関数 $H(a, b, c, d)$ を図で示されるように $3$ つの関数 $G_1(a, b, c), G_2(a, b, c)$ および $F(d, g_1, g_2)$ を使って実現することを考える．図に示されるように，$g_1, g_2$ はそれぞれ関数 $G_1, G_2$ の出力に接続しているものとする．関数 $G_1$ の真理値表が以下の表で与えられる時，$F$ および $G_2$ の真理値表を示せ．

【問 2】

$5$ つのステージからなるパイプライン式データパスを有するマイクロプロセッサについて考える．実装されたパイプラインステージは，IF（命令取得），ID（命令デコード），EX（実行），MEM（メモリアクセス），ならびに，WB（ライトバック）である．加算命令とロードワード命令の実行における各ステージの処理内容は以下の表に従う．ここで，パイプラインストールの発生を除き，各パイプラインステージの実行は常に $1$ クロックサイクルで完了できると仮定する．また，WB ステージでレジスタに書き込まれた値は，同一クロックサイクルにて，後続命令の ID ステージで読み出し可能である．以下の各問いに答えよ．

ステージ	加算命令：add $x, $y, $z	ロードワード命令：lw $x, offset($y)
IF	メモリより実行すべき命令を取得し，次命令取得のためにプログラム・カウンタを更新.	メモリより実行すべき命令を取得し，次命令取得のためにプログラム・カウンタを更新.
ID	命令の解読. レジスタファイルからレジスタ $y ならびに $z を読み出し.	命令の解読. レジスタファイルからレジスタ $y を読み出し.
EX	$y と $z の加算を実行.	$y と offset を加算しメモリアドレスを生成.
MEM	特に無し（加算結果を WB ステージへ転送）.	生成したメモリアドレスに対応するワードデータをデータメモリから読み出し.
WB	加算結果をレジスタファイル内のレジスタ $x に書き込み.	データメモリから読み出したデータをレジスタファイル内のレジスタ $x に書き込み.

(1) 以下に示すプログラムについて考える．各行においてシャープ記号から右はコメントである．プログラム中に存在するフロー依存関係について，どの命令が，どの命令のどのレジスタに関して依存しているかをすべて列挙せよ．

 lw $2,  20($1)  # <1>
add $10, $1,$5   # <2>
add $12, $10,$2  # <3>
 lw $11, 40($1)  # <4>
add $15, $11,$2  # <5>

(2) 上記 (1) のフロー依存関係のうち，命令パイプライン処理で実行した際にデータハザードを生じさせるものを示せ．

(3) 上記 (2) のデータハザードを以下の方式によって対処した場合の上記 (1) のプログラムの実行に要するクロックサイクル数を求めよ．

• (A) パイプラインストールのみ
• (B) データフォワーディング＋パイプラインストール

(4) マイクロプロセッサの動作周波数は $1.0$ GHz であると仮定する．上記 (3) の (B) の方式を適用した場合，上記 (1) のプログラムの実行時間（単位はナノ秒）を答えよ．

(5) 上記 (3) に関して，(A) に対する (B) の性能向上比を答えよ．

【問 3】

コンピュータのメモリシステムについて，以下の各問いに答えよ．

(1) マイクロプロセッサに搭載されたフルアソシアティブ・キャッシュについて考える．ワードサイズは $4$ バイト，キャッシュ・サイズは $16$ バイト，ブロックサイズは $4$ バイト，アドレス長は $4$ ビットであり，キャッシュの初期状態は空とする．また，ブロック置換ポリシは LRU（Least Recently Used）アルゴリズムを採用する．以下に示すワードアドレス(2 進表現) に対してメモリアクセスが順次発生した場合のキャッシュ・ミス率を答えよ．

$0101 \Rightarrow 1111 \Rightarrow 1001 \Rightarrow 0101 \Rightarrow 0001 \Rightarrow 1100 \Rightarrow 1111 \Rightarrow 0101 \Rightarrow 0011 \Rightarrow 1100$

(2) あるプログラムを実行したところ，実行時間の $30$%がメモリへのアクセスに費やされることが分かった．そこで，ハードウェア設計を改善し，性能への悪影響を伴うこと無く，メモリアクセスを $3$ 倍高速にした．この改善により得られる性能向上率を求めよ．

题目描述

【问题 1】逻辑函数 $H(a,b,c,d)$ 的真值表及其分解结构见原题图。要求按图用三个函数 $G_1(a,b,c)$、$G_2(a,b,c)$ 和 $F(d,g_1,g_2)$ 实现 $H$，其中信号 $g_1,g_2$ 分别连接到 $G_1,G_2$ 的输出。已知图中给出的 $G_1$ 真值表，写出 $F$ 与 $G_2$ 的真值表。

【问题 2】考虑具有 IF（取指）、ID（译码）、EX（执行）、MEM（访存）和 WB（写回）五级流水数据通路的微处理器。除发生流水线停顿外，每一级总能在 $1$ 个时钟周期内完成；WB 阶段写入寄存器的值可在同一时钟周期被后续指令的 ID 阶段读取。加法与装载字指令各阶段的操作如下：

阶段	加法指令 add $x, $y, $z	装载字指令 lw $x, offset($y)
IF	从存储器取出待执行指令，并更新程序计数器以取下一条指令。	从存储器取出待执行指令，并更新程序计数器以取下一条指令。
ID	译码，从寄存器堆读出 $y 与 $z。	译码，从寄存器堆读出 $y。
EX	执行 $y 与 $z 的加法。	将 $y 与 offset 相加，生成存储器地址。
MEM	无特殊操作，将加法结果送往 WB。	从数据存储器读出所生成地址处的一个字。
WB	将加法结果写入寄存器堆中的 $x。	将数据存储器读出的数据写入寄存器堆中的 $x。

对以下程序（每行 # 右侧为注释）回答：

 lw $2,  20($1)  # <1>
add $10, $1,$5   # <2>
add $12, $10,$2  # <3>
 lw $11, 40($1)  # <4>
add $15, $11,$2  # <5>

1. 枚举程序中的全部流依赖（真依赖），逐一指出哪条指令依赖哪条指令产生的哪个寄存器。
2. 指出上述流依赖中哪些会在流水执行时造成数据冒险。
3. 分别采用下列方式处理这些冒险时，求程序执行所需时钟周期数：
   • (A) 仅使用流水线停顿；
   • (B) 使用数据前递并配合流水线停顿。
4. 若处理器频率为 $1.0\,\mathrm{GHz}$，采用 (B) 时求程序执行时间，单位为纳秒。
5. 求 (B) 相对于 (A) 的性能提升比。

【问题 3】回答以下存储系统问题：

1. 某全相联缓存的字长为 $4$ 字节、容量为 $16$ 字节、块大小为 $4$ 字节、地址长度为 $4$ 位，初始为空，替换策略为 LRU。依次访问下列二进制字地址时，求缓存缺失率：

   $$0101\Rightarrow1111\Rightarrow1001\Rightarrow0101\Rightarrow0001 \Rightarrow1100\Rightarrow1111\Rightarrow0101\Rightarrow0011\Rightarrow1100.$$

2. 某程序有 $30\%$ 的执行时间用于访问存储器。现改进硬件，在不引入其他性能损失的前提下将存储器访问加速到原来的 $3$ 倍，求总体性能提升率。

Kai

【問 1】

a b c\d	$G_1$	$G_2$	0	1
0 0 0	0	0	0	0
0 0 1	1	0	0	1
0 1 0	1	0	0	1
0 1 1	1	1	1	0
1 0 0	0	1	1	1
1 0 1	0	1	1	1
1 1 0	1	1	1	0
1 1 1	1	0	0	1

$$H = \overline{G_1}G_2 + G_1G_2\overline{d} + G_1\overline{G_2}d$$

a b c	$G_2$
0 0 0	0
0 0 1	0
0 1 0	0
0 1 1	1
1 0 0	1
1 0 1	1
1 1 0	1
1 1 1	0

d $g_1$ $g_2$	F
0 0 0	0
0 0 1	1
0 1 0	0
0 1 1	1
1 0 0	0
1 0 1	1
1 1 0	1
1 1 1	0

【問 2】

(1)

<1> $\rightarrow$ <3> ($2$)

<2> $\rightarrow$ <3> ($10$)

<1> $\rightarrow$ <5> ($2$)

<4> $\rightarrow$ <5> ($11$)

(2)

データハザードを生じるのは、<1> $\rightarrow$ <3>（$2$）、<2> $\rightarrow$ <3>（$10$）、<4> $\rightarrow$ <5>（$11$）である。<1> $\rightarrow$ <5> は、<5> の ID より前に <1> の WB が完了するのでハザードにならない。

(3)

• (A) <3> の ID で $2$ サイクル、<5> の ID で $2$ サイクル停止する。したがって $5+4+4=13$ クロックサイクル。
• (B) <4> の直後に <5> がロード結果を使う箇所だけ $1$ サイクル停止する。したがって $5+4+1=10$ クロックサイクル。

(4)

$1.0\,\mathrm{GHz}$ では $1$ クロックが $1\,\mathrm{ns}$ なので、$10\,\mathrm{ns}$。

(5)

性能向上比は

$$\frac{13}{10}=1.3$$

であり、$1.3$ 倍（$30\%$ 向上）である。

【問 3】

(1)

キャッシュには $16/4=4$ ブロック入る。アクセスの成否は

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

なので、ミス率は $7/10=70\%$。

(2)

$T$ を改善前の実行時間とすると、改善後は

$$0.7T+\frac{0.3T}{3}=0.8T.$$

したがって性能向上率は $T/(0.8T)=1.25$、すなわち $25\%$ 向上である。