Morris' Blog

2013-06-25 16:56:26Morris

[計算機組織][作業] 模擬 pipeline

留言 0 收藏 0 推薦 0

輸入格式：
MIPS 32 bits instruction, 以字元的方式表示。
一行一個指令，直到 EOF。

助教會陸續公布不同的指令順序，其中會包含需要處理 data hazard, hazard with load and branch hazard, 每次公布的指令都會放在「.txt」檔中，並由同學們寫的模擬程式讀入。

輸出格式：
CC 1:

Registers:
$0: 0    $1: 1    $2: 2
$3: 3    $4: 4    $5: 5
$6: 6    $7: 7    $8: 8

Data memory:
0: 1
4: 2
8: 3
12: 4
16: 5

IF/ID:
PC                  4
Instruction         00000000001000110001000000100010

ID/EX:
A                   0
B                   0
sign_ext            0
Rs                  0
Rt                  0
Rd                  0
Control signals     000000000

EX/MEM:
ALUout              0
WriteData           0
Rd                  0
Control signals     00000

MEM/WB:
ReadData            0
ALUout              0
Control signals     00

=================================
簡約如上，根據每個 clock cycle 輸出當時狀態的記憶體與暫存器內容，以及 pipeline 中的情況。
直到指令達到結束(都是空指令)，初始化 $i = i

依照每次公布的指令順序，將結果分別寫入到「genResult.txt, dataResult.txt, loadResult.txt, branchResult.txt」中, 輸出格式請參照以下範例, 即印出在每個 clock cycle 時，各個 pipeline registers 所儲存的值。「Instruction, Control signals」以 binary number 表示，其餘以十進制(signed integer)。

程式碼說明 https://docs.google.com/file/d/0B7RwmWo93u-mTDYtZlYwYmluRnM/edit?usp=sharing

能交個樣子就好了, 管它屍體還是什麼的。

