Access Restriction

Author Frumkin, Michael A. ♦ Van der Wijngaart, Rob F.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2002
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Cache memory ♦ Cache misses ♦ Fundamental parallelepiped ♦ Lattice ♦ Lower and upper bounds ♦ Reduced basis ♦ Scientific computing ♦ Structured grids
Abstract We derive tight bounds on cache misses for evaluation of explicit stencil operators on rectangular grids. Our lower bound is based on the isoperimetric property of the discrete crosspolytope. Our upper bound is based on a good surface-to-volume ratio of a parallelepiped spanned by a reduced basis of the interference lattice of a grid. Measurements show that our algorithm typically reduces the number of cache misses by a factor of three, relative to a compiler optimized code. We show that stencil calculations on grids whose interference lattices have a short vector feature abnormally high numbers of cache misses. We call such grids unfavorable and suggest to avoid these in computations by appropriate padding. By direct measurements on a MIPS R10000 processor we show a good correlation between abnormally high numbers of cache misses and unfavorable three-dimensional grids.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2002-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 49
Issue Number 3
Page Count 20
Starting Page 434
Ending Page 453

Open content in new tab

   Open content in new tab
Source: ACM Digital Library