Document Open Access Logo

Fine-Grain Iterative Compilation for WCET Estimation

Authors Isabelle Puaut, Mickaël Dardaillon, Christoph Cullmann, Gernot Gebhard, Steven Derrien

PDF
Thumbnail PDF

File

OASIcs.WCET.2018.9.pdf
  • Filesize: 0.52 MB
  • 12 pages

Document Identifiers

Author Details

Isabelle Puaut
  • Univ Rennes, Inria, CNRS, IRISA
Mickaël Dardaillon
  • Univ Rennes, Inria, CNRS, IRISA
Christoph Cullmann
  • AbsInt Angewandte Informatik GmbH, Science Park 1, D-66123 Saarbrücken, Germany
Gernot Gebhard
  • AbsInt Angewandte Informatik GmbH, Science Park 1, D-66123 Saarbrücken, Germany
Steven Derrien
  • Univ Rennes, Inria, CNRS, IRISA

Cite As Get BibTex

Isabelle Puaut, Mickaël Dardaillon, Christoph Cullmann, Gernot Gebhard, and Steven Derrien. Fine-Grain Iterative Compilation for WCET Estimation. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/OASIcs.WCET.2018.9

Abstract

Compiler optimizations, although reducing the execution times of programs, raise issues in static WCET estimation techniques and tools. Flow facts, such as loop bounds, may not be automatically found by static WCET analysis tools after aggressive code optimizations. In this paper, we explore the use of iterative compilation (WCET-directed program optimization to explore the optimization space), with the objective to (i) allow flow facts to be automatically found and (ii) select optimizations that result in the lowest WCET estimates. We also explore to which extent code outlining helps, by allowing the selection of different optimization options for different code snippets of the application.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
  • Computer systems organization → Embedded systems
Keywords
  • Worst-Case Execution Time Estimation
  • Compiler optimizations
  • Iterative Compilation
  • Flow fact extraction
  • Outlining

Metrics

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

References

  1. aiT:the industry standard for static timing analysis. http://www.absint.com/ait. Google Scholar
  2. Felix V. Agakov, Edwin V. Bonilla, John Cavazos, Björn Franke, Grigori Fursin, Michael F. P. O'Boyle, John Thomson, Marc Toussaint, and Christopher K. I. Williams. Using machine learning to focus iterative optimization. In Fourth IEEE/ACM International Symposium on Code Generation and Optimization (CGO 2006), 26-29 March 2006, New York, New York, USA, pages 295-305, 2006. Google Scholar
  3. Guillem Bernat and Niklas Holsti. Compiler support for WCET analysis: a wish list. In Proceedings of the 3rd International Workshop on Worst-Case Execution Time Analysis, WCET 2003 - a Satellite Event to ECRTS 2003, Polytechnic Institute of Porto, Portugal, July 1, 2003, pages 65-69, 2003. Google Scholar
  4. Yang Chen, Shuangde Fang, Yuanjie Huang, Lieven Eeckhout, Grigori Fursin, Olivier Temam, and Chengyong Wu. Deconstructing iterative optimization. TACO, 9(3):21:1-21:30, 2012. URL: http://dx.doi.org/10.1145/2355585.2355594.
  5. Keith Cooper and Linda Torczon. Engineering a compiler. Morgan Kaufmann, 2011. Google Scholar
  6. Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steven W. Reeves, Devika Subramanian, Linda Torczon, and Todd Waterman. ACME: adaptive compilation made efficient. In Proceedings of the 2005 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'05), Chicago, Illinois, USA, June 15-17, 2005, pages 69-77, 2005. Google Scholar
  7. Christoph Cullmann and Florian Martin. Data-Flow Based Detection of Loop Bounds. In Christine Rochange, editor, 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07), volume 6 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2007. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2007.1193.
  8. Steven Derrien, Isabelle Puaut, Panayiotis Alefragis, Marcus Bednara, Harald Bucher, Clement David, Yann Debray, Umut Durak, Imen Fassi, Christian Ferdinand, Damien Hardy, Angeliki Kritikakou, Gerard K. Rauwerda, Simon Reder, Martin Sicks, Timo Stripf, Kim Sunesen, Timon D. ter Braak, Nikolaos S. Voros, and Jürgen Becker. Wcet-aware parallelization of model-based applications for multi-cores: The ARGO approach. In Design, Automation & Test in Europe Conference & Exhibition, DATE 2017, Lausanne, Switzerland, March 27-31, 2017, pages 286-289, 2017. Google Scholar
  9. Heiko Falk, Peter Marwedel, and Paul Lokuciejewski. Reconciling compilation and timing analysis. In Advances in Real-Time Systems (to Georg Färber on the occasion of his appointment as Professor Emeritus at TU München after leading the Lehrstuhl für Realzeit-Computersysteme for 34 illustrious years)., pages 145-170, 2012. Google Scholar
  10. A. Floc'h, T. Yuki, A. El-Moussawi, A. Morvan, K. Martin, M. Naullet, M. Alle, L. L'Hours, N. Simon, S. Derrien, F. Charot, C. Wolinski, and O. Sentieys. Gecos: A framework for prototyping custom hardware design flows. In Source Code Analysis and Manipulation (SCAM), 2013 IEEE 13th International Working Conference on, pages 100-105, Sept 2013. Google Scholar
  11. Raimund Kirner, Peter P. Puschner, and Adrian Prantl. Transforming flow information during code optimization for timing analysis. Real-Time Systems, 45(1-2):72-105, 2010. URL: http://dx.doi.org/10.1007/s11241-010-9091-8.
  12. Chris Lattner and Vikram Adve. LLVM: A compilation framework for lifelong program analysis and transformation. In International Symposium on Code Generation and Optimization, pages 75-88, San Jose, CA, USA, Mar 2004. Google Scholar
  13. Thomas Lefeuvre, Imen Fassi, Christoph Cullmann, Gernot Gebbard, Emin Koray Kasnakli, Isabelle Puaut, and Steven Derrien. Using polyhedral techniques to tighten wcet estimates of optimized code: a case study with array contraction. In Design, Automation & Test in Europe Conference & Exhibition, DATE 2018, Dresden, Germany, March 19-23, 2018, 2018. Google Scholar
  14. Hanbing Li, Isabelle Puaut, and Erven Rohou. Traceability of flow information: Reconciling compiler optimizations and wcet estimation. In Proceedings of the 22Nd International Conference on Real-Time Networks and Systems, RTNS '14, pages 97:97-97:106, New York, NY, USA, 2014. ACM. Google Scholar
  15. Hanbing Li, Isabelle Puaut, and Erven Rohou. Tracing flow information for tighter WCET estimation: Application to vectorization. In 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2015, Hong Kong, China, August 19-21, 2015, pages 217-226, 2015. Google Scholar
  16. Chunhua Liao, Daniel J Quinlan, Richard Vuduc, and Thomas Panas. Effective source-to-source outlining to support whole program empirical optimization. In Languages and Compilers for Parallel Computing, pages 308-322. Springer, 2010. Google Scholar
  17. Paul Lokuciejewski, Sascha Plazar, Heiko Falk, Peter Marwedel, and Lothar Thiele. Approximating pareto optimal compiler optimization sequences - a trade-off between wcet, ACET and code size. Softw., Pract. Exper., 41(12):1437-1458, 2011. URL: http://dx.doi.org/10.1002/spe.1079.
  18. Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, and Per Stenström. The worst-case execution-time problem - overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst., 7(3):36:1-36:53, 2008. 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