Throughput Propagation in Constraint-Based Design Space Exploration for Mixed-Criticality Systems

ABSTRACT

When designing complex mixed-critical systems on multiprocessor platforms, a huge number of design alternatives has to be evaluated. Therefore, there is a need for tools which systematically find and analyze the ample alternatives and identify solutions that satisfy the design constraints. The recently proposed design space exploration (DSE) tool DeSyDe uses constraint programming (CP) to find implementations with performance guarantees for multiple applications with potentially mixed-critical design constraints on a shared platform. A key component of the DeSyDe tool is its throughput analysis component, called a throughput propagator in the context of CP. The throughput propagator guides the exploration by evaluating each design decision and is therefore executed excessively throughout the exploration. This paper presents two throughput propagators based on different analysis methods for DeSyDe. Their performance is evaluated in a range of experiments with six different application graphs, heterogeneous platform models and mixed-critical design constraints. The results suggest that the MCR throughput propagator is more efficient.

References

1. A. Bonfietti, L. Benini, M. Lombardi, and M. Milano. An efficient and complete approach for throughput-maximal SDF allocation and scheduling on multi-core platforms. In DATE, pages 897--902, 2010.
2. A. Bonfietti, M. Lombardi, M. Milano, and L. Benini. Throughput constraint for synchronous data flow graphs. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 26--40. Springer Berlin Heidelberg, 2009.
3. Boost Graph Library. http://www.boost.org. Accessed: 2016-11-20.
4. G. C. Buttazzo. Hard Real-time Computing Systems: Predictable Scheduling Algorithms And Applications. Springer, Santa Clara, CA, USA, 2011.
5. A. Dasdan and R. Gupta. Faster maximum and minimum mean cycle algorithms for system-performance analysis. IEEE TCAD, 17(10):889--899, 1998.
6. R. de Groote, P. K. F. Hölzenspies, J. Kuper, and H. Broersma. Back to basics: Homogeneous representations of multi-rate synchronous dataflow graphs. In MEMCODE'13, pages 35--46, 2013.
7. R. De Groote, J. Kuper, H. Broersma, and G. J. Smit. Max-plus algebraic throughput analysis of synchronous dataflow graphs. In EUROMICRO-SEAA, pages 29--38, 2012.
8. DeSyDe. https://github.com/forsyde/DeSyDe. Accessed: 2016-11-10.
9. M. Fakih, K. Grüttner, M. Fränzle, and A. Rettberg. Towards performance analysis of SDFGs mapped to shared--bus architectures using model--checking. In DATE, 2013.
10. A. H. Ghamarian, M. Geilen, S. Stuijk, T. Basten, A. Moonen, M. J. Bekooij, B. D. Theelen, and M. Mousavi. Throughput analysis of synchronous data flow graphs. In ACSD, pages 25--36, 2006.
11. A. Hansson, K. Goossens, M. Bekooij, and J. Huisken. CoMPSoC: A template for composable and predictable multi-processor system on chips. ACM TODAES, 14(1):2:1--2:24, Jan. 2009.
12. K. Ito and K. K. Parhi. Determining the minimum iteration period of an algorithm. VLSI Signal Processing, 11(3):229--244, 1995.
13. N. Khalilzad, K. Rosvall, and I. Sander. A modular design space exploration framework for multiprocessor real-time systems. In FDL, September 2016.
14. E. A. Lee and D. G. Messerschmitt. Synchronous data flow. In Proceedings of the IEEE, volume 75 of 9, pages 1235--1245, September 1987.
15. E. A. Lee and A. Sangiovanni-Vincentelli. A framework for comparing models of computation. IEEE TCAD, 17(12):1217--1229, Dec. 1998.
16. B. Lickly, I. Liu, S. Kim, H. D. Patel, S. A. Edwards, and E. A. Lee. Predictable programming on a precision timed architecture. In CASES, pages 137--146, New York, NY, USA, 2008. ACM.
17. U. M. Mirza, F. Gruian, and K. Kuchcinski. Mapping streaming applications on multiprocessors with time-division-multiplexed network-on-chip. CEE, 40(8):276--291, 2014.
18. O. Moreira, J.-D. Mol, M. Bekooij, and J. Van Meerbergen. Multiprocessor resource allocation for hard-real-time streaming with a dynamic job-mix. In IEEE RTAS, pages 332--341, 2005.
19. C. Pitter and M. Schoeberl. A real-time Java chip-multiprocessor. ACM TECS, 10(1):9:1--9:34, Aug. 2010.
20. K. Rosvall and I. Sander. A constraint-based design space exploration framework for real-time applications on MPSoCs. In DATE, pages 1--6, 2014.
21. C. Schulte, G. Tack, and M. Z. Lagerkvist. Modeling and Programming with Gecode, 2016. http://www.gecode.org/.
22. S. Sriram and S. S. Bhattacharyya. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker, Inc., New York, NY, USA, 2000.
23. S. Stuijk, T. Basten, M. Geilen, and H. Corporaal. Multiprocessor resource allocation for throughput-constrained synchronous dataflow graphs. In DAC, pages 777--782, 2007.
24. R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, et al. The worst-case execution-time problem---overview of methods and survey of tools. ACM TECS, 7(3):1--53, 2008.
25. J. Zhu, I. Sander, and A. Jantsch. Buffer minimization of real-time streaming applications scheduling on hybrid CPU/FPGA architectures. In DATE, pages 1506--1511, 2009.
26. J. Zhu, I. Sander, and A. Jantsch. Constrained global scheduling of streaming applications on MPSoCs. In ASP-DAC, pages 223--228, 2010.

• Computer systems organization

• Networks