Solving Graph Partitioning Problems Arising in Tagless Cache Management Combinatorial Optimization

The instruction cache is a critical component in any microprocessor. It must have high performance to enable fetching of instructions on every cycle. In this paper, we consider an optimization problem arising in the management of a new hybrid hardware and linker-assisted approach for cache memory management. A graph partitioning formulation is presented and different ILP formulations are proposed, obtained by strengthening and/or relaxing constraints and by reducing the number of integer variables. The formulations are tested on large benchmarks (with thousands of nodes and edges) arising from real applications.