Max-Plus Algebraic Throughput Analysis of Synchronous Dataflow Graphs
Robert de Groote, Jan Kuper, Hajo J. Broersma, Gerard J.M. Smit · 2012
In this paper we present a novel approach to throughput analysis of synchronous dataflow (SDF) graphs. Our approach is based on describing the evolution of actor firing times as a linear time-invariant system in max-plus algebra. Experimental results indicate that our approach is faster than state-of-the-art approaches to throughput analysis of SDF graphs. The efficiency of our approach is due to an exploitation of the regular structure of the max-plus system's graphical representation, the properties of which we thoroughly prove.