|
Symbolic NDFA Based Scheduling
Abstract
Despite decades of work and several commercial tools,
behavioral synthesis has yet to make up a substantial
portion of modern design. We believe that this is due
to several reasons, from inadequate generality of the
scheduler to difficulty in capturing/specifying
sequential constraints. In this talk, we present a
symbolic model for scheduling which is based on simple
co-execution of NDFA automata. By careful attention to
construction and traversal techniques, the scale of
practical scheduling instances can be made comparable
to if not superior to alternative exact techniques.
This is especially true for very highly constrained
instances in which a relatively small number of
schedules have optimal latency. We describe the
technique for CDFG graphs and for looping DFGs, and
briefly describe the generalizations necessary for
looping CDFGs. Of particular interest is the simple
technique with which arbitrary interface and module
sequencing constraints are handled. In particular,
scheduling problems arising from protocol-specification
NFAs can be supported by this technique. Results from
classical HLS benchmarks as well as several larger
synthetic benchmarks are presented.
|