# DynamicScheduling **Repository Path**: lwhengbit/dynamic-scheduling ## Basic Information - **Project Name**: DynamicScheduling - **Description**: Dynamic Scheduling technology which Based on RISC-V - **Primary Language**: Python - **License**: GPL-3.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2021-11-09 - **Last Updated**: 2023-11-13 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # DynamicScheduling ## 1. 程序功能 - 实现对基本块的5级流水情况下的运行情况分析 ## 2. 实现思路 - 约定延迟同*Computer Architecture--A Quantitative Approach* 书中延迟相同 - 使用DAG图描述基本块指令之间的相关性 - 其中顶点为每条指令，边为存在相关的指令之间的延迟，使用邻接矩阵存储DAG图 - 例如对于测试集： ```assembly Loop: fld f0, 0(x1) fld f2, -8(x1) fadd.d f4, f0, f1 fadd.d f6, f2, f1 fsd f4, 0(x1) fsd f6, -8(x1) addi x1, x1, -16 bne x1, x2, Loop ``` - 对应的DAG图为 ``` [0, 1, 0, 0, 1, 0, 0, 0] [0, 0, 2, 0, 0, 2, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 1, 0, 0, 0] [0, 0, 0, 0, 0, 2, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1] [0, 0, 0, 0, 0, 0, 0, 0] ``` - 对应的输出为 ```assembly Loop:fld f0, 0(x1) fld f2, -8(x1) fadd.d f4, f0, f1 fadd.d f6, f2, f1 Stall fsd f4, 0(x1) fsd f6, -8(x1) addi x1, x1, -16 Stall bne x1, x2, Loop ``` ## 3. 实现细节 - InstructionAnalysis - 提供RISC-V寄存器名 - 提供延迟约定 - 提供单条指令拆分功能 ```python class InstructionAnalysis: """ 存储寄存器号到寄存器ABI名的映射 """ index2RegABIName = { 0: "zero", # 0 1: "ra", 2: "sp", 3: "gp", 4: "tp", 5: "t0", 6: "t1", 7: "t2", 8: ["s0", "fp"], 9: "s1", 10: "a0", 11: "a1", 12: "a2", 13: "a3", 14: "a4", 15: "a5", 16: "a6", 17: "a7", 18: "s2", 19: "s3", 20: "s4", 21: "s5", 22: "s6", 23: "s7", 24: "s8", 25: "s9", 26: "s10", 27: "s11", 28: "t3", 29: "t4", 30: "t5", 31: "t6", 32: "t7", } """ 存储寄存器号到寄存器名的映射 """ index2RegName = { 0: "x0", 1: "x1", 2: "x2", 3: "x3", 4: "x4", 5: "x5", 6: "x6", 7: "x7", 8: "x8", 9: "x9", 10: "x10", 11: "x11", 12: "x12", 13: "x13", 14: "x14", 15: "x15", 16: "x16", 17: "x17", 18: "x18", 19: "x19", 20: "x20", 21: "x21", 22: "x22", 23: "x23", 24: "x24", 25: "x25", 26: "x26", 27: "x27", 28: "x28", 29: "x29", 30: "x30", 31: "x31", 32: "x32", } instructionOpcode = ['fld', 'fsd', 'fadd.d', 'addi', 'bne'] instructionOpcode3 = ['fld', 'fsd'] latenceSet = {'fld': {'fsd': 0, 'fadd.d': 1}, 'fsd': 0, 'fadd.d': {'fadd.d': 3, 'fsd': 2}, 'bne': 1, 'addi': 1 } def __init__(self): self.regName = [k for k, v in self.reverse_dict(self.index2RegName).items()] self.regABIName = [k for k, v in self.reverse_dict(self.index2RegABIName).items()] pass def reverse_dict(self, d): """ 字典key, value值互换函数 """ reverse_d = {} for k, v in d.items(): if isinstance(v, list): for temp in v: reverse_d[temp] = k else: reverse_d[v] = k return reverse_d def instructionSplit(self, ist): print(str(ist).strip().replace(", ", ",").replace(" ,", ",")) return str(ist).strip().replace(", ", ",").replace(" ,", ",").replace('(', " ").replace(")", " ").replace(",", " ").split(" ") ``` - DynamicScheduling - 读取指令，并拆分 - 分析指令并构造DAG图 - 根据DAG图，输出指令阻塞情况 ```python from InstructionAnalysis import InstructionAnalysis class DynamicScheduling: instructionAnalysis = InstructionAnalysis() instructions = [] instructionsSplitList = [] graphDAG = [] stallTimes = [] def __init__(self): print(self.instructionAnalysis.regName) print(self.instructionAnalysis.regABIName) pass def readCode(self, filename): """ Args: filename:汇编文件 Returns:没有返回，设置instructions和instructionsSplitList """ tempIstList = [] for i in open(filename): i = i.strip() tempIstList.append(i) tempIstList = [ist for ist in tempIstList if ist != ""] for i in range(1, len(tempIstList)): if ":" in tempIstList[i]: continue elif ":" in tempIstList[i-1]: self.instructions.append(tempIstList[i-1] + tempIstList[i]) else: self.instructions.append(tempIstList[i]) for ist in self.instructions: self.instructionsSplitList.append([i for i in self.instructionAnalysis.instructionSplit(ist) if i != ""]) for i in range(0,len(self.instructions)): self.graphDAG.append([0 for i in self.instructions]) self.stallTimes.append([0 for i in self.instructions]) def BuildDAG(self, instructionsSplitList): print(len(self.instructionsSplitList)) print(len(self.instructions)) # print(len(instructionsSplitList), end=' :\n') for i in range(0, len(instructionsSplitList)): for j in range(i+1, len(instructionsSplitList)): print(instructionsSplitList[i], end=' :\n') print(instructionsSplitList[j]) opt_forword = '' opt_backword = '' for opt in self.instructionAnalysis.instructionOpcode: if opt in self.instructions[i]: opt_forword = opt if opt in self.instructions[j]: opt_backword = opt print(opt_forword, end="-->") print(opt_backword) if isinstance(self.instructionAnalysis.latenceSet[opt_forword], dict): if opt_backword in self.instructionAnalysis.latenceSet[opt_forword]: if instructionsSplitList[i][1] in instructionsSplitList[j]: tempIndex = instructionsSplitList[j].index(instructionsSplitList[i][1]) judgeIndex = 1 if opt_backword == 'fsd': judgeIndex = 0 if tempIndex != judgeIndex: self.graphDAG[i][j] = self.instructionAnalysis.latenceSet[opt_forword][opt_backword] # for temp in range(1, len(instructionsSplitList[i])): # if instructionsSplitList[i][temp] in instructionsSplitList[j]: # # if instructionsSplitList[j].index(instructionsSplitList[i][temp]) != 1: # self.graphDAG[i][j] = self.instructionAnalysis.latenceSet[opt_forword][opt_backword] elif isinstance(self.instructionAnalysis.latenceSet[opt_forword], int): self.graphDAG[i][j] = self.instructionAnalysis.latenceSet[opt_forword] # print(self.instructionAnalysis.latenceSet[opt_forword][opt_backword]) # print() # print() def PrintDAG(self, graph): for row in graph: print(row) def PrintScheduledInstructions(self): print(self.instructions[0]) for column in range(1, len(self.instructions)): for row in range(0, column): sum = 0 for temp_column in range(row + 1, column): for temp_row in range(0, column - 1): sum = sum + self.stallTimes[temp_row][temp_column] if self.graphDAG[row][column]-sum > column-(row+1): self.stallTimes[row][column] = self.graphDAG[row][column] - (column-row-1) print("Stall\n"*(self.graphDAG[row][column] - (column-row-1)), end='') print(self.instructions[column]) ```