A code motion pruning technique for global scheduling

L.C.V. Santos, dos, M.J.M. Heijligers, C.A.J. Eijk, van, J.T.J. Eijndhoven, van, J.A.G. Jess

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
1 Downloads (Pure)

Abstract

In the high-level synthesis of ASICs or in the code generation for ASIPs, the presence of conditionals in the behavioral description represents an obstacle to exploit parallelism. Most existing methods use greedy choices in such a way that the search space is limited by the applied heuristics. For example, they might miss opportunities to optimize across basic block boundaries when treating conditional execution. We propose a constructive method which allows generalized code motions. Scheduling and code motion are encoded in the form of a unified resource-constrained optimization problem. In our approach many alternative solutions are constructed and explored by a search algorithm, while optimal solutions are kept in the search space. Our method can cope with issues like speculative execution and code such duplication. Moreover, it can tackle constraints imposed by the advance choice of a controller, such as pipelined-control delay and limited branch capabilities. The underlying timing models support chaining and multicycling. As tasking code motion into account may lead to a larger search space, a code-motion pruning technique is presented. This pruning is proven to keep optimal solutions in the search space for cost functions in terms of schedule lengths.
Original languageEnglish
Pages (from-to)1-38
Number of pages38
JournalACM Transactions on Design Automation of Electronic Systems
Volume5
Issue number1
DOIs
Publication statusPublished - 2000

Fingerprint Dive into the research topics of 'A code motion pruning technique for global scheduling'. Together they form a unique fingerprint.

  • Cite this

    Santos, dos, L. C. V., Heijligers, M. J. M., Eijk, van, C. A. J., Eijndhoven, van, J. T. J., & Jess, J. A. G. (2000). A code motion pruning technique for global scheduling. ACM Transactions on Design Automation of Electronic Systems, 5(1), 1-38. https://doi.org/10.1145/329458.329461