Оператор редукции
Концепция компьютерной науки

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

Теория

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

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

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

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

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

Оператор редукции может быть применен за постоянное время к входному набору векторов с элементами каждый. Результатом операции является комбинация элементов , и она должна быть сохранена на указанном корневом процессоре в конце выполнения. Если результат должен быть доступен на каждом процессоре после завершения вычисления, его часто называют Allreduce. Оптимальный последовательный алгоритм линейного времени для редукции может применять оператор последовательно от начала к концу, всегда заменяя два вектора результатом операции, примененной ко всем его элементам, тем самым создавая экземпляр, в котором на один вектор меньше. Ему нужны шаги, пока не останется только . Последовательные алгоритмы не могут работать лучше, чем за линейное время, но параллельные алгоритмы оставляют некоторое пространство для оптимизации. ⊕ {\displaystyle \oplus} В = { в 0 = ( е 0 0 ⋮ е 0 м − 1 ) , в 1 = ( е 1 0 ⋮ е 1 м − 1 ) , … , в п − 1 = ( е п − 1 0 ⋮ е п − 1 м − 1 ) } {\displaystyle 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\}} п {\displaystyle p} м {\displaystyle м} г {\displaystyle r} г = ( е 0 0 ⊕ е 1 0 ⊕ ⋯ ⊕ е п − 1 0 ⋮ е 0 м − 1 ⊕ е 1 м − 1 ⊕ ⋯ ⊕ е п − 1 м − 1 ) = ( ⨁ я = 0 п − 1 е я 0 ⋮ ⨁ я = 0 п − 1 е я м − 1 ) {\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} ( п − 1 ) ⋅ м {\displaystyle (p-1)\cdot м} г {\displaystyle r}

Пример

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

IEEE 754-2019 определяет 4 вида редукций сумм и 3 вида редукций масштабированных произведений. Поскольку операции являются операторами редукции, стандарты определяют, что «реализации могут ассоциироваться в любом порядке или оцениваться в любом более широком формате». [5]

Непример

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

Алгоритмы

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

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

PRAM-алгоритм

Этот алгоритм представляет собой широко распространенный метод обработки входов, где — степень двойки. Обратная процедура часто используется для трансляции элементов. [6] [7] [8] п {\displaystyle p}

Визуализация алгоритма при p = 8, m = 1 и сложении в качестве оператора редукции
для того, чтобы сделать к ← 0 {\displaystyle k\получает 0} ⌈ бревно 2 ⁡ п ⌉ − 1 {\displaystyle \lceil \log _ {2}p\rceil -1}
для того, чтобы делать параллельно я ← 0 {\displaystyle i\получает 0} п − 1 {\displaystyle p-1}
если активен, то п я {\displaystyle p_{i}}
если бит установлен , то к {\displaystyle к} я {\displaystyle я}
установлен в неактивное состояние п я {\displaystyle p_{i}}
иначе если я + 2 к < п {\displaystyle i+2^{k}<p}
х я ← х я ⊕ ⋆ х я + 2 к {\displaystyle x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}}

Бинарный оператор для векторов определяется поэлементно таким образом, что ( е я 0 ⋮ е я м − 1 ) ⊕ ⋆ ( е дж 0 ⋮ е дж м − 1 ) = ( е я 0 ⊕ е дж 0 ⋮ е я м − 1 ⊕ е дж м − 1 ) . {\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 я} п {\displaystyle p} п 0 , п 1 , … п н − 1 {\displaystyle p_{0},p_{1},\точки p_{n-1}} п я {\displaystyle p_{i}} х я {\displaystyle x_{i}} х дж {\displaystyle x_{j}} дж {\displaystyle j} дж > я {\displaystyle j>я} п дж {\displaystyle p_{j}} х я {\displaystyle x_{i}} х дж {\displaystyle x_{j}} Х {\displaystyle X} 0 {\displaystyle 0} п − 1 {\displaystyle p-1} к {\displaystyle к} к {\displaystyle к}

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

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

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

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

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

для того, чтобы сделать к ← 0 {\displaystyle k\получает 0} ⌈ бревно 2 ⁡ п ⌉ − 1 {\displaystyle \lceil \log _ {2}p\rceil -1}
для того, чтобы делать параллельно я ← 0 {\displaystyle i\получает 0} п − 1 {\displaystyle p-1}
если активен, то п я {\displaystyle p_{i}}
если бит установлен , то к {\displaystyle к} я {\displaystyle я}
отправить ​ х я {\displaystyle x_{i}} п я − 2 к {\displaystyle p_{i-2^{k}}}
установлен в неактивное состояние п к {\displaystyle p_{k}}
иначе если я + 2 к < п {\displaystyle i+2^{k}<p}
получать х я + 2 к {\displaystyle x_{i+2^{k}}}
х я ← х я ⊕ ⋆ х я + 2 к {\displaystyle x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}}

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

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

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

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

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

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

