Buffer sizing for rate-optimal single-rate data-flow scheduling revisited

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

32 Citaten (Scopus)
110 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)188-201
Aantal pagina's14
TijdschriftIEEE Transactions on Computers
Volume59
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - feb 2010

Vingerafdruk Duik in de onderzoeksthema's van 'Buffer sizing for rate-optimal single-rate data-flow scheduling revisited'. Samen vormen ze een unieke vingerafdruk.

Citeer dit