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 to provide a robust system which can handle l arge 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 requirement s, or requiring unacceptable execution times. One of the main problems in scheduling is the dichotomy between control and data, Many algorit hms 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 h as been done in order to simplify the problem; however, it has resulte d in many algorithms unable to handle efficiently large designs with c omplex control and data functionality, This paper presents algorithms for combining data-flow and control-how techniques into a robust sched uling 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 r eordering 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-th e-fly, Results involving billions of paths are presented and analyzed.