Оператор редукции

В информатике , то оператор сокращения ^[1] представляет собой тип оператора , который обычно используется в параллельном программировании , чтобы уменьшить элементы массива в единый результат. Операторы редукции ассоциативны и часто (но не обязательно) коммутативны . ^{[2] [3] [4]} Сокращение наборов элементов является неотъемлемой частью моделей программирования, таких как Map Reduce , где оператор сокращения применяется ( отображается ) ко всем элементам перед их уменьшением. Другие параллельные алгоритмыиспользуйте операторы сокращения в качестве основных операций для решения более сложных задач. Многие операторы сокращения могут использоваться для широковещательной передачи для распределения данных по всем процессорам.

Теория [ править ]

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

Оператор является оператором редукции, если:

• Он может уменьшить массив до одного скалярного значения. ^[2]
• Окончательный результат должен быть получен из результатов созданных частичных задач. ^[2]

Эти два требования выполняются для коммутативных и ассоциативных операторов, которые применяются ко всем элементам массива.

Некоторые операторы, которые удовлетворяют этим требованиям, - это сложение, умножение и некоторые логические операторы (и, или и т. Д.).

Оператор сокращения может быть применен в постоянное время на входной набор из векторов с элементами каждыми. Результатом операции является комбинация элементов, которая должна быть сохранена в указанном корневом процессоре в конце выполнения. Если результат должен быть доступен на каждом процессоре после завершения вычисления, его часто называют Allreduce. Оптимальный последовательный алгоритм сокращения с линейным временем может применять оператор последовательно спереди назад, всегда заменяя два вектора результатом операции, примененной ко всем ее элементам, таким образом создавая экземпляр, который имеет на один вектор меньше. Нужны шаги, пока только${\ displaystyle \ oplus}$${\displaystyle V=\{v_{0}={\begin{pmatrix}e_{0}^{0}\\\vdots \\e_{0}^{m-1}\end{pmatrix}},v_{1}={\begin{pmatrix}e_{1}^{0}\\\vdots \\e_{1}^{m-1}\end{pmatrix}},\dots ,v_{p-1}={\begin{pmatrix}e_{p-1}^{0}\\\vdots \\e_{p-1}^{m-1}\end{pmatrix}}\}}$${\displaystyle p}$${\displaystyle m}$${\displaystyle r}$${\displaystyle r={\begin{pmatrix}e_{0}^{0}\oplus e_{1}^{0}\oplus \dots \oplus e_{p-1}^{0}\\\vdots \\e_{0}^{m-1}\oplus e_{1}^{m-1}\oplus \dots \oplus e_{p-1}^{m-1}\end{pmatrix}}={\begin{pmatrix}\bigoplus _{i=0}^{p-1}e_{i}^{0}\\\vdots \\\bigoplus _{i=0}^{p-1}e_{i}^{m-1}\end{pmatrix}}}$${\displaystyle r}$${\displaystyle (p-1)\cdot m}$${\displaystyle r}$осталось. Последовательные алгоритмы не могут работать лучше, чем линейное время, но параллельные алгоритмы оставляют некоторое пространство для оптимизации.

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

Предположим, у нас есть массив . Сумму этого массива можно вычислить последовательно, последовательно уменьшая массив до единой суммы с помощью оператора «+». Начиная суммирование с начала массива, получаем:${\displaystyle [2,3,5,1,7,6,8,4]}$

${\displaystyle {\Bigg (}{\bigg (}{\Big (}{\big (}\,(\,(2+3)+5)+1{\big )}+7{\Big )}+6{\bigg )}+8{\Bigg )}+4=36}$

