九州大学 システム情報科学府 情報理工学専攻 2018年度 計算機アーキテクチャ

Author

Zero

Description

【問 1】

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

【問 2】

\(5\) つのステージからなるパイプライン式データパスを有するマイクロプロセッサについて考える．実装されたパイプラインステージは，IF（命令取得），ID（命令デコード），EX（実行），MEM（メモリアクセス），ならびに，WB（ライトバック）である．加算命令，ロードワード命令，ストアワード命令の実行における各ステージの処理内容は以下の表に従う．ここで，パイプラインストールの発生を除き，各パイプラインステージの実行は常に \(1\) クロックサイクルで完了できると仮定する．また，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)

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

\[ 1100 \Rightarrow 1010 \Rightarrow 1101 \Rightarrow 0101 \Rightarrow 1100 \Rightarrow 0101 \Rightarrow 1010 \Rightarrow 0101 \Rightarrow 0011 \Rightarrow 0101 \]

(2)

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

Kai

【問 1】

b	d	\(G_1\)
0	0	1
0	1	0
1	0	0
1	1	0

a	b	\(G_2\)
0	0	0
0	1	1
1	0	0
1	1	0

c	d	\(G_3\)
0	0	0
0	1	1
1	0	1
1	1	1

【問 2】

(1)

フロー依存は

レジスタ \(3\) に関し　命令　\(1\) と \(3\) , \(1\) と \(5\) , \(1\) と \(6\)

レジスタ \(4\) に関し　命令　\(2\) と \(3\)

レジスタ \(10\) に関し　命令　\(3\) と \(4\) , \(5\) と \(6\) , \(2\) と \(6\)

逆依存は

レジスタ \(4\) に関し　命令　\(3\) と \(6\)

出力依存は

レジスタ \(10\) に関し　命令　\(3\) と \(4\) , \(5\) と \(6\) , \(4\) と \(5\)

レジスタ \(4\) に関し　命令　\(2\) と \(6\)

(2)

それぞれ、データハザードを起こす

フロー依存は

レジスタ \(3\) に関し　命令　\(1\) と \(3\)

レジスタ \(4\) に関し　命令　\(2\) と \(3\)

レジスタ \(10\) に関し　命令　\(3\) と \(4\)

出力依存は

レジスタ \(10\) に関し　命令　\(3\) と \(4\)

(3)

(A)

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
lw	IF	ID	EX	MEM	WB	0	0	0	0	0	0	0	0	0	0	0
lw	0	IF	ID	EX	MEM	WB	0	0	0	0	0	0	0	0	0	0
add	0	0	IF	IF	IF	ID	EX	-	WB	0	0	0	0	0	0	0
sw	0	0	0	0	0	IF	IF	IF	ID	EX	MEM	0	0	0	0	0
add	0	0	0	0	0	0	0	0	IF	ID	EX	-	WB	0	0	0
add	0	0	0	0	0	0	0	0	0	IF	IF	IF	ID	EX	-	WB

上の表から、\(16\) クロック

(B)

下の表より、\(11\) クロック

0	1	2	3	4	5	6	7	8	9	10	11
lw	IF	ID	EX	MEM	WB	0	0	0	0	0	0
lw	0	IF	ID	EX	MEM	WB	0	0	0	0	0
add	0	0	IF	IF	ID	EX	-	WB	0	0	0
sw	0	0	0	0	IF	ID	EX	MEM	0	0	0
add	0	0	0	0	0	IF	ID	EX	-	WB	0
add	0	0	0	0	0	0	IF	ID	EX	-	WB

(4)

後ろの命令のレジスタ書き込みの前に前の命令のレジスタ読み出しを行う逆依存は命令を同時に並行処理した時に発生する。命令順を入れ替えた場合、出力依存によって最後の結果がわかってしまう。

【問 3】