計算機アーキテクチャ特論レポート課題 (ヒント)

以下に課題実現のためのヒントを示す。
※質問・疑問は随時受け付ける。

課題1. 命令パイプラインシミュレータの作成

以下の作業を行い、データハザードに対応できるようにする。

データフォワーディング機能の実装
EXステージの処理において、先行する命令(つまり、MAステージおよび WBステージで処理中の命令)のデスティネーションレジスタの値を入力データとして使っている場合に、パイプラインレジスタ中の変数 A, B の代わりに、後続のパイプラインレジスタ中の変数 ALUOutput や LMD の値を使うように変更する。
(EXステージの最初の方で実際に使われる値を A, B に代入しておくとよい)
具体的にどのパイプラインレジスタのどの変数の値を使えばよいかについては、配付資料図A.22, A.23を参考にすること。

注意：
データフォワーディングの対象となるレジスタ番号に書込みを行なう命令が MAステージおよびWBステージの両方に存在する場合は、近い方のステージの命令の結果(つまり、MAステージで処理中の命令側の結果)をフォワーディングすること。

例えば、以下のような実装を行う。

EXステージにおいて、ALUへの2つの入力に対して後続のパイプラインレジスタから適切なオペランド値を取得するメンバ関数 select_ALUInput_A() および select_ALUInput_B() を作成し、オペランド値を格納している A および B の値を EXステージの処理の最初の方で更新する。

***** mips::EX() *****
...
    // 以下を追加
    //
    // data forwarding
    //
    A = select_ALUInput_A(IR, A);
    B = select_ALUInput_B(IR, B);

    //
    // dispatch
    //
    switch (opcode(IR)) {
...

メンバ関数 select_ALUInput_A() および select_ALUInput_B() の中身は以下のようなコードとなる。
注意：未実装の箇所がいくつかあるので、コードを追加すること。

sim_word
mips::select_ALUInput_A(sim_inst IR, sim_word A)
{
    // Aを使わない命令はここでおわり
    if (!(is_ALU_inst(IR) || is_ALUimm_inst(IR) ||
	  is_load_inst(IR) || is_store_inst(IR) || is_branch_inst(IR) ||
	  is_muldiv_inst(IR)))
	return A;

    // レジスタ0番の場合はデータフォワーディング不要
    if (rs(IR) == 0)
	return A;
	
    if ( ... ) {

	A = EX_MA_reg.get_ALUOutput();
	cout << "  data forwarding from EX_MA_reg" << endl;
	cout << "  A=" << hex << A << endl;
    }
    else if ( ... ) {

	A = MA_WB_reg.get_ALUOutput();
	cout << "  data forwarding from MA_WB_reg" << endl;
	cout << "  A=" << hex << A << endl;
    }
    else if ...

    ...

    }
    // MFHI/MFLO (乗除算関連命令)のための処理
    else if (is_mfhilo_inst(EX_MA_reg.get_IR()) &&
	     rd(EX_MA_reg.get_IR()) == rs(IR)) {

	A = EX_MA_reg.get_ALUOutput();
	cout << "  data forwarding from EX_MA_reg" << endl;
	cout << "  A=" << hex << A << endl;
    }
    else if (is_mfhilo_inst(MA_WB_reg.get_IR()) &&
	     rd(MA_WB_reg.get_IR()) == rs(IR)) {

	A = MA_WB_reg.get_ALUOutput();
	cout << "  data forwarding from MA_WB_reg" << endl;
	cout << "  A=" << hex << A << endl;
    }

    return A;
}

