The key idea behind the technique is to logically divide the cache into a number of partitions and adjust the array layout in memory such that data from different arrays is mapped into different partitions of the cache throughout the execution of the loop nest. Hence, there is no additional hardware complexity which may affect performance. The aim of cache partitioning is to eliminate conflicts between reused portions of different arrays. Reuse which extends across many loop iterations requires large portions of data to be retained in the cache. Conflicts among these reusable portions of data lead to unnecessary cache misses.
Conflicts occur data from different arrays map into overlapping regions of the cache.
Cache partitioning derives a data layout which ensures a conflict-free mapping of data from different arrays into the cache. Cache partitioning is most effective when data access patterns are compatible, which means data is accessed from different arrays with the same stride and direction. Compatible data access patterns are common in loop nests in which there is data reuse. The regularity in such data access patterns implies that once conflicts begin to occur, they continue to occur in frequent, regular patterns. Hence, it is important to address the case of compatible data accesses.