Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Original language | English |
---|---|

Title of host publication | Embedded Computer Systems (SAMOS), 2012 International Conference on |

Publisher | IEEE |

Pages | 152-159 |

Number of pages | 8 |

DOIs | |

State | Published - 1 Jul 2012 |

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.

- 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