CUDA計算積分數列的方法

使用平行運算計算總和，還可以理解。但要算積分，不符合平行運算的方法，這下要如何?
積分數列的數學問題是這樣的：
數列 X=[ a0 a1 a2 ... aN ]
要算出 Y=[ a0 a0+a1 a0+a1+a2 ... a0+a1+a2+...+aN ]

其實有注意到的人會發現，為何這個問題Bee要用平行運算。因為這就是圖像積分法(integral image)的基本運算。因為要移進GPGPU來做，問題就來了。
因為每一個數列元素要等上一個元素的值出現才能算，可是平行運算要沒有相關才能用，這下子有解嗎?
找了許多文章，一張圖解了這個問題。

果然還是因為沒有收集平行運算的演算法，才會不知道往那裡去找。
找到了之後，發現這個動作可以做以下的計算：
Radix sort
Quicksort
String comparison
Lexical analysis
Stream compaction
Sparse matrices
Polynomial evaluation
Solving recurrences
Tree operations
Histograms
看來是很重要的演算法，值得好好去了解。