In computing, external memory algorithms or out-of-core algorithms are algorithms that are designed to process data that are too large to fit into a computer's main memory at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory (auxiliary memory) such as hard drives or tape drives, or when memory is on a computer network. External memory algorithms are analyzed in the external memory model.

Model

thumb|The cache on the left holds <math>\tfrac{M}{B}</math> blocks of size <math>B</math> each, for a total of objects. The external memory on the right is unbounded.

External memory algorithms are analyzed in an idealized model of computation called the external memory model (or I/O model, or disk access model). The external memory model is an abstract machine similar to the RAM machine model, but with a cache in addition to main memory. The model captures the fact that read and write operations are much faster in a cache than in main memory, and that reading long contiguous blocks is faster than reading randomly using a disk read-and-write head. The running time of an algorithm in the external memory model is defined by the number of reads and writes to memory required. The model was introduced by Alok Aggarwal and Jeffrey Vitter in 1988. The external memory model is related to the cache-oblivious model, but algorithms in the external memory model may know both the block size and the cache size. For this reason, the model is sometimes referred to as the cache-aware model.

The model consists of a processor with an internal memory or cache of size , connected to an unbounded external memory. Both the internal and external memory are divided into blocks of size . One input/output or memory transfer operation consists of moving a block of contiguous elements from external to internal memory, and the running time of an algorithm is determined by the number of these input/output operations. An early use of the term "out-of-core" with respect to algorithms appears in 1971.

See also

  • Cache-oblivious algorithm
  • External memory graph traversal
  • Online algorithm
  • Parallel external memory
  • Streaming algorithm

References

  • Out of Core SVD and QR
  • Out of core graphics
  • Scalapack design