Edinburgh Research Explorer

K-Periodic schedules for evaluating the maximum throughput of a Synchronous Dataflow graph

Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • B. Bodin
  • A. Munier-Kordon
  • B. D. de Dinechin

Related Edinburgh Organisations

Original languageEnglish
Title of host publicationEmbedded Computer Systems (SAMOS), 2012 International Conference on
PublisherIEEE
Pages152-159
Number of pages8
DOIs
StatePublished - 1 Jul 2012

Abstract

Synchronous Dataflow graphs, introduced by Lee and Messerschmitt in 1987, are a well-known formalism commonly used to model data-exchanges between parallel processes. This model was extensively studied in the last two decades because of the importance of its applications. However, the determination of a maximal throughput is a difficult question, for which no polynomial time algorithm exists to date. In this context, several authors proved that a K-Periodic schedule, where K is a vector of no polynomially bounded values, reaches the maximum throughput. On the other hand, a 1-Periodic schedule may be built polynomially, but without any guarantee on the throughput achieved. Therefore, the investigated problem is the trade-off between the schedule size induced by the vector K (called the periodicity vector) and its corresponding throughput. Necessary and sufficient conditions for the existence of K-Periodic schedules are first shown for any fixed value in the vector K; the computation of the maximum throughput of a K-Periodic schedule is deduced. A set of dominant values of K is exhibited, and a relationship between the optimal throughput of these values is proved. Some real-life experiments measure the variation of the throughput according to K.

Research areas

  • computational complexity, data flow graphs, parallel processing, vectors, data-exchange modeling, k-periodic schedules, maximum throughput evaluation, necessary and sufficient conditions, optimal throughput, periodicity vector, polynomial time algorithm, real-life experiments, synchronous dataflow graph, Complexity theory, Computational modeling, Polynomials, Production, Schedules, Throughput, Vectors

ID: 24370974