Heuristics for register-constrained software pipelining
Heuristics for register-constrained software pipelining
复制标题
寄存器受限软件流水线的启发式方法
DOI：
10.1109/micro.1996.566466
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
E. Ayguadé
中科院分区：
文献类型：
--
作者：
J. Llosa;M. Valero;E. Ayguadé
软件流水线是一种循环调度技术，它通过重叠几个连续迭代的执行来从循环中提取并行性。为了在资源约束下生成吞吐量最优调度，以及最近在最小寄存器要求下生成吞吐量最优调度，已经进行了大量的工作。遗憾的是，如果需要的寄存器比目标机器上可用的寄存器多，那么即使是具有最低寄存器需求的吞吐量优化调度也是无用的。本文评价了几种产生寄存器受限模运算表的技术：增加初始化间隔(II)和增加溢出代码。我们表明，一般来说，增加II的性能很差，并且可能在某些循环中不收敛。本文还提出了一种适用于任何软件流水线技术的迭代溢出机制，并提出了几种加速调度过程的启发式算法。
Software Pipelining is a loop scheduling technique that extracts parallelism from loops by overlapping the execution of several consecutive iterations. There has been a significant effort to produce throughput-optimal schedules under resource constraints, and more recently to produce throughput-optimal schedules with minimum register requirements. Unfortunately even a throughput-optimal schedule with minimum register requirements is useless if it requires more registers than those available in the target machine. This paper evaluates several techniques for producing register-constrained modulo schedules: increasing the initiation interval (II) and adding spill code. We show that, in general, increasing the II performs poorly and might not converge for some loops. The paper also presents an iterative spilling mechanism that can be applied to any software pipelining technique and proposes several heuristics in order to speed-up the scheduling process.