Префиксная сумма

Последовательность в информатике

В информатике префиксная сумма , кумулятивная сумма , инклюзивное сканирование или просто сканирование последовательности чисел x ₀ , x ₁ , x ₂ , ... — это вторая последовательность чисел y ₀ , y ₁ , y ₂ , ... , суммы префиксов ( текущие итоги ) входной последовательности:

у0 = х0_​​

у1 = х0 + х1_​​​

у2 = х0 + х1 + х2_​​​​

...

Например, префиксные суммы натуральных чисел являются треугольными числами :

Префиксные суммы тривиально вычисляются в последовательных моделях вычислений, используя формулу y _i = y _{i − 1} + x _i для вычисления каждого выходного значения в порядке последовательности. Однако, несмотря на простоту вычисления, префиксные суммы являются полезным примитивом в некоторых алгоритмах, таких как сортировка подсчетом , ^{[1] [2],} и они формируют основу функции сканирования высшего порядка в функциональных языках программирования. Префиксные суммы также много изучались в параллельных алгоритмах , как в качестве тестовой задачи, которую нужно решить, так и в качестве полезного примитива для использования в качестве подпрограммы в других параллельных алгоритмах. ^{[3] [4] [5]}

Абстрактно, префиксная сумма требует только бинарного ассоциативного оператора ⊕ , что делает ее полезной для многих приложений, от вычисления хорошо разделенных парных разложений точек до обработки строк. ^{[6] [7]}

Математически операция взятия префиксных сумм может быть обобщена с конечных на бесконечные последовательности; в этом контексте префиксная сумма известна как частичная сумма ряда . Префиксное суммирование или частичное суммирование образуют линейные операторы на векторных пространствах конечных или бесконечных последовательностей; их обратные операторы являются операторами конечной разности .

Сканировать функцию высшего порядка

В терминах функционального программирования префиксная сумма может быть обобщена на любую бинарную операцию (не только на операцию сложения ); функция более высокого порядка, полученная в результате этого обобщения, называется сканированием , и она тесно связана с операцией сложения . И сканирование, и операция сложения применяют заданную бинарную операцию к одной и той же последовательности значений, но отличаются тем, что сканирование возвращает всю последовательность результатов бинарной операции, тогда как сложение возвращает только конечный результат. Например, последовательность факториальных чисел может быть сгенерирована сканированием натуральных чисел с использованием умножения вместо сложения:

Инклюзивное и эксклюзивное сканирование

Реализации сканирования на языке программирования и в библиотеках могут быть как инклюзивными , так и исключительными . Инклюзивное сканирование включает входные данные x _i при вычислении выходных данных y _i (т. е. ), а исключающее сканирование — нет (т. е. ). В последнем случае реализации либо оставляют y ₀ неопределенным, либо принимают отдельное значение " x ₋₁ ", которым задается сканирование. Любой тип сканирования может быть преобразован в другой: инклюзивное сканирование может быть преобразовано в исключительное сканирование путем сдвига массива, полученного при сканировании, вправо на один элемент и вставки значения идентичности слева от массива. И наоборот, исключающее сканирование может быть преобразовано в инклюзивное сканирование путем сдвига массива, полученного при сканировании, влево и вставки суммы последнего элемента сканирования и последнего элемента входного массива справа от массива. ^[8] ${\textstyle y_{i}=\bigoplus _{j=0}^{i}x_{j}}$ ${\textstyle y_{i}=\bigoplus _{j=0}^{i-1}x_{j}}$

В следующей таблице приведены примеры функций инклюзивного и эксклюзивного сканирования, предоставляемых несколькими языками программирования и библиотеками:

Модель параллельного программирования OpenMP на основе директив поддерживает как инклюзивное, так и эксклюзивное сканирование, начиная с версии 5.0.

Параллельные алгоритмы

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

Алгоритм 1: более короткий промежуток, более параллельный

Схемотехническое представление высокопараллельной 16-входовой параллельной префиксной суммы

Хилис и Стил представляют следующий алгоритм параллельной префиксной суммы: ^[9]

