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

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

Модель

Кэш слева содержит ${ displaystyle { tfrac {M} {B}}}$ блоки размера ${ displaystyle B}$ каждый, в общей сложности M объекты. Объем внешней памяти справа неограничен.

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

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

Алгоритмы

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

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

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

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

Приложения

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

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

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

История

Термин «вне ядра» в качестве прилагательного был впервые использован в 1962 году в связи с устройства что кроме основная память из IBM 360.^[6] Раннее использование термина «вне ядра» в отношении алгоритмы появляется в 1971 году.^[7]

Смотрите также

• Внешняя сортировка
• Онлайн алгоритм
• Алгоритм потоковой передачи
• Алгоритм без кеширования
• Параллельная внешняя память
• Обход графа внешней памяти

Рекомендации

внешняя ссылка

• Out of Core SVD и QR
• Вне основной графики
• Дизайн скалапака