В информатике префиксная сумма, кумулятивная сумма, инклюзивное сканирование или просто сканирование последовательности чисел x0, x1, x2, … называется последовательность чисел y0, y1, y2, …, являющаяся префиксной суммой от входной последовательности:

…

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

{| class="wikitable" !входные числа | 1 | 2 | 3 | 4 | 5 | 6 |… |- !префиксная сумма | 1 | 3 | 6 |10 |15 |21 |…

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

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

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

Сканирование функции высшего порядка В терминах функционального программирования префиксная сумма может быть обобщена на любую двоичную операцию (не только операцию сложения); функция более высокого порядка, полученная в результате этого обобщения, называется сканированием, и она тесно связана с операцией свертки. Обе операции сканирования и свертки применяют данную двоичную операцию к одной и той же последовательности значений, но отличаются тем, что сканирование возвращает всю последовательность результатов двоичной операции, тогда как свертка возвращает только конечный результат. Например, последовательность факториальных чисел может быть сгенерирована путем сканирования натуральных чисел с использованием умножения вместо сложения: {| class="wikitable" |- !входные числа |  1 ||  2 ||  3 ||  4 ||   5 ||   6 || … |- !префиксные значения |  1 ||  2 ||  6 || 24 || 120 || 720 || …

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

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

{| class="wikitable" style="text-align: left;" |- !Языки/библиотеки !Инклюзивное сканирование !Эксклюзивное сканирование |- |Haskell |scanl1 |scanl |- |MPI |MPI_Scan |MPI_Exscan |- |C++ |std::inclusive_scan |std::exclusive_scan |- |Scala |scan

|Rust |scan

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

Алгоритм 1: меньшая глубина, большая предрасположенность к распараллеливанию

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

for to do for to do in parallel if then

else

Обозначение означает значение -го элемента массива на шаге .

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

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

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

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

Если входная последовательность имеет размер , то рекурсия продолжается до глубины , которая также ограничена временем параллельного выполнения этого алгоритма. Количество операций алгоритма равно , и их можно реализовать на абстрактной параллельной ЭВМ с общей памятью (PRAM) с количеством процессоров без какого-либо асимптотического замедления путем назначения нескольких индексов каждому процессору в вариантах алгоритма, для которых больше элементов, чем процессоров.

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

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

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

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

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

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

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

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

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

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 := индекс текущего PE from j = i * n / (p+1) to (i+1) * n / (p+1) - 1 do { // Здесь хранится префиксная сумма локальных блоков store_prefix_sum_with_offset_in(elements, 0, prefix_sum)

x = 0

for 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 from j = i * n / (p+1) to (i+1) * n / (p+1) - 1 do { offset := prefix_sum[i * n / (p+1)] // Рассчитывание префиксной суммы в качестве смещения суммы предыдущих блоков store_prefix_sum_with_offset_in(elements, offset, prefix_sum)

return prefix_sum }

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

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

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

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

i := Index of own processor element (PE) m := prefix sum of local elements of this PE