Поскольку '+' коммутативен и ассоциативен, это оператор редукции. Следовательно, это сокращение может выполняться параллельно с использованием нескольких ядер, где каждое ядро ​​вычисляет сумму подмножества массива, а оператор сокращения объединяет результаты. Использование двоичного дерева сокращения позволило бы 4 ядра для вычисления , , , и . Затем два ядра могут вычислять и , наконец, одно ядро ​​вычисляет . Таким образом, для пошагового вычисления суммы можно использовать всего 4 ядра вместо шагов, необходимых для последовательной версии. Этот метод параллельного двоичного дерева вычисляет${\displaystyle (2+3)}$${\displaystyle (5+1)}$${\displaystyle (7+6)}$${\displaystyle (8+4)}$${\displaystyle (5+6)}$${\displaystyle (13+12)}$${\displaystyle (11+25)=36}$${\displaystyle \log _{2}8=3}$${\displaystyle 7}$${\displaystyle {\big (}\,(2+3)+(5+1)\,{\big )}+{\big (}\,(7+6)+(8+4)\,{\big )}}$. Конечно, результат тот же, но только из-за ассоциативности оператора редукции. Коммутативность оператора сокращения была бы важна, если бы главное ядро ​​распределяло работу между несколькими процессорами, поскольку тогда результаты могли бы возвращаться на главный процессор в любом порядке. Свойство коммутативности гарантирует, что результат будет таким же.

Nonexample [ править ]

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

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

Алгоритмы биномиального дерева [ править ]

Что касается параллельных алгоритмов, существует две основные модели параллельных вычислений: параллельная машина с произвольным доступом как расширение ОЗУ с общей памятью между процессорами и основной синхронный параллельный компьютер, который принимает во внимание связь и синхронизацию . Обе модели по-разному влияют на временную сложность , поэтому будут показаны два алгоритма.

PRAM-алгоритм [ править ]

Этот алгоритм представляет собой широко распространенный метод обработки входных данных со степенью двойки. Для элементов вещания часто используется обратная процедура. ^{[5] [6] [7]}${\displaystyle p}$

для того, чтобы делать${\displaystyle k\gets 0}$ ${\displaystyle \lceil \log _{2}p\rceil -1}$

для , чтобы сделать параллельно${\displaystyle i\gets 0}$ ${\displaystyle p-1}$

если активен, то${\displaystyle p_{i}}$

если бит из установлен , то${\displaystyle k}$ ${\displaystyle i}$

установлен в неактивный${\displaystyle p_{i}}$

иначе если ${\displaystyle i+2^{k}<p}$

${\displaystyle x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}}$

Бинарный оператор для векторов определяется поэлементно так, что . Далее алгоритм предполагает, что в начале для всех и является степенью двойки, и использует блоки обработки . На каждой итерации половина процессоров становится неактивной и не участвует в дальнейших вычислениях. На рисунке показана визуализация алгоритма с использованием сложения в качестве оператора. Вертикальные линии представляют блоки обработки, в которых происходит вычисление элементов в этой строке. Восемь входных элементов расположены внизу, и каждый шаг анимации соответствует одному параллельному шагу в выполнении алгоритма. Активный процессор оценивает данный оператор на элементе, который он в настоящее время удерживает, и где${\displaystyle {\begin{pmatrix}e_{i}^{0}\\\vdots \\e_{i}^{m-1}\end{pmatrix}}\oplus ^{\star }{\begin{pmatrix}e_{j}^{0}\\\vdots \\e_{j}^{m-1}\end{pmatrix}}={\begin{pmatrix}e_{i}^{0}\oplus e_{j}^{0}\\\vdots \\e_{i}^{m-1}\oplus e_{j}^{m-1}\end{pmatrix}}}$${\displaystyle x_{i}=v_{i}}$${\displaystyle i}$${\displaystyle p}$${\displaystyle p_{0},p_{1},\dots p_{n-1}}$${\displaystyle p_{i}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle j}$- выполнение минимального индекса , поэтому на текущем шаге он становится неактивным процессором. и не обязательно являются элементами входного набора, поскольку поля перезаписываются и повторно используются для ранее вычисленных выражений. Чтобы координировать роли блоков обработки на каждом этапе, не вызывая дополнительной связи между ними, используется тот факт, что блоки обработки индексируются числами от до . Каждый процессор смотрит на свой -й младший бит и решает, следует ли ему стать неактивным или вычислить оператор для своего собственного элемента и элемента с индексом, в котором-- ый бит не установлен. Базовый коммуникационный паттерн алгоритма - биномиальное дерево, отсюда и название алгоритма.${\displaystyle j>i}$${\displaystyle p_{j}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle X}$${\displaystyle 0}$${\displaystyle p-1}$${\displaystyle k}$${\displaystyle k}$

