Comparative Study of Cache Utilization for Matrix Multiplication Algorithms

Abstract-- In this work, the performance of basic and strassen’s matrix multiplication algorithms are compared in terms of memory hierarchy utilization. The problem taken here is MATRIX MULTIPLICATION (Basic and Strassen’s). Strassen’s Matrix Multiplication Algorithm has time complexity of O(n2.807) with respect to the Basic multiplication algorithm with time complexity of O(n3). This slight reduction in time makes Strassen’s Algorithm seems to be faster but introduction of additional temporary storage makes Strassen’s Algorithm less efficient in space point of view. Access patterns of the two multiplication algorithms are generated and then cache replacement algorithms (namely LRU and FIFO) are applied to find the misses in cache. With the number of misses in hand and time taken to process 1 miss taken from Hou Fang’s research, we calculate the overall time consumed to process misses in case of both the matrix multiplication algorithms. It is found that the basic matrix multiplication is far better than the Strassen’s matrix multiplication algorithm beacause of higher memory usage. This analysis is important because memory plays more vital role in deciding the efficiency of an algorithm. Additional temporary storage causes increase in number of memory locations and number of memory accesses too in case of strassen’s algorithm