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

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

• 1 Теория
  • 1.1 Пример
  • 1.2 Нет примера
• 2 Алгоритмы
  • 2.1 Алгоритмы биномиального дерева
    • 2.1.1 PRAM-алгоритм
      • 2.1.1.1 Анализ времени выполнения
    • 2.1.2 Алгоритм распределенной памяти
      • 2.1.2.1 Анализ времени выполнения
  • 2.2 Конвейерный алгоритм
    • 2.2.1 Анализ времени выполнения
• 3 Приложения
• 4 См. Также
• 5 Ссылки
• 6 Книги
• 7 Внешние ссылки

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

Оператор является оператором сокращения, если:

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

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

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

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

Пример

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

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

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

Непример

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

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

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

PRAM-алгоритм

Этот алгоритм представляет собой широко распространенный метод обработки входных данных, где $p\; \{\backslash \; displaystyle\; p\}$- степень двойки. Для элементов широковещательной передачи часто используется обратная процедура.

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

для $k\; \leftarrow \; 0\; \{\backslash \; displaystyle\; k\; \backslash \; получает\; 0\}$to$\lceil \; log\; 2\; \; p\; \rceil \; -\; 1\; \{\backslash \; displaystyle\; \backslash \; lceil\; \backslash \; log\; \_\; \{2\}\; p\; \backslash \; rceil\; -1\}$do

for$i\; \leftarrow \; 0\; \{\backslash \; displaystyle\; i\; \backslash \; gets\; 0\}$to$p\; -\; 1\; \{\backslash \; displaystyle\; p-1\}$делать параллельно

if$pi\; \{\backslash \; displaystyle\; p\_\; \{i\}\}$активен, то

если бит $k\; \{\backslash \; displaystyle\; k\}$of$i\; \{\backslash \; displaystyle\; i\}$установлен, тогда

установить $pi\; \{\backslash \; displaystyle\; p\_\; \{i\}\}$в неактивное состояние

иначе, если

$xi\; \leftarrow \; xi\; \oplus \; \star \; xi\; +\; 2\; k\; \{\backslash \; displaystyle\; x\_\; \{i\}\; \backslash \; получает\; x\_\; \{i\}\; \backslash \; oplus\; ^\; \{\backslash \; star\}\; x\_\; \{i\; +\; 2\; ^\; \{k\; \}\}\}$

