Buffer Sizing for Rate-Optimal Single-Rate Data-Flow Scheduling Revisited
Buffer Sizing for Rate-Optimal Single-Rate Data-Flow Scheduling Revisited
复制标题
DOI：
10.1109/tc.2009.155
复制
发表时间：
2010-02
影响因子：
3.7
通讯作者：
Orlando Moreira;T. Basten;M. Geilen;S. Stuijk
中科院分区：
文献类型：
--
作者：
Orlando Moreira;T. Basten;M. Geilen;S. Stuijk
单速率数据流（SRDF）图，也称为同质同步数据流（HSDF）图或标记图，通常用于对并发DSP和多媒体应用的实现进行建模和进行时间分析。实施以SRDF图表示的应用程序时的一个重要问题是计算实施静态周期性计划（SPS）所需的最小缓冲量，该计划在执行速率或吞吐量方面是最佳的。Ning和Gao [1]提出了一个基于线性规划的多项式算法来计算这个最小存储量，声称是最优的。我们通过一个反例表明，该算法是不是最佳的。我们证明了这个问题实际上是NP完全的。我们给出了一个精确的解决方案，并通过实验评估宁和高的算法的不准确程度。
Single-Rate Data-Flow (SRDF) graphs, also known as Homogeneous Synchronous Data-Flow (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 (SPS) that is optimal in terms of execution rate, or throughput. Ning and Gao [1] propose a linear-programming-based polynomial algorithm to compute this minimal storage amount, claiming optimality. We show via a counterexample 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.