Document Open Access Logo

Isolation-Aware Timing Analysis and Design Space Exploration for Predictable and Composable Many-Core Systems

Authors Behnaz Pourmohseni , Fedor Smirnov, Stefan Wildermann, Jürgen Teich

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2019.12.pdf
  • Filesize: 0.79 MB
  • 24 pages

Document Identifiers

Author Details

Behnaz Pourmohseni
  • Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Germany
Fedor Smirnov
  • Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Germany
Stefan Wildermann
  • Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Germany
Jürgen Teich
  • Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Germany

Acknowledgements

This work is funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project Number 146371743 - TRR 89 Invasive Computing.

Cite As Get BibTex

Behnaz Pourmohseni, Fedor Smirnov, Stefan Wildermann, and Jürgen Teich. Isolation-Aware Timing Analysis and Design Space Exploration for Predictable and Composable Many-Core Systems. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ECRTS.2019.12

Abstract

Composable many-core systems enable the independent development and analysis of applications which will be executed on a shared platform where the mix of concurrently executed applications may change dynamically at run time. For each individual application, an off-line DSE is performed to compute several mapping alternatives on the platform, offering Pareto-optimal trade-offs in terms of real-time guarantees, resource usage, etc. At run time, one mapping is then chosen to launch the application on demand. In this context, to enable an independent analysis of each individual application at design time, so-called inter-application isolation schemes are applied which specify temporal/spatial isolation policies between applications. State-of-the-art composable many-core systems are developed based on a fixed isolation scheme that is exclusively applied to every resource in every mapping of every application and use a timing analysis tailored to that isolation scheme to derive timing guarantees for each mapping. A fixed isolation scheme, however, heavily restricts the explored space of solutions and can, therefore, lead to suboptimality. Lifting this restriction necessitates a timing analysis that is applicable to mappings with an arbitrary mix of isolation schemes on different resources. To address this issue, in this paper, we (a) present an isolation-aware timing analysis that - unlike existing analyses - can handle multiple isolation schemes in combination within one mapping and delivers safe yet tight timing bounds by identifying and excluding interference scenarios that can never happen under the given combination of isolation schemes. Based on the timing analysis, we (b) present a DSE which explores the choices of isolation scheme per resource within each mapping and uses the proposed timing analysis for timing verification. Experimental results demonstrate that, for a variety of real-time applications and many-core platforms, the proposed approach achieves an improvement of up to 67% in the quality of delivered mappings compared to approaches based on a fixed isolation scheme.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
  • Computer systems organization → Embedded and cyber-physical systems
  • Computer systems organization → Multicore architectures
