Out-of-core algorithm

TheInfoList

In
computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and software. It has sci ...

, external memory algorithms or out-of-core algorithms are
algorithms In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ...
that are designed to process data that are too large to fit into a computer's
main memory Computer data storage is a technology consisting of computer A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations automatically. Modern computers can perform ...
at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory (
auxiliary memory Computer data storage is a technology consisting of computer components and Data storage device, recording media that are used to retain digital data (computing), data. It is a core function and fundamental component of computers. The cent ...
) such as
hard drives A hard disk drive (HDD), hard disk, hard drive, or fixed disk is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage and one or more rigid rapidly rotating hard disk platter, platters c ...
or
tape drives A tape drive is a Computer data storage, data storage device that digital recording, reads and writes data on a magnetic tape. Magnetic tape data storage is typically used for offline, archival data storage. Tape media generally has a favorable un ...
, or when memory is on a
computer network A computer network is a set of computer A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations automatically. Modern computers can perform generic sets of operati ...
. 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 (or I/O model, or disk access model). The external memory model is an abstract machine similar to the RAM model, RAM machine model, but with a Cache (computing), cache in addition to
main memory Computer data storage is a technology consisting of computer A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations automatically. Modern computers can perform ...
. The model captures the fact that read and write operations are much faster in a cache (computing), cache than in
main memory Computer data storage is a technology consisting of computer A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations automatically. Modern computers can perform ...
, and that Reading (computer), 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 algorithm#Idealized cache model, cache-oblivious model, but algorithms in the external memory model may know both the Block (data storage), block size and the Cache (computing), cache size. For this reason, the model is sometimes referred to as the cache-aware model. The model consists of a processor (computing), processor with an internal memory or cache (computing), cache of size , connected to an infinity, unbounded external memory. Both the internal and external memory are divided into Block (data storage), 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 $B$. This property is sometimes referred to as locality. Searching for an element among $N$ objects is possible in the external memory model using a B-tree with branching factor $B$. Using a B-tree, searching, insertion, and deletion can be achieved in $O\left(\log _B N\right)$ time (in Big O notation). Information theory, 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 $\tfrac$K-way merge algorithm, -way merge sort. Both variants achieve the asymptotically optimal runtime of $O\left(\tfrac \log _ \tfrac\right)$ to sort objects. This bound also applies to the fast Fourier transform in the external memory model. The permutation problem is to rearrange $N$ 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 $O\left(\min \left(N, \tfrac \log _ \tfrac\right)\right)$ time.

# Applications

The external memory model captures the memory hierarchy, which is not modeled in other common models used in analyzing data structures, such as the random-access machine, and is useful for proving lower bounds for data structures. The model is also useful for analyzing algorithms that work on datasets too big to fit in internal memory. A typical example is geographic information systems, especially digital elevation models, where the full data set easily exceeds several gigabytes or even terabytes of data. This methodology extends beyond Central processing unit, general purpose CPUs and also includes Graphics processing unit, GPU computing as well as classical digital signal processing. In general-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 as random-access memory, RAM) are utilized with relatively slow CPU-to-GPU memory transfer (when compared with computation bandwidth).

# History

An early use of the term "out-of-core" as an adjective is in 1962 in reference to ''devices'' that are other than the Magnetic-core memory, core memory of an IBM 360. An early use of the term "out-of-core" with respect to ''algorithms'' appears in 1971.