Skip to Main content Skip to Navigation
Conference papers

Execution Time Optimization Using Delayed Multidimensional Retiming

Abstract : — 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.
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01800762
Contributor : Yaroub Elloumi <>
Submitted on : Monday, May 28, 2018 - 3:39:42 AM
Last modification on : Thursday, October 22, 2020 - 3:02:02 PM
Long-term archiving on: : Wednesday, August 29, 2018 - 12:38:03 PM

File

Execution Time Optimization Us...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01800762, version 1

Collections

Citation

Yaroub Elloumi, Mohamed Akil, Mohamed 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⟩

Share