累積和

ウィキペディア

累積和

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/09/27 09:42 UTC 版)

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

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

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

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 
     $\oplus$
    

     ワーク効率が高い16入力の並列累積和の回路表現
    
ワーク効率の良い並列累積和は、以下の手順で計算できる。


    

     
隣接する要素の和を計算する（ペアの先頭要素のインデックスが偶数であるものを対象とする）。

      

       
例：
          $z_{0}=x_{0}\oplus x_{1},z_{1}=x_{2}\oplus x_{3},\dots$
      

     
ステップ1で得た数列 
        $z_{0},z_{1},z_{2},\dots$ に対して、再帰的に累積和を計算する。

      

       
結果として、新たな数列 
          $w_{0},w_{1},w_{2},\dots$ を得る。
      

     
最終的な累積和 
        $y_{0},y_{1},y_{2},\dots$ を、中間数列の値を用いて求める。

      

       
具体的には、各 
          $y_{i}$ は、これまでに計算された中間数列の要素の和で表される。

       
例：

        

         

            $y_{0}=x_{0}$
 
         

            $y_{1}=z_{0}$
 
         

            $y_{2}=z_{0}\oplus x_{2}$
 
         

            $y_{3}=w_{1}$
        

       
最初の値 
          $y_{0}$ を決めた後、それ以降の各 
          $y_{i}$ は、数列 
          $w$ の半分の位置にある値をコピーするか、直前の値に数列 
          $x$ の一部の値を加えることで求める。
      
    
入力数列の長さを 
       $n$ とすると、このアルゴリズムの再帰の深さは 
       $O(\log n)$ となる。したがって、並列実行時の計算時間も 
       $O(\log n)$ に抑えられる。  
このアルゴリズムの総ステップ数は 
       $O(n)$ であり、
       $O(n/\log n)$ 個のプロセッサを持つ並列ランダムアクセス機械（PRAM）上で、非対称的な遅延なしに実装可能である。これは、プロセッサの数よりも要素数が多い段階では、1つのプロセッサが複数のインデックスを処理するように割り当てることで実現される。


    
     
より一般的なfoldやscanに適用する方法
    
本項では、要素 
       $\oplus$ 要素（Haskellの表記では型a -> a -> a）として書いているが、関数型プログラミング言語では、


    

     
初期状態（型b）

     
f(状態, 要素) = 次の状態（型b -> a -> b）
    
と考えることにより、foldやscanで逐次処理を表現している。foldは最終状態（型b）で、scanは状態遷移列（型[b]）である。
ここで、結合法則を満たす


    

     
状態 
        $\oplus$ 状態 = 結合した状態（型b -> b -> b）
    
が存在すると、


    

     
まず、f(状態, 要素) は f(初期状態, 要素) でしか計算しないので、要素から f(初期状態, 要素) へのmap変換を行う。

     
その上で、状態 
        $\oplus$ 状態 -> 結合状態を使用すると、上記の並列アルゴリズムが適用できる。
    
これにより、逐次処理のfoldやscanで表現していたものに対して、並列アルゴリズムが使えるようになる。
具体例として、指数移動平均 
       $s_{t}=(1-\alpha )s_{t-1}+\alpha x_{t},\ s_{0}=0$ を考える。要素は 
       $x_{t}$ だが、状態を (指数移動平均の最後の値, 指数移動平均の長さ) のタプルとすると下記変換式により並列計算ができる。


    

     
初期状態 = 
        $(0,0)$

     
f(初期状態 
        $(0,0)$, 要素 
        $x_{t}$) = 
        $(\alpha x_{t},1)$

     
状態 
        $(s_{t},l_{t})$ 
        $\oplus$ 状態 
        $(s_{u},l_{u})$ = 結合状態 
        $((1-\alpha )^{l_{u}}s_{t}+s_{u},l_{t}+l_{u})$
    
これをNVIDIA CUDAのThrust(C++)で実装する。要素数nが十分大きく、二項演算子の計算量が小さい場合はinclusive_scanはメモリコピーの速度で動くが、要素から状態への並列map、状態の並列scan、状態から要素への並列mapが必要で、単純に実装すると3回分のメモリコピーが発生するが、Thrustではtransform_iteratorを使用すると1回分のメモリコピーにまとめることができるので、それを使用している。


    

     
#include <thrust/device_vector.h>
#include <thrust/iterator/transform_output_iterator.h>

struct State { float v; int len; };

struct toState { // 要素→状態
    const float alpha;
    __device__ State operator()(const float x) const { return State{alpha * x, 1}; }
};
struct toElement { // 状態→要素
    __device__ float operator()(const State &s) const { return s.v; }
};
struct plusStates { // 状態＋状態
    const float alpha;
    __device__ State operator()(const State &a, const State &b) const {
        return State{std::pow(1 - alpha, (float) b.len) * a.v + b.v, a.len + b.len};
    }
};

int main() {
    const float alpha = 0.2f;
    thrust::device_vector<float> input = {3, 1, 4, 1, 5, 9, 2, 6};
    thrust::device_vector<float> output(input.size());

    // 指数移動平均の計算
    thrust::inclusive_scan(
        thrust::make_transform_iterator(input.begin(), toState{alpha}),
        thrust::make_transform_iterator(input.end(), toState{alpha}),
        thrust::make_transform_output_iterator(output.begin(), toElement{}),
        plusStates{alpha}
    );

    // 計算結果の出力
    for (float x: output) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}