sim_word
mips::select_ALUInput_B(sim_inst IR, sim_word B)
{
    // Bを使わない命令はここでおわり
    if (!(is_ALU_inst(IR) || is_muldiv_inst(IR)))
	return B;

    // レジスタ0番の場合はデータフォワーディング不要
    if (rt(IR) == 0)
	return B;

    if ( ... ) {

	B = EX_MA_reg.get_ALUOutput();
	cout << "  data forwarding from EX_MA_reg" << endl;
	cout << "  B=" << hex << B << endl;
    }
    else if ( ... ) {

	B = MA_WB_reg.get_ALUOutput();
	cout << "  data forwarding from MA_WB_reg" << endl;
	cout << "  B=" << hex << B << endl;
    }
    else if ...

    ...

    }
    // MFHI/MFLO (乗除算関連命令)のための処理
    else if (is_mfhilo_inst(EX_MA_reg.get_IR()) &&
	     rd(EX_MA_reg.get_IR()) == rt(IR)) {

	B = EX_MA_reg.get_ALUOutput();
	cout << "  data forwarding from EX_MA_reg" << endl;
	cout << "  B=" << hex << B << endl;
    }
    else if (is_mfhilo_inst(MA_WB_reg.get_IR()) &&
	     rd(MA_WB_reg.get_IR()) == rt(IR)) {

	B = MA_WB_reg.get_ALUOutput();
	cout << "  data forwarding from MA_WB_reg" << endl;
	cout << "  B=" << hex << B << endl;
    }

    return B;
}

なお、メンバ関数内で使っている is_ALU_inst() 等の命令の種類を判定する関数については以下の通りになっている。
privateなメンバ関数として追加する。

***** 命令の種類を判定する補助関数 *****

// 3つのレジスタを使うALU命令
bool
mips::is_ALU_inst(sim_inst ir)
{
    if (opcode(ir) == 0x00 &&
	(funct(ir) == 0x04 || funct(ir) == 0x06 || funct(ir) == 0x07 ||
	 (funct(ir) >= 0x18 && funct(ir) <= 0x1b) ||
	 (funct(ir) >= 0x20 && funct(ir) <= 0x27) ||
	 funct(ir) == 0x2a || funct(ir) == 0x2b))
	return true;
    return false;
}

// 2つのレジスタを使うALU命令
bool
mips::is_ALUimm_inst(sim_inst ir)
{
    if ((opcode(ir) == 0x0 &&
	 (funct(ir) == 0x0 || funct(ir) == 0x2 || funct(ir) == 0x3)) ||
	(opcode(ir) >= 0x08 && opcode(ir) <= 0x0f))
	return true;
    return false;
}

// ロード命令
bool
mips::is_load_inst(sim_inst ir)
{
    if (opcode(ir) >= 0x20 &&
	opcode(ir) <= 0x26)
	return true;
    return false;
}

// ストア命令
bool
mips::is_store_inst(sim_inst ir)
{
    if (opcode(ir) >= 0x28 &&
	opcode(ir) <= 0x2e)
	return true;
    return false;
}

// ジャンプ/分岐命令
bool
mips::is_branch_inst(sim_inst ir)
{
    if (opcode(ir) == 0x0 &&
	(funct(ir) == 0x8 || funct(ir) == 0x9))
	return true;
    if (opcode(ir) >= 0x2 && opcode(ir) <= 0x7)
	return true;
    return false;
}

// syscall/break命令
bool
mips::is_trap_inst(sim_inst ir)
{
    if (opcode(ir) == 0x0 &&
	(funct(ir) == 0xc || funct(ir) == 0xd))
	return true;
    return false;
}

// 乗除算命令
bool
mips::is_muldiv_inst(sim_inst ir)
{
    if (opcode(ir) == 0x0 &&
	(funct(ir) >= 0x18 && funct(ir) <= 0x1b))
	return true;
    return false;
}

// MFHI/MFLO命令
bool
mips::is_mfhilo_inst(sim_inst ir)
{
    if (opcode(ir) == 0x0 &&
	(funct(ir) == 0x10 || funct(ir) == 0x12))	// MFHI/MFLO
	return true;
    return false;
}

パイプラインインタロック機能の実装
パイプラインのインタロック条件を調べて、パイプラインを止める必要がある場合に、当該ステージの処理結果を次のステージに受け渡さないようにする。
そこで、各ステージの処理を保留する必要があるかどうかを示すフラグを用意することで、インタロックの制御を行えるように変更を行う。

例えば、以下のような実装を行う。

各ステージ毎に処理を保留するかどうかを示すフラグを privateなメンバ変数として追加する。
mipsクラスに以下を追加。

    // stall condition flag for each pipe stage
    bool	IF_stall_f;
    bool	IS_stall_f;
    bool	RR_stall_f;
    bool	EX_stall_f;
    bool	MA_stall_f;
    bool	WB_stall_f;

