Throughput Analysis of Synchronous Data Flow Graphs

A.H. Ghamarian, M.C.W. Geilen, S. Stuijk, T. Basten, A.J.M. Moonen, M.J.G. Bekooij, B.D. Theelen, M.R. Mousavi, Proceedings of the Sixth International Conference on Applications of Concurrency to System Design (ACSD'06), Turku, Finland, pp. 27--30, IEEE Computer Society Press, June 2006.

Abstract

Synchronous Data Flow Graphs (SDFGs) are a useful tool for modeling and analyzing embedded data flow applications, both in a single processor and a multiprocessing context or for application mapping on platforms. Throughput analysis of these SDFGs is an important step for verifying throughput requirements of concurrent real-time applications, for instance within design-space exploration activities. Analysis of SDFGs can be hard, since the worst-case complexity of analysis algorithms is often high. This is also true for throughput analysis. In particular, many algorithms involve a conversion to another kind of data flow graph, the size of which can be exponentially larger than the size of the original graph. In this paper, we present a method for throughput analysis of SDFGs, based on explicit statespace exploration and we show that the method, despite its worst-case complexity, works well in practice, while existing methods often fail. We demonstrate this by comparing the method with state-of-the-art cycle mean computation algorithms. Moreover, since the state-space exploration method is essentially the same as simulation of the graph, the results of this paper can be easily obtained as a byproduct in existing simulation tools.

@InProceedings{MousaviAcsd06,
    author      = "Ghamarian, A.H.  and Geilen, M.C.W.  and Stuijk, S.  and Basten, T.  and Moonen, A.J.M. 
                    and Bekooij, M.J.G.  and Theelen, B.D.  and Mousavi, M.R.", 
    title       = "Throughput Analysis of Synchronous Data Flow Graphs",
    booktitle   = "Proceedings of the 6th International Conference on Application of Concurrency to System Design (ACSD'06)",
    pages       = "27--30",
    publisher   = "IEEE Computer Society Press, Los Alamitos, CA, USA, 2006"
}