跳到主要内容

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

标签：

Author​

Zero, 祭音Myyura

Description​

【問 1】​

以下の真理値表で与えられた論理関数 F(a,b,c,d)F(a, b, c, d) を図で示されるように 33 つの関数 G1(b,d),G2(a,b)，G3(c,d)G1(b, d), G2(a, b)，G3(c, d) および AND ゲートと OR ゲートを使って実現することを考える．関数 G1,G2G1, G2 および G3G3 の真理値表を示せ．

【問 2】​

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

(1)​

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

        lw $3,  10($2)   # <1>
        lw $4,  18($2)   # <2>
       add $10, $3, $4   # <3>
        sw $10, 40($2)   # <4>
       add $10, $3, $3   # <5>
       add $4,  $3, $10  # <6>

(2)​

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

(3)​

上記 (2) のデータハザードを以下それぞれの方式によって対処した場合の上記 (1) のプログラムの実行における CPI (Clock cycles Per Instruction) を求めよ．

  • (A) パイプラインストールのみ

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

(4)​

逆依存関係や出力依存関係が生じる理由を説明せよ．

【問 3】​

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

(1)​

マイクロプロセッサに搭載されたダイレクトマップ・キャッシュについて考える．ワードサイズは 44 バイト，キャッシュ・サイズは 16 バイト，ブロックサイズは 88 バイト，アドレス長は 44 ビットであり，キャッシュの初期状態は空とする．以下に示すワードアドレス (22 進表現) に対してメモリアクセスが順次発生した場合のキャッシュ・ミス率を答えよ．

1100⇒1010⇒1101⇒0101⇒1100⇒0101⇒1010⇒0101⇒0011⇒01011100 \Rightarrow 1010 \Rightarrow 1101 \Rightarrow 0101 \Rightarrow 1100 \Rightarrow 0101 \Rightarrow 1010 \Rightarrow 0101 \Rightarrow 0011 \Rightarrow 0101

(2)​

初期参照ミスとは何か答えよ．また，初期参照ミス回数を削減する方法を述べよ．

题目描述​

【问题 1】逻辑函数 F(a,b,c,d)F(a,b,c,d) 的真值表和组合逻辑结构见原题图。要求按图使用 G1(b,d)G1(b,d)、G2(a,b)G2(a,b)、G3(c,d)G3(c,d) 三个函数以及 AND、OR 门实现 FF，写出 G1G1、G2G2、G3G3 的真值表。

【问题 2】考虑具有 IF（取指）、ID（译码）、EX（执行）、MEM（访存）和 WB（写回）五级流水数据通路的微处理器。加法、装载字与存储字指令在各级中的具体操作见原题阶段表。除发生流水线停顿外，每一级均在 11 个时钟周期内完成；WB 阶段写入寄存器的值可在同一周期被后续指令的 ID 阶段读取。对以下程序（# 右侧为注释）回答：

        lw $3,  10($2)   # <1>
        lw $4,  18($2)   # <2>
       add $10, $3, $4   # <3>
        sw $10, 40($2)   # <4>
       add $10, $3, $3   # <5>
       add $4,  $3, $10  # <6>
  1. 枚举程序中全部流依赖、反依赖和输出依赖，逐一指出哪条指令依赖哪条指令以及涉及哪个寄存器。
  2. 指出这些依赖中哪些会在流水线执行时导致数据冒险。
  3. 分别采用下列方式处理冒险时，求该程序的 CPI（每条指令平均时钟周期数）：
    • (A) 仅使用流水线停顿；
    • (B) 使用数据前递并配合流水线停顿。
  4. 说明反依赖和输出依赖产生的原因。

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

  1. 某直接映射缓存采用 44 字节字长、1616 字节容量、88 字节块和 44 位地址，初始为空。依次访问下列二进制字地址时，求缓存缺失率：

    1100⇒1010⇒1101⇒0101⇒1100⇒0101⇒1010⇒0101⇒0011⇒0101.1100\Rightarrow1010\Rightarrow1101\Rightarrow0101\Rightarrow1100 \Rightarrow0101\Rightarrow1010\Rightarrow0101\Rightarrow0011\Rightarrow0101.

  2. 解释什么是首次访问缺失（强制缺失），并说明减少其次数的方法。

Kai​

【問 1】​

bdG1G_1
001
010
100
110
abG2G_2
000
011
100
110
cdG3G_3
000
011
101
111

【問 2】​

(1)​

フロー依存は

  • レジスタ 33: <1> →\rightarrow <3>, <1> →\rightarrow <5>, <1> →\rightarrow <6>
  • レジスタ 44: <2> →\rightarrow <3>
  • レジスタ 1010: <3> →\rightarrow <4>, <5> →\rightarrow <6>

逆依存は

  • レジスタ 44: <3> →\rightarrow <6>
  • レジスタ 1010: <4> →\rightarrow <5>

出力依存は

  • レジスタ 1010: <3> →\rightarrow <5>
  • レジスタ 44: <2> →\rightarrow <6>

(2)​

ハザードを生じるのはフロー依存 <1> →\rightarrow <3>（33）、<2> →\rightarrow <3>（44）、<3> →\rightarrow <4>（1010）、<5> →\rightarrow <6>（1010）である。このインオーダ・パイプラインでは逆依存と出力依存はハザードを生じない。

(3)​

(A)​
012345678910111213141516
lwIFIDEXMEMWB00000000000
lw0IFIDEXMEMWB0000000000
add00IFIFIFIDEX-WB0000000
sw00000IFIFIFIDEXMEM00000
add00000000IFIDEX-WB000
add000000000IFIFIFIDEX-WB

上の表から 1616 クロックであり、CPI は

166=83.\frac{16}{6}=\frac83.
(B)​

下の表より 1111 クロックであり、CPI は

116.\frac{11}{6}.
01234567891011
lwIFIDEXMEMWB000000
lw0IFIDEXMEMWB00000
add00IFIFIDEX-WB000
sw0000IFIDEXMEM000
add00000IFIDEX-WB0
add000000IFIDEX-WB

(4)​

逆依存と出力依存は、異なる値に同じレジスタ名を再利用するために生じる名前依存である。アウトオブオーダ実行では、後続命令の書込みが先行命令の読出しより先になると WAR、二つの書込みの順序が逆になると WAW ハザードになる。レジスタ・リネーミングで除去できる。

【問 3】​

(1)​

ブロック内オフセットは 11 ビット、インデックスは 11 ビットである。アクセスの成否は

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

なので、ミス率は 6/10=60%6/10=60\%。

(2)​

初期参照ミスは、あるメモリブロックを最初に参照した際、そのブロックがまだキャッシュにないために起こるミスである。ブロックサイズを大きくして空間的局所性を利用する、またはプリフェッチすることで削減できる。

本页目录