WCET Nested-Loop Minimization in Terms of Instruction-Level-Parallelism

Yaroub Elloumi (1, 2) , Mohamed Akil (3) , Mohamed Hedi Bedoui (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 TIM - Laboratoire Technologie et Imagerie Médicale [Monastir]
3 Algorithms, architectures, image analysis and computer graphics

—Several high-performance applications integrate loop bodies which represent the most critical sections. This aspect brings two challenges. First, the Worst Case Execution Time (WCET) must be determined in order to define the nested loop timing behaviour. The second challenge consists in raising the parallelism-level to enhance the performance. In particular, the Multidimensional Retiming (MR) is an important optimization approach that offers several instruction-level-parallelism solutions. Despite the fact that full parallelism allows achieving the optimal WCET, it leads to a high growth in processing cores, which is inadequate to embedded real-time implementations. The main idea of this paper consists in driving the parallelism-level rise in terms of WCET development. First, the MR parameters that correspond to the nested loops are extracted. Thereafter, the WCET is formulated in term of the parallelism level rise. Then, an optimization heuristic is proposed which identifies the parallelism level that allows respecting the WCET constraint. Our experiments indicate the WCET prediction is accurate within an error rate of 8.54%. Secondly, the optimization heuristic implementations show an average improvement on number of cores of 27.18% compared to full parallel ones.

Mots clés: HW/SW codesign; design space exploration; optimization; WCET; nested loops; parallelism

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Yaroub Elloumi, Mohamed Akil, Mohamed Hedi Bedoui. WCET Nested-Loop Minimization in Terms of Instruction-Level-Parallelism. International Conference on High Performance Computing & Simulation (HPCS), Jul 2015, Amsterdam, Netherlands. ⟨hal-01796771⟩