Simultaneous Minimization of Capacity and Conflict Misses

Loop tiling (or loop blocking) is a well-known loop transformationto improve temporal locality in nested loops which perform matrixcomputations. When targeting caches that have low associativities, oneof the key challenges for loop tiling is to simultaneously minimizecapacity misses and conflict misses. This paper analyzes the effect ofthe tile size and the array-dimension size on capacity misses andconflict misses. The analysis supports the approach of combiningtile-size selection (to minimize capacity misses) with array padding (tominimize conflict misses).