Multiconstraint Static Scheduling of Synchronous Dataflow Graphs Via Retiming and Unfolding

Multiconstraint Static Scheduling of Synchronous Dataflow Graphs Via Retiming and Unfolding

Zhu, X.Y.
Geilen, M.
Basten, T.
Stuijk, S.

2016

Synchronous dataflow graphs (SDFGs) are widely used to represent digital signal processing algorithms and streaming media applications. This paper presents several methods for binding and scheduling SDFGs on a multiprocessor platform. Exploring the state space generated by a self-timed execution (STE) of an SDFG, we present an exact method for static rate-optimal scheduling of SDFGs via implicit retiming and unfolding. By modeling a constraint as an extra enabling condition for the STE, we get a constrained STE which implies a schedule under the constraint. We present a general framework for scheduling SDFGs under constraints on the number of processors, buffer sizes, auto-concurrency, or combinations of them. Exploring the state space generated by the constrained STE, we can check whether a retiming, which leads to a rate-optimal schedule under the processor (or memory) constraint, exists. Combining this with a binary search strategy, we present heuristic methods to find a proper retiming and a static scheduling that schedules the retimed SDFG with optimal rate and with as few processors (or as little storage space) as possible. None of the methods explicitly converts an SDFG to its equivalent homogenous SDFG, the size of which may be tremendously larger than the original SDFG. We perform experiments on several models of real applications and hundreds of synthetic SDFGs. The results show that the exact method outperforms existing methods significantly; our heuristics reduce the resources used and are computationally efficient.

ICT
ESI - Embedded Systems Innovations
TS - Technical Sciences
Industrial Innovation
Mapping
Multi-constraint
Resource optimization
Scheduling
Timing optimization

http://resolver.tudelft.nl/uuid:3ccd3b64-76cf-40e7-9266-be5aee6d5923

https://doi.org/10.1109/tcad.2015.2495167

536843

Institute of Electrical and Electronics Engineers Inc.

0278-0070

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 35 (6), 905-918

7308019

article