Symbolic NDFA Based Scheduling


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.

©2002-2018 U.C. Regents