Reduction techniques for synchronous dataflow graphs

ABSTRACT

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.

REFERENCES

• 1: F. Baccelli, G. Cohen, G. Olsder, and J. P. Quadrat. Synchronization and Linearity. John Wiley & Sons, 1992.
• 2: N. Bambha, V. Kianzad, M. Khandelia, and S. Bhattacharya. Intermediate representations for design automation of multiprocessor DSP systems. Design Automation for Embedded Systems, 7:307--323, 2002.
• 3: M. Bekooij, O. Moreira, P. Poplavko, B. Mesman, M. Pastrnak, and J. V. Meerbergen. Predictable multiprocessor system design. In SCOPES 2004, 8th Int. Workshop on Software and Compilers for Embedded Systems, 2004.
• 4: S. Bhattacharyya, P. Murthy, and E. Lee. Software Synthesis from Dataflow Graphs. Kluwer Academic Publishers, 1996.
• 5: A. Dasdan, S. S. Irani, and R. K. Gupta. Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems. In DAC '99: Proceedings of the 36th ACM/IEEE conference on Design automation, pages 37--42, New York, NY, USA, 1999. ACM.
• 6: M. Geilen. Reduction techniques for synchronous dataflow graphs. Technical Report ESR-2009-01, Electronic Systems Group, Dept. of Electrical Engineering, Eindhoven University of Technology, 2009.
• 7: M. Geilen. Synchronous data flow scenarios. Transactions on Embedded Computing Systems, Special issue on Model-driven Embedded-system Design, to be published, 2009.
• 8: A. Ghamarian, M. Geilen, S. Stuijk, T. Basten, A. Moonen, M. Bekooij, B. Theelen, and M. Mousavi. Throughput analysis of synchronous data flow graphs. In Proceedings of the 6th International Conference on Application of Concurrency to System Design (ACSD'06), pages 27--30. IEEE Computer Society Press, Los Alamitos, CA, USA, 2006, 2006.
• 9: A. Ghamarian, S. Stuijk, T. Basten, M. Geilen, and B. Theelen. Latency minimization for synchronous data flow graphs. Digital Systems Design, Euromicro Symposium on, pages 189--196, 2007.
• 10: R. Govindarajan and G. R. Gao. Rate-optimal schedule for multi-rate dsp computations. J. VLSI Signal Process. Syst., 9(3):211--232, 1995.
• 11: E. Lee and D. Messerschmitt. Synchronous data flow. IEEE Proceedings, 75(9):1235--1245, Sept. 1987.
• 12: P. K. Murthy. Scheduling Techniques for Synchronous and Multidimensional Synchronous Dataflow. PhD thesis, University of California, Berkeley, December 1996.
• 13: P. Poplavko, T. Basten, and J. van Meerbergen. Execution-time prediction for dynamic streaming applications with task-level parallelism. In DSD '07: Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools, pages 228--235, Washington, DC, USA, 2007. IEEE Computer Society.
• 14: SDF³. http://www.cs.clc.tue.nl/sdf3.
• 15: S. Sriram and S. S. Bhattacharyya. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker, Inc., New York, NY, USA, 2000.
• 16: S. Stuijk, T. Basten, B. Mesman, and M. Geilen. Predictable embedding of large data structures in multiprocessor networks-on-chip. In Proc. DSD, 8th Euromicro Conference, DSD'05, pages 388--395. IEEE Computer Society Press, 2005.
• 17: S. Stuijk, M. Geilen, and T. Basten. SDF³: SDF For Free. In Application of Concurrency to System Design, 6th International Conference, ACSD 2006, Proceedings, pages 276--278. IEEE Computer Society Press, Los Alamitos, CA, USA, June 2006.
• 18: S. Stuijk, M. Geilen, and T. Basten. Throughput-buffering trade-off exploration for cyclo-static and synchronous dataflow graphs. IEEE Trans. Comput., 57(10):1331--1345, 2008.
• 19: M. Wiggers, M. Bekooij, and G. J. M. Smit. Efficient computation of buffer capacities for cyclo-static dataflow graphs. In DAC, pages 658--663, 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
model-based design, reduction techniques, synchronous dataflow graphs