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

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

Модель

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

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

Алгоритмы

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

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

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

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

Приложения

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

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

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

История

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

См. также

Ссылки

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

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

[1] Виттер, Дж. С. (2001). «Алгоритмы внешней памяти и структуры данных: работа с МАССОВЫМИ ДАННЫМИ». Обзоры вычислительной техники ACM . 33 (2): 209–271. CiteSeerX 10.1.1.42.7064 . дои : 10.1145/384192.384193 . S2CID 2155038 .

[Vitter-2] Jump up to: ^а ^б Виттер, Дж. С. (2008). Алгоритмы и структуры данных для внешней памяти (PDF) . Серия «Основы и тенденции в теоретической информатике». Том. 2. Ганновер, Массачусетс: Now Publishers. стр. 305–474. CiteSeerX 10.1.1.140.3731 . дои : 10.1561/0400000014 . ISBN 978-1-60198-106-6 . {{cite book}}: |journal= игнорируется ( помогите )

[Springer-3] Чжан, Дунхуэй; Цотрас, Василис Дж.; Левиальди, Стивен; Гринштейн, Жорж; Берри, Дэймон Эндрю; Гуэ-Брюне, Валери; Кош, Харальд; Дёллер, Марио; Дёллер, Марио; Кош, Харальд; Майер, Пол; Бхаттачарья, Арнаб; Льоса, Вебйорн; Нак, Фрэнк; Бартолини, Илария; Гуэ-Брюне, Валери; Мэй, Тао; Руи, Ён; Крочано, Майкл; Ши, Фрэнк Ю.; Фан, Вэньфэй; Ульман-Кульере, Молли; Кларк, Юджин; Аронсон, Сэмюэл; Меллин, Джонас; Берндтссон, Майкл; Гране, Гость; Бертосси, Леопольдо; Дун, Гожу; и др. (2009). «Модель ввода-вывода вычислений». Энциклопедия систем баз данных . Springer Science+Business Media . стр. 1333–1334. дои : 10.1007/978-0-387-39940-9_752 . ISBN 978-0-387-35544-3 .

[Aggarwal88-4] Jump up to: ^а ^б ^с ^д Аггарвал, Алок; Виттер, Джеффри (1988). «Сложность ввода/вывода сортировки и связанные с ней проблемы» . Коммуникации АКМ . 31 (9): 1116–1127. дои : 10.1145/48529.48535 . S2CID 6264984 .

[Demaine02-5] Демейн, Эрик (2002). Алгоритмы и структуры данных, не обращающие внимания на кэш (PDF) . Конспект лекций Летней школы ВЭФ по массивным наборам данных. Орхус: БРИКС.

[6] НАСА СП . НАСА. 1962. с. 276.

[7] Компьютеры в кризисе . АКМ. 1971. с. 296.

[1]

[2]

[3]

[4]

[5]

[6]

[7]