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

Copyright [©] (1997) by IEEE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

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.

By: Reinaldo A. Bergamaschi, Salil Raje (Northwestern Univ.), Indira Nair and Louise Trevillyan

Published in: IEEE Transactions on VLSI Systems, volume 5, (no 1), pages 82-100 in 1997

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .