Uniform memory hierarchies

Abstract

The authors introduce a model, called the uniform memory hierarchy (UMH) model, which reflects the hierarchical nature of computer memory more accurately than the RAM (random-access-machine) model, which assumes that any item in memory can be accessed with unit cost. In the new model memory occurs as a sequence of increasingly large levels. Data are transferred between levels in fixed-size blocks (the size is level dependent). Within a level blocks are random access. The model is easily extended to handle parallelism. The UMH model is really a family of models parameterized by the rate at which the bandwidth decays as one travels up the hierarchy. The model is sufficiently accurate for it to make sense to be concerned about constant factors. A program is parsimonious on a UMH if the leading terms of the program's (time) complexity on the UMH and on a RAM are identical. If these terms differ by more than a constant factor, then the program is inefficient. It is shown that matrix transpose is inherently unparsimonious, even with constant bandwidth assumed throughout the hierarchy, and that (standard) matrix multiplication can be programmed parsimoniously, even on a hierarchy with a quickly decaying bandwidth. The authors analyze two standard FFT programs with the same RAM complexity. One is efficient; the other is not.