跳到主要内容

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

标签：

Author​

Zero

Description​

【問 1】​

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

【問 2】​

55 つのステージからなるパイプライン式データパスを有するマイクロプロセッサについて考える．実装されたパイプラインステージは，IF（命令取得），ID（命令デコード），EX（実行），MEM（メモリアクセス），ならびに，WB（ライトバック）である．加算命令とロードワード命令の実行における各ステージの処理内容は以下の表に従う．ここで，パイプラインストールの発生を除き，各パイプラインステージの実行は常に 11 クロックサイクルで完了できると仮定する．また，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.01.0 GHz であると仮定する．上記 (3) の (B) の方式を適用した場合，上記 (1) のプログラムの実行時間（単位はナノ秒）を答えよ．

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

【問 3】​

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

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

0101⇒1111⇒1001⇒0101⇒0001⇒1100⇒1111⇒0101⇒0011⇒11000101 \Rightarrow 1111 \Rightarrow 1001 \Rightarrow 0101 \Rightarrow 0001 \Rightarrow 1100 \Rightarrow 1111 \Rightarrow 0101 \Rightarrow 0011 \Rightarrow 1100

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

题目描述​

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

【问题 2】考虑具有 IF（取指）、ID（译码）、EX（执行）、MEM（访存）和 WB（写回）五级流水数据通路的微处理器。除发生流水线停顿外，每一级总能在 11 个时钟周期内完成；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 GHz1.0\,\mathrm{GHz}，采用 (B) 时求程序执行时间，单位为纳秒。
  5. 求 (B) 相对于 (A) 的性能提升比。

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

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

    0101⇒1111⇒1001⇒0101⇒0001⇒1100⇒1111⇒0101⇒0011⇒1100.0101\Rightarrow1111\Rightarrow1001\Rightarrow0101\Rightarrow0001 \Rightarrow1100\Rightarrow1111\Rightarrow0101\Rightarrow0011\Rightarrow1100.

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

考点​

  • 布尔函数分解与化简：依据给定真值表和组合逻辑连接关系，反推出中间函数及输出函数的真值表。
  • 五级流水线数据依赖与冒险：区分流依赖是否在具体时序中形成写后读数据冒险，并准确排出各指令阶段。
  • 流水线停顿与数据前递：比较仅停顿和前递结合停顿两种处理方式的周期数、执行时间与加速比。
  • 全相联缓存与最近最少使用替换：根据块容量、初始空状态和访问序列逐次判断命中、强制缺失与替换。
  • 阿姆达尔定律：由可加速部分占比及其加速倍数计算整个程序的性能提升。

Kai​

【問 1】​

a b c\dG1G_1G2G_201
0 0 00000
0 0 11001
0 1 01001
0 1 11110
1 0 00111
1 0 10111
1 1 01110
1 1 11001
H=G1‾G2+G1G2d‾+G1G2‾dH = \overline{G_1}G_2 + G_1G_2\overline{d} + G_1\overline{G_2}d
a b cG2G_2
0 0 00
0 0 10
0 1 00
0 1 11
1 0 01
1 0 11
1 1 01
1 1 10
d g1g_1 g2g_2F
0 0 00
0 0 11
0 1 00
0 1 11
1 0 00
1 0 11
1 1 01
1 1 10

【問 2】​

(1)​

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

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

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

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

(2)​

TODO

(3)​

TODO

(4)​

TODO

(5)​

TODO

【問 3】​

(1)​

TODO

(2)​

本页目录