для  i <- 0 до пола (log 2 ( n )) выполнить  для  j <- 0 до n - 1 выполнить параллельно  если  j < 2 i  тогда  xя +1 
дж<- хя 
дж еще  хя +1 
дж<- хя 
дж+ хя 
дж - 2 я

В приведенном выше обозначении обозначается значение j -го элемента массива x на временном шаге i . ${\displaystyle x_{j}^{i}}$

С одним процессором этот алгоритм будет работать за время O ( n log n ) . Однако, если машина имеет по крайней мере n процессоров для параллельного выполнения внутреннего цикла, алгоритм в целом будет работать за время O (log n ) , количество итераций внешнего цикла.

Алгоритм 2: Эффективная работа

Схемотехническое представление эффективной 16-входовой параллельной префиксной суммы

Эффективную по работе параллельную префиксную сумму можно вычислить с помощью следующих шагов. ^{[3] [10] [11]}

1. Вычислите суммы последовательных пар элементов, в которых первый элемент пары имеет четный индекс: z ₀ = x ₀ + x ₁ , z ₁ = x ₂ + x ₃ и т. д.
2. Рекурсивно вычислить префиксную сумму w ₀ , w ₁ , w ₂ , ... последовательности z ₀ , z ₁ , z ₂ , ...
3. Выразите каждый член конечной последовательности y ₀ , y ₁ , y ₂ , ... как сумму до двух членов этих промежуточных последовательностей: y ₀ = x ₀ , y ₁ = z ₀ , y ₂ = z ₀ + x ₂ , y ₃ = w ₁ и т. д. После первого значения каждое последующее число y _i либо копируется с позиции, находящейся на половину дальше по последовательности w , либо представляет собой предыдущее значение, прибавленное к одному значению в последовательности x .

Если входная последовательность имеет n шагов, то рекурсия продолжается до глубины O (log n ) , что также является границей параллельного времени выполнения этого алгоритма. Количество шагов алгоритма равно O ( n ) , и он может быть реализован на параллельной машине с произвольным доступом с O ( n /log n ) процессорами без какого-либо асимптотического замедления путем назначения нескольких индексов каждому процессору в раундах алгоритма, для которых элементов больше, чем процессоров. ^[3]

Обсуждение

Каждый из предыдущих алгоритмов выполняется за время O (log n ) . Однако первый алгоритм занимает ровно log ₂ n шагов, тогда как последний требует 2 log ₂  n − 2 шагов. Для проиллюстрированных примеров с 16 входами алгоритм 1 является 12-сторонним параллельным (49 единиц работы, разделенных на промежуток 4), тогда как алгоритм 2 является только 4-сторонним параллельным (26 единиц работы, разделенных на промежуток 6). Однако алгоритм 2 эффективен по работе — он выполняет только постоянный множитель (2) от объема работы, требуемого последовательным алгоритмом — в то время как алгоритм 1 неэффективен по работе — он выполняет асимптотически больше работы (логарифмический множитель), чем требуется последовательно. Следовательно, алгоритм 1, вероятно, будет работать лучше, когда доступен обильный параллелизм, но алгоритм 2, вероятно, будет работать лучше, когда параллелизм более ограничен.

Параллельные алгоритмы для префиксных сумм часто можно обобщить для других операций сканирования на ассоциативных бинарных операциях , ^{[3] [4]} и их также можно эффективно вычислять на современном параллельном оборудовании, таком как графический процессор . ^[12] Идея создания на аппаратном уровне функционального блока, предназначенного для вычисления многопараметрической префиксной суммы, была запатентована Узи Вишкиным . ^[13]

Многие параллельные реализации следуют двухпроходной процедуре, где частичные суммы префиксов вычисляются в первом проходе на каждом процессорном блоке; префиксная сумма этих частичных сумм затем вычисляется и транслируется обратно в процессорные блоки для второго прохода, используя теперь известный префикс в качестве начального значения. Асимптотически этот метод занимает приблизительно две операции чтения и одну операцию записи на элемент.

