On-chip memory, in the form of (hardware-managed) cache, (software-managed) scratchpad memory (SPM) or some combination of both, is widely used in embedded systems. Most high-end embedded systems have both cache and SPM on-chip since each addresses a different need. Caches allow easy integration and are often effective but are unpredictable. SPMs are more energy-efficient than caches since they do not need complex tag-decoding logic. In addition, SPMs provide absolutely predictable performance but the programmer or compiler must schedule explicit data/instruction transfers between the SPM and off-chip main memory in an embedded system. In today’s industry, this task is largely accomplished manually. The programmer often spends a lot of time on partitioning data and/or instructions and inserting explicit data/instruction transfers required between the SPM and main memory. Such a manual approach is time-consuming and error-prone. Obtaining satisfactory solutions for large application programs by hand can be challenging. Furthermore, hand-crafted code is not portable since it is usually customised for one particular architecture.

This talk introduces a compiler approach, called memory coloring, that we have recently developed to automatically allocating the arrays in a program to an SPM. The arrays are frequently used in embedded applications such as image processing and signal processing. The novelty of this approach lies in partitioning an SPM into a pseudo register file, splitting the live ranges of arrays to create potential data transfer statements between the SPM and off-chip main memory, and finally, adapting an existing graph-colouring algorithm for register allocation to assign the arrays in the program into the register file. This compiler-directed approach is efficient due to the practical efficiency of graph-colouring algorithms. We have implemented this work in the SUIF/machSUIF compiler framework. Preliminary results over benchmarks show