A NEW SYMBOLIC TECHNIQUE FOR CONTROL-DEPENDENT SCHEDULING

This paper describes an exact symbolic formulation of control-dependen t, resource-constrained scheduling. The technique provides a closed-fo rm solution set in which all satisfying schedules are encapsulated in a compressed OBDD-based representation. This solution format greatly i ncreases the flexibility of the synthesis task by enabling incremental incorporation of additional constraints and by supporting solution sp ace exploration without the need for rescheduling. The technique provi des a systematic treatment of speculative operation execution in arbit rary forward-branching control/data paths. An iterative construction m ethod is presented along with benchmark results. The experiments demon strate the ability of the proposed technique to efficiently exploit pa rallelism not explicitly specified in the input description.