𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Combinatorics of Cache Misses during Matrix Multiplication

✍ Scribed by Philip J. Hanlon; Dean Chung; Siddhartha Chatterjee; Daniela Genius; Alvin R. Lebeck; Erin Parker

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
333 KB
Volume
63
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we construct an analytic model of cache misses during matrix multiplication. The analysis in this paper applies to square matrices of size 2 m where the array layout function is given in terms of a function 3 that interleaves the bits in the binary expansions of the row and column indices. We first analyze the number of cache misses for direct-mapped caches and then indicate how to extend this analysis to A-way associative caches. The work in this paper accomplishes two things. First, we construct fast algorithms to estimate the number of cache misses. Second, we develop a theoretical understanding of cache misses that will allow us, in subsequent work, to approach the problem of minimizing cache misses by appropriately choosing the bit interleaving function that goes into the array layout function.

📜 SIMILAR VOLUMES

A Note on the Combinatorics of Multiplic
A Note on the Combinatorics of Multiplication in Groups
✍ A. Juhász; A. Leibman 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 111 KB

Let S be a finite subset of a group G, |S| = n, and let g ∈ S • S. Then g induces a partial function λ g : S → S by λ g (s) = t if and only if st = g and λ g (s) is not defined if g ∈ sS. For every g ∈ S • S, λ g is a one-to-one mapping. In this note we describe the groups which have a finite genera

The mathematical group of scattering mat
The mathematical group of scattering matrices: Introduction of scattering matrix multiplication
✍ Osvaldo Buccafusca 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract This paper provides a new step towards a mathematical foundation for S‐matrices. It introduces a new operation, the S‐matrix multiplication, and defines the mathematical group of S‐matrices, allowing the power of Group Theory to be applied to S‐parameter network analysis. © 2006 Wiley P

A submatrix algorithm for the matrix-vec
A submatrix algorithm for the matrix-vector multiplication of very large matrices
✍ Roland Lindh; Per-Årke Malmquist 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 179 KB

In self-consistent field (SCF) calculations the construction of the Fock matrix is most time-consuming step. The Fock matrix construction may formally be seen as a matrix-vector multiplication, where the matrix is the supermatrix, Tikl, and the vector is the first-order density matrix, yi. This form

Impact of mixed-parallelism on parallel
Impact of mixed-parallelism on parallel implementations of the Strassen and Winograd matrix multiplication algorithms
✍ F. Desprez; F. Suter 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 277 KB

## Abstract In this paper we study the impact of the simultaneous exploitation of data‐ and task‐parallelism, so called mixed‐parallelism, on the Strassen and Winograd matrix multiplication algorithms. This work takes place in the context of Grid computing and, in particular, in the Client–Agent(s)

Sensitivity enhancement and matrix effec
Sensitivity enhancement and matrix effect evaluation during summation of multiple transition pairs—case studies of clopidogrel and ramiprilat
✍ J. Manjunath Swamy; Narendra Kamath; Anil Kumar Radha Shekar; Nuggehally R. Srin 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 359 KB

## Abstract Sensitivity enhancement via summation of multiple MRM transition pairs is gaining popularity in tandem mass spectrometric assays. Numerous validation experiments describing the assays for two model substrates, clopidogrel and ramiprilat, were performed. The quantitation of clopidogrel w