Incomputing,external memory algorithms orout-of-core algorithms arealgorithms that are designed to process data that are too large to fit into a computer'smain memory at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory (auxiliary memory) such ashard drives ortape drives, or when memory is on acomputer network.^[1][2] External memory algorithms are analyzed in theexternal memory model.

External memory algorithms are analyzed in an idealizedmodel of computation called the external memory model (orI/O model, ordisk access model). The external memory model is anabstract machine similar to theRAM machine model, but with acache in addition tomain memory. The model captures the fact that read and write operations are much faster in acache than inmain memory, and thatreading long contiguous blocks is faster than reading randomly using adisk read-and-write head. Therunning time of analgorithm in the external memory model is defined by the number of reads and writes to memory required.^[3] The model was introduced by Alok Aggarwal andJeffrey Vitter in 1988.^[4] The external memory model is related to thecache-oblivious model, but algorithms in the external memory model may know both theblock size and thecache size. For this reason, the model is sometimes referred to as thecache-aware model.^[5]

The model consists of aprocessor with an internal memory orcache of sizeM, connected to anunbounded external memory. Both the internal and external memory are divided intoblocks of sizeB. One input/output or memory transfer operation consists of moving a block ofB contiguous elements from external to internal memory, and therunning time of an algorithm is determined by the number of these input/output operations.^[4]

Algorithms in the external memory model take advantage of the fact that retrieving one object from external memory retrieves an entire block of sizeB. This property is sometimes referred to as locality.

Searching for an element amongN objects is possible in the external memory model using aB-tree with branching factorB. Using a B-tree, searching, insertion, and deletion can be achieved in${\displaystyle O({\log }_{B}N)}$ time (inBig O notation).Information theoretically, this is the minimumrunning time possible for these operations, so using a B-tree isasymptotically optimal.^[4]

External sorting is sorting in an external memory setting. External sorting can be done via distribution sort, which is similar toquicksort, or via a${\displaystyle \frac{M}{B}}$-way merge sort. Both variants achieve theasymptotically optimal runtime of${\displaystyle O\left(\frac{N}{B}{\log }_{\frac{M}{B}}\frac{N}{B}\right)}$ to sortN objects. This bound also applies to thefast Fourier transform in the external memory model.^[2]

The permutation problem is to rearrangeN elements into a specificpermutation. 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${\displaystyle O\left(min\left(N,\frac{N}{B}{\log }_{\frac{M}{B}}\frac{N}{B}\right)\right)}$ time.

The external memory model captures thememory hierarchy, which is not modeled in other common models used in analyzingdata structures, such as therandom-access machine, and is useful for provinglower bounds for data structures. The model is also useful for analyzing algorithms that work on datasets too big to fit in internal memory.^[4]

A typical example isgeographic information systems, especiallydigital elevation models, where the full data set easily exceeds severalgigabytes or eventerabytes of data.

This methodology extends beyondgeneral purpose CPUs and also includesGPU computing as well as classicaldigital signal processing. Ingeneral-purpose computing on graphics processing units (GPGPU), powerful graphics cards (GPUs) with little memory (compared with the more familiar system memory, which is most often referred to simply asRAM) are utilized with relatively slow CPU-to-GPU memory transfer (when compared with computation bandwidth).

An early use of the term "out-of-core" as an adjective is in 1962 in reference todevices that are other than thecore memory of anIBM 360.^[6] An early use of the term "out-of-core" with respect toalgorithms appears in 1971.^[7]

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

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

• Algorithms
• Models of computation
• Cache (computing)
• Analysis of algorithms
• External memory algorithms

• CS1 errors: periodical ignored
• Articles with short description
• Short description is different from Wikidata