Конкретные реализации алгоритмов префиксной суммы

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

Общая память: двухуровневый алгоритм

Следующий алгоритм предполагает модель машины с общей памятью ; все элементы обработки (PE) имеют доступ к одной и той же памяти. Версия этого алгоритма реализована в Multi-Core Standard Template Library (MCSTL), ^{[14] [15]} параллельной реализации стандартной библиотеки шаблонов C++ , которая предоставляет адаптированные версии для параллельных вычислений различных алгоритмов.

Для того чтобы одновременно вычислить сумму префикса по элементам данных с элементами обработки, данные делятся на блоки, каждый из которых содержит элементы (для простоты мы предполагаем, что делит ). Обратите внимание, что хотя алгоритм делит данные на блоки, только элементы обработки работают параллельно в один момент времени. ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle p+1}$ ${\displaystyle {\frac {n}{p+1}}}$ ${\displaystyle p+1}$ ${\displaystyle n}$ ${\displaystyle p+1}$ ${\displaystyle p}$

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

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

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

function prefix_sum ( elements ) { n := size ( elements ) p := количество обрабатываемых элементов prefix_sum : = [ 0. . .0 ] размера n do parallel i = 0 to p - 1 { // i : = индекс текущего PE от j = i * n / ( p + 1 ) до ( i + 1 ) * n / ( p + 1 ) - 1 do { // Это сохраняет только префиксную сумму локальных блоков store_prefix_sum_with_offset_in ( elements , 0 , prefix_sum ) } } x = 0 для i = 1 to p { // Последовательное накопление общей суммы блоков x += prefix_sum [ i * n / ( p + 1 ) - 1 ] // Построение префиксной суммы по первым p блокам prefix_sum [ i * n / ( p + 1 )] = x // Сохранение результатов для использования в качестве смещений во втором цикле } do parallel i = 1 to p { // i := индекс текущего PE от j = i * n / ( p + 1 ) до ( i + 1 ) * n / ( p + 1 ) - 1 do { offset := prefix_sum [ i * n / ( p + 1 )] // Вычислить сумму префикса, взяв сумму предыдущих блоков в качестве смещения                                                                                                                        store_prefix_sum_with_offset_in ( элементы , смещение , prefix_sum ) } } return prefix_sum }       

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

Распределенная память: алгоритм гиперкуба

Алгоритм суммы префиксов гиперкуба ^[16] хорошо адаптирован для платформ с распределенной памятью и работает с обменом сообщениями между процессорными элементами. Он предполагает, что в алгоритме участвует процессорных элементов (PE), количество которых равно количеству углов в -мерном гиперкубе . ${\displaystyle p=2^{d}}$ ${\displaystyle d}$

Различные гиперкубы для разного количества узлов

На протяжении всего алгоритма каждый PE рассматривается как угол в гипотетическом гиперкубе со знанием общей суммы префиксов , а также суммы префиксов всех элементов до него (в соответствии с упорядоченными индексами среди PE), оба в своем собственном гиперкубе. ${\displaystyle \sigma }$ ${\displaystyle x}$

• Алгоритм начинается с предположения, что каждый PE является единственным углом нульмерного гиперкуба и, следовательно , и равны локальной префиксной сумме его собственных элементов. ${\displaystyle \sigma }$ ${\displaystyle x}$
• Алгоритм продолжается путем объединения гиперкубов, которые являются смежными вдоль одного измерения. Во время каждого объединения происходит обмен и агрегация между двумя гиперкубами, что сохраняет инвариант, что все PE в углах этого нового гиперкуба хранят общую сумму префиксов этого нового объединенного гиперкуба в своей переменной . Однако только гиперкуб, содержащий PE с более высоким индексом, также добавляет это к своей локальной переменной , сохраняя инвариант, который хранит только значение суммы префиксов всех элементов в PE с индексами, меньшими или равными их собственному индексу. ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle x}$ ${\displaystyle x}$

В -мерном гиперкубе с PE в углах алгоритм должен быть повторен несколько раз, чтобы объединить нульмерные гиперкубы в одномерный -мерный гиперкуб. Предполагая дуплексную модель связи , где два соседних PE в разных гиперкубах могут обмениваться в обоих направлениях за один шаг связи, это означает запуски связи. ${\displaystyle d}$ ${\displaystyle 2^{d}}$ ${\displaystyle d}$ ${\displaystyle 2^{d}}$ ${\displaystyle d}$ ${\displaystyle \sigma }$ ${\displaystyle d=\log _{2}p}$

i : = Индекс собственного процессорного элемента ( PE ) m : = префиксная сумма локальных элементов этого PE d : = число измерений гиперкуба​​​​                        x = m ; // Инвариант: префиксная сумма до этого PE в текущем подкубе σ = m ; // Инвариант: префиксная сумма всех элементов в текущем подкубе      for ( k = 0 ; k <= d - 1 ; k ++ ) { y = σ @ PE ( i xor 2 ^ k ) // Получить общую сумму префиксов противоположного подкуба по измерению k σ = σ + y // Агрегировать сумму префиксов обоих подкубов                     if ( i & 2 ^ k ) { x = x + y // Агрегировать только сумму префикса из другого подкуба, если этот PE имеет более высокий индекс. } }           

Большие размеры сообщений: конвейерное двоичное дерево

Конвейерный алгоритм двоичного дерева ^[17] — еще один алгоритм для платформ с распределенной памятью, который особенно хорошо подходит для сообщений большого размера.

Как и алгоритм гиперкуба, он предполагает особую структуру связи. Элементы обработки (PE) гипотетически расположены в бинарном дереве (например, дереве Фибоначчи) с инфиксной нумерацией в соответствии с их индексом внутри PE. Связь на таком дереве всегда происходит между родительскими и дочерними узлами.

Инфиксная нумерация гарантирует, что для любого заданного PE _j индексы всех узлов, достижимых его левым поддеревом, меньше , а индексы всех узлов в правом поддереве больше . Индекс родителя больше любого из индексов в поддереве PE _{j , если PE j} является левым потомком, и меньше, если PE _j является правым потомком. Это позволяет сделать следующие рассуждения: ${\displaystyle \mathbb {[l...j-1]} }$ ${\displaystyle j}$ ${\displaystyle \mathbb {[j+1...r]} }$ ${\displaystyle j}$

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

• Локальная префиксная сумма левого поддерева должна быть агрегирована для вычисления локальной префиксной суммы PE _j . ${\displaystyle \mathbb {\oplus [l..j-1]} }$ ${\displaystyle \mathbb {\oplus [l..j]} }$
• Локальная префиксная сумма правого поддерева должна быть агрегирована для вычисления локальной префиксной суммы PE более высокого уровня _h , которые достигаются на пути, содержащем соединение левых дочерних узлов (что означает ). ${\displaystyle \mathbb {\oplus [j+1..r]} }$ ${\displaystyle h>j}$
• Общая сумма префиксов PE _j необходима для расчета общих сумм префиксов в правом поддереве (например, для узла с наивысшим индексом в поддереве). ${\displaystyle \mathbb {\oplus [0..j]} }$ ${\displaystyle \mathbb {\oplus [0..j..r]} }$
• Для вычисления общей суммы префикса PE _j необходимо включить общую сумму префикса первого узла более высокого порядка, который достигается через восходящий путь, включающий правое дочернее соединение. ${\displaystyle \mathbb {\oplus [0..l-1]} }$

Обратите внимание на различие между локальными для поддерева и общими префиксными суммами. Пункты два, три и четыре могут привести к мысли, что они образуют циклическую зависимость, но это не так. PE более низкого уровня могут потребовать общую сумму префикса PE более высокого уровня для расчета общей суммы префикса, но PE более высокого уровня требуют только локальные суммы префикса поддерева для расчета общей суммы префикса. Корневой узел как узел самого высокого уровня требует только локальную сумму префикса своего левого поддерева для расчета собственной суммы префикса. Каждый PE на пути от PE ₀ до корня PE требует только локальную сумму префикса своего левого поддерева для расчета собственной суммы префикса, тогда как каждый узел на пути от PE _{p-1 (последний PE) до корня} PE требует общую сумму префикса своего родителя для расчета собственной суммы префикса.

Это приводит к двухфазному алгоритму:

Восходящая фаза.
Распространение суммы локального префикса поддерева на его родительский элемент для каждого PE _j . ${\displaystyle \mathbb {\oplus [l..j..r]} }$

Нисходящая фаза
Распространение исключительной (исключительный PE _j , а также PE в его левом поддереве) общей суммы префиксов всех PE нижнего индекса, которые не включены в адресуемое поддерево PE _j, на PE нижнего уровня в левом дочернем поддереве PE _j . Распространение инклюзивной суммы префиксов на правое дочернее поддерево PE _j . ${\displaystyle \mathbb {\oplus [0..l-1]} }$ ${\displaystyle \mathbb {\oplus [0..j]} }$

Обратите внимание, что алгоритм выполняется параллельно на каждом PE, и PE будут блокироваться при получении до тех пор, пока их дочерние/родительские узлы не предоставят им пакеты.

k := количество пакетов в сообщении m PE m @ { left , right , parent , this } : = // Сообщения в разных PE                  х = м @ это    // Восходящая фаза - вычисление локальных префиксных сумм поддерева для j = 0 до k - 1 : // Конвейеризация: для каждого пакета сообщения, если hasLeftChild : блокировка получения m [ j ] @ left // Это заменяет локальный m[j] на полученный m[j] // Агрегируем инклюзивную локальную префиксную сумму из PE с более низким индексом x [ j ] = m [ j ] ⨁ x [ j ]                   если hasRightChild : блокировка получения m [ j ] @ right // Мы не агрегируем m[j] в локальную сумму префиксов, так как правые потомки являются PE с более высоким индексом отправить x [ j ] ⨁ m [ j ] родителю else : отправить x [ j ] родителю                  // Нисходящая фаза для j = 0 до k - 1 : m [ j ] @ this = 0         если hasParent : блокировка получения m [ j ] @ parent // Для левого потомка m[j] — это исключительная префиксная сумма родителей, для правого потомка — включающая префиксная сумма x [ j ] = m [ j ] ⨁ x [ j ] отправить m [ j ] налево // Общая префиксная сумма всех PE, меньших этого или любого PE в левом поддереве отправить x [ j ] направо // Общая префиксная сумма всех PE, меньших или равных этому PE                        

Конвейеризация

Если сообщение m длины n можно разделить на k пакетов и оператор ⨁ можно использовать для каждого соответствующего пакета сообщения отдельно, то возможна конвейеризация . ^[17]

Если алгоритм используется без конвейеризации, всегда есть только два уровня (отправляющие PE и принимающие PE) двоичного дерева в работе, пока все остальные PE ждут. Если есть p элементов обработки и используется сбалансированное двоичное дерево, дерево имеет уровни, длина пути от до составляет , поэтому что представляет собой максимальное количество непараллельных операций связи во время восходящей фазы, аналогично, связь на нисходящем пути также ограничена запусками. Предполагая, что время запуска связи и время побайтовой передачи , восходящая и нисходящая фазы ограничены в неконвейерном сценарии. ${\displaystyle \log _{2}p}$ ${\displaystyle PE_{0}}$ ${\displaystyle PE_{\mathbb {root} }}$ ${\displaystyle \log _{2}p-1}$ ${\displaystyle \log _{2}p-1}$ ${\displaystyle T_{\mathbb {start} }}$ ${\displaystyle T_{\mathbb {byte} }}$ ${\displaystyle (2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })}$

