Execution Time Optimization Using Delayed Multidimensional Retiming

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

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

— Multidimensional retiming is an efficient optimization approach that ensures increasing a parallelism level in order to optimize the execution time. Two existing techniques called incremental and chained multidimensional retiming are based on this approach, which aim at achieving a full parallelism on loop body in order to schedule applications with a minimum cycle period. However, the cycle number increases in terms of parallelism level which presents a limiting factor to respect the execution time constraint of real-time applications. In this paper, we show how the minimal cycle period is achieved in multidimensional applications without applying a full parallelism. We present the theory of a novel technique, called delayed multidimensional retiming. Firstly, two efficient algorithms are presented where the first one insures the extraction of timing and data dependency properties of the application and the second one selects the set of data path for retiming. Then, we propose theorems to deduce a retiming function for the selected paths. Finally, a third algorithm describing the optimization approach is introduced. The experimental results show that our technique improves execution times in comparison to existing techniques. It achieves average improvements on the execution time of 41.57% compared to the Incremental technique and 11.55% compared to the Chained technique.

Mots clés: Parallelism; modeling; nested loop; Optimization

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

Yaroub Elloumi, Mohamed Akil, Mohamed Hedi Bedoui. Execution Time Optimization Using Delayed Multidimensional Retiming. IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications, Oct 2012, Dublin, Ireland. ⟨hal-01800762⟩