メンバ関数 mips::reset() の中で各フラグ変数を false に初期化するコードを追加する。

    IF_stall_f = false;
    IS_stall_f = false;
    RR_stall_f = false;
    EX_stall_f = false;
    MA_stall_f = false;
    WB_stall_f = false;

各ステージの処理の最初の方でフラグをチェックして処理を保留するかどうかを判定するコードを追加する。
例えば、mips::IS() は以下のようなコードになる。
他のステージについても同様にコードを追加する。
※各ステージ毎に、参照するフラグの名前が異なるので注意。
```
void
mips::IS()
{
    if (!IF_IS_reg.is_valid())
        return;

    cout << "---------- IS ----------" << endl;;
    // 以下の if文を追加
    if (IS_stall_f) {
	cout << "*** IS stalled ***" << endl;
	return;
    }

    // from previous stage
    sim_addr PC = IF_IS_reg.get_PC();
    sim_addr NPC = IF_IS_reg.get_NPC();
...
```

フラグをチェックして各パイプラインレジスタの内容を次のステージに受け渡すかどうかを切り替えるコードを追加する。
フラグが true の場合は次のステージに受け渡さないようにする。
そのため、mips::update_piperegs() の中身を以下のように修正する。

    // update all pipeline registers
    IF_IS_reg.update(IS_stall_f);
    IS_RR_reg.update(RR_stall_f);
    RR_EX_reg.update(EX_stall_f);
    EX_MA_reg.update(MA_stall_f);
    MA_WB_reg.update(WB_stall_f);

    // reset all stall condition flags
    IF_stall_f = false;
    IS_stall_f = false;
    RR_stall_f = false;
    EX_stall_f = false;
    MA_stall_f = false;
    WB_stall_f = false;

最後に、各ステージで処理を保留するかどうかを判定して、フラグ変数の値を適切に設定する処理を追加する。
publicなメンバ関数 check_stall_condition() を mipsクラスに追加し、 cpuクラスのメンバ関数 execute() を以下のように修正する。

	cout << "********** cycle=" << dec << cycle_time
	     << " **********" << endl;

	// 以下のコードを追加
	// pipeline stall condition check
	machdep->check_stall_condition();

	// process each pipeline stage
	machdep->IF();
	machdep->IS();
	machdep->RR();
	machdep->EX();
	machdep->MA();
	machdep->WB();

メンバ関数 check_stall_condition() の中身は以下のようなコードとなる。

