A new approach to optimal cache scheduling (Q1122358)

An algorithm is presented to optimal cache scheduling in the field of register management for RISC machines or in the development of globally optimal strategies for multiple-stage storage hierarchies. This algorithm answers the following question: is there a sequence of loads and stores such that all blocks lie in the cache at their reference times? Although presented algorithm does not guarantee to yield a solution in all cases, experiments showed that it is powerful to solve problems occurring in practice.