Параллельная внешняя память

Модель PEM

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

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

Определение [ править ]

Модель PEM ^[1] представляет собой комбинацию модели EM и модели PRAM. Модель PEM - это модель вычислений, которая состоит из процессоров и двухуровневой иерархии памяти . Эта иерархия памяти состоит из большой внешней памяти (основной памяти) определенного размера и небольших внутренних запоминающих устройств (кешей) . Процессоры совместно используют основную память. Каждый кеш является эксклюзивным для одного процессора. Процессор не может получить доступ к чужому кешу. Кеши имеют размер, который разделен на блоки . Процессоры могут выполнять операции только с данными, которые находятся в их кэше. Данные могут передаваться между основной памятью и кешем в блоках размера .${\ displaystyle P}$${\ displaystyle N}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle B}$${\ displaystyle B}$

Сложность ввода / вывода [ править ]

Мера сложности модели PEM является сложность ввода / вывода, ^[1] , который определяет количество параллельных блоков переводов между основной памятью и кэш - памяти. Во время параллельной передачи блоков каждый процессор может передавать блок. Таким образом, если процессоры загружают в свои кеши параллельно блок данных размером с основную память, это считается сложностью ввода-вывода, а не нет . Программа в модели PEM должна минимизировать передачу данных между основной памятью и кешами и работать с данными в кэшах в максимально возможной степени.${\ displaystyle P}$${\ displaystyle B}$${\ displaystyle O (1)}$${\ Displaystyle O (P)}$

Конфликты чтения / записи [ править ]

В модели PEM нет прямой сети связи между процессорами P. Процессоры должны косвенно обмениваться данными через основную память. Если несколько процессоров пытаются получить доступ к одному и тому же блоку в основной памяти одновременно, возникают конфликты чтения / записи ^[1] . Как и в модели PRAM, рассматриваются три различных варианта этой задачи:

• Concurrent Read Concurrent Write (CRCW): один и тот же блок в основной памяти может быть прочитан и записан несколькими процессорами одновременно.
• Параллельное чтение и монопольная запись (CREW): один и тот же блок в основной памяти может быть прочитан несколькими процессорами одновременно. Только один процессор может записывать в блок за раз.
• Эксклюзивное чтение Эксклюзивная запись (EREW): один и тот же блок в основной памяти не может быть прочитан или записан несколькими процессорами одновременно. Только один процессор может получить доступ к блоку одновременно.

Следующие два алгоритма ^[1] решают проблему CREW и EREW, если процессоры одновременно записывают в один и тот же блок. Первый подход - сериализовать операции записи. Только один процессор за другим записывает в блок. Это приводит к параллельным передачам блоков. Второй подход требует параллельной передачи блоков и дополнительного блока для каждого процессора. Основная идея состоит в том, чтобы запланировать операции записи в виде двоичного дерева и постепенно объединить данные в один блок. В первом раунде процессоры объединяют свои блоки в блоки. Затем процессоры объединяют блоки в . Эта процедура продолжается до тех пор, пока все данные не будут объединены в один блок.${\ Displaystyle P \ leq B}$${\ displaystyle P}$${\ Displaystyle О (\ журнал (P))}$${\ displaystyle P}$${\ displaystyle P / 2}$${\ displaystyle P / 2}$${\ displaystyle P / 2}$${\ displaystyle P / 4}$

Сравнение с другими моделями [ править ]

Примеры [ править ]

Многостороннее разбиение [ править ]

Позвольте быть вектором d-1 опорных точек, отсортированных в порядке возрастания. Позвольте быть неупорядоченным набором из N элементов. Двустороннее разбиение ^[1] из - это множество , где и для . называется i-м ведром. Количество элементов в больше и меньше чем . В следующем алгоритме ^[1] входные данные разделяются на непрерывные сегменты размером N / P в основной памяти. Процессор i в первую очередь работает на сегменте . Алгоритм многостороннего разделения ( ^[1] ) использует алгоритм суммы префиксов PEM ^[1] для вычисления суммы префиксов с оптимальным${\ Displaystyle M = \ {m_ {1}, ..., m_ {d-1} \}}$${\ displaystyle A}$${\ displaystyle A}$${\ Displaystyle \ Pi = \ {A_ {1}, ..., A_ {d} \}}$${\ Displaystyle \ чашка _ {я = 1} ^ {d} A_ {i} = A}$${\ Displaystyle A_ {i} \ cap A_ {j} = \ emptyset}$${\ Displaystyle 1 \ Leq я <J \ Leq d}$${\ displaystyle A_ {i}}$${\ displaystyle A_ {i}}$${\ displaystyle m_ {i-1}}$${\ displaystyle m_ {i} ^ {2}}$${\ displaystyle S_ {1}, ..., S_ {P}}$${\ displaystyle S_ {i}}$PEM_DIST_SORT${\ Displaystyle О ({\ гидроразрыва {N} {PB}} + \ log (P))}$Сложность ввода / вывода. Этот алгоритм моделирует оптимальный алгоритм суммы префиксов PRAM.

