Scalable Analysis for Multi-Scale Dataflow Models

Abstract

Multi-scale dataflow models have actors acting at multiple granularity levels, e.g., a dataflow model of a video processing application with operations on frame, line, and pixel level. The state of the art timing analysis methods for both static and dynamic dataflow types aggregate the behaviours across all granularity levels into one, often large iteration, which is repeated without exploiting the structure within such an iteration. This poses scalability issues to dataflow analysis, because behaviour of the large iteration is analysed by some form of simulation that involves a large number of actor firings. We take a fresh perspective of what is happening inside the large iteration. We take advantage of the fact that the iteration is a sequence of smaller behaviours, each captured in a scenario, that are typically repeated many times. We use the (max ,+) linear model of dataflow to represent each of the scenarios with a matrix. This allows a compositional worst-case throughput analysis of the repeated scenarios by raising the matrices to the power of the number of repetitions, which scales logarithmically with the number of repetitions, whereas the existing throughput analysis scales linearly. We moreover provide the first exact worst-case latency analysis for scenario-aware dataflow. This compositional latency analysis also scales logarithmically when applied to multi-scale dataflow models. We apply our new throughput and latency analysis to several realistic applications. The results confirm that our approach provides a fast and accurate analysis.

References

1. H. Alizadeh Ara, A. Behrouzian, M. Geilen, et al. 2016. Analysis and visualization of execution traces of dataflow applications. In Proceedings of the 2nd Embedded Computing and Architecture (IDEA) Workshop on Integrating Dataflow. ESR-2017-01, 19--20.
2. H. Alizadeh Ara, M. Geilen, T. Basten, et al. 2016. Tight temporal bounds for dataflow applications mapped onto shared resources. In Proceedings of the 11th IEEE Symposium on Industrial Embedded Systems (SIES’16). IEEE, 1--8.
3. François Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. 1992. Synchronization and Linearity, Vol. 2. Wiley, New York.
4. Shuvra S. Bhattacharyya, Praveen K. Murthy, and Edward A. Lee. 1999. Synthesis of embedded software from synchronous dataflow specifications. Journal of VLSI Signal Processing Systems for Signal, Image and Video Technology 21, 2 (01 Jun 1999), 151--166.
5. G. Bilsen, M. Engels, R. Lauwereins, and J. Peperstraete. 1996. Cyclo-static dataflow. IEEE Transactions on Signal Processing 44, 2 (February 1996), 397--408.
6. Anne Brüggemann-Klein. 1993. Regular expressions into finite automata. Theoretical Computer Science 120, 2 (1993), 197--213.
7. Thomas H. Cormen. 2009. Introduction to Algorithms. MIT press.
8. R. de Groote, P. K. F. Hölzenspies, J. Kuper, and G. J. M. Smit. 2014. Single-rate approximations of cyclo-static synchronous dataflow graphs. In Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES’14). ACM, New York, NY, 11--20.
9. Stéphane Gaubert. 1995. Performance evaluation of (max,+) automata. IEEE Trans. on Automatic Control 40, 12 (1995), 2014--2025.
10. M. Geilen. 2011. Synchronous dataflow scenarios. ACM Trans. Embed. Comput. Syst. 10, 2, Article 16 (Jan. 2011), 31 pages.
11. M. Geilen, J. Falk, C. Haubelt, et al. 2014. Performance analysis of weakly-consistent scenario-aware dataflow graphs. In Proceeding of 48th Asilomar Conference on Signals, Systems and Computers. 393--397.
12. M. Geilen, J. Falk, C. Haubelt, et al. 2017. Performance analysis of weakly-consistent scenario-aware dataflow graphs. Signal Processing Systems 87, 1 (2017), 157--175.
13. Marc Geilen and Sander Stuijk. 2010. Worst-case performance analysis of synchronous dataflow scenarios. In Proceedings of the 8th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES/ISSS’10). ACM, New York, NY, 125--134.
14. A. H. Ghamarian, M. C. W. Geilen, S. Stuijk, et al. 2006. Throughput analysis of synchronous data flow graphs. In Proceedings of the 6th International Conference on Application of Concurrency to System Design (ACSD’06). 25--36.
15. A. H. Ghamarian, S. Stuijk, T. Basten, et al. 2007. Latency minimization for synchronous data flow graphs. In 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools (DSD’07). 189--196.
16. Michel Gondran and Michel Minoux. 1984. Graphs and Algorithms. Wiley.
17. C. Hagenah and A. Muscholl. 2000. Computing ε-free NFA from regular expressions in O(n log²n) time. RAIRO Inform. Théor 34 (2000), 257--277.
18. R. M. Karp. 1978. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics 23, 3 (1978), 309--311.
19. J. Keinert, H. Dutta, F. Hannig, et al. 2009. Model-based synthesis and optimization of static multi-rate image processing algorithms. In Proceedings of the 9th Conference on Design, Automation and Test in Europe (DATE’09). European Design and Automation Association, 3001 Leuven, Belgium, Belgium, 135--140.
20. E. A. Lee and D. G. Messerschmitt. 1987. Synchronous data flow. Proc. IEEE 75, 9 (Sept 1987), 1235--1245.
21. W. Liu, M. Yuan, X. He, et al. 2008. Efficient SAT-based mapping and scheduling of homogeneous synchronous dataflow graphs for throughput optimization. In Proceedings of Real-Time Systems Symposium. 492--504.
22. O. Moreira and H. Corporaal. 2014. Scheduling Real-time Streaming Applications onto an Embedded Multiprocessor. Springer, 67--75.
23. A. Nelson, K. Goossens, and B. Akesson. 2015. Dataflow formalisation of real-time streaming applications on a composable and predictable multi-processor SOC. Systems Architecture 61, 9 (2015), 435--448.
24. P. Poplavko, T. Basten, M. Bekooij, et al. 2003. Task-level timing models for guaranteed performance in multiprocessor networks-on-chip. In Proceedings of 2003 International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES’03). ACM, New York, NY, 63--72.
25. S. Ritz, M. Pankert, V. Zivojinovic, and H. Meyr. 1993. Optimum vectorization of scalable synchronous dataflow graphs. In Proceedings of 1993 International Conference on Application-Specific Array Processors. 285--296.
26. F. Siyoum, M. Geilen, and H. Corporaal. 2014. Symbolic analysis of dataflow applications mapped onto shared heterogeneous resources. In Proceedings of the 51st ACM/EDAC/IEEE Design Automation Conference (DAC’14). 1--6.
27. S. Sriram and S. S. Bhattacharyya. 2009. Embedded Multiprocessors: Scheduling and Synchronization. CRC Press.
28. S. Stuijk. 2007. Predictable Mapping of Streaming Applications on Multiprocessors. Ph.D. Dissertation. Technische Universiteit Eindhoven, Eindhoven, NL.
29. S. Stuijk, M. Geilen, and T. Basten. 2006. Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs. In Proceedings of the 43rd ACM/IEEE Design Automation Conference. 899--904.
30. S. Stuijk, M. Geilen, and T. Basten. 2006. SDF3: SDF for free. In Proceedings of the 6th International Conference on Application of Concurrency to System Design. IEEE, 276--278.
31. S. Stuijk, M. Geilen, and T. Basten. 2008. Throughput-buffering trade-off exploration for cyclo-static and synchronous dataflow graphs. IEEE Transactions on Computers 57, 10 (Oct 2008), 1331--1345.
32. S. Stuijk, M. Geilen, B. Theelen, and T. Basten. 2011. Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications. In 2011 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation. 404--411.
33. B. D. Theelen, M. C. W. Geilen, T. Basten, et al. 2006. A scenario-aware data flow model for combined long-run average and worst-case performance analysis. In Proceedings of the 4th ACM and IEEE International Conference on Formal Methods and Models for Co-Design (MEMOCODE’06). IEEE Computer Society, Washington, DC, 185--194.

Index Terms

• Theory of computation

  • Models of computation

    • Timed and hybrid models