Efficient Computation of the Max-Plus Semantics of Synchronous Dataflow Graphs

Hossein Elahi (Corresponding author), M. Geilen, T. Basten

Research output: Contribution to journalArticleAcademicpeer-review

64 Downloads (Pure)


Streaming systems are naturally modeled with synchronous dataflow graphs (SDFGs). The max-plus semantics of an SDFG is a compact matrix representation of its timing behavior. The max-plus semantics enables us to analyze and control timing properties of the systems, such as the obtainable minimum guaranteed throughput and maximum latency. Deriving the max-plus semantics, and consequently, performance analysis may be computationally expensive since the state-of-the-art method simulates one iteration of an SDFG. This holds, in particular, for systems whose components operate at different levels of granularity, as this results in many executions of some components in one iteration. This article aims at efficiently calculating the max-plus semantics of SDFGs. This article proposes an optimization framework exploring decompositions of a given SDFG and finding a composition sequence whose computational effort for compositionally obtaining the max-plus semantics is minimal. Not only does our proposed technique accelerate the performance analysis of multiscale streaming systems, but it also allows us to compute the max-plus semantics of some systems for which the state-of-the-art method does not succeed because of memory limitations.

Original languageEnglish
Article number10025363
Pages (from-to)3412-3425
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number10
Early online date24 Jan 2023
Publication statusPublished - 1 Oct 2023


  • Streaming systems
  • Multiscale systems
  • Dataflow graphs
  • Performance analysis
  • Max-plus semantics
  • Computational modeling
  • Semantics
  • Transform coding
  • Streaming media
  • Throughput
  • Decoding
  • Optimization
  • multiscale systems
  • streaming systems
  • max-plus semantics
  • performance analysis


Dive into the research topics of 'Efficient Computation of the Max-Plus Semantics of Synchronous Dataflow Graphs'. Together they form a unique fingerprint.

Cite this