文章基本信息

标题：Comparative Study of Cache Utilization for Matrix Multiplication Algorithms
本地全文：下载
作者：Vikash Kumar Singh ; Hemant Makwana ; Richa Gupta 等
期刊名称：International Journal of Computer Technology and Applications
电子版ISSN：2229-6093
出版年度：2011
卷号：2
期号：4
页码：1078-1081
出版社：Technopark Publications
摘要：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
关键词：Matrix Multiplication; Strassen’s Multiplication; LRU; FIFO; Access pattern