#include <stdio.h>
#include <string.h>
#include <map>
#include <iostream>
using namespace std;
struct Rtype {// lowbit -> hightbit
    unsigned int funct:6;
    unsigned int shamt:5;
    unsigned int rd:5;
    unsigned int rt:5;
    unsigned int rs:5;
    unsigned int opcode:6;
};
struct Itype {
    unsigned int immediate:16;
    unsigned int rt:5;
    unsigned int rs:5;
    unsigned int opcode:6;
};
struct Jtype {
    unsigned int address:26;
    unsigned int opcode:6;
};
union Instruction {
    unsigned int word;
    Rtype R;
    Itype I;
    Jtype J;
};
struct E {
    int type;
    Instruction code;
};
map<int, string> Rstr, Istr, Jstr;
void buildName() {
    string Rname[] = {"add", "addu", "sub", "subu","and",
        "or", "xor", "nor", "slt", "sll", "srl", "sra", "jr"};
    int funct[] = {0x20, 0x21, 0x22, 0x23, 0x24,
        0x25, 0x26, 0x27, 0x2A, 0x0, 0x2, 0x3, 0x8};
    for(int i = 0; i < 13; i++)
        Rstr[funct[i]] = Rname[i];

    string Iname[] = {"addi", "addiu", "lw", "sw", "andi",
        "ori", "slti", "beq", "bne"};
    int opcode[] = {0x8, 0x9, 0x23, 0x2B, 0xC,
        0xD, 0xA, 0x4, 0x5};
    for(int i = 0; i < 9; i++)
        Istr[opcode[i]] = Iname[i];

    Jstr[0x2] = "j";
    Jstr[0x3] = "jal";
}
void convertBinary(unsigned n, int m) {
    for(int i = m-1; i >= 0; i--)
        printf("%d", (n>>i)&1);
    puts("");
}
void pipelineProcess(E cmd[], int n) {
    int i, j, k;

    E path[4];
    memset(path, 0, sizeof(path));
    path[0] = cmd[0];
    int pathlevel[4] = {0,1,2,3};//IFID(0), IDEX(1), EXMEM(2), MEMWB(3)
    int pathctrl[4] = {0,0,0,0};
    int pathALU[4] = {0,0,0,0}, pathALU2[4] = {0,0,0,0};
    int pathmem[4] = {0,0,0,0};
    int pc = 1, CC = 0;
    const int regsize = 9, memsize = 5;
    unsigned int reg[regsize], mem[memsize];
    for(i = 0; i < regsize; i++)    reg[i] = i;
    for(i = 0; i < memsize; i++)    mem[i] = i+1;

    if(cmd[0].type == 'R') {
        pathctrl[0] = 386;
    } else if(cmd[0].type == 'I') {
        if(Istr[cmd[0].code.I.opcode] == "beq") {
            pathctrl[0] = 80;
        } else if(Istr[cmd[0].code.I.opcode] == "bne") {
            pathctrl[0] = 80;
        } else { // action for memory-reference
            if(Istr[cmd[0].code.I.opcode] == "lw") {
                pathctrl[0] = 43;
            } else // sw
                pathctrl[0] = 36;
        }
    } else
        pathctrl[0] = 0;
    int eofFlag = 0;
    bool stall = false;
    while(true) {
        if(eofFlag)
            break;
        if(path[0].code.word == 0 && path[1].code.word == 0
           && path[2].code.word == 0 && path[3].code.word == 0)
           eofFlag = 1;

        unsigned A, B;
        bool Aforward = false, Bforward = false;
        if(pathctrl[2]&2) { //EX/MEM.RegWrite
            if(pathctrl[2]&1) {
                if(path[1].code.R.rs == path[2].code.R.rt)
                    {Aforward = true, A = pathALU[2];}
                if(path[1].code.R.rt == path[2].code.R.rt)
                    {Bforward = true, B = pathALU[2];}
            } else {
                if(path[1].code.R.rs == path[2].code.R.rd)
                    {Aforward = true, A = pathALU[2];}
                if(path[1].code.R.rt == path[2].code.R.rd)
                    {Bforward = true, B = pathALU[2];}
            }
        }
        if(pathctrl[3]&2) { //MEM/WB.RegWrite
            if(pathctrl[3]&1) { // lw
                if(path[1].code.R.rs == path[3].code.R.rt && !Aforward)
                    {Aforward = true, A = pathALU2[3];}
                if(path[1].code.R.rt == path[3].code.R.rt && !Bforward)
                    {Bforward = true, B = pathALU2[3];}
            } else {
                if(path[1].code.R.rs == path[3].code.R.rd && !Aforward)
                    {Aforward = true, A = pathALU2[3];}
                if(path[1].code.R.rt == path[3].code.R.rd && !Bforward)
                    {Bforward = true, B = pathALU2[3];}
            }
        }

        if(path[1].code.R.rs == 0) Aforward = false;
        if(path[1].code.R.rt == 0) Bforward = false;
        if(!Aforward)   A = reg[path[1].code.R.rs];
        //else    puts("forwarding A");
        if(!Bforward)   B = reg[path[1].code.R.rt];
        //else    puts("forwarding B");
        printf("CC %d:\n\n", ++CC);
        printf("Registers:");
        for(i = 0; i < regsize; i++) {
            if(i%3 == 0) puts("");
            printf("$%d: %-5d", i, reg[i]);
        }   puts("\n");
        puts("Data memory:");
        for(i = 0; i < memsize; i++) {
            printf("%d: %d\n", i<<2, mem[i]);
        }   puts("");

        puts("IF/ID:");
        printf("%-20s%d\n", "PC", (pc+(stall == true))<<2);
        printf("%-20s", "Instruction"), convertBinary(path[0].code.word, 32), puts("");

        puts("ID/EX:");
        printf("%-20s%d\n", "A", A);
        printf("%-20s%d\n", "B", B);
        printf("%-20s%d\n", "sign_ext", path[1].type == 'I' ? path[1].code.I.immediate : 0);
        printf("%-20s%d\n", "Rs", path[1].code.R.rs);
        printf("%-20s%d\n", "Rt", path[1].code.R.rt);
        printf("%-20s%d\n", "Rd", path[1].code.R.rd);
        printf("%-20s", "Control signals"), convertBinary(pathctrl[1], 9), puts("");

        puts("EX/MEM:");
        printf("%-20s%d\n", "ALUout", pathALU[2]);
        printf("%-20s%d\n", "WriteData", (pathctrl[2]&4) ? reg[path[2].code.I.rt] : 0);
        if(pathctrl[2]&12) // lw/sw
            printf("%-20s%d\n", "Rt", path[2].code.R.rt);
        else
            printf("%-20s%d\n", "Rd", path[2].code.R.rd);
        printf("%-20s", "Control signals"), convertBinary(pathctrl[2], 5), puts("");

        puts("MEM/WB:");
        printf("%-20s%d\n", "ReadData", (pathctrl[3]&8) ? pathALU2[3] : 0);
        printf("%-20s%d\n", "ALUout", (pathctrl[3]&4) ? 0 : pathALU[3]);
        printf("%-20s", "Control signals"), convertBinary(pathctrl[3], 2), puts("");
        puts("=================================");
        getchar();
        if(pathctrl[3]&2) {//MEM/WB.RegWrite
            if(pathctrl[3]&1) {//MEM/WB.MemToReg == lw
                reg[path[3].code.R.rt] = pathALU2[3];
            } else {
                reg[path[3].code.R.rd] = pathALU2[3];
            }
            reg[0] = 0;
        }
        if(pathctrl[2]&4)//EX/MEM.MemWrite
            mem[pathALU[2]>>2] = reg[path[2].code.R.rt];
        else if(pathctrl[2]&8)//EX/MEM.MemRead
            pathALU2[2] = mem[pathALU[2]>>2];
        else
            pathALU2[2] = pathALU[2];

        path[3] = path[2], pathctrl[3] = pathctrl[2], pathALU[3] = pathALU[2], pathmem[3] = pathmem[2];
        pathALU2[3] = pathALU2[2];

        if(path[1].type == 'R') {
            if(Rstr[path[1].code.R.funct] == "add")
                pathALU[1] = A + B;
            if(Rstr[path[1].code.R.funct] == "sub")
                pathALU[1] = A - B;
            if(Rstr[path[1].code.R.funct] == "and")
                pathALU[1] = A & B;
            if(Rstr[path[1].code.R.funct] == "or")
                pathALU[1] = A | B;
        } else if(path[1].type == 'I') {
            if(Istr[path[1].code.I.opcode] == "beq") {
                if(A == B) {
                    pc += path[1].code.I.immediate - 1;
                    pathctrl[0] = 0;
                }
            } else if(Istr[path[1].code.I.opcode] == "bne") {
                if(A != B) {
                    pc += path[1].code.I.immediate - 1;
                    pathctrl[0] = 0;
                }
            } else { // action for memory-reference
                pathALU[1] = A + path[1].code.I.immediate;
            }
        } else if(path[1].type == 'J'){
            pc = pc + path[1].code.J.address;
        }

        path[2] = path[1], pathctrl[2] = pathctrl[1], pathALU[2] = pathALU[1], pathmem[2] = pathmem[1];

        path[1] = path[0], pathctrl[1] = pathctrl[0], pathALU[1] = pathALU[0], pathmem[1] = pathmem[0];

        path[0] = cmd[pc++], pathALU[0] = 0, pathmem[0] = 0;

        stall = false;//<test stall>
        if(pathctrl[1]&8) {//ID/EX.MemRead
            if(path[1].code.I.rt == path[0].code.I.rs ||
               path[1].code.I.rt == path[0].code.I.rt)
               stall = true;
        }
        if(stall) {
            memset(&path[0], 0, sizeof(path[0]));
            pathctrl[0] = 0;
            pc--;
            continue;
        }//</test stall>

        if(path[0].type == 'R') {
            pathctrl[0] = 386;
        } else if(path[0].type == 'I') {
            if(Istr[path[0].code.I.opcode] == "beq")
                pathctrl[0] = 80;
            else if(Istr[path[0].code.I.opcode] == "bne")
                pathctrl[0] = 80;
            else { // action for memory-reference
                if(Istr[path[0].code.I.opcode] == "lw")
                    pathctrl[0] = 43;
                else // sw
                    pathctrl[0] = 36;
            }
        } else
            pathctrl[0] = 0;
    }
}

