Path Grouping and Data Dependence Relaxation for Software Pipelining

摘要

Software pipelining of loops with conditional branches remains a challenge. There are two antagonistic problems, transfer time minimization and the worst-case constraints. The paper presents a novel framework to address them without conflict. The key ideas are: (1) Path grouping, which splits paths into distinct groups based on their execution and transfer probabilities, so as to minimize the transfer time. (2) Data dependence relaxation, which avoids the worst-case constraints by respecting data dependencies only when they have instances. Analysis suggests that the approach has better temporal benefit than that of path splitting and as-a-whole scheduling. A useful classification of existing algoirthms is also provided.