для того, чтобы сделать к ← 0 {\displaystyle k\получает 0} п + м − 3 {\displaystyle p+m-3}
для того, чтобы делать параллельно i ← 0 {\displaystyle i\gets 0} p − 1 {\displaystyle p-1}
если i ≤ k < i + m ∧ i ≠ p − 1 {\displaystyle i\leq k<i+m\land i\neq p-1}
отправить ​ x i k − i {\displaystyle x_{i}^{k-i}} p i + 1 {\displaystyle p_{i+1}}
если i − 1 ≤ k < i − 1 + m ∧ i ≠ 0 {\displaystyle i-1\leq k<i-1+m\land i\neq 0}
получить от x i − 1 k + i − 1 {\displaystyle x_{i-1}^{k+i-1}} p i − 1 {\displaystyle p_{i-1}}
x i k + i − 1 ← x i k + i − 1 ⊕ x i − 1 k + i − 1 {\displaystyle x_{i}^{k+i-1}\gets x_{i}^{k+i-1}\oplus x_{i-1}^{k+i-1}}

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

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

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

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

Приложения

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

OpenMP предлагает редукционный пункт для описания того, как результаты параллельных операций собираются вместе. [12]

MapReduce в значительной степени опирается на эффективные алгоритмы сокращения для обработки больших наборов данных, даже в огромных кластерах. [13] [14]

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

Смотрите также

Ссылки

  1. ^ "Reduction Clause". www.dartmouth.edu . Dartmouth College. 23 марта 2009 г. Получено 26 сентября 2016 г.
  2. ^ abc Солихин, Ян (2016). Основы параллельной многоядерной архитектуры . ЦРК Пресс. п. 75. ИСБН 978-1-4822-1118-4.
  3. ^ Чандра, Рохит (2001). Параллельное программирование в OpenMP . Морган Кауфманн. стр. 59–77. ISBN 1558606718.
  4. ^ Коул, Мюррей (2004). «Вытаскивание скелетов из шкафа: прагматичный манифест скелетного параллельного программирования» (PDF) . Параллельные вычисления . 30 (3): 393. doi :10.1016/j.parco.2003.12.002. hdl : 20.500.11820/8eb79d42-de83-4cfb-9faa-30d9ac3b3839 .
  5. ^ IEEE Computer Society (22 июля 2019 г.). "9.4 Операции приведения". Стандарт IEEE для арифметики с плавающей точкой . IEEE STD 754-2019. IEEE. стр.  1– 84. doi :10.1109/IEEESTD.2019.8766229. ISBN 978-1-5044-5924-2. Стандарт IEEE 754-2019.
  6. ^ Бар-Ной, Амоц; Кипнис, Шломо (1994). «Трансляция нескольких сообщений в системах одновременной отправки/приема». Дискретная прикладная математика . 55 (2): 95– 105. doi :10.1016/0166-218x(94)90001-9.
  7. ^ Сантос, Юнис Э. (2002). «Оптимальные и эффективные алгоритмы суммирования и префиксного суммирования на параллельных машинах». Журнал параллельных и распределенных вычислений . 62 (4): 517– 543. doi :10.1006/jpdc.2000.1698.
  8. ^ Слейтер, П.; Кокейн, Э.; Хедетниеми, С. (1981-11-01). «Распространение информации в деревьях». Журнал SIAM по вычислениям . 10 (4): 692– 701. doi :10.1137/0210052. ISSN  0097-5397.
  9. ^ Рабенсейфнер, Рольф; Трефф, Йеспер Ларссон (2004-09-19). "Более эффективные алгоритмы сокращения для числа процессоров, не равного степени двойки, в параллельных системах передачи сообщений". Последние достижения в области параллельных виртуальных машин и интерфейса передачи сообщений . Конспект лекций по информатике. Том 3241. Springer, Берлин, Гейдельберг. С.  36–46 . doi :10.1007/978-3-540-30218-6_13. ISBN 9783540231639.
  10. ^ Бар-Ной, А.; Кипнис, С. (1994-09-01). «Проектирование алгоритмов вещания в почтовой модели для систем передачи сообщений». Математическая теория систем . 27 (5): 431– 452. CiteSeerX 10.1.1.54.2543 . doi :10.1007/BF01184933. ISSN  0025-5661. S2CID  42798826. 
  11. ^ Pješivac-Grbović, Jelena; Angskun, Thara; Bosilca, George; Fagg, Graham E.; Gabriel, Edgar; Dongarra, Jack J. (2007-06-01). «Анализ производительности коллективных операций MPI». Cluster Computing . 10 (2): 127– 143. CiteSeerX 10.1.1.80.3867 . doi :10.1007/s10586-007-0012-0. ISSN  1386-7857. S2CID  2142998. 
  12. ^ "10.9. Редукция — Примеры интерфейса прикладного программирования OpenMP". passlab.github.io .
  13. ^ Лэммель, Ральф (2008). «Модель программирования MapReduce от Google — повторный взгляд». Science of Computer Programming . 70 (1): 1– 30. doi :10.1016/j.scico.2007.07.001.
  14. ^ Senger, Hermes; Gil-Costa, Veronica; Arantes, Luciana; Marcondes, Cesar AC; Marín, Mauricio; Sato, Liria M.; da Silva, Fabrício AB (10.06.2016). "BSP cost and scalability analysis for MapReduce operations". Concurrency and Computation: Practice and Experience . 28 (8): 2503– 2527. doi : 10.1002/cpe.3628. hdl : 10533/147670 . ISSN  1532-0634. S2CID  33645927.
  15. ^ Акстманн, Михаэль; Бингманн, Тимо; Сандерс, Питер; Шульц, Кристиан (2014-10-24). «Практическая массивно-параллельная сортировка». arXiv : 1410.6754 [cs.DS].
Retrieved from "https://en.wikipedia.org/w/index.php?title=Reduction_operator&oldid=1256335781"