Multiconstraint static scheduling of synchronous dataflow graphs via retiming and unfolding

Research output: Contribution to journalArticleAcademicpeer-review

14 Citations (Scopus)
310 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)905-918
Number of pages19
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number6
Publication statusPublished - 18 May 2016


Dive into the research topics of 'Multiconstraint static scheduling of synchronous dataflow graphs via retiming and unfolding'. Together they form a unique fingerprint.

Cite this