一种受限资源的软件流水滚动调度算法

Resource-constrained rotation scheduling algorithm for software pipelining

在VLIW处理器程序设计时,良好的手动汇编通常比复杂的编译器能够更有效地解决实际问题,但手动编码是一项易出错、耗时的工作,为了有效地实现手动编码,提出了一种手动编码的启发式实现方法,循环可以用数据流图(DFG)来表达,而每种DFG代表了一种调度,根据DFG可以建立一张带资源限制的调度表,通过对表的滚动(隐式重定时),可以逐步实现更紧凑的调度,同时尽可能多地预先罗列出算法的多种调度方案,以选择其中最佳的方案.该方法相对于单纯的手动编码和复杂的编译器能够在更短的时间内实现算法,并能达到最优的并行效果.

In programming for VLIW-type processors, excellent hand-coding method is more efficient than sophisticated compilers. But hand-coding method is error-prone and time consuming. For realizing hand-coding efficiently, a novel method based on a framework of scheduling heuristics was presented. A loop was modeled as a data flow graph (DFG) where each DFG represented a kind of scheduling. DFG was used to build a resource-constrained pipelining scheduling table. Adoption of a rotation technology (also called implicit retiming) on the scheduling table, a complex schedule was transformed to a more compact schedule. It is necessary to explore as many as possible scheduling algorithms in determining the optimal scheduling. The methodology helps to produce more efficient code in a shorter time compared to simple hand-coding approaches as well as sophisticated compilers, and can achieve the best parallel result.