Алгоритм внешней памяти

редактировать

В вычислениях, алгоритмах внешней памяти или Внешние алгоритмы - это алгоритмы, которые предназначены для обработки данных, размер которых слишком велик, чтобы сразу поместиться в основную память компьютера. Такие алгоритмы должны быть оптимизированы для эффективного извлечения и доступа к данным, хранящимся в медленной основной памяти (вспомогательная память ), например, жестких дисках или ленточных накопителях, или когда память в компьютерной сети . Алгоритмы внешней памяти анализируются в модели внешней памяти .

Содержание

1 Модель
2 Алгоритмы
3 Приложения
4 История
5 См. Также
6 Ссылки
7 Внешние ссылки

Модель

Кэш слева содержит блоки размером

МБ {\ displaystyle {\ tfrac {M} {B}}}

{\ displaystyle {\ tfrac {M} {B}}}

размером

B {\ displaystyle B}

B

каждый, всего M объектов. Внешняя память справа не ограничена.

Алгоритмы внешней памяти анализируются в идеализированной модели вычислений, называемой моделью внешней памяти (или моделью ввода-вывода, или модель доступа к диску ). Модель внешней памяти - это абстрактная машина, аналогичная модели RAM машины, но с кэш-памятью в дополнение к основной памяти. Модель учитывает тот факт, что операции чтения и записи в кэше выполняются намного быстрее, чем в основной памяти, и что чтение длинных непрерывных блоков происходит быстрее, чем чтение случайным образом. с использованием дисковой головки чтения и записи . время выполнения алгоритма в модели внешней памяти определяется количеством требуемых операций чтения и записи в память. Модель была представлена Алоком Аггарвалом и Джеффри Виттером в 1988 году. Модель внешней памяти связана с моделью без учета кеша, но алгоритмы в модели внешней памяти могут знать как размер блока и размер кэша. По этой причине модель иногда называют моделью с учетом кеширования .

. Модель состоит из процессора с внутренней памятью или кеш-памяти размером M, подключен к неограниченной внешней памяти. Как внутренняя, так и внешняя память разделены на блоки размера B. Одна операция ввода / вывода или передачи памяти состоит из перемещения блока из B смежных элементов из внешней во внутреннюю память и времени выполнения алгоритма определяется количеством этих операций ввода / вывода.

Алгоритмы

Алгоритмы в модели внешней памяти используют тот факт, что получение одного объекта из внешней памяти извлекает весь блок размером $B {\ displaystyle B}$ $B$ . Это свойство иногда называют местностью.

Поиск элемента среди $N {\ displaystyle N}$ $N$ объектов возможен в модели внешней памяти с использованием B-дерева с коэффициентом ветвления $В {\ Displaystyle B}$ $B$ . С помощью B-дерева поиск, вставка и удаление могут быть выполнены за $O (log B ⁡ N) {\ displaystyle O (\ log _ {B} N)}$ ${\ displaystyle O (\ log _ {B} N)}$ времени (in Обозначение Big O ). Информация теоретически, это минимальное время выполнения, возможное для этих операций, поэтому использование B-дерева является асимптотически оптимальным.

Внешняя сортировка сортирует в настройка внешней памяти. Внешняя сортировка может выполняться с помощью сортировки по распределению, которая аналогична quicksort, или с помощью $MB {\ displaystyle {\ tfrac {M} {B}}}$ ${\ displaystyle {\ tfrac {M} {B}}}$ сортировки слиянием. Оба варианта достигают асимптотически оптимального времени выполнения $O (NB log MB ⁡ NB) {\ displaystyle O ({\ tfrac {N} {B}} \ log _ {\ tfrac {M} { B}} {\ tfrac {N} {B}})}$ ${\ displaystyle O ({\ tfrac {N} {B}} \ log _ {\ tfrac {M} {B}} {\ tfrac {N} {B}})}$ для сортировки N объектов. Эта граница также применяется к быстрому преобразованию Фурье в модели внешней памяти.

Проблема перестановки состоит в том, чтобы переставить элементы $N {\ displaystyle N}$ $N$ в конкретная перестановка. Это можно сделать либо путем сортировки, для чего требуется указанная выше среда выполнения сортировки, либо путем вставки каждого элемента по порядку и игнорирования преимущества локальности. Таким образом, перестановка может быть выполнена за $O (min (N, NB log MB ⁡ NB)) {\ displaystyle O (\ min (N, {\ tfrac {N} {B}} \ log _ {\ tfrac { M} {B}} {\ tfrac {N} {B}}))}$ ${\ displaystyle O (\ min (N, {\ tfrac {N} {B}} \ log _ {\ tfrac {M} {B}} {\ tfrac {N} { B}}))}$ время.

Приложения

Модель внешней памяти захватывает иерархию памяти, которая не моделируется в других распространенных моделях, используемых при анализе структур данных, таких как машина с произвольным доступом, и полезна для доказательства нижних границ для структур данных. Модель также полезна для анализа алгоритмов, которые работают с наборами данных, слишком большими для размещения во внутренней памяти.

Типичным примером является географические информационные системы, особенно цифровые модели рельефа, где полный набор данных легко превышает несколько гигабайт или даже терабайт данных.

Эта методология выходит за рамки ЦП общего назначения и также включает вычисления на GPU, а также классическую обработку цифровых сигналов. В вычислениях общего назначения на графических процессорах (GPGPU) мощные графические карты (GPU) с небольшим объемом памяти (по сравнению с более привычной системной памятью, которую чаще всего называют просто RAM ) используются при относительно медленной передаче памяти от CPU к GPU (по сравнению с пропускной способностью вычислений).

История

Термин «вне ядра» впервые использовался в качестве прилагательного в 1962 году в отношении устройств, отличных от основной памяти и IBM 360. Термин «вне ядра» впервые использовался в отношении алгоритмов в 1971 году.

См. Также

Ссылки

Внешние ссылки