Buffer Sizing for Rate-optimal Single-rate Dataflow Scheduling Revisited

Single-Rate Dataflow (SRDF) graphs, also known as Homogeneous Synchronous Dataflow (HSDF) graphs or Marked Graphs, are often used to model the implementation and do temporal analysis of concurrent DSP and multimedia applications. An important problem in implementing applications expressed as SRDF graphs is the computation of the minimal amount of buffering needed to implement a static periodic schedule that is optimal in terms of execution rate, or throughput. Ning and Gao propose in [1] a linear-programming-based polynomial algorithm to compute this minimal storage amount, claiming optimality. We show via a counter-example that the proposed algorithm is not optimal. We prove that the problem is in fact NP-complete. We give an exact solution, and experimentally evaluate the degree of inaccuracy of the algorithm of Ning and Gao.