При разделении на k пакетов, каждый размером и отправке их отдельно, первый пакет все еще должен быть распространен как часть локальной суммы префиксов, и это произойдет снова для последнего пакета, если . Однако между ними все PE на пути могут работать параллельно, и каждая третья операция связи (получить левый, получить правый, отправить родительскому элементу) отправляет пакет на следующий уровень, так что одна фаза может быть завершена в операциях связи, и обе фазы вместе требуют , что благоприятно для больших размеров сообщений n . ${\displaystyle {\tfrac {n}{k}}}$ ${\displaystyle (\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)}$ ${\displaystyle PE_{\mathbb {root} }}$ ${\displaystyle k>\log _{2}p}$ ${\displaystyle 2\log _{2}p-1+3(k-1)}$ ${\displaystyle (4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)}$

Алгоритм можно дополнительно оптимизировать, используя полнодуплексную или телефонную модель связи и накладывая восходящую и нисходящую фазы. ^[17]

Структуры данных

Когда набор данных может обновляться динамически, он может храниться в структуре данных дерева Фенвика . Эта структура позволяет как искать любое индивидуальное значение суммы префикса, так и изменять любое значение массива за логарифмическое время на операцию. ^[18] Однако в более ранней статье 1982 года ^[19] представлена ​​структура данных, называемая деревом частичных сумм (см. раздел 5.1), которая, по-видимому, перекрывает деревья Фенвика; в 1982 году термин «префиксная сумма» еще не был так распространен, как сегодня.

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

