© 1997 by British Computer Society
Resource-Directed Loop Pipelining: Exposing Just Enough Parallelism
Department of Information and Computer Science, University of California, Irvine, CA 92697-3425, USA Email: snovack{at}csrd.uiuc.edu
Many techniques have been proposed for exploiting instruction-level parallelism, ranging from the optimal and expensive but ignoring resource constraints, to various forms of introducing resource constraints. One of the most aggressive of these techniques is resource-constrained software pipelining (RCSP). RCSP works by repeatedly scheduling successive iterations of a loop in parallel until the data and resource dependence structure of the loop causes the process to converge on a repeating scheduling pattern. This repeating pattern is then used as the new loop body. In principle, this process can be made optimal with respect to full unrolling and scheduling of the loop. Of course, this is not the same as absolute optimality; however, given the NP-hard nature of the problem and the results of Schwiegelshohn et al., this may be the strongest form possible for general loop pipelining. The main drawback of RCSP is that, in practice, its space/time overhead can be fairly expensive. In this paper, we present resource-directed loop pipelining (RDLP), a new approach that attempts to retain many of the advantages of RCSP while minimizing the expense. It does so by allowing the availability of target resources to in some sense guide the application of parallelism exposing and parallelizing transformations. One of the key features of RDLP is the separation of control heuristics from transformations that allow the loop pipelining to be as general as the underlying system of code motion transformations. Results are presented which show that even with very unsophisticated heuristics, RDLP achieves roughly the same performance as RCSP, while providing a fourfold decrease in the space/time cost; moreover, we show that RDLP exposes ‘just enough’ parallelism–incurs a minimum of code explosion–to maximally utilize resources.
Received October 31, 1996. revised July 15, 1997.