Weitere Kapitel dieses Buchs durch Wischen aufrufen
Static dataflow graphs such as those presented in earlier chapters are attractive from a performance point of view, as the rate at which data is processed can be assessed beforehand. Assessing this performance involves analysing the dependency structure and the timings of the different nodes. This chapter describes different ways to approach this problem, and provides a mathematical basis from which these approaches follow. Methods for efficiently analysing the throughput are given, for single-rate (or homogeneous) graphs, synchronous dataflow graphs, and cyclo-static dataflow graphs.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Mohamed Bamakhrama and Todor Stefanov. Hard-real-time scheduling of data-dependent tasks in embedded streaming applications. In Proceedings of the ninth ACM international conference on Embedded software, pages 195–204. ACM, 2011.
Mohamed Bamakhrama and Todor Stefanov. On the hard-real-time scheduling of embedded streaming applications. Design Automation for Embedded Systems, 17(2):221–249, 2013. CrossRef
Mohamed Benazouz, Olivier Marchetti, Alix Munier-Kordon, and Thierry Michel. A new method for minimizing buffer sizes for Cyclo-Static Dataflow graphs. In 8th IEEE Workshop on Embedded Systems for Real-Time Multimedia, pages 11–20. IEEE, Oct 2010.
Mohamed Benazouz, Alix Munier-Kordon, Thomas Hujsa, and Bruno Bodin. Liveness evaluation of a cyclo-static DataFlow graph. In Proceedings of the 50th Annual Design Automation Conference on - DAC ’13, page 1, New York, New York, USA, May 2013. ACM Press.
G. Bilsen, M. Engels, R. Lauwereins, and J. Peperstraete. Cyclo-Static dataflow. IEEE Transactions on Signal Processing, 44(2):397–408, 1996. CrossRef
B. Bodin, A. Munier-Kordon, and B.D. de Dinechin. K-periodic schedules for evaluating the maximum throughput of a synchronous dataflow graph. In Proceedings of the International Conference on Embedded Computer Systems (SAMOS), pages 152–159, July 2012.
Bruno Bodin, Alix Munier-Kordon, and Benoit Dupont de Dinechin. Periodic schedules for Cyclo-Static Dataflow. In Proceedings of the 11th IEEE Symposium on Embedded Systems for Real-time Multimedia, pages 105–114. IEEE, October 2013.
Bruno Bodin, Alix Munier-Kordon, and Benoît Dupont de Dinechin. Optimal and fast throughput evaluation of csdf. In Proceedings of the 53rd Annual Design Automation Conference, page 160. ACM, 2016.
Jean Cochet-terrasson, Guy Cohen, Stéphane Gaubert, Michael Mc Gettrick, and Jean-Pierre Quadrat. Numerical Computation of Spectral Elements in Max-Plus Algebra. In Proceedings of the IFAC Conference on System Structure and Control, July 1998.
Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. Synchronization and linearity: an algebra for discrete event systems. Wiley New York, 1992.
Ali Dasdan. Experimental analysis of the fastest optimum cycle ratio and mean algorithms. ACM Transactions on Design Automation of Electronic Systems (TODAES), 9(4):385–418, 2004. CrossRef
Robert de Groote. On the Analysis of Synchronous Dataflow Graphs: a System-theoretic Perspective. PhD thesis, University of Twente, the Netherlands, February 2016.
Robert de Groote, Philip K. F. Hölzenspies, Jan Kuper, and Gerard J. M. Smit. Multi-rate Equivalents of Cyclo-Static Synchronous Dataflow Graphs. In Proceedings of the 14th International Conference on Application of Concurrency to System Design (ACSD), pages 62–71. IEEE Computer Society, June 2014.
Robert de Groote, Philip K. F. Hölzenspies, Jan Kuper, and Gerard J. M. Smit. Single-Rate Approximations of Cyclo-Static Synchronous Dataflow Graphs. In Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES), pages 11–20, June 2014.
Robert de Groote, Jan Kuper, Hajo Broersma, and Gerard J.M. Smit. Max-Plus Algebraic Throughput Analysis of Synchronous Dataflow Graphs. In Proceedings of the 38th Euromicro Conference on Software Engineering and Advanced Applications (SEAA), pages 29–38. IEEE, September 2012.
M. Engels, G. Bilsen, R. Lauwereins, and J. Peperstraete. Cycle-static dataflow: model and implementation. In Proceedings of the 28th Asilomar Conference on Signals, Systems and Computers, volume 1, pages 503–507. IEEE Comput. Soc. Press, 1994.
A. H. Ghamarian, M. C. W. Geilen, S. Stuijk, T. Basten, B. D. Theelen, M. R. Mousavi, A. J. M. Moonen, and M. J. G. Bekooij. Throughput Analysis of Synchronous Data Flow Graphs. In Proceedings of the 6th International Conference on Application of Concurrency to System Design (ACSD), pages 25–36. IEEE, 2006.
A.H. Ghamarian, M. Geilen, T. Basten, B. Theelen, M.R. Mousavi, and S. Stuijk. Liveness and boundedness of synchronous data flow graphs. In Proceedings of the 6th conference on Formal Methods in Computer Aided Design (FMCAD), pages 68–75. IEEE, November 2006.
Amir Hossein Ghamarian. Timing analysis of synchronous data flow graphs. PhD thesis, Eindhoven University of Technology, The Netherlands, July 2008.
Steve Goddard. On the Management of Latency in the synthesis of real-time signal processing systems from processing graphs. PhD thesis, University of North Carolina at Chapel Hill, 1998.
S. Ha and H. Oh. Decidable signal processing dataflow graphs. In S. S. Bhattacharyya, E. F. Deprettere, R. Leupers, and J. Takala, editors, Handbook of Signal Processing Systems. Springer, third edition, 2018.
B. Heidergott, Geert Jan Olsder, and Jacob van der Woude. Max Plus at Work: modeling and analysis of synchronized systems. Princeton University Press, 2006.
K. Ito and K.K. Parhi. Determining the iteration bounds of single-rate and multi-rate data-flow graphs. In Proceedings of the 1994 Asia Pacific Conference on Circuits and Systems, pages 163–168. IEEE, 1994.
E.A. Lee and D.G. Messerschmitt. Synchronous data flow. Proceedings of the IEEE, 75(9):1235–1245, 1987. CrossRef
E.A. Lee and T.M. Parks. Dataflow process networks. Proceedings of the IEEE, 83(5):773–801, May 1995. CrossRef
R. Leupers, M. A. Aguilar, J. Castrillon, and W. Sheng. Software compilation techniques for heterogeneous embedded multi-core systems. In S. S. Bhattacharyya, E. F. Deprettere, R. Leupers, and J. Takala, editors, Handbook of Signal Processing Systems. Springer, third edition, 2018.
Orlando Moreira and Henk Corporaal. Scheduling Real-Time Streaming Applications onto an Embedded Multiprocessor, volume 24 of Embedded Systems. Springer International Publishing, Cham, 2014. CrossRef
K.K. Parhi. Algorithm transformation techniques for concurrent processors. Proceedings of the IEEE, 77(12):1879–1895, 1989. CrossRef
T.M. Parks and E.A. Lee. Non-preemptive real-time scheduling of dataflow systems. In Acoustics, Speech, and Signal Processing, 1995. ICASSP-95., 1995 International Conference on, volume 5, pages 3235–3238. IEEE, 1995.
T.M. Parks, J.L. Pino, and E.A. Lee. A Comparison of Synchronous and Cyclo-static Dataflow. In Proceedings of the 29th Asilomar Conference on Signals, Systems and Computers, volume 1, pages 204–210. IEEE Comput. Soc. Press, 1995.
Raymond Reiter. Scheduling Parallel Computations. Journal of the ACM, 15(4):590–599, October 1968. CrossRef
Firew Siyoum, Marc Geilen, Orlando Moreira, and Henk Corporaal. Worst-case throughput analysis of real-time dynamic streaming applications. In Proceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis - CODES+ISSS ’12, page 463, New York, New York, USA, October 2012. ACM Press.
Sundararajan Sriram and Shuvra S. Bhattacharyya. Embedded Multiprocessors: Scheduling and Synchronization. CRC Press, February 2009. CrossRef
Enrique Teruel, Piotr Chrzastowski-Wachtel, José Manuel Colom, and Manuel Silva. On Weighted T-Systems. Application and Theory of Petri Nets, pages 348–367, June 1992.
Maarten Wiggers, Marco Bekooij, Pierre Jansen, and Gerard Smit. Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure. In Proceedings of the 4th international conference on Hardware/software codesign and system synthesis - CODES+ISSS ’06, page 10, New York, New York, USA, 2006. ACM Press.
M.H. Wiggers, M.J.G. Bekooij, and G.J.M. Smit. Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs. In Proceedings of the 44th ACM/IEEE Design Automation Conference (DAC), pages 658–663. IEEE, 2007.
Neal E. Young, Robert E. Tarjant, and James B. Orlin. Faster parametric shortest path and minimum-balance algorithms. Networks, 21(2):205–221, mar 1991.
- Throughput analysis of dataflow graphs
Robert de Groote
Neuer Inhalt/© Filograph | Getty Images | iStock