Приложения

Сортировка подсчетом — это алгоритм сортировки целых чисел , который использует префиксную сумму гистограммы частот ключей для вычисления позиции каждого ключа в отсортированном выходном массиве. Он работает за линейное время для целочисленных ключей, которые меньше количества элементов, и часто используется как часть сортировки по основанию , быстрого алгоритма сортировки целых чисел, которые менее ограничены по величине. ^[1]

Ранжирование списка , проблема преобразования связанного списка в массив , представляющий ту же последовательность элементов, может рассматриваться как вычисление префиксной суммы последовательности 1, 1, 1, ... и последующее сопоставление каждого элемента с позицией массива, заданной его значением префиксной суммы; путем объединения ранжирования списка, префиксных сумм и циклов Эйлера многие важные проблемы на деревьях могут быть решены с помощью эффективных параллельных алгоритмов. ^[4]

Раннее применение алгоритмов параллельной префиксной суммы было в разработке двоичных сумматоров , булевых схем, которые могут складывать два n -битных двоичных числа. В этом приложении последовательность битов переноса сложения может быть представлена ​​как операция сканирования последовательности пар входных битов, используя функцию большинства для объединения предыдущего переноса с этими двумя битами. Затем каждый бит выходного числа может быть найден как исключающее или двух входных битов с соответствующим битом переноса. Используя схему, которая выполняет операции алгоритма параллельной префиксной суммы, можно разработать сумматор, который использует O ( n ) логических вентилей и O (log n ) временных шагов. ^{[3] [10] [11]}

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

