Title: Guidance of loop ordering for reduced memory usage in signal processing applications
Authors: Kjeldsberg, Per Gunnar ×
Catthoor, Francky
Verdoolaege, Sven
Palkovic, Martin
Vandecappelle, Arnout
Aas, Einar J. #
Issue Date: 2008
Publisher: Springer New York LLC
Series Title: Journal of Signal Processing Systems vol:53 issue:3 pages:301-321
Abstract: Data dominated signal processing applications are
typically described using large and multi-dimensional arrays and loop nests. The
order of production and consumption of array elements in these loop nests has
huge impact on the amount of memory required during execution. This is essential
since the size and complexity of the memory hierarchy is the
dominating factor for power, performance and chip size in these applications.
This paper presents a number of guiding principles for the ordering of the
dimensions in the loop nests.
They enable the designer, or design tools, to find the optimal ordering of loop nest
dimensions for individual data dependencies in the code. We prove the validity
of the guiding principles when no prior restrictions are given regarding fixation
of dimensions. If some dimensions are already fixed at
given nest levels, this is taken into account when fixing the remaining dimensions.
In most cases an optimal ordering is found for this situation as well.
The guiding principles can be used in the early design phases in
order to enable minimization of the memory requirement through in-place mapping.
We use real life examples to
show how they can be applied to reach a cost optimized end product. The results
show orders of magnitude improvement in memory requirement compared to using the
declared array sizes, and similar penalties for choosing the suboptimal
ordering of loops when in-place mapping is exploited.
ISSN: 1939-8018
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
Associated Section of ESAT - INSYS, Integrated Systems
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
VLSISignalProcRev1Subm.pdfMain article Published 189KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science