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

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

Модель [ править ]

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

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

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

Алгоритмы [ править ]

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

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

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

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

Приложения [ править ]

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

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

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

История [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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