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

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

Модель

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

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

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

Алгоритмы

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

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

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

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

Приложения

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

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

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

История

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

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

• Алгоритм, игнорирующий кэш
• Обход графа внешней памяти
• Онлайн алгоритм
• Параллельная внешняя память
• Алгоритм потоковой передачи

Ссылки

1. Vitter, JS (2001). «Алгоритмы внешней памяти и структуры данных: работа с МАССИВНЫМИ ДАННЫМИ». ACM Computing Surveys . 33 (2): 209–271. CiteSeerX  10.1.1.42.7064 . doi :10.1145/384192.384193. S2CID  2155038.
2. Vitter, JS (2008). Алгоритмы и структуры данных для внешней памяти (PDF) . Серия по основам и тенденциям в теоретической информатике. Том 2. Ганновер, Массачусетс: Now Publishers. С. 305–474. CiteSeerX 10.1.1.140.3731 . doi :10.1561/0400000014. ISBN  978-1-60198-106-6. {{cite book}}: |journal=проигнорировано ( помощь )
3. Чжан, Дунхуэй; Цотрас, Василис Дж.; Левиальди, Стефано; Гринштейн, Жорж; Берри, Дэймон Эндрю; Гуэ-Брюне, Валери; Кош, Харальд; Дёллер, Марио; Дёллер, Марио; Кош, Харальд; Майер, Пол; Бхаттачарья, Арнаб; Льоса, Вебьёрн; Нак, Фрэнк; Бартолини, Илария; Гуэ-Брюне, Валери; Мэй, Тао; Руи, Ён; Круциану, Мишель; Ши, Фрэнк Ю.; Фан, Вэньфэй; Ульман-Кульере, Молли; Кларк, Юджин; Аронсон, Сэмюэл; Меллин, Джонас; Берндтссон, Микаэль; Гране, Гёста; Бертосси, Леопольдо; Дун, Гожу; и др. (2009). "Модель ввода-вывода вычислений". Энциклопедия систем баз данных . Springer Science+Business Media . стр. 1333–1334. doi :10.1007/978-0-387-39940-9_752. ISBN 978-0-387-35544-3.
4. Аггарвал, Алок; Виттер, Джеффри (1988). «Сложность ввода-вывода сортировки и связанные с ней проблемы». Сообщения ACM . 31 (9): 1116–1127. doi : 10.1145/48529.48535 . S2CID  6264984.
5. Демейн, Эрик (2002). Алгоритмы и структуры данных, не учитывающие кэш (PDF) . Заметки к лекциям летней школы EEF по массивным наборам данных. Орхус: BRICS.
6. НАСА СП. НАСА. 1962. с. 276.
7. Компьютеры в кризисе. ACM. 1971. С. 296.

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

• Вне основных SVD и QR
• Из основных графических ресурсов
• Дизайн Scalapack