期刊
IEEE TRANSACTIONS ON COMPUTERS
卷 59, 期 2, 页码 188-201出版社
IEEE COMPUTER SOC
DOI: 10.1109/TC.2009.155
关键词
Scheduling; single-rate data flow; homogeneous synchronous data flow; buffer minimization; throughput optimization
资金
- Dutch Science Foundation NWO [612.064.206]
- PROMES
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据