Real-Time Task Migration for Dynamic Resource Management in Many-Core Systems

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



PDF
Thumbnail PDF

File

OASIcs.NG-RES.2020.5.pdf
  • Filesize: 0.52 MB
  • 14 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

Cite AsGet BibTex

Behnaz Pourmohseni, Fedor Smirnov, Stefan Wildermann, and Jürgen Teich. Real-Time Task Migration for Dynamic Resource Management in Many-Core Systems. In Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2020). Open Access Series in Informatics (OASIcs), Volume 77, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/OASIcs.NG-RES.2020.5

Abstract

Dynamic resource management strategies in embedded many-core systems rely on task migration to adapt the deployment (mapping) of applications dynamically, e.g., for thermal/power management or load balancing. In case of hard real-time applications, however, the current practice of on-line application adaptation is limited to reconfiguring the whole application between a set of statically computed mappings with statically verified timing guarantees. This heavily restricts the application’s adaptability. To enable hard real-time task migrations in many-core systems without relying on a static analysis, this paper presents (i) a predictable task migration mechanism supported with (ii) a lightweight migration timing analysis and (iii) a lightweight migration timing feasibility check which can be applied on-line to bound on the worst-case temporal overhead of a migration and examine the admissibility of this overhead w.r.t. the hard real-time requirements of the application. For a variety of applications and many-core platforms, we experimentally demonstrate the feasibility of hard real-time task migrations, the lightness of the proposed timing analysis and feasibility check for on-line use, and the advantage of the proposed task migration approach over mapping reconfiguration as the state-of-the-art real-time adaptation approach for many-core systems.

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
  • Hard real-time
  • task migration
  • timing analysis
  • dynamic resource management
  • multi-core
  • many-core

Metrics

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

