Optimal Cache Replacement Policy for Matrix Multiplication

Matrix multiplication is compute intensive, memory demand and cache intensive algorithm. It performs O(N 3) operations, demands storing O(N 2) elements and accesses O(N) times each element, where N is the matrix size. Implementation of cache intensive algorithms can achieve speedups due to cache memory behavior if the algorithms frequently reuse the data. A block replacement of already stored elements is initiated when the requirements exceed the limitations of cache size. Cache misses are produced when data of replaced block is to be used again. Several cache replacement policies are proposed to speedup different program executions.