累積和

ウィキペディア

累積和

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/23 10:14 UTC 版)

累積和（るいせきわ、英: prefix sum, cumulative sum, scan）とは、計算機科学において、数列 ${\displaystyle x_{0},x_{1},x_{2},\dots }$

並列性の高い16入力の並列累積和の回路表現

HillisとSteeleは、以下の並列累積和アルゴリズムを提案している。^[12]

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 ${\displaystyle \oplus }$
ワーク効率が高い16入力の並列累積和の回路表現
ワーク効率の良い並列累積和は、以下の手順で計算できる。[5][14][15]

隣接する要素の和を計算する（ペアの先頭要素のインデックスが偶数であるものを対象とする）。
例：${\displaystyle z_{0}=x_{0}\oplus x_{1},z_{1}=x_{2}\oplus x_{3},\dots }$