Optimizing Memory Cost with Loop Transformations

Embedded systems are usually constrained in terms of timing, power, and memory. Many embedded applications, especially in the multi-media and telecom domains, are inherently data dominant. These embedded DSP applications usually exhibit intensive computations in the form of multi-level loops. The performance of these embedded DSP applications mainly depends on the code quality of the loops and the memory hierarchy design. During the design phase of the embedded system, it is important to estimate the overall storage requirement to guide the memory system design and take advantage of the memory system by program transformations and loop transformations. Loop transformations including loop permutation, loop fusion and loop tiling are important program transformation techniques utilized to improve the data reuse, thus reduce the life time of data elements and memory cost. In this thesis, we propose a technique to estimate the memory cost of a nested loop. We then propose loop optimization strategies to combine various loop transformation techniques to reduce the overall memory cost. In addition to significantly reduce the running time from original loops to fused loops, the results of our experiment presented that our proposed loop optimization schemes can also reduce memory cost and cache misses