Keywords
  • Many-core systems
  • timing analysis
  • design space exploration (DSE)
  • isolation scheme
  • predictability
  • composability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Benny Akesson, Anca Molnos, Andreas Hansson, Jude Ambrose Angelo, and Kees Goossens. Composability and predictability for independent application development, verification, and execution. In Multiprocessor System-on-Chip, pages 25-56. Springer, 2011. Google Scholar
  2. Sebastian Altmeyer, Robert I Davis, Leandro Indrusiak, Claire Maiza, Vincent Nelis, and Jan Reineke. A generic and compositional framework for multicore response time analysis. In Proceedings of the Conference on Real Time Networks and Systems (RTNS), pages 129-138. ACM, 2015. Google Scholar
  3. Tobias Blickle, Jürgen Teich, and Lothar Thiele. System-level synthesis using evolutionary algorithms. Design Automation for Embedded Systems, 3(1):23-58, 1998. Google Scholar
  4. Tilera Corporation. Tile Processor Architecture Overview for the TILE-Gx Series, 2012. Google Scholar
  5. William J Dally. Virtual-channel flow control. IEEE Transactions on Parallel and Distributed systems, 3(2):194-205, 1992. Google Scholar
  6. Dakshina Dasari, Vincent Nelis, and Benny Akesson. A framework for memory contention analysis in multi-core platforms. Real-Time Systems, 52(3):272-322, 2016. Google Scholar
  7. Lawrence Davis. Handbook of genetic algorithms. VNR computer library. Van Nostrand Reinhold, 1991. Google Scholar
  8. Robert I Davis, Sebastian Altmeyer, Leandro S Indrusiak, Claire Maiza, Vincent Nelis, and Jan Reineke. An extensible framework for multicore response time analysis. Real-Time Systems, pages 1-55, 2017. Google Scholar
  9. Benoît Dupont de Dinechin, Renaud Ayrignac, Pierre-Edouard Beaucamps, Patrice Couvert, Benoit Ganne, Pierre Guironnet de Massas, François Jacquet, Samuel Jones, Nicolas Morey Chaisemartin, Frédéric Riss, et al. A clustered manycore processor architecture for embedded and accelerated applications. In Proceedings of High Performance Extreme Computing Conference (HPEC), pages 1-6. IEEE, 2013. Google Scholar
  10. Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182-197, 2002. Google Scholar
  11. Robert Dick. Embedded system synthesis benchmarks suite (E3S), 2010. URL: http://ziyang.eecs.umich.edu/~dickrp/e3sdd/.
  12. Carlos M. Fonseca and Peter J. Fleming. Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization. In Proceedings of the International Conference on Genetic Algorithms, pages 416-423. Morgan Kaufmann Publishers Inc., 1993. Google Scholar
  13. Carlos M Fonseca and Peter J Fleming. An overview of evolutionary algorithms in multiobjective optimization. Evolutionary computation, 3(1):1-16, 1995. Google Scholar
  14. Michael R Garey and David S Johnson. A Guide to the Theory of NP-Completeness. Computers and Intractability, pages 37-79, 1990. Google Scholar
  15. Georgia Giannopoulou, Kai Lampka, Nikolay Stoimenov, and Lothar Thiele. Timed model checking with abstractions: Towards worst-case response time analysis in resource-sharing manycore systems. In Proceedings of the International Conference on Embedded Software, pages 63-72. ACM, 2012. Google Scholar
  16. Georgia Giannopoulou, Nikolay Stoimenov, Pengcheng Huang, and Lothar Thiele. Scheduling of mixed-criticality applications on resource-sharing multicore systems. In Proceedings of the International Conference on Embedded Software, page 17. ACM, 2013. Google Scholar
  17. Georgia Giannopoulou, Nikolay Stoimenov, Pengcheng Huang, Lothar Thiele, and Benoît Dupont de Dinechin. Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources. Real-Time Systems, 52(4):399-449, 2016. Google Scholar
  18. Michael Glaß, Jürgen Teich, Martin Lukasiewycz, and Felix Reimann. Hybrid optimization techniques for system-level design space exploration. In Handbook of Hardware/Software Codesign, volume 1, pages 217-246. Springer, 2017. Google Scholar
  19. Kees Goossens, Arnaldo Azevedo, Karthik Chandrasekar, Manil Dev Gomony, Sven Goossens, Martijn Koedam, Yonghui Li, Davit Mirzoyan, Anca Molnos, Ashkan Beyranvand Nejad, et al. Virtual execution platforms for mixed-time-criticality systems: the CompSOC architecture and design flow. ACM SIGBED Review, 10(3):23-34, 2013. Google Scholar
  20. Sebastian Hahn, Jan Reineke, and Reinhard Wilhelm. Towards compositionality in execution time analysis: definition and challenges. ACM SIGBED Review, 12(1):28-36, 2015. Google Scholar
  21. Andreas Hansson, Kees Goossens, Marco Bekooij, and Jos Huisken. CoMPSoC: A template for composable and predictable multi-processor system on chips. ACM Transactions on Design Automation of Electronic Systems (TODAES), 14(1):2, 2009. Google Scholar
  22. Jan Heisswolf, Ralf König, Martin Kupper, and Jürgen Becker. Providing multiple hard latency and throughput guarantees for packet switching networks on chip. Computers &Electrical Engineering, 39(8):2603-2622, 2013. Google Scholar
  23. Jason Howard, Saurabh Dighe, Yatin Hoskote, Sriram Vangal, David Finan, Gregory Ruhl, David Jenkins, Howard Wilson, Nitin Borkar, Gerhard Schrom, et al. A 48-core IA-32 message-passing processor with DVFS in 45nm CMOS. In International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), pages 108-109. IEEE, 2010. Google Scholar
  24. Timon Kelter, Tim Harde, Peter Marwedel, and Heiko Falk. Evaluation of resource arbitration methods for multi-core real-time systems. In Proceedings of the workshop on Worst-Case Execution Time Analysis (WCET). Schloss Dagstuhl-Leibniz-Zentrum f"ur Informatik, 2013. Google Scholar
  25. James Kennedy. Particle swarm optimization. Encyclopedia of Machine Learning, pages 760-766, 2010. Google Scholar
  26. Pham Nam Khanh, Amit Kumar Singh, Akash Kumar, and Khin Mi Mi Aung. Incorporating energy and throughput awareness in design space exploration and run-time mapping for heterogeneous MPSoCs. In Proceedings of the Euromicro Conference on Digital System Design (DSD), pages 513-521. IEEE, 2013. Google Scholar
  27. Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. Optimization by simulated annealing. science, 220(4598):671-680, 1983. Google Scholar
  28. Marco Laumanns, Lothar Thiele, Kalyanmoy Deb, and Eckart Zitzler. Combining convergence and diversity in evolutionary multiobjective optimization. Evolutionary Computation, 10(3):263-282, 2002. Google Scholar
  29. Martin Lukasiewycz, Michael Glaß, Christian Haubelt, and Jürgen Teich. SAT-decoding in evolutionary algorithms for discrete constrained optimization problems. In Proceedings of the IEEE Congress onEvolutionary Computation, pages 935-942. IEEE, 2007. Google Scholar
  30. Martin Lukasiewycz, Michael Glaß, Felix Reimann, and Jürgen Teich. Opt4J: a modular framework for meta-heuristic optimization. In Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO), pages 1723-1730. ACM, 2011. Google Scholar
  31. Martin Lukasiewycz, Shanker Shreejith, and Suhaib A Fahmy. System simulation and optimization using reconfigurable hardware. In International Symposium on Integrated Circuits (ISIC), pages 468-471, 2014. Google Scholar
  32. Guilherme Madalozzo, Liana Duenha, Rodolfo Azevedo, and Fernando G Moraes. Scalability evaluation in many-core systems due to the memory organization. In Proceedings of the International Conference on Electronics, Circuits and Systems (ICECS), pages 396-399. IEEE, 2016. Google Scholar
  33. Giovanni Mariani, Prabhat Avasare, Geert Vanmeerbeeck, Chantal Ykman-Couvreur, Gianluca Palermo, Cristina Silvano, and Vittorio Zaccaria. An industrial design space exploration framework for supporting run-time resource management on multi-core systems. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE), pages 196-201, 2010. Google Scholar
  34. Tulika Mitra, Jürgen Teich, and Lothar Thiele. Time-Critical Systems Design: A Survey. IEEE Design &Test, 35(2):8-26, 2018. Google Scholar
  35. Lionel M Ni and Philip K McKinley. A survey of wormhole routing techniques in direct networks. Computer, 26(2):62-76, 1993. Google Scholar
  36. Roberta Piscitelli and Andy D Pimentel. Design space pruning through hybrid analysis in system-level design space exploration. In Proceedings of the Conference on Design, Automation and Test in Europe Conference and Exhibition (DATE), pages 781-786. IEEE, 2012. Google Scholar
  37. Behnaz Pourmohseni, Stefan Wildermann, Michael Glaß, and Jürgen Teich. Hard real-time application mapping reconfiguration for NoC-based many-core systems. Real-Time Systems, pages 1-37, 2019. Google Scholar
  38. Felix Reimann, Martin Lukasiewycz, Michael Glaß, and Fedor Smirnov. OpenDSE - open design space exploration framework, 2018. URL: http://opendse.sourceforge.net/.
  39. Jan Reineke, Björn Wachter, Stefan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker. A definition and classification of timing anomalies. In Proceedings of the International Workshop on Worst-Case Execution Time Analysis (WCET). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2006. Google Scholar
  40. Hamza Rihani, Matthieu Moy, Claire Maiza, Robert I Davis, and Sebastian Altmeyer. Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor. In Proceedings of the conference on Real-Time Networks and Systems (RTNS), pages 67-76. ACM, 2016. Google Scholar
  41. Benjamin Rouxel, Steven Derrien, and Isabelle Puaut. Tightening contention delays while scheduling parallel applications on multi-core architectures. ACM Transactions on Embedded Computing Systems (TECS), 16(5s):164, 2017. Google Scholar
  42. Pradip Kumar Sahu, Tapan Shah, Kanchan Manna, and Santanu Chattopadhyay. Application mapping onto mesh-based network-on-chip using discrete particle swarm optimization. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 22(2):300-312, 2014. Google Scholar
  43. Z. Shi and A. Burns. Real-Time Communication Analysis for On-Chip Networks with Wormhole Switching. In International Symposium on Networks-on-Chip (NOCS), pages 161-170, 2008. Google Scholar
  44. Amit Kumar Singh, Akash Kumar, and Thambipillai Srikanthan. Accelerating throughput-aware runtime mapping for heterogeneous MPSoCs. ACM Transaction on Design Automation of Electronic Systems (TODAES), 18(1):9:1-9:29, 2013. Google Scholar
  45. Amit Kumar Singh, Muhammad Shafique, Akash Kumar, and Jörg Henkel. Mapping on multi/many-core systems: survey of current and emerging trends. In Proceedings of the Design Automation Conference (DAC), pages 1-10, 2013. Google Scholar
  46. Stefanos Skalistis and Alena Simalatsar. Worst-case execution time analysis for many-core architectures with NoC. In International Conference on Formal Modeling and Analysis of Timed Systems, pages 211-227. Springer, 2016. Google Scholar
  47. Stefanos Skalistis and Alena Simalatsar. Near-optimal deployment of dataflow applications on many-core platforms with real-time guarantees. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE), pages 752-757. IEEE, 2017. Google Scholar
  48. Andreas Weichslgartner, Deepak Gangadharan, Stefan Wildermann, Michael Glaß, and Jürgen Teich. DAARM: Design-time application analysis and run-time mapping for predictable execution in many-core systems. In Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), pages 1-10, 2014. Google Scholar
  49. Andreas Weichslgartner, Stefan Wildermann, Deepak Gangadharan, Michael Glaß, and Jürgen Teich. A design-time/run-time application mapping methodology for predictable execution time in MPSoCs. ACM Transactions on Embedded Computing Systems (TECS), 2018. Google Scholar
  50. Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, and Jürgen Teich. Invasive Computing for mapping parallel programs to many-core architectures. Springer, 2018. Google Scholar
  51. Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, et al. The worst-case execution-time problem-overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems (TECS), 7(3):36, 2008. Google Scholar
  52. Pascal T Wolkotte, Gerard JM Smit, Nikolay Kavaldjiev, Jens E Becker, and Jürgen Becker. Energy model of networks-on-chip and a bus. In Proceedings of the International Symposium on System-on-Chip (SoC), pages 82-85, 2005. Google Scholar
  53. Chantal Ykman-Couvreur, Prabhat Avasare, Giovanni Mariani, Gianluca Palermo, Cristina Silvano, and Vittorio Zaccaria. Linking run-time resource management of embedded multi-core platforms with automated design-time exploration. IET Computers and Digital Techniques, 5(2):123-135, 2011. Google Scholar
  54. Jia Zhan, Nikolay Stoimenov, Jin Ouyang, Lothar Thiele, Vijaykrishnan Narayanan, and Yuan Xie. Designing energy-efficient NoC for real-time embedded systems through slack optimization. In Proceedings of the Design Automation Conference (DAC), pages 1-6. IEEE, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact