Evaluation of the Exact Throughput of a Synchronous DataFlow Graph

摘要

Synchronous DataFlow Graph (SDFG in short) is a formalism frequently considered in electronic design and software compilers to model communications between components with different rates. The development of efficient algorithms to evaluate the maximum throughput of SDFGs is a challenging question. This paper presents a mathematical framework to perform schedulability analysis and to compute the maximum throughput of SDFGs. This work focuses on strictly K-Periodic schedules for which a fixed set of execution times coupled with a period are associated with each task and define a schedule of every task executions. This class of schedules can always reach maximal throughput; we present an algorithm that computes the exact maximum throughput by iteratively generating K-periodic schedules until we reach optimality. The complexity of this iterative algorithm is studied by using the well-established benchmarking suite SDF3, and compared against the most common throughput analysis techniques. We show several orders of magnitude improvement over state-of-the-art both in terms of computation time, and size of the final schedules.