Skip to Main content Skip to Navigation
Conference papers

Tracing Flow Information for Tighter WCET Estimation: Application to Vectorization

Hanbing Li 1 Isabelle Puaut 1 Erven Rohou 1 
1 ALF - Amdahl's Law is Forever
Inria Rennes – Bretagne Atlantique , IRISA-D3 - ARCHITECTURE
Abstract : Real-time systems have become ubiquitous, and many play an important role in our everyday life. For hard real-time systems, computing correct results is not the only requirement. In addition, these results must be produced within predetermined deadlines. Designers must compute the worst-case execution times (WCET) of the tasks composing the system, and guarantee that they meet the required timing constraints. Standard static WCET estimation techniques establish a WCET bound from an analysis of the machine code, taking into account additional flow information provided at source code level, either by the programmer or from static code analysis. Precise flow information helps produce tighter WCET bounds, hence limiting over-provisioning the system. However, flow information is difficult to maintain consistent through the dozens of optimizations applied by a compiler, and the majority of real-time systems simply do not apply any optimization. Vectorization is a powerful optimization that exploits data-level parallelism present in many applications, using the SIMD (single instruction multiple data) extensions of processor instruction sets. Vectorization is a mature optimization, and it is key to the performance of many systems. Unfortunately, it strongly impacts the control flow structure of functions and loops, and makes it more difficult to trace flow information from high-level down to machine code. For this reason, as many other optimizations, it is overlooked in real-time systems. In this paper, we propose a method to trace and maintain flow information from source code to machine code when vectorization optimization is applied. WCET estimation can benefit from this traceability. We implemented our approach in the LLVM compiler. In addition, we show through measurements on single-path programs that vectorization not only improves average-case performance but also WCETs. The WCET improvement ratio ranges from 1.18x to 1.41x depending on the target architecture on a benchmark suite designed for vectorizing compilers (TSVC).
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Erven Rohou Connect in order to contact the contributor
Submitted on : Friday, July 17, 2015 - 11:38:28 AM
Last modification on : Monday, June 27, 2022 - 3:05:10 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 7:03:32 AM


Files produced by the author(s)


  • HAL Id : hal-01177902, version 1


Hanbing Li, Isabelle Puaut, Erven Rohou. Tracing Flow Information for Tighter WCET Estimation: Application to Vectorization. 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Aug 2015, Hong-Kong, China. pp.10. ⟨hal-01177902⟩



Record views


Files downloads