Proceedings of the ITI 2013 35th international conference on information technology interfaces
Date Issued
2012-09-12
Author(s)
Anchev, Nenad
Atanasovski, Blagoj
Abstract
Matrix multiplication is compute intensive, memory demand
and cache intensive algorithm. It performs O(N3) operations, demands
storing O(N2) 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 replace policies are proposed to speedup different
program executions.
In this paper we analyze and compare two most implemented cache replacement policies First-In-First-Out (FIFO) and Least-Recently-Used
(LRU). The results of the experiments show the optimal solutions for
sequential and parallel dense matrix multiplication algorithm. As the
number of operations does not depend on cache replacement policy, we
define and determine the average memory cycles per instruction that the
algorithm performs, since it mostly affects the performance.
and cache intensive algorithm. It performs O(N3) operations, demands
storing O(N2) 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 replace policies are proposed to speedup different
program executions.
In this paper we analyze and compare two most implemented cache replacement policies First-In-First-Out (FIFO) and Least-Recently-Used
(LRU). The results of the experiments show the optimal solutions for
sequential and parallel dense matrix multiplication algorithm. As the
number of operations does not depend on cache replacement policy, we
define and determine the average memory cycles per instruction that the
algorithm performs, since it mostly affects the performance.
Subjects
File(s)![Thumbnail Image]()
Loading...
Name
ICEST Dataflow V1.1.pdf
Size
369.95 KB
Format
Adobe PDF
Checksum
(MD5):2bb3eb07e93518c6e75552b38f8c9174