Temporal-based procedure reordering for improved instruction cache performance

As the gap between memory and processor performance continues to grow, it becomes increasingly important to exploit cache memory effectively. Both hardware and software techniques can be used to better utilize the cache. Hardware solutions focus on organization, while most software solutions investigate how to best layout a program on the available memory space. In this paper we present a new link-time code reordering algorithm targeted at reducing the frequency of misses in the cache. In past work we focused on eliminating first generation cache conflicts (i.e., conflicts between a procedure, and any of its immediate callers or callees) based on calling frequencies. In this work we exploit procedure-level temporal interaction, using a structure called a Conflict Miss Graph (CMG). In the CMG every edge weight is an approximation of the worst-case umber of misses two competing procedures can inflict upon one another. We use the ordering implied by the edge weights to apply color-based mapping and eliminate conflict misses between procedures lying either in the same or in different call chains. Using programs taken from SPEC 95, Gnu applications, and C++ applications, we have been able to improve upon previous algorithms, reducing the number of instruction cache conflicts by 20% on average compared to the best procedure reordering algorithm.