Только держит результат в конце концов, поэтому корневая процессор. Для операции Allreduce результат должен быть распределен, что можно сделать, добавив широковещательную рассылку из . Кроме того, количество процессоров ограничено степенью до двух. Этого можно избежать, увеличив количество процессоров до ближайшей степени двойки. Существуют также алгоритмы, которые больше подходят для этого варианта использования. ^[8]${\displaystyle p_{0}}$${\displaystyle p_{0}}$${\displaystyle p}$

Анализ времени выполнения [ править ]

Основной цикл выполняется раз, время, необходимое для части, выполняемой параллельно, составляет, поскольку блок обработки либо объединяет два вектора, либо становится неактивным. Таким образом, параллельное время для PRAM составляет . Стратегия обработки конфликтов чтения и записи может быть выбрана такой же ограничительной, как исключительное чтение и монопольная запись (EREW). Ускорение алгоритма является и , следовательно, эффективность является . Эффективность страдает из-за того, что половина активных блоков обработки становится неактивной после каждого шага, поэтому блоки активны на шаге .${\displaystyle \lceil \log _{2}p\rceil }$${\displaystyle {\mathcal {O}}(m)}$${\displaystyle T(p,m)}$${\displaystyle T(p,m)={\mathcal {O}}(\log(p)\cdot m)}$${\displaystyle S(p,m)}$${\displaystyle S(p,m)\in {\mathcal {O}}\left({\frac {T_{seq}}{T(p,m)}}\right)={\mathcal {O}}\left({\frac {p}{\log(p)}}\right)}$${\displaystyle E(p,m)\in {\mathcal {O}}\left({\frac {S(p,m)}{p}}\right)={\mathcal {O}}\left({\frac {1}{\log(p)}}\right)}$${\displaystyle {\frac {p}{2^{i}}}}$${\displaystyle i}$

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

В отличие от алгоритма PRAM, в модели распределенной памяти память не распределяется между блоками обработки, и данные должны обмениваться явно между блоками обработки. Следовательно, данные должны обмениваться между устройствами явно, как можно увидеть в следующем алгоритме.

для того, чтобы делать${\displaystyle k\gets 0}$ ${\displaystyle \lceil \log _{2}p\rceil -1}$

для , чтобы сделать параллельно${\displaystyle i\gets 0}$ ${\displaystyle p-1}$

если активен, то${\displaystyle p_{i}}$

если бит из установлен , то${\displaystyle k}$ ${\displaystyle i}$

отправить в${\displaystyle x_{i}}$ ${\displaystyle p_{i-2^{k}}}$

установлен в неактивный${\displaystyle p_{k}}$

иначе если ${\displaystyle i+2^{k}<p}$

получить ${\displaystyle x_{i+2^{k}}}$

${\displaystyle x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}}$

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

Анализ времени выполнения [ править ]

Связь между устройствами приводит к некоторым накладным расходам. Простой анализ алгоритма использует BSP-модель и включает время, необходимое для инициирования связи, и время, необходимое для отправки байта. Тогда результирующее время выполнения будет таким , поскольку элементы вектора отправляются на каждой итерации и имеют общий размер .${\displaystyle T_{start}}$${\displaystyle T_{byte}}$${\displaystyle \Theta ((T_{start}+n\cdot T_{byte})\cdot log(p))}$${\displaystyle m}$${\displaystyle n}$

Трубопровод-алгоритм [ править ]

