Reduction techniques for synchronous dataflow graphs.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

20 Citations (Scopus)
117 Downloads (Pure)


The Synchronous Dataflow (SDF) model of computation is popular for modelling the timing behaviour of real-time embedded hardware and software systems and applications. It is an essential ingredient of several automated design-flows and design-space exploration tools. The model can be analysed for throughput and latency properties. Although the SDF model is fairly simple, the analysis algorithms are often of high complexity and the models that need to be analysed may be fairly large. This paper introduces two graph transformations for reducing large SDF graphs into simpler, smaller ones that can be analysed more efficiently and give a conservative and often tight estimation of the timing of the original model and hence of the hard real-time system. We can make SDF based methods more efficient and prove that analyses that were done manually in an ad-hoc fashion in the past, can be done automatically and with guaranteed correctness. Additionally we introduce a novel conversion from SDF to Homogeneous SDF, a step applied in many analysis methods for SDF, which yields an up to 250X improvement on the number of actors, thus mitigating the problems with the size explosion observed in the traditional conversion.
Original languageEnglish
Title of host publicationProceedings of the 46th ACM/IEEE Design Automation Conference 2009, DAC'09, 26-31 July 2009, San Francisco, California
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
ISBN (Print)978-1-60558-497-3
Publication statusPublished - 2009


Dive into the research topics of 'Reduction techniques for synchronous dataflow graphs.'. Together they form a unique fingerprint.

Cite this