Алгоритмы внешней памяти: обработка больших данных, не помещающихся в оперативную память. Оптимизация доступа к медленным носителям (HDD, сети). I/O модель.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В вычислительной технике алгоритмы внешней памяти, или алгоритмы работы с выносом за пределы основной памяти, – это алгоритмы, предназначенные для обработки данных, которые не помещаются в оперативную память компьютера целиком. Такие алгоритмы должны быть оптимизированы для эффективного получения и доступа к данным, хранящимся в медленной внешней памяти (вспомогательной памяти), такой как жесткие диски или магнитные ленты, или при использовании памяти в компьютерной сети. Анализ алгоритмов внешней памяти проводится в модели внешней памяти.
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.
Модель
Алгоритмы внешней памяти анализируются в идеализированной модели вычислений, называемой моделью внешней памяти (или моделью ввода-вывода, или моделью доступа к диску). Модель внешней памяти – это абстрактная машина, подобная модели оперативной памяти, но дополненная кэшем. Модель отражает тот факт, что операции чтения и записи значительно быстрее выполняются в кэше, чем в основной памяти, и что чтение длинных непрерывных блоков происходит быстрее, чем случайное чтение с использованием головки чтения и записи диска. Время работы алгоритма в модели внешней памяти определяется количеством операций чтения и записи в память. Модель была предложена Алоком Аггарвалом и Джеффри Виттером в 1988 году. Модель внешней памяти связана с моделью, не учитывающей кэш, однако алгоритмы в модели внешней памяти могут учитывать как размер блока, так и размер кэша. По этой причине модель иногда называют моделью, учитывающей кэш. Модель состоит из процессора с внутренней памятью или кэшем размером M, подключенного к неограниченной внешней памяти. Как внутренняя, так и внешняя память разделены на блоки размером B. Одна операция ввода-вывода или передачи данных состоит в перемещении блока из B смежных элементов из внешней во внутреннюю память, а время работы алгоритма определяется количеством таких операций ввода-вывода. Первое использование термина "out-of-core" (вне оперативной памяти) по отношению к алгоритмам зафиксировано в 1971 году.
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 M, connected to an unbounded external memory. Both the internal and external memory are divided into blocks of size B. One input/output or memory transfer operation consists of moving a block of B 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.