DSP architectures typically provide dedicated memory address generation units and indirect addressing modes with auto-increment and auto-decrement that subsume address arithmetic calculation. The heavy use of auto-increment and auto-decrement indirect addressing require DSP compilers to perform a careful placement of variables in storage to minimize address arithmetic instructions to generate compact and efficient DSP code. Liao et al. [11] formulated the problem of storage assignment as the simple o set assignment problem (SOA) and the general offset assignment problem (GOA), and proposed heuristic solutions. The storage allocation of variables critically depends on the sequence of variable accesses. In this paper we present techniques to optimize the access sequence of variables by applying algebraic transformations (such as commutativity and associativity) on expression trees to obtain the least cost offset assignment. We develop a new formulation of this problem as the least cost acces...

This work addresses the issue of exploiting intra-tile parallelism by overlapping communication with computation removing the restriction of atomicity of tiles. The effectiveness of tiling is then critically dependent on the execution order of tasks within a tile. We present a theoretical framework based on equivalence classes that provides an optimal task ordering under assumptions of constant and different permutations of tasks in individual tiles. Our framework is able to handle constant but compile-time unknown dependences by generating optimal task permutations at run-time and results in significantly lower loop completion times. Our solution is an improvement over previous approaches (Chou and Kung, 1993) (Dion et al., 1995) and is optimal for all problem instances. We also propose efficient algorithms that provide the optimal solution. The framework has been implemented as an optimization pass in the SUIF compiler and has been tested on a distributed memory system using a message passing model. We show that the performance improvement over previous results is substantial.