Optimal software pipelining with function unit and register constraints
Erik Altman · eScholarship@McGill (McGill) · 1995
This dissertation is concerned with software pipelining in the presence of resource constraints--both register and function unit. Software pipelining attempts to combine or schedule operations from different iterations of a loop into a new loop body which can execute as fast as possible or rate-optimally on a given architecture. Approaches for software pipelining can be categorized as exact--meaning the approach guarantees it will find a rate-optimal schedule--or inexact meaning the approach makes no such guarantee. This thesis proposes two novel and exact approaches. One approach represents the software pipelining problem as an Integer Linear Programming (ILP) problem. A unified framework is developed that includes both function unit and register constraints. This framework can represent both fully pipelined function units as well as function units with structural hazards. In the latter case, difficulties in mapping instructions to function units are identified and a solution developed. Our other software pipelining approach is to enumerate a sufficiently large set of schedules so as to guarantee inclusion of a rate-optimal, minimum register schedule fitting the target architecture. As the set of legal schedules is often large or infinite, drastic pruning is required to make this approach feasible. Requirements for this pruning are developed which insure that the enumerated set still contains all schedules of interest. Both the enumeration and ILP approaches are easily adapted to handle resource minimization, making them suitable for use in synthesis and architectural definition as well as in compilers. A powerful tested containing over 35,000 lines of C code was constructed to evaluate the proposed approaches against each other, as well as to compare them to a set of leading inexact methods. Performance was compared on over 1000 benchmark loops. For a significant number of the loops, use of the proposed ILP and enumeration techniques resulted in schedules that were faster and/or used fewer registers than the inexact methods.