Uniform memory hierarchies
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 600-608vol.2
- https://doi.org/10.1109/fscs.1990.89581
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 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. 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. The authors analyze two standard FFT programs with the same RAM complexity. One is efficient; the other is not.Keywords
This publication has 9 references indexed in Scilit:
- Visualizing computer memory architecturesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Optimal disk I/O with parallel block transferPublished by Association for Computing Machinery (ACM) ,1990
- Tradeoffs between communication and spacePublished by Association for Computing Machinery (ACM) ,1989
- Impact of Hierarchical Memory Systems On Linear Algebra Algorithm DesignThe International Journal of Supercomputing Applications, 1988
- Virtual memory algorithmsPublished by Association for Computing Machinery (ACM) ,1988
- Supernode partitioningPublished by Association for Computing Machinery (ACM) ,1988
- Hierarchical memory with block transferPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- A model for hierarchical memoryPublished by Association for Computing Machinery (ACM) ,1987
- Permuting Information in Idealized Two-Level StoragePublished by Springer Nature ,1972