Monotonic optimization of dataflow buffer sizes

Martijn Hendriks (Corresponding author), Hadi Alizadeh Ara, Marc Geilen, Twan Basten, Ruben Guerra Marin, Rob de Jong, Steven van der Vlugt

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
90 Downloads (Pure)


Many high data-rate video-processing applications are subject to a trade-off between throughput and the sizes of buffers in the system (the storage distribution). These applications have strict requirements with respect to throughput as this directly relates to the functional correctness. Furthermore, the size of the storage distribution relates to resource usage which should be minimized in many practical cases. The computation kernels of high data-rate video-processing applications can often be specified by cyclo-static dataflow graphs. We therefore study the problem of minimization of the total (weighted) size of the storage distribution under a throughput constraint for cyclo-static dataflow graphs. By combining ideas from the area of monotonic optimization with the causal dependency analysis from a state-of-the-art storage optimization approach, we create an algorithm that scales better than the state-of-the-art approach. Our algorithm can provide a solution and a bound on the suboptimality of this solution at any time, and it iteratively improves this until the optimal solution is found. We evaluate our algorithm using several models from the literature, and on models of a high data-rate video-processing application from the healthcare domain. Our experiments show performance increases up to several orders of magnitude.

Original languageEnglish
Pages (from-to)21–32
Number of pages12
JournalJournal of Signal Processing Systems
Issue number1
Publication statusPublished - 1 Jan 2019


  • Buffer size
  • Cyclo-static dataflow
  • Monotonic optimization
  • Throughput


Dive into the research topics of 'Monotonic optimization of dataflow buffer sizes'. Together they form a unique fingerprint.

Cite this