Title: Execution time optimisation using delayed multidimensional retiming

Authors: Yaroub Elloumi; Mohamed Akil; Mohamed Hedi Bedoui

Addresses: ESIEE Paris, Laboratoire d'Informatique Gaspard Monge, Universite Paris-Est, Equipe A3SI 93162 Noisy-le-Grand, France; Faculty of Medicine of Monastir, Laboratory of Medical Technology and Image Processing, University of Monastir, 5019, Monastir, Tunisia ' ESIEE Paris, Laboratoire d'Informatique Gaspard Monge, Universite Paris-Est, Equipe A3SI 93162 Noisy-le-Grand, France ' Faculty of Medicine of Monastir, Laboratory of Medical Technology and Image Processing, University of Monastir, 5019, Monastir, Tunisia

Abstract: Multidimensional retiming (MR) is a software pipelining approach that ensures increasing the instruction-level parallelism across all the nested loops. All the MR techniques aim at achieving a full parallelism in order to schedule applications with a minimal cycle period. However, the growth of code sizes in terms of parallelism level engenders the rise in cycle period numbers. Thus, fully parallel multidimensional applications frequently face limiting factors when implemented on real-time systems. This paper presents a novel technique, called delayed MR, which schedules nested loops with a minimal cycle period, without achieving full parallelism. It is formulated into two efficient steps whose first one sweeps the nested loops with the target of selecting and ordering paths, whereas the second one applies an optimal MR to the selected paths. Our technique is verified by implementing several nested loops in NVIDIA architectures. The experimental results show that our technique achieves average improvements on execution time of 32.8% compared to the incremental technique and 19.35% compared to the chained one.

Keywords: nested loops; parallelism; software pipelining; loop transformation; execution time optimisation; delayed retiming; multidimensional retiming.

DOI: 10.1504/IJHPSA.2015.070393

International Journal of High Performance Systems Architecture, 2015 Vol.5 No.3, pp.178 - 191

Received: 24 Oct 2014
Accepted: 21 Mar 2015
Published online: 04 Jul 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article