1 min to read

RRVM 编译器优化-software pipelining

Featured image

rrvm-software pipelining

本 Post 更类似于对龙书软流水的摘抄和理解，Sysyc 在实现上采用的是硬流水的方法，本 Post 并无实现对应

必要性

对于循环指令，在循环展开的基础上用软流水来减少硬件流水线中 load 之后立即 alu 等情况，从而提高性能

龙书算法

数据依赖

假设第i次迭代中的运算 n_2 必须在第 i-alpha 次迭代中的运算 n_1 执行至少d个时钟周期后才可以执行，则给依赖边 n_1->n_2 加上标号 <alpha,d> 则 (alpha*T)+S(n2)-S(n1)>=d (T 为之前说的启动时间的间隔)

简化-无环数据依赖图

已知：机器的资源表示 R=[r1,r2,…,rn]，数据依赖图G=(N,E)，其中每个节点表示一个指令，每条边如上面的数据依赖所定义

  1. 求出理论上的最小启动间隔T_0 (比较简单，套用前面的公式)
  2. 对于T_0,对于按照优先级的拓扑顺序访问每个节点n,
    我们先按照数据依赖的约束求出一个最小的 s 为该运算相对于它所处迭代的开始时刻的执行时间，然后先从s到s+T_0-1，判断是否满足模数资源预约中的不等式条件，如果可以就找到了解法，否则将T_0<=T_0+1 重复上述过程

有环数据依赖图调度

if 比如说有环： (alpha1*T)+S(n_2)-S(n_1)>=d1
(alpha2*T)+S(n_1)-S(n_2)>=d2
then S(n_1)+d1-(alpha1*T)<=S(n_2)<=S(n_1)-d2+(alpha2*T) 考虑图的强连通分量，每个节点都可以从分量中其他节点到达，考虑对SCC中一个节点的调度： 存在一个从n_1到n_2的路径p，则有 \(S(n2)-S(n1)>=\sum_{e在p中}(d_e-(\alpha _e*T))\) 可以得出以下结论：

和无环数据依赖图调度相比有如下变化：

  1. 对于数据依赖图中一个环c， \(T_0>=max(\sum_{e in c}d_e/\sum_{e in c}\alpha _e) ---------------①\) 所以要满足 ① 和无环数据依赖图的两个约束条件
  2. 一开始需要求出E’={e|e in E,alpha_e=0}，和无环数据依赖图相比，调度单位为SCC（强连通分量）
    所以算法整体 belike: ``` for (T=T_0,T_0+1,…..,所有 resources 都被调度完毕)： E* = AllPairsLongestPath(G,T); // 以带优先级的拓扑顺序排序G中的SCC C for SCC C in G: for n in C: s0(n)=max_{e=p->n in E* with p scheduled}(S(p)+d_e); first=使得 s0(n) 取最小值的n; s0=s0(first); for s in range(s0,s0+T): if(SccScheduled(RT,T,C,first,s)) break; if C 不能在 RT 中调度 break

其中的SccScheduled belike: if not NodeScheduled: return false; for E’ 中各边的优先级的拓扑排序访问c中剩下的每一个n: S_l=max_{e=n’->n in E,n’ in c and n’ scheduled}(S(n’)+d_e-(alpha_eT)) S_u=min_{e=n’->n in E,n’ in c and n’ scheduled}(S(n’)-d_e+(alpha_eT)) for(s=S_l;s<=min(S_u,S_l+T-1);s++): if(NodeScheduled(RT’,T,n,s)) break; if n 不能在RT’中调度 return false; ```

模数变量扩展

如果一个变量的活跃范围在单个循环内，那么称该标量变量为可私有化的
变量扩展把一个可私有化标量变量转化为一个数组，让循环的第i次迭代读写第i个元素，可以消除数据依赖图中的环
if 一个寄存器生命周期为l时钟，启动间隔为T，则同一个时间点只有 $q=\left\lceil l/T\right\rceil$个变量是活跃的
算法改进：

  1. 先把和可私有化变量的相关的依赖关系删了
  2. 在1的基础上进行有环数据依赖图调度
  3. 对于每个可私有化变量v，计算q_v;令 Q=max(q_v);
  4. 生成经过软件流水线化过的循环中，分配给可私有化变量v的寄存器数目为 q_v’=(q_v if Q mod q_v==0 else Q) todo 考虑寄存器分配，e.g. caller save callee save 这步在寄存器分配之前先 precolored 这一步会把稳定时候的代码大小增加到原先q倍

和实际应用的差别