软件流水是循环调度的重要方法.有分支循环的流水依然是个难题.现有算法可以分为4类:循环线性化、路径分离、整体调度和路径选择.它们都未能和谐地解决两个对立问题:转移时间最小化和最差约束问题.提出了基于路径分组和数据相关松弛的软件流水框架,试图无矛盾地解决上述问题.其主要思想是:(1)路径分组，即按照路径的执行概率和转移概率将路径分组,力求最小化转移时间;(2)数据相关松弛,力求避免最差约束，即当循环有多条路径时,有些相关在循环执行中并不一定有实例，理想的策略是仅当它有实例时才遵守.初步实验和定性分析表明,此

Software pipelining is an effective approach of loop scheduling. Pipelining of loops with conditional branches remains a challenge. Current algorithms are divided into four classes: loop linearizaton, path splitting, as-a-whole scheduling and path selecting. All of them fail to solve concurrently two conflicting problems: transfer time minimization and worst-case constraints. In this paper, a novel software pipelining framework is presented to do so. The key ideas are: (1) Path grouping, which splits paths into distinct groups based on their execution and transfer probability, so as to minimize transfer time; (2) Data dependence relaxation. Some data dependences may not have instances during execution when the loop has multiple paths. The ideal policy is to obey them only when they have instances. Thus the worst-case constraints are avoided. Preliminary experiments and qualitative analysis all suggest that the temporal benefit of the proposed approach is better than that of path splitting and as-a-whole scheduling.

国家自然科学基金资助项目(69773028)