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

Abstract : —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.