В докторской диссертации Гая Блеллоха ^[22] параллельные префиксные операции являются частью формализации модели параллелизма данных , предоставляемой такими машинами, как Connection Machine . Connection Machine CM-1 и CM-2 предоставляли гиперкубическую сеть, на которой мог быть реализован Алгоритм 1 выше, тогда как CM-5 предоставлял выделенную сеть для реализации Алгоритма 2. ^[23]

При построении кодов Грея , последовательностей двоичных значений со свойством, что последовательные значения последовательности отличаются друг от друга в одной битовой позиции, число n может быть преобразовано в значение кода Грея в позиции n последовательности, просто взяв исключающее ИЛИ n и n / 2 (число, образованное сдвигом n вправо на одну битовую позицию). Обратная операция, декодирование значения Грея x в двоичное число, более сложна, но может быть выражена как префиксная сумма битов  x , где каждая операция суммирования в префиксной сумме выполняется по модулю два. Префиксная сумма этого типа может быть эффективно выполнена с использованием побитовых булевых операций, доступных на современных компьютерах, путем вычисления исключающего ИЛИ x с каждым из чисел, образованных сдвигом x влево на количество битов, которое является степенью двух. [ ^24]

Параллельный префикс (использующий умножение в качестве базовой ассоциативной операции) также может использоваться для построения быстрых алгоритмов для параллельной полиномиальной интерполяции . В частности, его можно использовать для вычисления коэффициентов разделенной разности формы Ньютона интерполяционного полинома. ^[25] Этот подход на основе префикса также можно использовать для получения обобщенных разделенных разностей для (конфлюэнтной) интерполяции Эрмита , а также для параллельных алгоритмов для систем Вандермонда . ^[26]