Для моделей распределенной памяти может иметь смысл использовать конвейерную связь. Это особенно актуально, когда он мал по сравнению с . Обычно линейные конвейеры разделяют данные или задачи на более мелкие части и обрабатывают их поэтапно. В отличие от алгоритмов биномиального дерева конвейерный алгоритм использует тот факт, что векторы не являются неотделимыми, но оператор может быть вычислен для отдельных элементов: ^[9]${\displaystyle T_{start}}$${\displaystyle T_{byte}}$

для того, чтобы делать${\displaystyle k\gets 0}$ ${\displaystyle p+m-3}$

для , чтобы сделать параллельно${\displaystyle i\gets 0}$ ${\displaystyle p-1}$

если ${\displaystyle i\leq k<i+m\land i\neq p-1}$

отправить в${\displaystyle x_{i}^{k-i}}$ ${\displaystyle p_{i+1}}$

если ${\displaystyle i-1\leq k<i-1+m\land i\neq 0}$

получать от${\displaystyle x_{i-1}^{k+i-1}}$ ${\displaystyle p_{i-1}}$

${\displaystyle x_{i}^{k+i-1}\gets x_{i}^{k+i-1}\oplus x_{i-1}^{k+i-1}}$

Важно отметить, что для работы алгоритма операции отправки и получения должны выполняться одновременно. Вектор результата сохраняется в конце. Соответствующая анимация показывает выполнение алгоритма над векторами размера четыре с пятью модулями обработки. Два шага анимации визуализируют один параллельный шаг выполнения.${\displaystyle p_{p-1}}$

Анализ времени выполнения [ править ]

Количество шагов в параллельном выполнении является , он принимает меры , пока последний блок обработки не получает свой первый элемент и дополнительный , пока не будут получены все элементы. Следовательно, время выполнения в BSP-модели равно , если предположить, что это общий размер вектора в байтах.${\displaystyle p+m-2}$${\displaystyle p-1}$${\displaystyle m-1}$${\displaystyle T(n,p,m)=\left(T_{start}+{\frac {n}{m}}\cdot T_{byte}\right)(p+m-2)}$${\displaystyle n}$

Хотя имеет фиксированное значение, можно логически сгруппировать элементы вектора вместе и уменьшить . Например, экземпляр задачи с векторами размера четыре может быть обработан путем разделения векторов на первые два и последние два элемента, которые всегда передаются и вычисляются вместе. В этом случае каждый шаг отправляется в два раза больше, но количество шагов уменьшилось примерно вдвое. Это означает, что параметр уменьшается вдвое, а общий размер байта остается прежним. Время выполнения для этого подхода зависит от значения , которые могут быть оптимизированы , если и известны. Это оптимально для , если предположить, что в результате получается меньшее , чем исходное.${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle n}$${\displaystyle T(p)}$${\displaystyle m}$${\displaystyle T_{start}}$${\displaystyle T_{byte}}$${\displaystyle m={\sqrt {\frac {n\cdot (p-2)\cdot T_{byte}}{T_{start}}}}}$${\displaystyle m}$

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

Редукция - одна из основных коллективных операций, реализованных в интерфейсе передачи сообщений , где производительность используемого алгоритма важна и постоянно оценивается для различных вариантов использования. ^[10] Операторы могут использоваться в качестве параметров для MPI_Reduceи MPI_Allreduce, с той разницей, что результат доступен на одном (корневом) процессоре или на всех из них. MapReduce в значительной степени полагается на эффективные алгоритмы сокращения для обработки больших наборов данных, даже на огромных кластерах. ^{[11] [12]}

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

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

• Сложить (функция высшего порядка)

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

Книги [ править ]

• Чандра, Рохит (2001). Параллельное программирование в OpenMP . Морган Кауфманн. стр.  59 -77. ISBN 1558606718.
• Солихин, Ян (2016). Основы параллельной многоядерной архитектуры . CRC Press. п. 75. ISBN 978-1-4822-1118-4.

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

• Оговорка о сокращении, ссылка на оговорку о сокращении