Control-flow versus data-flow-based scheduling: combining both approaches in an adaptive scheduling system
- 1 March 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Very Large Scale Integration (VLSI) Systems
- Vol. 5 (1) , 82-100
- https://doi.org/10.1109/92.555989
Abstract
As high-level synthesis techniques gain acceptance among designers, it is important to be able to provide a robust system which can handle large designs in short execution times, producing high-quality results. Scheduling is one of the most complex tasks in high-level synthesis, and although many algorithms exist for solving the scheduling problem, it remains a main source of inefficiency by either not producing high-quality results, not taking into account realistic design requirements, or requiring unacceptable execution times. One of the main problems in scheduling is the dichotomy between control and data. Many algorithms to date have been able to provide scheduling solutions by looking only at either the data part or the control part of the design. This has been done in order to simplify the problem; however, it has resulted in many algorithms unable to handle efficiently large designs with complex control and data functionality. This paper presents algorithms for combining dataflow and control-flow techniques into a robust scheduling system. The main characteristics of this system are as follows: 1) it uses path-based techniques for efficient handling of control and mutual exclusiveness (for resource sharing), 2) it allows operation reordering and parallelism extraction within the context of path-based scheduling, 3) it contains a control partitioning algorithm for design space exploration as well as for reducing the number of control paths, and 4) it combines the above algorithms into an adaptive scheduling system which is capable of trading optimality for execution time on-the-fly. Results involving billions of paths are presented and analyzed.Keywords
This publication has 14 references indexed in Scilit:
- A graph-based silicon compiler for concurrent VLSI systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- AMICAL: An interactive high level synthesis environmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- High-level synthesis in an industrial environmentIBM Journal of Research and Development, 1995
- Experiments with low-level speculative computation based on multiple branch predictionIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1993
- Timing analysis in high-level synthesisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Scheduling under resource constraints and module assignmentIntegration, 1991
- Path-based scheduling for synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- Incorporating bottom-up design into hardware synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1990
- Algorithmic and Register-Transfer Level Synthesis: The System Architect’s WorkbenchPublished by Springer Nature ,1990
- Force-directed scheduling for the behavioral synthesis of ASICsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989