Journal of Signal Processing Systems vol:53 issue:3 pages:301-321
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.