Tomasulo/Tomasulo.py

import prettytable as pt
import pandas as pd
import numpy as np

# 循环次数 (循环一直执行的话，会导致访问的寄存器R地址超出限制）
loop_num = 3
# 初始化
# 整数寄存器
R = [i for i in range(32)]
# 浮点寄存器
F = [2.0 * i for i in range(16)]
# 内存（只有1024个单元）
Mem = [i for i in range(1024)]

# 跳转label对应的PC值 dictionary数据结构
label2pc = {}
# 记录真实执行的程序指令
prgm_real = []

# 每个操作对应的功能单元
op2fun = {"L.D": "Load", "MUL.D": "Mult", "S.D": "Store", "DADDUI": "Add", "BNE": "Add",
         "SUB.D": "Add", "DIV.D": "Mult", "ADD.D": "Add"}
# 每个功能单元执行时间
funtime = {"L.D": "1", "MUL.D": "10", "S.D": "1", "DADDUI": "2", "BNE": "1",
          "SUB.D": "2", "DIV.D": "40", "ADD.D": "2"}
# 功能单元名称
fuName = ["Load1", "Load2", "Add1", "Add2", "Add3", "Mult1", "Mult2", "Store1", "Store2"]
# 每个操作对应的操作符
op2char = {"MUL.D": "*", "DADDUI": "+", "SUB.D": "-", "DIV.D": "/", "ADD.D": "+"}


# 初始化 
def init(prgm):
    # 生成 InstructionStatus指令状态表
    InsS = []
    # 生成ReservationStations保留站
    ResS = pd.DataFrame(np.empty([9, 9], str),
                        index=fuName,
                        columns=["Busy", "Op", "Vj", "Vk", "Qj", "Qk", "A", "Time", "InsNum"])
    ResS['Busy'] = "No"

    # 生成RegisterStatus寄存器状态表
    RegS = pd.DataFrame(np.empty([1, 16], str),
                        index=["Qi"], columns=["F" + str(i) for i in range(0, 16, 2)] + ["R" + str(i) for i in range(0, 8, 1)])

    return 0, InsS, ResS, RegS


# 指令译码
def DecIns(ins):
    # 如果有Loop标签指令 从指令中去除Loop再进行译码
    if ins.find("Loop: ") != -1:
        ins = ins.replace("Loop: ", "")
    ins = ins.replace(",", " ")
    ins = ins.replace("(", " ")
    ins = ins.replace(")", "")
    ins = ins.split(" ")

    op = ins[0]
    dest = ins[1]
    s1 = ins[2]
    s2 = ins[3]

    return op, dest, s1, s2


# 为指令分配功能部件
def GetFU(op, ResS):
    fu = op2fun[op]

    # 对应Load部件
    if fu == "Load":
        if ResS.loc["Load1", "Busy"] == "No":
            fu = "Load1"
        elif ResS.loc["Load2", "Busy"] == "No":
            fu = "Load2"
        else:
            fu = ""  # 没有空闲部件，则返回空字符串
    # 对应Add部件
    elif fu == "Add":
        if ResS.loc["Add1", "Busy"] == "No":
            fu = "Add1"
        elif ResS.loc["Add2", "Busy"] == "No":
            fu = "Add2"
        elif ResS.loc["Add3", "Busy"] == "No":
            fu = "Add3"
        else:
            fu = ""
    # 对应Mult部件
    elif fu == "Mult":
        if ResS.loc["Mult1", "Busy"] == "No":
            fu = "Mult1"
        elif ResS.loc["Mult2", "Busy"] == "No":
            fu = "Mult2"
        else:
            fu = ""
    # 对应Store部件
    else:
        if ResS.loc["Store1", "Busy"] == "No":
            fu = "Store1"
        elif ResS.loc["Store2", "Busy"] == "No":
            fu = "Store2"
        else:
            fu = ""
    return fu


