Оператор сокращения

В информатике оператор приведения — это тип оператора , который обычно используется в параллельном программировании для сведения элементов массива к одному результату. Операторы редукции ассоциативны и часто (но не обязательно) коммутативны . Сокращение наборов элементов является неотъемлемой частью таких моделей программирования, как Map Download , где оператор сокращения применяется ( сопоставляется ) ко всем элементам перед их сокращением. Другие параллельные алгоритмы используют операторы сокращения в качестве основных операций для решения более сложных задач. Многие операторы сокращения могут использоваться для широковещательной рассылки для распределения данных по всем процессорам.

Теория

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

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

• Он может свести массив к одному скалярному значению.
• Конечный результат должен быть получен из результатов созданных частичных задач.

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

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

Оператор сокращения $\oplus$ может применяться в постоянное время к входному набору $$V=\left\{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}}\right\}$$из $p$ векторы с $m$ элементы каждый. Результат $r$ операция представляет собой комбинацию элементов $$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}}$$ и должен быть сохранен в указанном корневом процессоре в конце выполнения. Если результат $r$ должен быть доступен на каждом процессоре после завершения вычислений, его часто называют Allreduce. Оптимальный последовательный алгоритм сокращения с линейным временем может применять оператор последовательно спереди назад, всегда заменяя два вектора результатом операции, примененной ко всем его элементам, создавая таким образом экземпляр, в котором на один вектор меньше. Это требует $(p-1)\cdot m$ шаги, пока только $r$ осталось. Последовательные алгоритмы не могут работать лучше, чем линейное время, но параллельные алгоритмы оставляют некоторое пространство для оптимизации.

Пример

Предположим, у нас есть массив $[2,3,5,1,7,6,8,4]$. Сумма этого массива может быть вычислена последовательно путем последовательного сведения массива к одной сумме с помощью оператора «+». Начав суммирование с начала массива, получим: $${\Bigg (}{\bigg (}{\Big (}{\big (}\,(\,(2+3)+5)+1{\big )}+7{\Big )}+6{\bigg )}+8{\Bigg )}+4=36$$

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

Беспримерный

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

Алгоритмы

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

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

PRAM-алгоритм

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

Визуализация алгоритма с p = 8, m = 1 и сложением в качестве оператора приведения

для $k\gets 0$ к $\lceil \log _{2}p\rceil -1$ делать

для $i\gets 0$ к $p-1$ делать параллельно

если $p_{i}$ тогда активен

если немного $k$ из $i$ устанавливается тогда

набор $p_{i}$ в неактивный

еще если $i+2^{k}<p$

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

Бинарный оператор для векторов определяется поэлементно так, что ${\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}}$. Далее алгоритм предполагает, что вначале $x_{i}=v_{i}$ для всех $i$ и $p$ представляет собой степень двойки и использует процессоры $p_{0},p_{1},\dots p_{n-1}$. На каждой итерации половина процессоров становится неактивной и не участвует в дальнейших вычислениях. На рисунке показана визуализация алгоритма, использующего сложение в качестве оператора. Вертикальные линии представляют собой процессоры, в которых происходят вычисления элементов в этой строке. Восемь входных элементов расположены внизу, и каждый шаг анимации соответствует одному параллельному шагу выполнения алгоритма. Активный процессор $p_{i}$ оценивает данный оператор на элементе $x_{i}$ в настоящее время он держится и $x_{j}$ где $j$ минимальный индекс, удовлетворяющий $j>i$, так что $p_{j}$ становится неактивным процессором на текущем этапе. $x_{i}$ и $x_{j}$ не обязательно являются элементами входного набора $X$ поскольку поля перезаписываются и повторно используются для ранее вычисленных выражений. Для координации ролей процессоров на каждом этапе, не вызывая дополнительной связи между ними, используется тот факт, что процессоры индексируются числами из $0$ к $p-1$ используется. Каждый процессор смотрит на свой $k$-th наименее значащий бит и решает, стать ли оператор неактивным или вычислить оператор для собственного элемента и элемента с индексом, где $k$-й бит не установлен. Базовым коммуникационным шаблоном алгоритма является биномиальное дерево, отсюда и название алгоритма.

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

Анализ времени выполнения

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

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

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

для $k\gets 0$ к $\lceil \log _{2}p\rceil -1$ делать

для $i\gets 0$ к $p-1$ делать параллельно

если $p_{i}$ тогда активен

если немного $k$ из $i$ устанавливается тогда

отправлять $x_{i}$ к $p_{i-2^{k}}$

набор $p_{k}$ в неактивный

еще если $i+2^{k}<p$

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

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

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

Анализ времени выполнения

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

Конвейерный алгоритм

Визуализация конвейерного алгоритма с p = 5, m = 4 и сложением в качестве оператора сокращения.

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

для $k\gets 0$ к $p+m-3$ делать

для $i\gets 0$ к $p-1$ делать параллельно

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

отправлять $x_{i}^{k-i}$ к $p_{i+1}$

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

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

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

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

Анализ времени выполнения

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

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

Приложения

Сокращение — одна из основных коллективных операций, реализованных в интерфейсе передачи сообщений , где важна производительность используемого алгоритма, которая постоянно оценивается для различных вариантов использования. Операторы могут использоваться в качестве параметров для MPI_Reduce и MPI_Allreduce, с той разницей, что результат доступен на одном (корневом) процессоре или на всех. MapReduce в значительной степени полагается на эффективные алгоритмы сокращения при обработке больших наборов данных, даже в огромных кластерах.

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

См. также

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