Compile time data cache management algorithm

The design and control of memory hierarchies greatly affect the performance of microprocessors. Hardware schemes have been proposed to enhance successfully the hit rate of instruction and data caches in various architectures. However, the increasing frequency of microprocessors make hardware schemes insufficient due to their poor look ahead capability. Compile time schemes make use of the compile time information and of the flow analysis of the program to manage data caches with special hardware support. In this paper, we propose a compile time data cache management algorithm for uniprocessors and proves its optimality. This algorithm is a branch and bound like algorithm making use of heuristics.