Execution Time and Code Size Optimization using Multidimensional Retiming and Loop Striping

International audience— Nested loops present the most critical sections in several embedded real-time applications. To achieve a higher performance, the design process employs an optimization technique in order to increase parallelism. However, the nested loop codes rise greatly in terms of parallelism level. Due to tight execution time constraints, each optimization technique produces implementations with an important code size. This criterion presents a limiting factor to implement the provided results in embedded real-time systems. In this paper, we propose a novel optimization approach that combines the delayed multidimensional retiming and loop striping techniques. It explores the solution space, which is composed by all parallelism cases proposed by both techniques, in order to provide the implementation that achieves the execution time constraint while uses a lower code size. In this context, we present the theory of combining both techniques. Then, we propose efficient algorithms that ensure selecting a set of parallelism transformations, based on their execution time and code size evolutions. The experimental results show that our optimization approach provides optimal solutions compared to those provided by applying only one technique. It achieves average improvements on the code size of 35.21% compared to the delayed multidimensional retiming and 16.38% compared to the loop striping