Memory Access Analysis for Embedded Systems

The memory subsystem has traditionally been a major bottleneck in the design of high performance processor based systems. As the disparity in speed between a processor and its main memory continues to widen, the need for an ecient exploitation of the memory hierarchy plays an increasingly important role in achieving good overall performance. When dealing with the design of embedded systems this is particularly important. As an embedded systems application is likely to run on the same system throughout its entire lifetime, a tailoring of the systems memory conguration to t certain application specic requirements, can be extremely benecial. Likewise a tailoring of a particular application to t the parameters of the memory hierarchy, can result in a better exploitation of data locality. As the latencies in memories are orders of magnitude larger than that of modern day processors, merely small changes in an applications memory access behaviour can yield considerate performance gains. Especially in data intensive applications where large amounts of data is accessed in multi level nested loops, signicant improvements can be obtained. In this thesis a wide range of techniques for improving memory access behaviour has been covered. The primary focus has however been put on the topics of carrying out memory layout- and control- transformations on application codes. The use of the former of these is to perform a specic layout of data in main memory, thereby improving data locality. The use of control transformations can in a similar way improve data locality, by rearranging memory references in an application. Based on the presented topics a high level compiler tool for optimizing memory access behaviour has been developed. This tool has been constructed by the aid of the SUIF compiler set, and is capable of carrying out the well known tiling transformation. The developed tool is able to perform an analysis of a given application, and to carry out the best suited tiling transformation based on this analysis. For some real-world benchmarks a 56 % reduction in the number of main memory accesses has been obtained