Reduction techniques for synchronous dataflow graphs

The Synchronous Dataflow (SDF) model of computation is popu-lar for modelling the timing behaviour of real-time embedded hard-ware and software systems and applications. It is an essential in-gredient of several automated design-flows and design-space explo-ration 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 meth-ods 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 conver-sion from SDF to Homogeneous SDF, a step applied in many anal-ysis 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