// Параллельно вычислить d-разделение сегментов данных для каждого процессора i параллельно do Считать вектор опорных точек в кэш.${\ displaystyle S_ {i}}$${\ displaystyle M}$ Разделите на d сегментов и пусть вектор будет количеством элементов в каждой корзине.конец для${\ displaystyle S_ {i}}$${\ displaystyle M_ {i} = \ {j_ {1} ^ {i}, ..., j_ {d} ^ {i} \}}$Выполните суммирование префикса PEM одновременно для набора векторов .${\ Displaystyle \ {M_ {1}, ..., M_ {P} \}}$// Используем вектор суммы префикса для вычисления последнего разделадля каждого процессора i параллельно выполните запись элементов в ячейки памяти, смещенные соответствующим образом на и .конец для${\ displaystyle S_ {i}}$${\displaystyle M_{i-1}}$${\displaystyle M_{i}}$Используя префиксные суммы, хранящиеся в последнем процессоре P, вычисляет вектор размеров корзины и возвращает его.${\displaystyle M_{P}}$${\displaystyle B}$

Если вектор опорных точек M и входной набор A расположены в непрерывной памяти, то проблема d-образного разбиения может быть решена в модели PEM со сложностью ввода-вывода. Содержимое последних сегментов должно располагаться в непрерывной памяти.${\displaystyle d=O({\frac {M}{B}})}$${\displaystyle O({\frac {N}{PB}}+\lceil {\frac {d}{B}}\rceil >\log(P)+d\log(B))}$

Выбор [ править ]

Проблема выбора заключается в нахождении k-го наименьшего элемента в неупорядоченном списке размеров . В следующем коде ^[1] используется алгоритм оптимальной сортировки PRAM, который выполняется , и алгоритм выбора оптимального однопроцессорного кэша.${\displaystyle A}$${\displaystyle N}$PRAMSORT${\displaystyle O(\log N)}$SELECT

если  тогда верните конец если${\displaystyle N\leq P}$  ${\displaystyle {\texttt {PRAMSORT}}(A,P)}$  ${\displaystyle A[k]}$ // Найти медиану каждого для каждого процессора в параллельном сделай конце для${\displaystyle S_{i}}$${\displaystyle i}$  ${\displaystyle m_{i}={\texttt {SELECT}}(S_{i},{\frac {N}{2P}})}$ // Сортировать медианы${\displaystyle {\texttt {PRAMSORT}}(\lbrace m_{1},\dots ,m_{2}\rbrace ,P)}$// Разделение вокруг медианы медиан${\displaystyle t={\texttt {PEMPARTITION}}(A,m_{P/2},P)}$если  тогда вернуть еще вернуться конец если${\displaystyle k\leq t}$   ${\displaystyle {\texttt {PEMSELECT}}(A[1:t],P,k)}$  ${\displaystyle {\texttt {PEMSELECT}}(A[t+1:N],P,k-t)}$

В предположении, что ввод хранится в непрерывной памяти, PEMSELECTимеет сложность ввода-вывода:

${\displaystyle O({\frac {N}{PB}}+\log(PB)\cdot \log({\frac {N}{P}}))}$

Сортировка распределения [ править ]

Сортировка распределения разделяет входной список размера на непересекающиеся сегменты одинакового размера. Затем каждая корзина рекурсивно сортируется, а результаты объединяются в полностью отсортированный список.${\displaystyle A}$${\displaystyle N}$${\displaystyle d}$

Если задача делегирована оптимальному для кеша однопроцессорному алгоритму сортировки.${\displaystyle P=1}$

В противном случае используется следующий алгоритм ^[1] :