Бинарный оператор для векторов определяется поэлементно так, что $(ei\; 0\; ⋮\; eim\; -\; 1)\; \oplus \; \star \; (ej\; 0\; ⋮\; ejm\; -\; 1)\; =\; (ei\; 0\; \oplus \; ej\; 0\; ⋮\; eim\; -\; 1\; \oplus \; ejm\; -\; 1)\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{pmatrix\}\; e\_\; \{i\}\; ^\; \{0\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; e\_\; \{i\}\; ^\; \{m-1\}\; \backslash \; end\; \{pmatrix\}\}\; \backslash \; oplus\; ^\; \{\backslash \; star\; \}\; \{\backslash \; begin\; \{pmatrix\}\; e\_\; \{j\}\; ^\; \{0\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; e\_\; \{j\}\; ^\; \{m-1\}\; \backslash \; end\; \{pmatrix\}\; \}\; =\; \{\backslash \; begin\; \{pmatrix\}\; e\_\; \{i\}\; ^\; \{0\}\; \backslash \; oplus\; e\_\; \{j\}\; ^\; \{0\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; e\_\; \{i\}\; ^\; \{m-1\}\; \backslash \; oplus\; e\_\; \{j\}\; ^\; \{\; м-1\}\; \backslash \; end\; \{pmatrix\}\}\}$. Далее алгоритм предполагает, что в начале $xi\; =\; vi\; \{\backslash \; displaystyle\; x\_\; \{i\}\; =\; v\_\; \{i\}\}$для всех $i\; \{\backslash \; displaystyle\; i\}$и $p\; \{\backslash \; displaystyle\; p\}$представляет собой степень двойки и использует блоки обработки $p\; 0,\; p\; 1,\dots \; pn\; -\; 1\; \{\backslash \; displaystyle\; p\_\; \{0\},\; p\_\; \{1\; \},\; \backslash \; точки\; p\_\; \{n-1\}\}$. На каждой итерации половина процессоров становится неактивной и не участвует в дальнейших вычислениях. На рисунке показана визуализация алгоритма с использованием сложения в качестве оператора. Вертикальные линии представляют собой блоки обработки, в которых происходит вычисление элементов в этой строке. Восемь входных элементов расположены внизу, и каждый шаг анимации соответствует одному параллельному шагу выполнения алгоритма. Активный процессор $pi\; \{\backslash \; displaystyle\; p\_\; \{i\}\}$оценивает данный оператор для элемента $xi\; \{\backslash \; displaystyle\; x\_\; \{i\}\}$, который он в настоящее время удерживает и $xj\; \{\backslash \; displaystyle\; x\_\; \{j\}\}$, где $j\; \{\backslash \; displaystyle\; j\}$- минимальный индекс, удовлетворяющий $j>i\; \{\backslash \; displaystyle\; j>i\}$, так что $pj\; \{\backslash \; displaystyle\; p\_\; \{j\}\}$становится неактивным процессором на текущем шаге. $xi\; \{\backslash \; displaystyle\; x\_\; \{i\}\}$и $xj\; \{\backslash \; displaystyle\; x\_\; \{j\}\}$не обязательно являются элементами входного набора $X\; \{\backslash \; displaystyle\; X\}$, поскольку поля перезаписываются и используются повторно для ранее оцененных выражений. Чтобы координировать роли блоков обработки на каждом шаге, не вызывая дополнительной связи между ними, тот факт, что блоки обработки индексируются числами из $0\; \{\backslash \; displaystyle\; 0\}$до $p\; -\; 1\; \{\backslash \; displaystyle\; p-1\}$. Каждый процессор смотрит на свой $k\; \{\backslash \; displaystyle\; k\}$-й младший бит и решает, следует ли ему стать неактивным или вычислить оператор для своего собственного элемента и элемента с индексом, где $k\; \{\backslash \; displaystyle\; k\}$-й бит не установлен. Базовый шаблон связи алгоритма - биномиальное дерево, отсюда и название алгоритма.

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

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

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

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

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

для$k\; \leftarrow \; 0\; \{\backslash \; displaystyle\; k\; \backslash \; gets\; 0\}$to$\lceil \; log\; 2\; \; p\; \rceil \; -\; 1\; \{\backslash \; displaystyle\; \backslash \; lceil\; \backslash \; log\; \_\; \{2\}\; p\; \backslash \; rceil\; -1\}$do

для $i\; \leftarrow \; 0\; \{\backslash \; displaystyle\; i\; \backslash \; gets\; 0\}$to$p\; -\; 1\; \{\backslash \; displaystyle\; p-1\}$do параллельно

if$pi\; \{\backslash \; displaystyle\; p\_\; \{i\}\; \}$активен, то

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

send $xi\; \{\backslash \; displaystyle\; x\_\; \{i\}\}$to$pi\; -\; 2\; k\; \{\backslash \; displaystyle\; p\_\; \{i-2\; ^\; \{k\}\}\}$

set$pk\; \{\backslash \; displaystyle\; p\_\; \{k\}\}$в неактивный

иначе, если

получить$xi\; +\; 2\; k\; \{\backslash \; displaystyle\; x\_\; \{i\; +\; 2\; ^\; \{k\}\}\}$

$xi\; \leftarrow \; xi\; \oplus \; \star \; xi\; +\; 2\; k\; \{\backslash \; displaystyle\; x\_\; \{i\}\; \backslash \; gets\; x\_\; \{i\}\; \backslash \; oplus\; ^\; \{\backslash \; star\}\; x\_\; \{i\; +\; 2\; ^\; \{k\}\}\}$

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

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

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

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

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

Для моделей распределенной памяти может иметь смысл использовать конвейерное взаимодействие. Это особенно важно, когда $T\; s\; t\; a\; r\; t\; \{\backslash \; displaystyle\; T\_\; \{start\}\}$мало по сравнению с $T\; b\; y\; t\; e\; \{\backslash \; displaystyle\; T\_\; \{byte\}\}$. Обычно линейные конвейеры разделяют данные или задачи на более мелкие части и обрабатывают их поэтапно. В отличие от алгоритмов биномиального дерева конвейерный алгоритм использует тот факт, что векторы не являются неразделимыми, но оператор может быть вычислен для отдельных элементов:

для $k\; \leftarrow \; 0\; \{\backslash \; displaystyle\; k\; \backslash \; gets\; 0\}$to$p\; +\; m\; -\; 3\; \{\backslash \; displaystyle\; p\; +\; m-3\}$do

for$i\; \leftarrow \; 0\; \{\backslash \; displaystyle\; i\; \backslash \; gets\; 0\}$to$p\; -\; 1\; \{\backslash \; displaystyle\; p\; -1\}$выполнить параллельно

if

отправить$xik\; -\; i\; \{\backslash \; displaystyle\; x\_\; \{i\}\; ^\; \{ki\}\}$to$pi\; +\; 1\; \{\backslash \; displaystyle\; p\_\; \{i\; +\; 1\}\}$

if

получить$xi\; -\; 1\; k\; +\; i\; -\; 1\; \{\backslash \; displaystyle\; x\_\; \{i-1\}\; ^\; \{k\; +\; i-1\}\}$из$pi\; -\; 1\; \{\backslash \; displaystyle\; p\_\; \{i-1\}\}$

$xik\; +\; i\; -\; 1\; \leftarrow \; xik\; +\; i\; -\; 1\; \oplus \; xi\; -\; 1\; k\; +\; i\; -\; 1\; \{\backslash \; displaystyle\; x\_\; \{i\}\; ^\; \{k\; +\; i-1\}\; \backslash \; gets\; x\_\; \{i\}\; ^\; \{k\; +\; i-1\}\; \backslash \; oplus\; x\_\; \{i-1\}\; ^\; \{k\; +\; i-1\}\}$

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

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

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

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

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

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

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

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

• Сокращающее предложение, Ссылка на сокращающее предложение