References

  1. Andrea Acquaviva, Andrea Alimonda, Salvatore Carta, and Michele Pittau. Assessing task migration impact on embedded soft real-time streaming multimedia applications. EURASIP journal on embedded systems, 2008(1):518904, 2007. Google Scholar
  2. 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
  3. Zaid Al-bayati, Brett H Meyer, and Haibo Zeng. Fault-tolerant scheduling of multicore mixed-criticality systems under permanent failures. In Proceedings of the IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT), pages 57-62, 2016. Google Scholar
  4. Gabriel Marchesan Almeida, Sameer Varyani, Rémi Busseuil, Gilles Sassatelli, Pascal Benoit, Lionel Torres, Everton Alceu Carara, and Fernando Gehm Moraes. Evaluating the impact of task migration in multi-processor systems-on-chip. In Proceedings of the 23rd Symposium on Integrated Circuits and System Design (SBCCI), pages 73-78, 2010. Google Scholar
  5. Stefano Bertozzi, Andrea Acquaviva, Davide Bertozzi, and Antonio Poggiali. Supporting task migration in multi-processor systems-on-chip: a feasibility study. In Proceedings of Design, Automation and Test in Europe Conference and Exhibition (DATE), pages 15-20, 2006. Google Scholar
  6. Eduardo Wenzel Brião, Daniel Barcelos, Fabio Wronski, and Flávio Rech Wagner. Impact of task migration in NoC-based MPSoCs for soft real-time applications. In Proceedings of the IFIP International Conference on Very Large Scale Integration, pages 296-299, 2007. Google Scholar
  7. William J Dally. Virtual-channel flow control. IEEE Transactions on Parallel and Distributed Systems (TPDS), 3(2):194-205, 1992. Google Scholar
  8. 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 IEEE High Performance Extreme Computing Conference (HPEC), pages 1-6, 2013. Google Scholar
  9. Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transaction on Evolutionary Computation (TEVC), 6(2):182-197, 2002. Google Scholar
  10. Robert Dick. Embedded system synthesis benchmarks suite (E3S), 2010. URL: http://ziyang.eecs.umich.edu/~dickrp/e3sdd/.
  11. Piotr Dziurzanski, Amit Kumar Singh, and Leandro Soares Indrusiak. Multi-criteria resource allocation in modal hard real-time systems. EURASIP Journal on Embedded Systems, 2017(1):30, 2017. Google Scholar
  12. Ashaf El-Antably, Olivier Gruber, Frederic Rousseau, and Nicolas Fournel. Transparent and portable agent based task migration for data-flow applications on multi-tiled architectures. In Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), pages 183-192, 2015. Google Scholar
  13. Shimon Even. Graph algorithms. Cambridge University Press, 2011. Google Scholar
  14. Weiwei Fu, Tianzhou Chen, Chao Wang, and Li Liu. Optimizing memory access traffic via runtime thread migration for on-chip distributed memory systems. The Journal of Supercomputing, 69(3):1491-1516, 2014. Google Scholar
  15. Laurent Gantel, Salah Layouni, Mohamed El Amine Benkhelifa, François Verdier, and Stéphanie Chauvet. Multiprocessor task migration implementation in a reconfigurable platform. In Proceedings of the International Conference on Reconfigurable Computing and FPGAs (ReConFig), pages 362-367, 2009. Google Scholar
  16. Yang Ge, Parth Malani, and Qinru Qiu. Distributed task migration for thermal management in many-core systems. In Proceedings of the 47th Design Automation Conference (DAC), pages 579-584, 2010. Google Scholar
  17. 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
  18. 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
  19. Robert Hilbrich and J Reinier Van Kampenhout. Partitioning and task transfer on NoC-based many-core processors in the avionics domain. Journal Softwaretechnik-Trends, 30(3):6, 2011. Google Scholar
  20. Simon Holmbacka, Wictor Lund, Sebastien Lafond, and Johan Lilius. Task Migration for Dynamic Power and Performance Characteristics on Many-Core Distributed Operating Systems. In Proceedings of the 21st Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), pages 310-317, 2013. Google Scholar
  21. 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 Proceedings of the IEEE International Solid-State Circuits Conference (ISSCC), pages 108-109, 2010. Google Scholar
  22. Sebastian Kobbe, Lars Bauer, Daniel Lohmann, Wolfgang Schröder-Preikschat, and Jörg Henkel. DistRM: distributed resource management for on-chip many-core systems. In Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), pages 119-128, 2011. Google Scholar
  23. H Kopetz. Real-Time Systems: Design Principles for Distributed Embedded Applications. Springer, 2 edition, 2011. Google Scholar
  24. Zao Liu, Sheldon X-D Tan, Xin Huang, and Hai Wang. Task migrations for distributed thermal management considering transient effects. IEEE Transactions on Very Large Scale Integration (VLSI) Systems (TVLSI), 23(2):397-401, 2015. Google Scholar
  25. Martin Lukasiewycz, Michael Glaß, Felix Reimann, and Jürgen Teich. Opt4J: a modular framework for meta-heuristic optimization. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO), pages 1723-1730, 2011. Google Scholar
  26. 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 IEEE International Conference on Electronics, Circuits and Systems (ICECS), pages 396-399, 2016. Google Scholar
  27. Fabrizio Mulas, David Atienza, Andrea Acquaviva, Salvatore Carta, Luca Benini, and Giovanni De Micheli. Thermal balancing policy for multiprocessor stream computing platforms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 28(12):1870-1882, 2009. Google Scholar
  28. Peter Munk and Jan Richling. Migration-aware WCET estimation for heterogeneous multi-cores. ACM SIGBED Review, 11(3):22-25, 2014. Google Scholar
  29. Lionel M Ni and Philip K McKinley. A survey of wormhole routing techniques in direct networks. Computer, 26(2):62-76, 1993. Google Scholar
  30. Michele Pittau, Andrea Alimonda, Salvatore Carta, and Andrea Acquaviva. Impact of task migration on streaming multimedia for embedded multiprocessors: A quantitative evaluation. In Proceedings of the IEEE/ACM/IFIP Workshop on Embedded Systems for Real-Time Multimedia, pages 59-64, 2007. Google Scholar
  31. 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 Proceedings of the 31st Euromicro Conference on Real-Time Systems (ECRTS), volume 133, pages 12:1-12:24, 2019. Google Scholar
  32. Behnaz Pourmohseni, Stefan Wildermann, Michael Glaß, and Jürgen Teich. Predictable Run-Time Mapping Reconfiguration for Real-Time Applications on Many-Core Systems. In Proceedings of the 25th International Conference on Real-Time Networks and Systems (RTNS), pages 148-157, 2017. Google Scholar
  33. 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, 55(2):433-469, 2019. Google Scholar
  34. Felix Reimann, Martin Lukasiewycz, Michael Glaß, and Fedor Smirnov. OpenDSE - open design space exploration framework, 2018. URL: http://opendse.sourceforge.net/.
  35. 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 6th International Workshop on Worst-Case Execution Time Analysis (WCET), 2006. Google Scholar
  36. Tilera Corporation. Tile Processor Architecture Overview for the TILE-Gx Series, 2012. Google Scholar
  37. Prabhat Kumar Saraswat, Paul Pop, and Jan Madsen. Task migration for fault-tolerance in mixed-criticality embedded systems. ACM SIGBED Review, 6(3):6, 2009. Google Scholar
  38. Abhik Sarkar, Frank Mueller, and Harini Ramaprasad. Predictable Task Migration for Locked Caches in Multi-Core Systems. ACM SIGPLAN Notices, 46(5):131-140, 2011. Google Scholar
  39. 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 50th Design Automation Conference (DAC), pages 1-10, 2013. Google Scholar
  40. Pranav Tendulkar and Sander Stuijk. A case study into predictable and composable MPSoC reconfiguration. In Proceedings of the IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum (IPDPSW), pages 293-300, 2013. Google Scholar
  41. Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, and Jürgen Teich. Invasive Computing for mapping parallel programs to many-core architectures. Springer, 2018. Google Scholar
  42. 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
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