# 根据指令编号，找到在ResS中正在执行该指令的功能部件
def GetFUbyNum(insnum, ResS):
    for name in fuName:
        if ResS.loc[name, "InsNum"] == insnum:
            fu = name
            return fu


# 指令发射
def Issue(ins, insnum, clk, InsS, ResS, RegS):
    op, dest, s1, s2 = DecIns(ins)
    fu = GetFU(op, ResS)

    # 如果功能部件为busy，直接返回
    if fu != "":
        InsS.append(["" for j in range(3)])
        InsS[insnum][0] = clk  # 指令状态表登记该指令Issue的时间
        ResS.loc[fu, "InsNum"] = insnum  # insnum项标记该功能部件是哪条指令在使用，方便后续操作直接根据该指令找到部件
        ResS.loc[fu, "Busy"] = "Yes"
        ResS.loc[fu, "Op"] = op  # Op记录的即为fu去除后面的编号

        if fu.find("Store") != -1:  # store指令
            # 计算store的内存地址
            addr = int(dest) + R[int(R[int(s1.replace("R", ""))])]  # 寄存器间接寻址
            ResS.loc[fu, "Vj"] = "#%s" % addr
            # 判断WAW冲突
            if RegS.loc["Qi", s2] == "":
                ResS.loc[fu, "Qk"] = "#%s" % F[int(s2.replace("F", "")) // 2]
            else:
                ResS.loc[fu, "Qk"] = RegS.loc["Qi", s2]
        elif fu.find("Load") != -1: # load指令
            # 记录目的寄存器
            RegS.loc["Qi", dest] = fu
            # 计算地址
            addr = int(s1) + R[int(R[int(s2.replace("R", ""))])]  # 寄存器间接寻址
            # 直接写地址立即数
            ResS.loc[fu, "A"] = "#%s" % addr
        elif ins.find("BNE") != -1: # BNE指令
            # 判断dest是否有效
            if RegS.loc["Qi", dest] == "":
                if dest.find("F") != -1:
                    ResS.loc[fu, "Vj"] = "#%s" % F[int(dest.replace("F", "")) // 2]
                elif s1.find("R") != -1:
                    ResS.loc[fu, "Vj"] = "#%s" % R[int(dest.replace("R", ""))]
            else:
                ResS.loc[fu, "Qj"] = RegS.loc["Qi", dest]
            # 判断s1是否有效
            if RegS.loc["Qi", s1] == "":
                if s1.find("F") != -1:
                    ResS.loc[fu, "Vk"] = "#%s" % F[int(s1.replace("F", "")) // 2]
                elif s1.find("R") != -1:
                    ResS.loc[fu, "Vk"] = "#%s" % R[int(s1.replace("R", ""))]
            else:
                ResS.loc[fu, "Qk"] = RegS.loc["Qi", s1]
        else:# 其他指令
            # 判断s1操作数是否有效
            if RegS.loc["Qi", s1] == "":
                if s1.find("F") != -1:
                    ResS.loc[fu, "Vj"] = "#%s" % F[int(s1.replace("F", "")) // 2]
                elif s1.find("R") != -1:
                    ResS.loc[fu, "Vj"] = "#%s" % R[int(s1.replace("R", ""))]
            else:
                ResS.loc[fu, "Qj"] = RegS.loc["Qi", s1]
            # 判断s2操作数是否有效
            if s2.find("#") != -1: # 立即数
                ResS.loc[fu, "Vk"] = s2
            elif RegS.loc["Qi", s2] == "": # 或为F寄存器值
                ResS.loc[fu, "Vk"] = "#%s" % F[int(s2.replace("F", "")) // 2]
            else:
                ResS.loc[fu, "Qk"] = RegS.loc["Qi", s2]
            # 写入目的寄存器
            RegS.loc["Qi", dest] = fu


    return InsS, ResS, RegS


# 指令执行
def Execute(ins, insnum, clk, InsS, ResS):
    op, dest, s1, s2 = DecIns(ins)
    fu = GetFUbyNum(insnum, ResS)

    # 当前指令尚未开始执行，则判断是否就绪，若未就绪则继续等待
    if ResS.loc[fu, "Time"] == "":
        if ResS.loc[fu, "Qj"] == "" and ResS.loc[fu, "Qk"] == "":
            ResS.loc[fu, "Time"] = funtime[op]
    else:
        ResS.loc[fu, "Time"] = str(int(ResS.loc[fu, "Time"]) - 1)
        if ResS.loc[fu, "Time"] == "0":
            InsS[insnum][1] = clk
            ResS.loc[fu, "Time"] = ""
    return InsS, ResS


# 写回数据
def WriteResult(ins, insnum, clk, InsS, ResS, RegS, PC):
    op, dest, s1, s2 = DecIns(ins)
    fu = GetFUbyNum(insnum, ResS)

    # 记录时钟
    InsS[insnum][2] = clk
    # Busy位置为no，则释放该功能部件
    ResS.loc[fu, "Busy"] = "No"
    # 寄存器状态表写回
    if fu.find("Load") != -1:  # 对于load指令
        RegS.loc["Qi", dest] = ""
        F[int(dest.replace("F", "")) // 2] = Mem[int(float(ResS.loc[fu, "A"].replace("#", ""))//1)]
        result = "#%s" % str(F[int(dest.replace("F", "")) // 2])
    elif fu.find("Store") != -1:  # 对于store指令，不对表执行任何操作
        Mem[int(ResS.loc[fu, "Vj"].replace("#", ""))] = float(ResS.loc[fu, "Vk"].replace("#", ""))//1
    elif ins.find("BNE") != -1:
        if ResS.loc[fu, "Vj"] != ResS.loc[fu, "Vk"]:    # 当s1和dest不相等时跳转
            PC = label2pc[s2]
    else:
        # 其他指令
        RegS.loc["Qi", dest] = ""
        if op2char[op] == "+":
            dest_result = float(ResS.loc[fu, "Vj"].replace("#", "")) + float(ResS.loc[fu, "Vk"].replace("#", ""))
        elif op2char[op] == "-":
            dest_result = float(ResS.loc[fu, "Vj"].replace("#", "")) - float(ResS.loc[fu, "Vk"].replace("#", ""))
        elif op2char[op] == "*":
            dest_result = float(ResS.loc[fu, "Vj"].replace("#", "")) * float(ResS.loc[fu, "Vk"].replace("#", ""))
        elif op2char[op] == "/":
            dest_result = float(ResS.loc[fu, "Vj"].replace("#", "")) / float(ResS.loc[fu, "Vk"].replace("#", ""))
        if dest.find("F") != -1:
            F[int(dest.replace("F", "")) // 2] = dest_result
        elif dest.find("R") != -1:
            R[int(dest.replace("R", ""))] = dest_result
        result = "#%s" % str(dest_result)
    # DBS广播数据
    for fuitem in fuName:
        # 遍历 ReservationStations的每行，找有无使用到当前写回结果的值
        if ResS.loc[fuitem, "Qj"] == fu:
            ResS.loc[fuitem, "Qj"] = ""
            ResS.loc[fuitem, "Vj"] = result
            # 广播该值后，该部件若数据已就绪可以执行，则开始计时
            if ResS.loc[fuitem, "Qk"] == "" and ResS.loc[fuitem, "Time"] == "":
                ResS.loc[fuitem, "Time"] = funtime[ResS.loc[fuitem, "Op"]]

        if ResS.loc[fuitem, "Qk"] == fu:
            ResS.loc[fuitem, "Qk"] = ""
            ResS.loc[fuitem, "Vk"] = result
            # 广播该值后，该部件若数据已就绪可以执行，则开始计时
            if ResS.loc[fuitem, "Qj"] == "" and ResS.loc[fuitem, "Time"] == "":
                ResS.loc[fuitem, "Time"] = funtime[ResS.loc[fuitem, "Op"]]

    return PC, InsS, ResS, RegS


# 输出表格
def printTumasulo(prgm, InsS, ResS, RegS):
    # InstructionStatusTable
    print("-----------------------------------------------------------------------")
    for item in ["Instruction", "Issue", "Execute", "Write result"]:
        print("{0: >16}".format(item), end='')
    print()
    for i in range(min(len(InsS),loop_num*(len(prgm)-1))):
        print("{0: >16}".format(prgm_real[i]), end='')
        for j in InsS[i]:
            print("{0: >16}".format(j), end='')
        print()
    print()  
    # ReservationStationsTable
    print("-------------------------------------------------------------------------------")
    print("{0: >10}".format(" "), end='')
    for item in ["Busy", "Op", "Vj", "Vk", "Qj", "Qk", "A"]:
        print("{0: >10}".format(item), end='')
    print()
    ResList = ResS.values.tolist()
    for i in range(len(ResList)):
        print("{0: >10}".format(fuName[i]), end='')
        for j in range(7):
            print("{0: >10}".format(ResList[i][j]), end='')
        print()
    print()  
    # RegisterStatus
    print("-------------------------------------------------------------------------------------------------------------")
    for item in ["Feild", "F0", "F2", "F4", "F6", "F8", "F10", "F12", "F14", "R0", "R1", "R2", "R3", "R4",
                         "R5", "R6", "R7"]:
        print("{0: >6}".format(item), end='')
    print()
        
    print("{0: >6}".format("Qi"), end='')
    for i in range(len(RegS.values.tolist())):
        print("{0: >6}".format(RegS.values.tolist()[0][i]), end='')
    print()
    print("-------------------------------------------------------------------------------------------------------------")


# 所有指令是否全部执行完
def PrgmFinish(InsS, prgm):
    # for i in range(len(prgm_real)):
    for i in range(loop_num*(len(prgm)-1)):
        for j in range(3):
            if InsS[i][j] == "":
                return False
    return True


if __name__ == '__main__':
    # 待执行指令程序
    prgm = ["Loop: L.D F0,0(R1)",
            "MUL.D F4,F0,F2",
            "S.D 0(R1),F4",
            "DADDUI R1,R1,#-8",
            "BNE R1,R2,Loop",
            "End"]

    # 初始化
    clk, InsS, ResS, RegS = init(prgm)
    PC = 0
    # 时钟周期驱动 每次循环一个时钟
    while True:
        clk += 1
        # 对跳转分支的标签记录PC
        if prgm[PC].find("Loop") == 0:
            label2pc["Loop"] = PC
            prgm[PC] = prgm[PC].replace("Loop: ", "")
        # 第一个周期 只流出第一条指令
        if clk == 1:
            # 指令流出 issue
            InsS, ResS, RegS = Issue(prgm[PC], PC, clk, InsS, ResS, RegS)
            prgm_real.append(prgm[PC])
            PC += 1
        else:
            # 根据已发射的指令各阶段完成状态 决定 指令当前周期处于哪个执行阶段
            for i in range(len(InsS) - 1, -1, -1):
                if InsS[i][1] == "":
                    # 执行 ex
                    InsS, ResS = Execute(prgm_real[i], i, clk, InsS, ResS)
                elif InsS[i][2] == "":
                    # 写结果 write result
                    PC, InsS, ResS, RegS = WriteResult(prgm_real[i], i, clk, InsS, ResS, RegS, PC)
            # 要不要发射新指令
            if prgm[PC] != "End" and (PC == 0 or InsS[PC - 1][0] != ""):
                # 发射新指令 issue
                InsS, ResS, RegS = Issue(prgm[PC], len(InsS), clk, InsS, ResS, RegS)
                prgm_real.append(prgm[PC])
                PC += 1

        print("clock:%d" % clk)
        #print("++---------------------------------------------------------------------------------------------------------++")
        printTumasulo(prgm, InsS, ResS, RegS)

        # 判断是否全部执行完
        if PrgmFinish(InsS, prgm):
            break