| タイトル | Minimizing Cache Misses Using Minimum-Surface Bodies |
| 本文（外部サイト） | http://hdl.handle.net/2060/20020053647 |
| 著者（英） | Biegel, Bryan; Frumkin, Michael; VanderWijngaart, Rob |
| 著者所属（英） | NASA Ames Research Center|Computer Sciences Corp. |
| 発行日 | 2002-01-01 |
| 言語 | eng |
| 内容記述 | A number of known techniques for improving cache performance in scientific computations involve the reordering of the iteration space. Some of these reorderings can be considered as coverings of the iteration space with the sets having good surface-to-volume ratio. Use of such sets reduces the number of cache misses in computations of local operators having the iteration space as a domain. First, we derive lower bounds which any algorithm must suffer while computing a local operator on a grid. Then we explore coverings of iteration spaces represented by structured and unstructured grids which allow us to approach these lower bounds. For structured grids we introduce a covering by successive minima tiles of the interference lattice of the grid. We show that the covering has low surface-to-volume ratio and present a computer experiment showing actual reduction of the cache misses achieved by using these tiles. For planar unstructured grids we show existence of a covering which reduces the number of cache misses to the level of structured grids. On the other hand, we present a triangulation of a 3-dimensional cube such that any local operator on the corresponding grid has significantly larger number of cache misses than a similar operator on a structured grid. |
| NASA分類 | Computer Programming and Software |
| 権利 | No Copyright |
| URI | https://repository.exst.jaxa.jp/dspace/handle/a-is/225020 |
