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 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
External memory algorithms are analyzed in an idealized model of computation called the external memory 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.
Algorithms
Algorithms in the external memory model take advantage of the fact that retrieving one object from external memory retrieves an entire block of size. This property is sometimes referred to as locality. Searching for an element among objects is possible in the external memory model using a B-tree with branching factor. Using a B-tree, searching, insertion, and deletion can be achieved in time. Information theoretically, this is the minimum running time possible for these operations, so using a B-tree is asymptotically optimal. External sorting is sorting in an external memory setting. External sorting can be done via distribution sort, which is similar to quicksort, or via a -way merge sort. Both variants achieve the asymptotically optimal runtime of to sort objects. This bound also applies to the Fast Fourier Transform in the external memory model. The permutation problem is to rearrange elements into a specific permutation. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in time.
An early use of the term "out-of-core" as an adjective is in 1962 in reference to devices that are other than the core memory of an IBM 360. An early use of the term "out-of-core" with respect toalgorithms appears in 1971.