Document Open Access Logo

Bus-Aware Static Instruction SPM Allocation for Multicore Hard Real-Time Systems

Authors Dominic Oehlert, Arno Luppold, Heiko Falk

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2017.1.pdf
  • Filesize: 0.63 MB
  • 22 pages

Document Identifiers

Author Details

Dominic Oehlert
Arno Luppold
Heiko Falk

Cite As Get BibTex

Dominic Oehlert, Arno Luppold, and Heiko Falk. Bus-Aware Static Instruction SPM Allocation for Multicore Hard Real-Time Systems. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ECRTS.2017.1

Abstract

Over the past years, multicore systems emerged into the domain of hard real-time systems. These systems introduce common buses and shared memories which heavily influence the timing behavior. We show that existing WCET optimizations may lead to suboptimal results when applied to multicore setups. Additionally we provide both a genetic and a precise Integer Linear Programming (ILP)-based static instruction scratchpad memory allocation optimization which are capable of exploiting multicore properties, resulting in a WCET reduction of 26% in average compared with a bus-unaware optimization. Furthermore, we show that our ILP-based optimization's average runtime is distinctively lower in comparison to the genetic approach. Although limiting the number of tasks per core to one and partially exploiting private instruction SPMs, we cover the most crucial elements of a multicore setup: the interconnection and shared resources.

Subject Classification

Keywords
  • Compiler
  • Optimization
  • WCET
  • Real-Time
  • Multicore

Metrics

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

References

  1. AbsInt Angewandte Informatik, GmbH. aiT Worst-Case Execution Time Analyzers, 2017. Google Scholar
  2. Sudipta Chattopadhyay and Abhik Roychoudhury. Static Bus Schedule Aware Scratchpad Allocation in Multiprocessors. In Proceedings of the 2011 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems, LCTES'11, pages 11-20, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1967677.1967680.
  3. Sudipta Chattopadhyay, Abhik Roychoudhury, and Tulika Mitra. Modeling Shared Cache and Bus in Multi-cores for Timing Analysis. In Proceedings of the 13th International Workshop on Software and Compilers for Embedded Systems, SCOPES'10, pages 6:1-6:10, New York, NY, USA, 2010. ACM. URL: http://dx.doi.org/10.1145/1811212.1811220.
  4. Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Björn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sørensen, Peter Wägemann, and Simon Wegener. TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research. In Proceedings of the 16th International Workshop on Worst-Case Execution Time Analysis (WCET), OpenAccess Series in Informatics (OASIcs), pages 2:1-2:10, Toulouse, France, 2016. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2016.2.
  5. Heiko Falk and Jan C. Kleinsorge. Optimal Static WCET-aware Scratchpad Allocation of Program Code. In Proceedings of the 46th Annual Design Automation Conference, DAC, pages 732-737, San Francisco, CA, USA, 2009. URL: http://dx.doi.org/10.1145/1629911.1630101.
  6. Heiko Falk and Paul Lokuciejewski. A compiler framework for the reduction of worst-case execution times. Real-Time Systems, 46(2):251-300, 2010. URL: http://dx.doi.org/10.1007/s11241-010-9101-x.
  7. David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, Inc., Boston, MA, USA, 1989. Google Scholar
  8. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. The Mälardalen WCET Benchmarks: Past, Present And Future. In 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010), OASIcs, pages 136-146, Dagstuhl, Germany, 2010. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2010.136.
  9. Morteza Mohajjel Kafshdooz and Alireza Ejlali. Dynamic Shared SPM Reuse for Real-Time Multicore Embedded Systems. ACM Transactions on Architecture and Code Optimization, 12(2):12:1-12:25, May 2015. URL: http://dx.doi.org/10.1145/2738051.
  10. T. Kelter, H. Borghorst, and P. Marwedel. WCET-aware scheduling optimizations for multi-core real-time systems. In 2014 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XIV), pages 67-74, Samos, Greece, July 2014. URL: http://dx.doi.org/10.1109/SAMOS.2014.6893196.
  11. Timon Kelter. WCET Analysis and Optimization for Multi-Core Real-Time Systems. PhD thesis, TU Dortmund, Department of Computer Science, Dortmund, Germany, March 2015. Google Scholar
  12. Timon Kelter, Heiko Falk, Peter Marwedel, Sudipta Chattopadhyay, and Abhik Roychoudhury. Static analysis of multi-core TDMA resource arbitration delays. Real-Time Systems, 50(2):185-229, 2014. URL: http://dx.doi.org/10.1007/s11241-013-9189-x.
  13. Y. Kim, D. Broman, J. Cai, and A. Shrivastaval. WCET-aware dynamic code management on scratchpads for Software-Managed Multicores. In 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 179-188, Berlin, Germany, April 2014. URL: http://dx.doi.org/10.1109/RTAS.2014.6926001.
  14. Donald Ervin Knuth. Fundamental algorithms. The art of computer programming. Addison-Wesley, Reading, MA, USA, 3. ed edition, 1997. Google Scholar
  15. Yu Liu and Wei Zhang. Scratchpad Memory Architectures and Allocation Algorithms for Hard Real-Time Multicore Processors. Journal of Computing Science and Engineering, 9(2):51-72, 2015. URL: http://dx.doi.org/10.5626/JCSE.2015.9.2.51.
  16. Dominic Oehlert, Arno Luppold, and Heiko Falk. Practical Challenges of ILP-based SPM Allocation Optimizations. In Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems, SCOPES'16, pages 86-89, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2906363.2906371.
  17. Vivy Suhendra and Tulika Mitra. Exploring Locking &Partitioning for Predictable Shared Caches on Multi-cores. In Proceedings of the 45th Annual Design Automation Conference, DAC'08, pages 300-303, New York, NY, USA, 2008. ACM. URL: http://dx.doi.org/10.1145/1391469.1391545.
  18. Vivy Suhendra, Tulika Mitra, Abhik Roychoudhury, and Ting Chen. WCET Centric Data Allocation to Scratchpad Memory. In Proceedings of the 26th IEEE International Real-Time Systems Symposium, RTSS'05, pages 223-232, Washington, DC, USA, 2005. IEEE Computer Society. URL: https://doi.org/10.1109/RTSS.2005.45.
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