Reducing cache conflicts by multi-level cache partitioning and array elements mapping

The paper presents an algorithm to reduce cache conflicts and improve cache localities. The proposed algorithm analyzes unique locality reference space for each reference pattern, partitions the multi-level cache into several parts with different size, and then maps array data onto the scheduled cache positions such that cache conflicts can be eliminated. To reduce the memory overhead for mapping array variables onto partitioned cache, a greedy method for rearranging array variables in declared statement is also developed. In addition, we combine loop tiling and the proposed schemes for exploiting both temporal and spatial reuse opportunities. To demonstrate that our approach is effective at reducing the number of cache conflicts and exploiting cache localities, we use Atom as a tool to develop a simulator for simulation of the behavior of direct-mapping cache. Experimental results show that applying our cache partitioning scheme can largely reduce the cache conflicts and thus save program execution time in both one-level cache and multi-level cache hierarchies.