Title
Buffer sizing for rate-optimal single-rate data-flow scheduling revisited
Author
Moreira, O.
Basten, T.
Geilen, M.
Stuijk, S.
Publication year
2010
Abstract
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.
Subject
Buffer minimization
Homogeneous synchronous data flow
Scheduling
Single-rate data flow
Throughput optimization
ICT
ESI - Embedded Systems Innovation
TS - Technical Sciences
To reference this document use:
http://resolver.tudelft.nl/uuid:10331960-d3e9-4e47-8b14-7decdc8a5aac
DOI
https://doi.org/10.1109/tc.2009.155
TNO identifier
954186
Publisher
IEEE
ISSN
0018-9340
Source
IEEE Transactions on Computers, 59 (59), 188-201
Document type
article