This paper presents asymptotically optimal algorithms for rectangular matrix transpose, FFT,
and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms …

The present book provides an introduction to using space-filling curves (SFC) as tools in
scientific computing. Special focus is laid on the representation of SFC and on resulting …

Compiler transformations can significantly improve data locality for many scientific programs.
In this paper, we show iterative solvers for partial differential equations (PDEs) in three …

This article presents asymptotically optimal algorithms for rectangular matrix transpose, fast
Fourier transform (FFT), and sorting on computers with multiple levels of caching. Unlike …

Matrix multiplication is an important kernel in linear algebra algorithms, and the performance
of both serial and parallel implementations is highly dependent on the memory system …

We develop algorithmic optimizations to improve the cache performance of four fundamental
graph algorithms. We present a cache-oblivious implementation of the Floyd-Warshall …

We develop from first principles an exact model of the behavior of loop nests executing in a
memory hicrarchy, by using a nontraditional classification of misses that has the key property …

We propose a version of cache oblivious search trees which is simpler than the previous
proposal of Bender, Demaine and Farach-Colton and has the same complexity bounds. In …

Caches have become increasingly important with the widening gap between main memory
and processor speeds. However, they are a source of unpredictability due to their …

Scratchpad memory (SPM), a fast software-managed on-chip SRAM, is now widely used in
modern embedded processors. Compared to hardware-managed cache, it is more efficient …