Control-Flow versus Data-Flow-Based Scheduling: Combining Both Approaches in an Adaptive Scheduling System

As high-level synthesis techniques gain acceptance among designers, it is important to be able provide a robust-system which can handle large designs in short execution times, producing high-quality results. Scheduling is the most complex task in high-level synthesis, and although many algorithms exist for solving the scheduling problem, it remains a main source of inefficiency by not producing high-quality results, not taking into account realistic design requirements, or requiring unacceptable execution times. A main problem in scheduling is the dichotomy between control and data. Many algorithms to date have been able to provide scheduling solutions by looking 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 data-flow and control-flow techniques into a robust scheduling system. The main characteristics of this system are: 1) it uses path-based techniques for efficient handling of control and mutual exclusiveness (for resource sharing); 2) it allows operation reordernig 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.