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

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

Кэш слева содержит M B блоки размером B Бкаждый, в общей сложности M объектов. Внешняя память справа не ограничена.

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

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

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

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

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

Поиск элемента среди N Нобъектов возможен в модели внешней памяти с использованием B-дерева с коэффициентом ветвления B . Используя B-дерево, поиск, вставка и удаление могут быть достигнуты во O ( log B ⁡ N ) времени (в большой o нотации ). Информация теоретически, это минимальное время выполнения, возможное для этих операций, поэтому использование B-дерева асимптотически оптимально .

Внешняя сортировка-это сортировка в настройках внешней памяти. Внешняя сортировка может быть выполнена через сортировку распределения, которая похожа на quicksort , или через M B }сортировку слияния A-way . Оба варианта достигают асимптотически оптимального времени выполнения O ( N B log M B ⁡ N B ) }для сортировки N объектов. Эта граница также применяется к быстрому преобразованию Фурье в модели внешней памяти.

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

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

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

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

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

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

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

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

Пруф[править]

.tau.ac.il/~stoledo/Bib/Pubs/pp01-qr.pdf