Префиксная сумма используется для балансировки нагрузки как малозатратный алгоритм распределения работы между несколькими процессорами, где главной целью является достижение равного объема работы на каждом процессоре. Алгоритмы используют массив весов, представляющих объем работы, требуемый для каждого элемента. После вычисления префиксной суммы рабочий элемент i отправляется на обработку в процессорный блок с номером . ^[27] Графически это соответствует операции, в которой объем работы в каждом элементе представлен длиной линейного сегмента, все сегменты последовательно размещаются на линии, а результат разрезается на количество частей, соответствующее количеству процессоров. ^[28] ${\displaystyle [{\frac {prefixSumValue_{i}}{{totalWork}/{numberOfProcessors}}}]}$

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

• Универсальные вычисления на графических процессорах
• Сегментированное сканирование
• Таблица суммированной площади

Ссылки

1. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "8.2 Сортировка подсчетом", Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill , стр. 168–170, ISBN 0-262-03293-7.
2. Коул, Ричард; Вишкин, Узи (1986), «Детерминированное подбрасывание монеты с применением к оптимальному параллельному ранжированию списков», Информация и управление , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7
3. Ladner, RE; Fischer, MJ (1980), "Parallel Prefix Computation", Journal of the ACM , 27 (4): 831–838, CiteSeerX 10.1.1.106.6247 , doi :10.1145/322217.322232, MR  0594702, S2CID  207568668 .
4. Tarjan, Robert E. ; Vishkin, Uzi (1985), «Эффективный параллельный алгоритм двусвязности», SIAM Journal on Computing , 14 (4): 862–874, CiteSeerX 10.1.1.465.8898 , doi :10.1137/0214061 .
5. Лакшмиварахан, С.; Дхалл, С.К. (1994), Параллелизм в проблеме префиксов , Oxford University Press , ISBN 0-19508849-2.
6. Blelloch, Guy (2011), Префиксные суммы и их применение (конспект лекций) (PDF) , Университет Карнеги-Меллона.
7. Каллахан, Пол; Косараджу, С. Рао (1995), «Разложение многомерных точечных множеств с приложениями к полям k-ближайших соседей и n-тел», Журнал ACM , 42 (1): 67–90, doi : 10.1145/200836.200853 , S2CID  1818562.
8. "GPU Gems 3".
9. Хиллис, В. Дэниел; Стил, младший, Гай Л. (декабрь 1986 г.). «Алгоритмы параллельной обработки данных». Сообщения ACM . 29 (12): 1170–1183. doi : 10.1145/7902.7903 .
10. Офман, Ю. (1962), Об алгоритмической сложности строительных работ, Доклады Академии наук СССР , 145 (1): 48–51, МР  0168423Английский перевод, «Об алгоритмической сложности дискретных функций», Доклады АН СССР, 7 : 589–591, 1963.
11. Храпченко, В.М. (1967), "Асимптотическая оценка времени сложения параллельного сумматора", Проблемы кибернетики. , 19 : 107–122. Английский перевод в Syst. Theory Res. 19 ; 105–122, 1970.
12. Сенгупта, Шубхабрата; Харрис, Марк; Чжан, Яо; Оуэнс, Джон Д. (2007). Примитивы сканирования для вычислений на графических процессорах. Труды 22-го симпозиума ACM SIGGRAPH/EUROGRAPHICS по графическому оборудованию. С. 97–106. Архивировано из оригинала 03.09.2014 . Получено 29.11.2007 .
13. Вышкин, Узи (2003). Префиксные суммы и их применение. Патент США 6,542,918.
14. Синглэр, Йоханнес. "MCSTL: The Multi-Core Standard Template Library" . Получено 29.03.2019 .
15. Синглэр, Йоханнес; Сандерс, Питер; Путце, Феликс (2007). "MCSTL: The Multi-core Standard Template Library". Euro-Par 2007 Parallel Processing . Lecture Notes in Computer Science. Vol. 4641. pp. 682–694. doi :10.1007/978-3-540-74466-5_72. ISBN 978-3-540-74465-8. ISSN  0302-9743.
16. Анант Грама; Випин Кумар; Аншул Гупта (2003). Введение в параллельные вычисления. Аддисон-Уэсли. стр. 85, 86. ISBN. 978-0-201-64865-2.
17. Сандерс, Питер; Трефф, Йеспер Ларссон (2006). "Параллельные префиксные (сканирующие) алгоритмы для MPI". Последние достижения в области параллельных виртуальных машин и интерфейса передачи сообщений . Конспект лекций по информатике. Том 4192. С. 49–57. doi :10.1007/11846802_15. ISBN 978-3-540-39110-4. ISSN  0302-9743.
18. Фенвик, Питер М. (1994), «Новая структура данных для кумулятивных таблиц частот», Программное обеспечение: Практика и опыт , 24 (3): 327–336, doi :10.1002/spe.4380240306, S2CID  7519761
19. Шилоах, Йосси; Вишкин, Узи (1982b), « Параллельный алгоритм максимального потока O ( n ²  log  n )», Журнал алгоритмов , 3 (2): 128–146, doi :10.1016/0196-6774(82)90013-X
20. Szeliski, Richard (2010), «Таблица суммированных площадей (интегральное изображение)», Computer Vision: Algorithms and Applications, Texts in Computer Science, Springer, стр. 106–107, ISBN 9781848829350.
21. Вишкин, Узи (1983), «Реализация одновременного доступа к адресам памяти в моделях, которые это запрещают», Журнал алгоритмов , 4 (1): 45–50, doi :10.1016/0196-6774(83)90033-0, MR  0689265.
22. Blelloch, Guy E. (1990). Векторные модели для параллельных вычислений данных . Кембридж, Массачусетс: MIT Press. ISBN 026202313X. OCLC  21761743.
23. Leiserson, Charles E. ; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Hillis, W. Daniel ; Kuszmaul, Bradley C.; St. Pierre, Margaret A. (15 марта 1996 г.). «Сетевая архитектура машины соединений CM-5». Журнал параллельных и распределенных вычислений . 33 (2): 145–158. doi :10.1006/jpdc.1996.0033. ISSN  0743-7315.
24. Уоррен, Генри С. (2003), Hacker's Delight, Addison-Wesley, стр. 236, ISBN 978-0-201-91465-8.
25. Эгесиоглу, О.; Галлопулос, Э.; Коч, К. (1990), «Параллельный метод для быстрой и практичной интерполяции Ньютона высокого порядка», BIT Computer Science and Numerical Mathematics , 30 (2): 268–288, doi :10.1007/BF02017348, S2CID  9607531.
26. Эгесиоглу, О.; Галлопулос, Э.; Коч, К. (1989), «Быстрое вычисление разделенных разностей и параллельная интерполяция Эрмита», Журнал сложности , 5 (4): 417–437, doi :10.1016/0885-064X(89)90018-6
27. Беккер, Аарон; Чжэн, Гэнбин; Кале, Лакшмикант В. (2011). «Балансировка нагрузки, распределенная память». Энциклопедия параллельных вычислений . Бостон, Массачусетс: Springer US. стр. 1046. doi :10.1007/978-0-387-09766-4_504. ISBN 978-0-387-09765-7.
28. Сандерс, Питер; Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (2019). «Балансировка нагрузки» (PDF) . Последовательные и параллельные алгоритмы и структуры данных . Cham: Springer International Publishing. стр. 419–434. doi :10.1007/978-3-030-25209-0_14. ISBN 978-3-030-25208-3.

Внешние ссылки

• Вайсштейн, Эрик В. «Накопительная сумма». MathWorld .