周知编译原理龙书阐述的基本块指令调度算法，它所使用的空的资源预约表RTD与每个指令的资源预约表RT，可以看作二维矩阵，行表示时钟周期、列表示cpu资源，其定位的元素值1表示占用/预约，0表示空闲/非预约。前者是随周期递增而动态扩大的矩阵，后者是固定尺寸(维数)的矩阵（指令花费周期与每周期预约资源皆已知）。在调度时，按带优先级比如关键路径的拓扑排序基本块内的指令，顺序选取一条指令Inst，计算每前驱发射周期加延迟的结果tmp，取所有tmp的最大值tmax作为Inst的发射周期，再判断处理器资源是否可用，即RTD和RT作
与运算，得到一个新矩阵RTN，若RTN为
全零矩阵则tmax为Inst的最终发射周期，否则递增tmax再做矩阵与运算，直至得到全零矩阵。最后更新RTD，即RTD与RT作
或运算结果存于RTD。重复上述过程直到基本块末尾。
综上不难看出，如果一个基本块很大比如有1000条指令，平均每指令花2个周期，则RTD需要2000个条目，若一条目即矩阵每行占用32字节（256种资源数），则总量约64k。当然这对于现代内存体量来说不算什么，但可以有更好的节省内存的做法：RTD尺寸其实可以相对固定，其上限为基本块中耗费周期最多指令的周期的一个大于1常数因子倍（为兼顾指令并行性），这样一来就要增加当指令完成时（当前指令发射周期大于前一条的终止周期时复位前一条指令的RTD）从发射周期处复位RTD即作一个矩阵反运算的操作，其它步骤对应的矩阵与、矩阵或运算的操作保留不变。另由于RTD固定了尺寸，因此发射周期递增后要取模
【备注】以上是我针对简单机器模型（每种资源数量仅一个，比如整数运算单元1个，内存访问单元1个，浮点运算单元1个）用布尔矩阵作的优化。如果是复杂的超标量机器即每种资源数有多个，那么只需修改如下：布尔矩阵换成整数矩阵；新增一个机器资源可用总数整数矩阵RDA（单列资源数同值），布尔矩阵与运算换成加法并与RDA比较，若大于RDA则递增tmax；布尔矩阵或运算换成加法；布尔矩阵反运算换成减法，RTD减RT存于RTD
posted on 2023-09-23 12:14
春秋十二月 阅读(337)
评论(0) 编辑 收藏 引用 所属分类:
Compiler