int main() {
    char s[50];
    int cmdCount = 0;
    E cmd[1005];
    memset(cmd, 0, sizeof(cmd));
    buildName();// instruct name

    //freopen("General.txt", "r+t", stdin);
   //freopen("genResult.txt", "w+t", stdout);

    //freopen("Datahazard.txt", "r+t", stdin);
   //freopen("dataResult.txt", "w+t", stdout);

    //freopen("Lwhazard.txt", "r+t", stdin);
   //freopen("loadResult.txt", "w+t", stdout);

    //freopen("Branchazard.txt", "r+t", stdin);
   //freopen("branchResult.txt", "w+t", stdout);
    while(scanf("%s", s) == 1) {
        unsigned int code = 0;
        // read 10001100010000010000000000000110
        //    hightbit ------------------- lowbit
        for(int i = 0; s[i]; i++)
            code = (code<<1)|(s[i]-'0');
        cmd[cmdCount].code.word = code;
        if(cmd[cmdCount].code.R.opcode == 0)
            cmd[cmdCount].type = 'R';
        else if(cmd[cmdCount].code.R.opcode == 0x2 || cmd[cmdCount].code.R.opcode == 0x3)
            cmd[cmdCount].type = 'J';
        else
            cmd[cmdCount].type = 'I';
        cmdCount++;
    }
    for(int i = 0; i < cmdCount; i++) {
        printf("[%c] ", cmd[i].type);
        if(cmd[i].type == 'R') {
            printf("%-5s $%d, $%d, $%d\n", Rstr[cmd[i].code.R.funct].c_str(), cmd[i].code.R.rd,
                    cmd[i].code.R.rs, cmd[i].code.R.rt);
        } else if(cmd[i].type == 'I') {
            printf("%-5s $%d, $%d, 0x%x\n", Istr[cmd[i].code.I.opcode].c_str(), cmd[i].code.I.rt,
                    cmd[i].code.I.rs, cmd[i].code.I.immediate);
        } else {
            printf("%-5s 0x%x\n", Jstr[cmd[i].code.J.opcode].c_str(), cmd[i].code.J.address<<2);
        }
    }
    pipelineProcess(cmd, cmdCount);
    return 0;
}
/*
Type R:opcode(6)-rs(5)-rt(5)-rd(5)-shamt(5)-funct(6)
Type I:opcode(6)-rs(5)-rt(5)-immediate(16)
Type J:opcode(6)-address(26)
// lw $t, C($s)

//instrln.txt
10001100010000010000000000000110
00000000000000100001100000100000
00010100000000100000000000000110

lw $1, 6($2)
add $3, $0, $2
bne $0, $2, 0x6
(1) ip 4, fetch $2 = 2, immediate = 6 | final $1 = 3
(2) ip 8, fetch $0 = 0, $2 = 2 | final $3 = 2
(3) ip 12, fetch $0 = 0, $2 = 2, immediate = 6, do clear one instruction
(4) ip = 12 + 6*4 + 4 = 40, this is a "nop" ...

//general.txt
10001100001001100000000000000111
00000000010000110011100000100010
00000000100001010100000000100100

lw $6, 7($1)
sub $7, $2, $3
and $8, $4, $5
(1) ip = 4, fetch $1 = 1, immediate = 7 | final $6 = 3
(2) ip = 8, fetch $2 = 2, $3 = 3 | final $7 = -1
(3) ip = 12, fetch $4 = 4, $5 = 5 | final $8 = 4

//datahazard.txt
00000000001000110001000000100010
00000000010001010010000000100100
00000000100000100010000000100101

sub $2, $1, $3
and $4, $2, $5
or $4, $4, $2
(1) ip = 4, fetch $1 = 1, $3 = 3 | final $2 = -2
(2) ip = 8, fetch $2 = -2(forwarding), $5 = 5 | final $4 = 4
(3) ip = 12, fetch $4 = 4(forwarding), $2 = -2(forwarding) | final $4 = -2

//lwhazard.txt
10001100001000100000000000000111
00000000010001010010000000100100
00000000100000100010000000100101

lw   $2, 7($1)
and $4, $2, $5
or   $4, $4, $2
(1) ip = 4, fetch $1 = 1, immediate = 7 | final $2 = mem[8] = 3
(-) -- lw make stall. --
(2) ip = 8, fetch $2 = 3(forwarding), $5 = 5 | final $4 = 1
(3) ip = 12, fetch $4 = 1(forwarding), $2 = 3 | final $4 = 3

Note: (3) $2 don't need via forwarding, but internal forwarding
lw :|IF-|-|ID-|-|ALU|-|MEM|-|WB-|
nop:|___|-|IF-|-|ID-|-|ALU|-|MEM|-|WB-|
and:|___|-|___|-|IF-|-|ID-|-|ALU|-|MEM|-|WB-|
or :|___|-|___|-|___|-|IF-|-|ID-|-|ALU|-|MEM|-|WB-|

//branchazard.txt
00000000100000110001000000100010
00010000001000100000000000000010
00000000100001010001100000100100
00000000111010000011000000100101
10001100001001000000000000000111

sub $2, $4, $3
beq $1, $2, 2 (需跳躍的指令個數)
and $3, $4, $5
or   $6, $7, $8
lw $4, 7($1)
(1) ip = 4, fetch $4 = 4, $3 = 3 | final $2 = 1
(2) ip = 8, fetch $1 = 1, $2 = 1(forwarding) | final ip = 12 + 2*4 = 20
(-) ip = 12, because branch clear, make control all zeroes.
(3) ip = 20, fetch $1 = 1, immediate = 7 | final $4 = mem[8] = 3

//sw.txt
10101100010000010000000000000010

sw $1, 2($2)
*/

上一篇：[編譯器][作業] Predict Set

下一篇：[高等演算法][作業一] 討論

Morris' Blog

[計算機組織][作業] 模擬 pipeline

你可能感興趣的文章

英雄【繪本版】/作者郝廣才、繪者波森堤妮 — 英雄不怕年紀小，做大事不用等長大以後！

日記1125

實在忍不住，要插播一下

2024.11.25 赤腳

銅鑼生活第200週之3(2024/11/17)

Morris' Blog

[計算機組織][作業] 模擬 pipeline

你可能感興趣的文章

英雄【繪本版】/作者 郝廣才、繪者 波森堤妮 — 英雄不怕年紀小，做大事不用等長大以後！

日記1125

實在忍不住，要插播一下

2024.11.25 赤腳

銅鑼生活第200週之3(2024/11/17)

英雄【繪本版】/作者郝廣才、繪者波森堤妮 — 英雄不怕年紀小，做大事不用等長大以後！