Optimal DSP memory layout generation as a quadratic assignment problem

Modern digital signal processors (DSPs) provide dedicated memory address generation units (AGUs) which can operate in parallel to other functional units. This allows address computation concurrently with other machine operations. However, maximum parallelism can only be achieved by taking advantage of indirect addressing modes with auto-modify and module operations. This requires optimized placement of program variables in the memory. In this paper, we present a novel procedure for generating optimized DSP memory layouts. Previously proposed algorithms are optimized only with respect to the specific case of auto-increment and decrement by 1 and do not support module addressing. We use a more general AGU model which is consistent with contemporary DSPs. For this model, optimal memory layout generation can be formulated as a quadratic assignment problem (QAP). The QAP is NP-hard but there are efficient heuristics leading to near-optimal solutions within short time. It is verified by experimental results that our approach achieves significant improvements over existing techniques.