Symbolic Scheduling Techniques
Ivan Radivojevic Forrest Brewer
Operation scheduling is the process of determining the assignment of operations to time steps of a synchronous system, subject to data/control-flow dependencies and resource/timing constraints. Increased use of high-level synthesis languages (VHDL, Verilog) in design has created the need for a systematic treatment of control-dominated problems that exhibit complex conditional behavior. Conventional exact techniques are not applicable to this problem, while current heuristic algorithms lack systematic techniques for code motion and conditional resource sharing.
In our previous work [TCAD95][IEICE95][EDTC95][DAC94][HLSS94][SASIMI93], we developed an exact symbolic formulation of resource-constrained control-dependent scheduling. This novel approach describes all of the scheduling constraints as Boolean functions which are represented using Ordered Binary Decision Diagrams (OBDDs). A solution set is generated in which, unlike other techniques, all feasible schedules are implicitly captured in a compressed form. This solution format introduces significant flexibility to a circuit design process by enabling incremental incorporation of additional constraints and by supporting solution space exploration without the need for rescheduling. The symbolic approach developed at UCSB is the only exact technique for resource-constrained scheduling with speculative operation execution. The experimental results demonstrated the ability of the proposed technique to efficiently exploit operation level parallelism [IEICE95]. Moreover, some larger problems were solved exactly for the first time using this approach [EDTC95].
Recently, we introduced an exact and efficient conditional resource sharing analysis using a guard-based control representation [ICCD95]. The analysis systematically handles complex conditional resource sharing for cases when folded (software pipelined) loops include conditional behavior within the loop body. Moreover, the proposed approach is not restricted to physical hardware resources, but can be applied to modelling of more general exclusion/synchronization constraints. In the future, we plan to implement a scheduler based on the concepts discussed in [ICCD95].
- [TCAD95]
- I. Radivojevic and F. Brewer, "A New Symbolic Technique for Control-Dependent Scheduling", IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, to appear.
- [ICCD95]
- "Analysis of Conditional Resource Sharing using a Guard-based Control Representation", Proc. Int. Conf. Computer Design, Austin, Texas, Oct. 1995.
- [IEICE95]
- "Symbolic Scheduling Techniques", IEICE Trans. Information and Systems, Japan, vol. e78-d, no. 3, March 1995.
- [EDTC95]
- "On Applicability of Symbolic Techniques to Larger Scheduling Problems", Proc. European Design and Test Conf., Paris, France, March 1995.
- [DAC94]
- "Incorporating Speculative Execution in Exact Control-Dependent Scheduling", Proc. 31st ACM/IEEE Design Automation Conf., San Diego, CA, June 1994.
- [HLSS94]
- "Ensemble Representation and Techniques for Exact Control-Dependent Scheduling", Proc. 7th Int. Symp. High-Level Synthesis, Niagara-on-the-Lake, Ontario, Canada, May 1994.
- [SASIMI93]
- "Symbolic Techniques for Optimal Scheduling", Proc. 4th Synthesis and Simulation Meeting and Int. Interchange (SASIMI), Nara, Japan, Oct. 1993.