Memory-Constrained Static Rate-Optimal Scheduling of Synchronous Dataflow Graphs via Retiming
Zhu, X Xueyang, Geilen, MCW Marc, Basten, AA Twan, Sander Stuijk · 2014
Abstract—Synchronous dataflow graphs (SDFGs) are widely used to model digital signal processing (DSP) and streaming me-dia applications. In this paper, we use retiming to optimize SDFGs to achieve a high throughput with low storage requirement. Using a memory constraint as an additional enabling condition, we define a memory constrained self-timed execution of an SDFG. Exploring the state-space generated by the execution, we can check whether a retiming exists that leads to a rate-optimal schedule under the memory constraint. Combining this with a binary search strategy, we present a heuristic method to find a proper retiming and a static scheduling which schedules the retimed SDFG with optimal rate (i.e., maximal throughput) and with as little storage space as possible. Our experiments are carried out on hundreds of synthetic SDFGs and several models of real applications. Differential synthetic graph results and real