// Примеры элементов из для каждого процессора параллельно делать , если затем загрузите в -sized страниц и сортировки страниц по отдельности еще загружать и сортировать в качестве одной страницы конца , если Заберите каждый «й элемент из каждой отсортированной страницы памяти в прилежащей вектор из образцов енд для${\displaystyle {\tfrac {4N}{\sqrt {d}}}}$${\displaystyle A}$ ${\displaystyle i}$   ${\displaystyle M<|S_{i}|}$  ${\displaystyle d=M/B}$${\displaystyle S_{i}}$${\displaystyle M}$ ${\displaystyle d=|S_{i}|}$${\displaystyle S_{i}}$${\displaystyle {\sqrt {d}}/4}$${\displaystyle R^{i}}$ параллельно do Объединить векторы в один непрерывный вектор Сделать копии : end do${\displaystyle R^{1}\dots R^{P}}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\sqrt {d}}}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {R}}_{1}\dots {\mathcal {R}}_{\sqrt {d}}}$// Найти шарниры для , чтобы параллельно сделайте конец для${\displaystyle {\sqrt {d}}}$${\displaystyle {\mathcal {M}}[j]}$ ${\displaystyle j=1}$${\displaystyle {\sqrt {d}}}$  ${\displaystyle {\mathcal {M}}[j]={\texttt {PEMSELECT}}({\mathcal {R}}_{i},{\tfrac {P}{\sqrt {d}}},{\tfrac {j\cdot 4N}{d}})}$Упаковать сводные точки в непрерывный массив ${\displaystyle {\mathcal {M}}}$// Разбиение точек на сегменты${\displaystyle A}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {B}}={\texttt {PEMMULTIPARTITION}}(A[1:N],{\mathcal {M}},{\sqrt {d}},P)}$// Рекурсивно сортировать сегментыдля , чтобы параллельно выполнять рекурсивный вызов на ведре размера с использованием процессоров , отвечающие за элементы в ведре конца для${\displaystyle j=1}$${\displaystyle {\sqrt {d}}+1}$ ${\displaystyle {\texttt {PEMDISTSORT}}}$${\displaystyle j}$${\displaystyle {\mathcal {B}}[j]}$${\displaystyle O\left(\left\lceil {\tfrac {{\mathcal {B}}[j]}{N/P}}\right\rceil \right)}$${\displaystyle j}$

Сложность ввода-вывода PEMDISTSORT:

${\displaystyle O\left(\left\lceil {\frac {N}{PB}}\right\rceil \left(\log _{d}P+\log _{M/B}{\frac {N}{PB}}\right)+f(N,P,d)\cdot \log _{d}P\right)}$

где

${\displaystyle f(N,P,d)=O\left(\log {\frac {PB}{\sqrt {d}}}\log {\frac {N}{P}}+\left\lceil {\frac {\sqrt {d}}{B}}\log P+{\sqrt {d}}\log B\right\rceil \right)}$

Если количество процессоров выбрано так, а сложность ввода-вывода составит:${\displaystyle f(N,P,d)=O\left(\left\lceil {\tfrac {N}{PB}}\right\rceil \right)}$${\displaystyle M<B^{O(1)}}$

${\displaystyle O\left({\frac {N}{PB}}\log _{M/B}{\frac {N}{B}}\right)}$

Другие алгоритмы PEM [ править ]

Алгоритм PEM	Сложность ввода / вывода	Ограничения
Сортировка слияния [1]	${\displaystyle O\left({\frac {N}{PB}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)={\textrm {sort}}_{P}(N)}$	${\displaystyle P\leq {\frac {N}{B^{2}}},M=B^{O(1)}}$
Рейтинг в списке [2]	${\displaystyle O\left({\textrm {sort}}_{P}(N)\right)}$	${\displaystyle P\leq {\frac {N/B^{2}}{\log B\cdot \log ^{O(1)}N}},M=B^{O(1)}}$
Эйлер тур [2]	${\displaystyle O\left({\textrm {sort}}_{P}(N)\right)}$	${\displaystyle P\leq {\frac {N}{B^{2}}},M=B^{O(1)}}$
Оценка дерева выражений [2]	${\displaystyle O\left({\textrm {sort}}_{P}(N)\right)}$	${\displaystyle P\leq {\frac {N}{B^{2}\log B\cdot \log ^{O(1)}N}},M=B^{O(1)}}$
Поиск MST [2]	${\displaystyle O\left({\textrm {sort}}_{P}(|V|)+{\textrm {sort}}_{P}(|E|)\log {\tfrac {|V|}{pB}}\right)}$	${\displaystyle p\leq {\frac {|V|+|E|}{B^{2}\log B\cdot \log ^{O(1)}N}},M=B^{O(1)}}$

Где время, необходимое для сортировки элементов с помощью процессоров в модели PEM.${\displaystyle {\textrm {sort}}_{P}(N)}$${\displaystyle N}$${\displaystyle P}$

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

• Параллельная машина с произвольным доступом (PRAM)
• Машина с произвольным доступом (RAM)
• Внешняя память (EM)

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