EFFICIENT PROCEDURE MAPPING USING CACHE LINE COLORING

As the gap between memory and processor performance continues to widen , it becomes increasingly important to exploit cache memory effectivel y. Both hardware and software approaches can be explored to optimize c ache performance. Hardware designers focus on cache organization issue s, including replacement policy, associativity, line size and the resu lting cache access time. Software writers use various optimization tec hniques, including software prefetching, data scheduling and code reor dering. Our focus is on improving memory usage through code reordering compiler techniques. In this paper we present a link-time procedure m apping algorithm which can significantly improve the effectiveness of the instruction cache. Our algorithm produces an improved program layo ut by performing a color mapping of procedures to cache lines, taking into consideration the procedure size, cache size, cache line size, an d call graph. We use cache line coloring to guide the procedure mappin g, indicating which cache lines to avoid when placing a procedure in t he program layout. Our algorithm reduces on average the instruction ca che miss Fate by 40% over the original mapping and by 17% over the map ping algorithm of Pettis and Hansen [12].