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

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

у ₀ = х ₀

у ₁ = х ₀ + х ₁

у ₂ = х ₀ + х ₁ + х ₂

...

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

ввод чисел	1	2	3	4	5	6	...
префиксные суммы	1	3	6	10	15	21	...

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

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

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

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

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

ввод чисел	1	2	3	4	5	6	...
префиксные продукты	1	2	6	24	120	720	...

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

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

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

Язык/библиотека	Инклюзивное сканирование	Эксклюзивное сканирование
АПЛ	+\
С++	std::inclusive_scan	std::exclusive_scan
Хаскелл	scanl1	scanl
HPF	sum_prefix	sum_prefix(..., exclusive=.true.)
Котлин	scan
ИМБ	MPI_Scan	MPI_Exscan
Ржавчина	scan
Скала	scan

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

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

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

Алгоритм 1: короче пролет, больше параллельности

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

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

for i <- 0 to floor(log2(n)) do
    for j <- 0 to n - 1 do in parallel
        if j < 2i then
            xi+1
j <- xi
j
        else
            xi+1
j <- xi
j + xi
j - 2i

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

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

Алгоритм 2: Эффективный

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

Эффективную сумму параллельных префиксов можно вычислить с помощью следующих шагов.

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 ) процессорами без какого-либо асимптотического замедления путем назначения нескольких индексов каждому процессору в раундах алгоритма для в которых элементов больше, чем процессоров.

Обсуждение

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

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

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

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

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

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

Следующий алгоритм предполагает модель машины с общей памятью ; все обрабатывающие элементы (PE) имеют доступ к одной и той же памяти. Версия этого алгоритма реализована в стандартной библиотеке многоядерных шаблонов (MCSTL). параллельная реализация стандартной библиотеки шаблонов C++ , которая предоставляет адаптированные версии для параллельных вычислений различных алгоритмов.

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

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

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

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

function prefix_sum(elements) {
    n := size(elements)
    p := number of processing elements
    prefix_sum := [0...0] of size n
    
    do parallel i = 0 to p-1 {
        // i := index of current PE
        from j = i * n / (p+1) to (i+1) * n / (p+1) - 1 do {
            // This only stores the prefix sum of the local blocks
            store_prefix_sum_with_offset_in(elements, 0, prefix_sum)
        }
    }
    
    x = 0
    
    for i = 1 to p {                        // Serial accumulation of total sum of blocks 
        x +=  prefix_sum[i * n / (p+1) - 1] // Build the prefix sum over the first p blocks
        prefix_sum[i * n / (p+1)] = x       // Save the results to be used as offsets in second sweep
    }
    
    do parallel i = 1 to p {
        // i := index of current PE
        from j = i * n / (p+1) to (i+1) * n / (p+1) - 1 do {
            offset := prefix_sum[i * n / (p+1)]
            // Calculate the prefix sum taking the sum of preceding blocks as offset
            store_prefix_sum_with_offset_in(elements, offset, prefix_sum)
        }
    }
    
    return prefix_sum
}

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

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

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

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

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

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

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

i := Index of own processor element (PE)
m := prefix sum of local elements of this PE
d := number of dimensions of the hyper cube

x = m;     // Invariant: The prefix sum up to this PE in the current sub cube
σ = m;     // Invariant: The prefix sum of all elements in the current sub cube

for (k=0; k <= d-1; k++) {
    y = σ @ PE(i xor 2^k)  // Get the total prefix sum of the opposing sub cube along dimension k
    σ = σ + y              // Aggregate the prefix sum of both sub cubes

    if (i & 2^k) {
        x = x + y  // Only aggregate the prefix sum from the other sub cube, if this PE is the higher index one.
    }
}

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

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

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

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

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

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

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

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

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

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

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

k := number of packets in a message m of a PE
m @ {left, right, parent, this} := // Messages at the different PEs

x = m @ this

// Upward phase - Calculate subtree local prefix sums
for j=0 to k-1: // Pipelining: For each packet of a message
    if hasLeftChild:
        blocking receive m[j] @ left // This replaces the local m[j] with the received m[j]
        // Aggregate inclusive local prefix sum from lower index PEs
        x[j] = m[j] ⨁ x[j]

    if hasRightChild:
        blocking receive m[j] @ right
        // We do not aggregate m[j] into the local prefix sum, since the right children are higher index PEs
        send x[j] ⨁ m[j] to parent
    else:
        send x[j] to parent

// Downward phase
for j=0 to k-1:
    m[j] @ this = 0

    if hasParent:
        blocking receive m[j] @ parent
        // For a left child m[j] is the parents exclusive prefix sum, for a right child the inclusive prefix sum
        x[j] = m[j] ⨁ x[j] 
    
    send m[j] to left  // The total prefix sum of all PE's smaller than this or any PE in the left subtree
    send x[j] to right // The total prefix sum of all PE's smaller or equal than this PE

Конвейерная обработка

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

См. также

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

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

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