void
mips::check_stall_condition()
{
    //
    // IF stage
    //

    // skip second next inst. of branch in RR stage
    if (IS_RR_reg.is_valid() && is_branch_inst(IS_RR_reg.get_IR())) {
	IF_stall_f = true;
    }

    //
    // IS stage
    //
    if (IF_IS_reg.is_valid() && !icache->is_done()) {
	IS_stall_f = true;
    }

    //
    // RR stage
    //
    if (IS_RR_reg.is_valid()) {
	sim_inst IR = IS_RR_reg.get_IR();

	if ((opcode(IR) == 0x00 &&
	     (funct(IR) == 0x08 || funct(IR) == 0x09)) ||	// JR/JALR
	    opcode(IR) == 0x06 || opcode(IR) == 0x07) {		// BLEZ/BGTZ

	    if ((RR_EX_reg.is_valid() &&
		 (is_ALU_inst(RR_EX_reg.get_IR()) ||
		  is_mfhilo_inst(RR_EX_reg.get_IR())) &&
		 rs(IR) != 0 && rd(RR_EX_reg.get_IR()) == rs(IR)) ||
		(RR_EX_reg.is_valid() &&
		 (is_ALUimm_inst(RR_EX_reg.get_IR()) ||
		  is_load_inst(RR_EX_reg.get_IR())) &&
		 rs(IR) != 0 && rt(RR_EX_reg.get_IR()) == rs(IR))) {

		IS_stall_f = true;			// stalling IS stage
		RR_stall_f = true;			// stalling RR stage
	    }

	}
	else if (opcode(IR) == 0x04 || opcode(IR) == 0x05) {	// BEQ/BNE

	    if ((RR_EX_reg.is_valid() &&
		 (is_ALU_inst(RR_EX_reg.get_IR()) ||
		  is_mfhilo_inst(RR_EX_reg.get_IR())) &&
		 ((rs(IR) != 0 && rd(RR_EX_reg.get_IR()) == rs(IR)) ||
		  (rt(IR) != 0 && rd(RR_EX_reg.get_IR()) == rt(IR)))) ||
		(RR_EX_reg.is_valid() &&
		 (is_ALUimm_inst(RR_EX_reg.get_IR()) ||
		  is_load_inst(RR_EX_reg.get_IR())) &&
		 ((rs(IR) != 0 && rt(RR_EX_reg.get_IR()) == rs(IR)) ||
		  (rt(IR) != 0 && rt(RR_EX_reg.get_IR()) == rt(IR))))) {

		IS_stall_f = true;			// stalling IS stage
		RR_stall_f = true;			// stalling RR stage
	    }

	}
	else if (opcode(IR) == 0x0 &&
		 (funct(IR) == 0x10 || funct(IR) == 0x12)) {	// MFHI/MFLO
	    if (RR_EX_reg.is_valid() &&
		is_muldiv_inst(RR_EX_reg.get_IR())) {

		IS_stall_f = true;			// stalling IS stage
		RR_stall_f = true;			// stalling RR stage
	    }
	}

	if (is_trap_inst(IR)) {		// syscall/break need pipeline flush
	    if (RR_EX_reg.is_valid() ||
		EX_MA_reg.is_valid() ||
		MA_WB_reg.is_valid()) {

		IS_stall_f = true;			// stalling IS stage
		RR_stall_f = true;			// stalling RR stage
	    }
	}

	if (RR_EX_reg.is_valid() && is_load_inst(RR_EX_reg.get_IR())) {
	    if (((is_ALU_inst(IR) || (is_muldiv_inst(IR))) &&
		 (rt(RR_EX_reg.get_IR()) == rs(IR) ||
		  rt(RR_EX_reg.get_IR()) == rt(IR))) ||
		((is_load_inst(IR) || is_store_inst(IR) ||
		  is_ALUimm_inst(IR) || is_branch_inst(IR)) &&
		 rt(RR_EX_reg.get_IR()) == rs(IR))) {

		IS_stall_f = true;			// stalling IS stage
		RR_stall_f = true;			// stalling RR stage
	    }
	    else if (is_branch_inst(IR) &&
		     rt(EX_MA_reg.get_IR()) == rs(IR)) {

		IS_stall_f = true;			// stalling IS stage
		RR_stall_f = true;			// stalling RR stage
	    }
	}
    }

    //
    // EX stage
    //
    if (RR_EX_reg.is_valid()) {
	sim_inst IR = RR_EX_reg.get_IR();
        if (is_muldiv_inst(IR) &&
            !MulDivUnit.is_ready()) {           // readiness check of mul/div unit

	    IS_stall_f = true;		// stalling IS stage
	    RR_stall_f = true;		// stalling RR stage
	    EX_stall_f = true;		// stalling EX stage
        }
        else if (is_mfhilo_inst(IR) &&
                 !MulDivUnit.is_done()) {       // completion check of mul/div operation

	    IS_stall_f = true;		// stalling IS stage
	    RR_stall_f = true;		// stalling RR stage
	    EX_stall_f = true;		// stalling EX stage
        }
    }

    //
    // MA stage
    //
    if (EX_MA_reg.is_valid()) {
	sim_inst IR = EX_MA_reg.get_IR();
	if ((is_load_inst(IR) || is_store_inst(IR)) &&
	    !dcache->is_done()) {

	    IS_stall_f = true;		// stalling IS stage
	    RR_stall_f = true;		// stalling RR stage
	    EX_stall_f = true;		// stalling EX stage
	    MA_stall_f = true;		// stalling MA stage
	}
    }

    //
    // WB stage
    // (no interlock)
    //
}

ここまで出来たところで、データハザードに対応できるか動作テストを行う。
以下のテストプログラム test2 を使うとよい。
アセンブリソース/ 逆アセンブルリスト/ ダンプテキストファイル

文責：大津

計算機アーキテクチャ特論 レポート課題 (ヒント)

課題1. 命令パイプラインシミュレータの作成

計算機アーキテクチャ特論レポート課題 (ヒント)