接頭辞の合計

コンピュータサイエンスにおいて、数値のシーケンス $x$ $0$ $、$ $x$ $1$ $、$ $x$ $2$ $、 ...$ の接頭辞和、累積和、包括的スキャン、または単にスキャンとは、入力シーケンスの接頭辞（累積合計）の合計である、別の数値のシーケンス $y$ $0$ $、$ $y$ $1$ $、$ $y$ $2$ $、 ...の$ ことです。

y 0 = x 0

y 1 = x 0 + x 1

y 2 = x 0 + x 1 + x 2

...

例えば、自然数の接頭辞和は三角数である。

プレフィックス和は、逐次計算モデルでは、式 $y i = y i - 1 + x i$ を使用して各出力値を順序通りに計算することで簡単に計算できます。しかし、計算が容易であるにもかかわらず、プレフィックス和は、カウントソートなどの特定のアルゴリズムで有用なプリミティブであり、^{[ 1 ]}^{[ 2 ]}関数型プログラミング言語のscan高階関数の基礎を形成します。プレフィックス和は、並列アルゴリズムでも、解決すべきテスト問題として、また他の並列アルゴリズムのサブルーチンとして使用できる有用なプリミティブとして、広く研究されています。^[³^]^[⁴^]^[⁵^]

抽象的に言えば、接頭辞和は二項結合演算子⊕のみを必要とするため、点の十分に分離されたペア分解の計算から文字列処理まで、多くのアプリケーションで役立ちます。^{[ 6 ]}^{[ 7 ]}

数学的には、接頭辞和をとる演算は有限数列から無限数列へと一般化できます。その場合、接頭辞和は数列の部分和として知られています。接頭辞和または部分和は、有限数列または無限数列のベクトル空間上の線形演算子を形成し、その逆演算子は有限差分演算子です。

スキャン高次関数

In functional programming terms, the prefix sum may be generalized to any binary operation (not just the addition operation); the higher order function resulting from this generalization is called a scan, and it is closely related to the fold operation. Both the scan and the fold operations apply the given binary operation to the same sequence of values, but differ in that the scan returns the whole sequence of results from the binary operation, whereas the fold returns only the final result. For instance, the sequence of factorial numbers may be generated by a scan of the natural numbers using multiplication instead of addition:

Inclusive and exclusive scans

Programming language and library implementations of scan may be either inclusive or exclusive. An inclusive scan includes input $x i$ when computing output $y i$ (i.e., ${\textstyle y_{i}=\bigoplus _{j=0}^{i}x_{j}}$ ) while an exclusive scan does not (i.e., ${\textstyle y_{i}=\bigoplus _{j=0}^{i-1}x_{j}}$ ). In the latter case, implementations either leave $y 0$ undefined or accept a separate " $x -1$ " value with which to seed the scan. Either type of scan can be transformed into the other: an inclusive scan can be transformed into an exclusive scan by shifting the array produced by the scan right by one element and inserting the identity value at the left of the array. Conversely, an exclusive scan be transformed into an inclusive scan by shifting the array produced by the scan left and inserting the sum of the last element of the scan and the last element of the input array at the right of the array.^[8]

The following table lists examples of the inclusive and exclusive scan functions provided by a few programming languages and libraries:

The directive-based OpenMP parallel programming model supports both inclusive and exclusive scan support beginning with Version 5.0.

Parallel algorithms

There are two key algorithms for computing a prefix sum in parallel. The first offers a shorter span and more parallelism but is not work-efficient. The second is work-efficient but requires double the span and offers less parallelism. These are presented in turn below.

Algorithm 1: Shorter span, more parallel

HillisとSteeleは、以下の並列プレフィックス和アルゴリズムを提示している。^{[ 9 ]}

i <- 0 から log 2 ₍ n )まで実行し、 j <- 0 からn - 1まで並列に実行します。j < 2 ⁱの場合、x i ⁺¹^j_< - x ⁱ_jとなります。そうでない場合、 x ⁱ⁺¹_j <- x ⁱ_j + x ⁱ_j_{- 2}_{^{iとなります。}}

上記では、表記法 $x_{j}^{i}$ $は、タイムステップi$ における配列 $xの$ $j$ 番目の要素の値を意味します。

単一のプロセッサでは、このアルゴリズムは $O (n log n)$ 時間で実行されます。^{[ 10 ]}ただし、マシンに少なくとも $n 個の$ プロセッサがあり、内側のループを並列に実行できる場合、アルゴリズム全体は、外側のループの反復回数である $O (log n)時間で実行されます。$

アルゴリズム2：作業効率

作業効率の良い並列プレフィックス和は、以下の手順で計算できます。^{[ 3 ]}^{[ 11 ]}^{[ 12 ]}

$連続する項目のペアの合計を計算します。ただし、$ ペアの最初の項目は偶数インデックスを持ちます。z $0 = x 0 + x 1$ 、 $z 1 = x 2 + x 3$ など。
$数列z$ $0$ $,$ $z$ $1$ $,$ $z$ $2$ $, ...$ の接頭辞和 $w 0$ $,$ $w$ $1$ $,$ $w$ $2$ $, ...$ を再帰的に計算します。
$最終数列y 0 、 y 1 、 y 2 、 ...$ の各項を、これらの中間数列の最大 2 つの項の和として表します。 $y 0 = x 0$ 、 $y 1 = z 0$ 、 $y 2 = z 0 + x 2$ 、 $y 3 = w 1$ など。最初の値の後、各連続する数値 $y i$ $は、 w$ 数列の半分の位置からコピーされるか、または前の値に $x$ 数列の 1 つの値を加えたものです。

入力シーケンスが $n$ ステップの場合、再帰は $O (log n)$ の深さまで継続し、これはこのアルゴリズムの並列実行時間の上限でもあります。アルゴリズムのステップ数は $O (n)$ であり、プロセッサ数よりも要素数が多いアルゴリズムのラウンドで各プロセッサに複数のインデックスを割り当てることにより、 $O$ $($ $n$ $/log$ $n$ $)個のプロセッサを持つ$ 並列ランダムアクセスマシン上で漸近的な速度低下なしに実装できます。^[³^]

議論

前述の各アルゴリズムは、 $O (log n)の$ 時間で実行されます。ただし、前者は正確に $log 2 n$ ステップかかるのに対し、後者は $2 log 2 n - 2$ ステップかかります。図示した16個の入力の例では、アルゴリズム 1は12方向並列（49単位の作業が4のスパンで分割）であるのに対し、アルゴリズム 2は4方向並列（26単位の作業が6のスパンで分割）です。しかし、アルゴリズム 2は作業効率が高く、逐次アルゴリズムに必要な作業量の定数倍（2）しか実行しません。一方、アルゴリズム 1は作業効率が低く、逐次処理に必要な作業量よりも漸近的に多くの作業（対数倍）を実行します。したがって、並列処理が豊富な場合はアルゴリズム1の方がパフォーマンスが良い可能性が高く、並列処理が限られている場合はアルゴリズム2の方がパフォーマンスが良い可能性が高いです。

接頭辞和の並列アルゴリズムは、結合法則を満たす二項演算の他のスキャン操作に一般化できる場合が多く、^{[ 3 ]}^{[ 4 ]}また、 GPUなどの最新の並列ハードウェア上で効率的に計算することもできます。^{[ 13 ]}多パラメータ接頭辞和の計算専用の機能ユニットをハードウェアに構築するというアイデアは、Uzi Vishkinによって特許取得されました。^{[ 14 ]}

多くの並列実装では、2段階の手順が採用されています。まず、各処理ユニットで最初の処理において部分的なプレフィックス和が計算されます。次に、これらの部分和のプレフィックス和が計算され、既知のプレフィックスを初期値として、2回目の処理のために処理ユニットにブロードキャストされます。漸近的には、この方法は項目ごとに約2回の読み出し操作と1回の書き込み操作を必要とします。

接頭辞和アルゴリズムの具体的な実装例

並列プレフィックス和アルゴリズムの実装は、他の並列アルゴリズムと同様に、プラットフォームの並列化アーキテクチャを考慮する必要があります。具体的には、共有メモリ上で動作するプラットフォームに適したアルゴリズムと、プロセス間通信の唯一の手段としてメッセージパッシングを使用する分散メモリを使用するプラットフォームに適したアルゴリズムが複数存在します。

共有メモリ：2段階アルゴリズム

以下のアルゴリズムは共有メモリマシンモデルを前提としており、すべての処理要素（PE）が同じメモリにアクセスできます。このアルゴリズムのバージョンは、マルチコア標準テンプレートライブラリ（MCSTL）^{[ 15 ]}^{[ 16 ]}に実装されています。MCSTLは、さまざまなアルゴリズムの並列計算用に調整されたバージョンを提供するC++標準テンプレートライブラリの並列実装です。

$n個の$ データ要素に対するプレフィックス和を $p個の$ 処理要素で同時に計算するために、データは分割されます。 $p+1$ ブロック、それぞれに ${\frac {n}{p+1}}$ 要素（簡略化のため、 $p+1$ $n$ を分割します)。アルゴリズムはデータを分割しますが、 $p+1$ ブロックでは、一度に並列実行される処理要素は $p個のみです。$

最初のスイープでは、各PEは自身のブロックのローカルプレフィックス和を計算します。最後のブロックは計算する必要はありません。なぜなら、これらのプレフィックス和は後続のブロックのプレフィックス和に対するオフセットとしてのみ計算され、最後のブロックは定義上後続しないからです。

$各ブロックの最後の位置に格納されているp個$ のオフセットは、それぞれ独自のプレフィックス和として累積され、後続の位置に格納されます。pが小さい場合は $、$ これを順次実行する方が高速ですが、 $p$ が大きい場合は、このステップを並列で実行することも可能です。

2回目のスキャンが実行されます。今回は、先行するブロックのオフセットを考慮する必要がないため、最初のブロックは処理する必要はありません。ただし、このスキャンでは代わりに最後のブロックが含まれ、各ブロックのプレフィックス和は、前回のスキャンで計算されたプレフィックス和ブロックのオフセットを考慮して計算されます。

function prefix_sum ( elements ) { n := size ( elements ) p :=処理する要素の数prefix_sum := [ 0. . .0 ]サイズnの並列i = 0から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 // 2 番目のスイープでオフセットとして使用するために結果を保存します} 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 }

改善点：ブロック数が多すぎて、単一のプロセッサを配置して逐次処理に時間がかかる場合、Hillis and Steeleアルゴリズムを使用して第2フェーズを高速化できます。

分散メモリ：ハイパーキューブアルゴリズム

ハイパーキューブプレフィックスサムアルゴリズム^{[ 17 ]}は分散メモリプラットフォームによく適応しており、処理要素間のメッセージ交換で動作します。 $p=2^{d}$ アルゴリズムに参加するプロセッサ要素（PE）の数は、 $d$ 次元超立方体の角の数に等しい。

アルゴリズム全体を通して、各PEは仮想的なハイパーキューブの頂点とみなされ、そのハイパーキューブ内の、自身までのすべての要素のプレフィックス和 $σ$ とプレフィックス和 $x$ （PE間の順序付けられたインデックスによる）の両方に関する情報が与えられます。

このアルゴリズムは、まずすべてのPEが0次元ハイパーキューブの単一の頂点であると仮定することから始まり、したがって $σ$ と $xは$ 自身の要素の局所的な接頭辞和に等しいと仮定します。
このアルゴリズムは、1つの次元で隣接するハイパーキューブを統合することによって進行します。各統合の際、 $σ$ は2つのハイパーキューブ間で交換および集約され、この新しいハイパーキューブの角にあるすべてのPEが、新しく統合されたハイパーキューブのプレフィックス合計を変数 $σ$ に格納するという不変条件が維持されます。ただし、より高いインデックスを持つPEを含むハイパーキューブのみが、この $σを$ ローカル変数 $x$ にも追加し、 $xが$ 自身のインデックス以下のインデックスを持つPEのすべての要素のプレフィックス合計の値のみを格納するという不変条件が維持されます。

$d$ 次元の超立方体では $2d$ 角にPEがある場合、アルゴリズムを $d回繰り返す必要があります。$ $2d$ ゼロ次元ハイパーキューブは、1つの $d$ 次元ハイパーキューブに統合されます。異なるハイパーキューブ内の隣接する2つのPEの $σ$ を1つの通信ステップで双方向に交換できる双方向通信モデルを仮定すると、これは次のことを意味します。 $d=\log _{2}p$ コミュニケーション関連のスタートアップ企業。

i : =自身のプロセッサ要素( PE )のインデックスm : =このPEのローカル要素のプレフィックス和d : =ハイパーキューブの次元数x = m ; // 不変: 現在のサブキューブ内のこの PE までの接頭辞和σ = m ; // 不変: 現在のサブキューブ内のすべての要素の接頭辞和for ( k = 0 ; k <= d -1 ; k ++ ) { y = σ @ PE ( i xor 2 ^ k ) // 次元 k に沿った反対側のサブキューブのプレフィックス合計を取得しますσ = σ + y // 両方のサブキューブのプレフィックス合計を集計しますif ( i & 2 ^ k ) { x = x + y // この PE がより高いインデックスである場合のみ、他のサブキューブからのプレフィックス合計を集計します。} }

大きなメッセージサイズ: パイプライン化されたバイナリツリー

パイプラインバイナリツリーアルゴリズム^{[ 18 ]}は、分散メモリプラットフォーム向けの別のアルゴリズムであり、特に大きなメッセージサイズに適しています。

ハイパーキューブアルゴリズムと同様に、このアルゴリズムも特殊な通信構造を前提としています。処理要素（PE）は、 PE内のインデックスに従って中置記数法で番号付けされた二分木（例えばフィボナッチ木）に仮想的に配置されます。このような木構造における通信は、常に親ノードと子ノード間で行われます。

中置記法により、任意の PE _jに対して、その左部分木で到達可能なすべてのノードのインデックスが保証されます。 $\color {Blue}{[l\dots j-1]}$ $j$ より小さく、インデックスは $\color {Blue}{[j+1\dots r]}$ 右サブツリー内のすべてのノードのうち、 $jより大きいものが存在する。PE$ _jが左の子である場合、親のインデックスは PE _jのサブツリー内のどのインデックスよりも大きく、PE _jが右の子である場合は小さくなる。これにより、次の推論が可能になる。

ローカル接頭辞の合計 $\color {Blue}{\oplus [l\dots j-1]}$ 左サブツリーの要素を集約して、PE _jのローカルプレフィックス合計を計算する必要がある。 $\color {Blue}{\oplus [l\dots j]}$ 。
ローカル接頭辞の合計 $\color {Blue}{\oplus [j+1\dots r]}$ 右サブツリーのを集約して、左子接続を含むパスで到達する上位レベルの PE _{hのローカルプレフィックス合計を計算する必要があります (つまり、} $h>j$ )
合計接頭辞和 $\color {Red}{\oplus [0\dots j]}$ PE _jは、右サブツリー内のプレフィックスの合計を計算するために必要です (例: $\color {Red}{\oplus [0\dots j\dots r]}$ （サブツリー内の最も高いインデックスのノードの場合）。
PE _{j に}は合計接頭辞の合計を含める必要があります $\color {Red}{\oplus [0\dots l-1]}$ 右子接続を含む上方向パスで到達する最初の上位ノードのプレフィックス合計を計算します。

サブツリーローカルプレフィックス合計と全プレフィックス合計の違いに注意してください。2、3、4番目の点から循環依存が形成されるように思われるかもしれませんが、そうではありません。下位レベルの PE は、自身の全プレフィックス合計を計算するために上位レベルの PE の全プレフィックス合計を必要とする場合がありますが、上位レベルの PE は、自身の全プレフィックス合計を計算するためにサブツリーローカルプレフィックス合計のみを必要とします。最上位レベルのノードであるルートノードは、自身のプレフィックス合計を計算するために左サブツリーのローカルプレフィックス合計のみを必要とします。PE _{0からルート PE までのパス上の各 PE は、自身のプレフィックス合計を計算するために左サブツリーのローカルプレフィックス合計のみを必要としますが、PE}_p-1 (最後の PE) から PE_ルートまでのパス上のすべてのノードは、自身の全プレフィックス合計を計算するために親の全プレフィックス合計を必要とします。

これにより、2段階のアルゴリズムが導き出される。

上昇期: サブツリーのローカル接頭辞和を伝播する $\color {Blue}{\oplus [l\dots j\dots r]}$ _{各 PE j}について、その親へ。

下降期: 排他的（排他的PE _jおよびその左サブツリー内のPEを含む）総プレフィックス和を伝播する $\color {Red}{\oplus [0\dots l-1]}$ _{PE j}のアドレス指定サブツリーに含まれていないすべての下位インデックス PE を、 PE _jの左子サブツリー内の下位レベルの PE に伝播します。包括的なプレフィックスサムを伝播します。 $\color {Red}{\oplus [0\dots j]}$ _{PE j}の右の子サブツリーへ。

アルゴリズムは各PEで並列実行され、PEは子/親からパケットを受け取るまで受信時にブロックされることに注意してください。

k := PE m のメッセージm内のパケット数@ { left , right , parent , this } : = //異なるPEのメッセージx = m @ this// 上向きフェーズ - j = 0からk - 1までのサブツリーローカルプレフィックス合計を計算します。// パイプライン処理: メッセージの各パケットについて、hasLeftChildの場合: blocking receive m [ j ] @ left // これにより、ローカル m[j] が受信された m[j] に置き換えられます// 下位インデックス PE からの包括的なローカルプレフィックス合計を集約しますx [ j ] = m [ j ] ⨁ x [ j ]if hasRightChild : blocking receive m [ j ] @ right // 右の子はインデックスが高いPEなので、m[j]をローカルのプレフィックス合計に集約しないsend x [ j ] ⨁ m [ j ] to parent else : send x [ j ] to parent// j = 0からk - 1 までの下降フェーズ: m [ j ] @ this = 0hasParentの場合:ブロッキング受信m [ j ] @ parent // 左の子の場合、m[j] は親の排他的プレフィックス和、右の子の場合、包含的プレフィックス和x [ j ] = m [ j ] ⨁ x [ j ] send m [ j ] to left // この PE または左サブツリー内の任意の PE より小さいすべての PE の合計プレフィックス和send x [ j ] to right // この PE より小さいか等しいすべての PE の合計プレフィックス和

パイプライン

$長さn$ のメッセージ $m を$ $k 個の$ パケットに分割でき、対応する各メッセージパケットに対して演算子 ⨁ を個別に使用できる場合、パイプライン処理が可能です。^[¹⁸^]

アルゴリズムをパイプライン処理なしで使用する場合、バイナリツリーの2つのレベル（送信PEと受信PE）のみが常に動作し、他のすべてのPEは待機状態になります。p $個$ の処理要素があり、バランスのとれたバイナリツリーを使用する場合、ツリーは次のようになります。 $\log _{2}p$ レベル、パスの長さ $\displaystyle PE_0$ に $PE_{\mathrm {root} }$ したがって $\log _{2}p-1$ これは上昇フェーズ中の非並列通信操作の最大数を表し、同様に下降パス上の通信も制限されます。 $\log _{2}p-1$ スタートアップ。通信開始時間を想定すると $T_{\mathrm {start} }$ バイト単位の送信時間は $T_{\mathrm {byte} }$ 上昇および下降フェーズは、 $(2\log _{2}p-2)(T_{\mathrm {start} }+n\cdot T_{\mathrm {byte} })$ パイプライン処理を行わないシナリオの場合。

k個のパケットに分割すると、それぞれのサイズは ${\tfrac {n}{k}}$ そしてそれらを別々に送信すると、最初のパケットはまだ $(\log _{2}p-1)\left(T_{\mathrm {start} }+{\frac {n}{k}}\cdot T_{\mathrm {byte} }\right)$ 伝播される $PE_{\mathrm {root} }$ ローカルプレフィックスサムの一部として、これは最後のパケットでも再び発生します。 $k>\log _{2}p$ しかし、その間、パス上のすべてのPEは並列に動作でき、3番目の通信操作（左受信、右受信、親への送信）ごとにパケットが次のレベルに送信されるため、1つのフェーズは $2\log _{2}p-1+3(k-1)$ 通信業務と両方のフェーズを合わせて必要とする $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathrm {start} }+{\frac {n}{k}}\cdot T_{\mathrm {byte} }\right)$ これは大きなメッセージサイズ $n$ に対して有利です。

このアルゴリズムは、全二重通信または電話モデル通信を利用し、上昇フェーズと下降フェーズを重ね合わせることでさらに最適化できる。^{[ 18 ]}

データ構造

データセットが動的に更新される場合、フェンウィックツリーデータ構造に格納されることがあります。この構造では、任意の個々のプレフィックス合計値のルックアップと、任意の配列値の変更を、操作ごとに対数時間で行うことができます。^{[ 19 ]}ただし、1982 年の論文^{[ 20 ]}では、フェンウィックツリーと重複すると思われる部分合計ツリーと呼ばれるデータ構造が提示されています (セクション 5.1 を参照)。1982 年当時は、プレフィックス合計という用語は今日ほど一般的ではありませんでした。

高次元配列の場合、合計面積テーブルは、任意の矩形サブ配列の合計を計算するためのプレフィックス合計に基づくデータ構造を提供します。これは、画像畳み込み演算において有用なプリミティブとなり得ます。^{[ 21 ]}

アプリケーション

計数ソートは、キー頻度のヒストグラムのプレフィックス和を使用して、ソートされた出力配列内の各キーの位置を計算する整数ソートアルゴリズムです。キーの整数値が項目の数より小さい場合は線形時間で実行され、大きさの制約が少ない整数をソートするための高速アルゴリズムである基数ソートの一部としてよく使用されます。^[¹^]

リストランキングとは、連結リストを同じ項目のシーケンスを表す配列に変換する問題であり、1, 1, 1, ... のシーケンスに対してプレフィックス和を計算し、各項目をそのプレフィックス和の値によって与えられる配列の位置にマッピングすることとして考えることができます。リストランキング、プレフィックス和、およびオイラーツアーを組み合わせることで、木構造に関する多くの重要な問題を効率的な並列アルゴリズムで解決できます。^{[ 4 ]}

並列プレフィックス和アルゴリズムの初期の応用例は、 2 つの $n$ ビットのバイナリ数を加算できるブール回路であるバイナリ加算器の設計でした。この応用では、加算のキャリービットのシーケンスは、入力ビットのペアのシーケンスに対するスキャン操作として表現でき、多数決関数を使用して前のキャリーをこれらの 2 つのビットと組み合わせます。出力数の各ビットは、対応するキャリービットとの 2 つの入力ビットの排他的論理和として見つけることができます。並列プレフィックス和アルゴリズムの操作を実行する回路を使用することで、 $O$ $($ $n$ $)$ 個の論理ゲートと $O$ $(log$ $n$ $)$ 個の時間ステップを使用する加算器を設計できます。^[³^]^[¹¹^]^[¹²^]

並列ランダムアクセスマシンの計算モデルでは、プレフィックス和を使用して、同時アクセスを禁止する並列マシン上で、複数のプロセッサが同時に同じメモリセルにアクセスできることを前提とする並列アルゴリズムをシミュレートできます。ソートネットワークを使用すると、一連の並列メモリアクセス要求を、同じセルへのアクセスがシーケンス内で連続するように順序付けできます。次に、スキャン操作を使用して、要求されたセルへの書き込みに成功したアクセスを決定し、メモリ読み出し操作の結果を、同じ結果を要求する複数のプロセッサに分配できます。^{[ 22 ]}

Guy Blellochの博士論文^{[ 23 ]}では、並列プレフィックス操作は、Connection Machineなどのマシンによって提供されるデータ並列モデルの形式化の一部を形成しています。Connection Machine CM-1 および CM-2 は、上記のアルゴリズム 1 を実装できるハイパーキューブネットワークを提供しましたが、CM-5 はアルゴリズム 2 を実装するための専用ネットワークを提供しました。^[²⁴^]

グレイコードの構成では、連続するシーケンス値が1ビット位置で互いに異なるという性質を持つバイナリ値のシーケンスにおいて、数値 $nは、$ $n$ と $n$ $/2 （nを$ $1$ ビット右にシフトして形成される数値）の排他的論理和を取るだけで、シーケンスの位置 $n$ のグレイコード値に変換できます。逆の操作、つまりグレイコード化された値 $xを$ バイナリ数にデコードすることはより複雑ですが、 $x$ のビットのプレフィックス和として表現できます。プレフィックス和内の各加算操作は、2を法として実行されます。この種のプレフィックス和は、現代のコンピュータで利用可能なビット単位のブール演算を使用して、 $xを$ 2のべき乗の数だけ左にシフトして形成される各数値と $x$ の排他的論理和を計算することで効率的に実行できます。 ^[²⁵^]

並列プレフィックス（基底となる結合法則として乗算を使用）は、並列多項式補間の高速アルゴリズムを構築するためにも使用できます。特に、補間多項式のニュートン形式の分割差分係数を計算するために使用できます。 ^[²⁶^]このプレフィックスベースのアプローチは、(合流)エルミート補間の一般化分割差分を取得するため、およびヴァンデルモンドシステムの並列アルゴリズムにも使用できます。^[²⁷^]

並列プレフィックスアルゴリズムは、ベイズフィルタ、カルマンフィルタ、および対応するスムーザーを含む再帰的ベイズ推定法の時間的並列化にも使用できます。 ^[²⁸^]コアとなるアイデアは、たとえば、ベイズ/カルマンフィルタリング問題の解が、フィルタリング演算子のプレフィックス「和」によってフィルタリング解が得られるように適切に定義された結合フィルタリング演算子で記述されるということです。これにより、並列プレフィックスアルゴリズムを適用してフィルタリングおよびスムーシング解を計算できます。同様のアイデアは、確率的数値計算のコンテキストで、ある種の確率的微分方程式ソルバーの並列化にも有効です^[²⁹^]。

最適制御の文脈では、並列プレフィックスアルゴリズムは、ベルマン方程式およびハミルトン・ヤコビ・ベルマン方程式（HJB方程式）の並列化に使用でき、線形二次レギュレータの特殊なケースも含まれます。^{[ 30 ]}^{[ 31 ]}ここでの考え方は、条件付き値関数の組み合わせ（終点に条件付き）に対する結合演算子を定義でき、この演算子のプレフィックス和がベルマン方程式またはHJB方程式の解を与えるということです。

プレフィックス和は、複数のプロセッサ間で作業を分散するための低コストアルゴリズムとして負荷分散に使用され、その最大の目的は各プロセッサで均等な作業量を達成することです。このアルゴリズムは、各項目に必要な作業量を表す重みの配列を使用します。プレフィックス和が計算された後、作業項目 $iは、$ [ ⁠ prefixSumValue _i / totalWork / numberOfProcessors ⁠ ]の数のプロセッサユニットに処理のために送信されます。^{[ 32 ]}グラフィカルには、これは各項目の作業量が線分の長さで表され、すべての線分が順番に線上に配置され、結果がプロセッサの数に対応する数のピースに分割される操作に対応します。^{[ 33 ]}

以下は、0から18までの数字について、余りを捨てた四分位数のルックアップテーブルです。これにより、 $9\times9$ までの数の乗算が可能になります。

例えば、9に3を掛けたい場合、和と差はそれぞれ12と6であることがわかります。これらの値を表で調べると、36と9が得られ、その差は27で、これは9と3の積です。

参考文献

1 2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill , pp. 168–170 , ISBN 0-262-03293-7。
↑ Cole, Richard; Vishkin, Uzi (1986)、「最適な並列リストランキングへの応用を伴う決定論的コイン投げ」(PDF)、Information and Control、70 (1): 32–53、doi : 10.1016/S0019-9958(86)80023-7
1 2 3 4 5 Ladner, RE; Fischer, MJ (1980)、「並列プレフィックス計算」、Journal of the ACM、27 (4): 831–838、CiteSeerX 10.1.1.106.6247、doi : 10.1145/322217.322232、MR 0594702、S2CID 207568668 。
1 2 3タージャン、ロバートE. Vishkin、Uzi (1985)、「効率的な並列双接続アルゴリズム」、SIAM Journal on Computing、14 (4): 862–874、CiteSeerX 10.1.1.465.8898、doi : 10.1137/0214061 。
↑ Lakshmivarahan, S.; Dhall, SK (1994), Parallelism in the Prefix Problem , Oxford University Press , ISBN 0-19508849-2。
↑ Blelloch, Guy (2011), Prefix Sums and Their Applications (Lecture Notes) (PDF) , カーネギーメロン大学。
↑ Callahan, Paul; Kosaraju, S. Rao (1995), "多次元点集合の分解とk近傍法およびn体ポテンシャル場への応用", Journal of the ACM , 42 (1): 67– 90, doi : 10.1145/200836.200853 , S2CID 1818562 。
↑ 「GPU Gems 3」。
↑ Hillis, W. Daniel; Steele, Jr., Guy L. (1986 年 12 月). "データ並列アルゴリズム" . Communications of the ACM . 29 (12): 1170– 1183. doi : 10.1145/7902.7903 .
↑ Owens, John D.; Luebke, David; Govindaraju, Naga; Harris, Mark; Krüger, Jens; Lefohn, Aaron E.; Purcell, Timothy J. (2007). "グラフィックスハードウェアにおける汎用計算の調査" (PDF) . Computer Graphics Forum . 26 (1): 80– 113. doi : 10.1111/j.1467-8659.2007.01012.x .
1 2オフマン、ユウ。 (1962)、 Об алгоритмической сложности дискретных функций、Doklady Akademii Nauk SSSR (ロシア語)、145 (1): 48–51、MR 0168423 英語訳、「離散関数のアルゴリズム的複雑性について」、ソビエト物理学ドクラディ7 : 589–591 1963。
1 2 Khrapchenko, VM (1967), "並列加算器の加算時間の漸近推定", Problemy Kibernet. (ロシア語), 19 : 107– 122英語訳はSyst. Theory Res. 19 ; 105–122, 1970に掲載。
↑ Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Scan primitives for GPU computing . Proc. 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. pp. 97–106 . 2014-09-03 のオリジナルからアーカイブ済み。2007-11-29に取得。
↑ヴィシュキン、ウジ (2003)。接頭辞和およびその応用。米国特許第6,542,918号。
↑シングラー、ヨハネス。「MCSTL: マルチコア標準テンプレートライブラリ」。 2019年3月29日取得。
↑ Singler, Johannes; Sanders, Peter; Putze, Felix (2007). "MCSTL: マルチコア標準テンプレートライブラリ". Euro-Par 2007 並列処理. Lecture Notes in Computer Science. Vol. 4641. pp. 682–694 . doi : 10.1007/ 978-3-540-74466-5_72 . ISBN 978-3-540-74465-8ISSN 0302-9743
↑アナンス・グラマ。ヴィピン・クマール。アンシュル・グプタ (2003)。並列コンピューティングの概要。アディソン・ウェスリー。85、86ページ。ISBN 978-0-201-64865-2。
1 2 3 Sanders, Peter; Träff, Jesper Larsson (2006). "MPI 用並列プレフィックス (スキャン) アルゴリズム". Recent Advances in Parallel Virtual Machine and Message Passing Interface . Lecture Notes in Computer Science. Vol. 4192. pp. 49–57 . doi : 10.1007/11846802_15 . ISBN 978-3-540-39110-4ISSN 0302-9743
↑ Fenwick, Peter M. (1994), "累積度数表のための新しいデータ構造", Software: Practice and Experience , 24 (3): 327–336 , doi : 10.1002/spe.4380240306 , S2CID 7519761
↑ Shiloach, Yossi; Vishkin, Uzi (1982b), "An O ( n ² log n ) parallel max-flow algorithm", Journal of Algorithms , 3 (2): 128– 146, doi : 10.1016/0196-6774(82)90013-X
↑ Szeliski, Richard (2010), "Summed area table (integral image)", Computer Vision: Algorithms and Applications , Texts in Computer Science, Springer, pp. 106–107 , ISBN 9781848829350。
↑ Vishkin, Uzi (1983), "同時メモリアドレスアクセスを禁止するモデルにおける同時メモリアドレスアクセスの実装", Journal of Algorithms , 4 (1): 45–50 , doi : 10.1016/0196-6774(83)90033-0 , MR 0689265 。
↑ Blelloch, Guy E. (1990). Vector models for data-parallel computing . Cambridge, MA: MIT Press. ISBN 026202313X. OCLC 21761743 .
↑ Leiserson, Charles E. ; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Hillis, W. Daniel ; Kuszmaul, Bradley C.; St. Pierre, Margaret A. (1996 年 3 月 15 日). "The Network Architecture of the Connection Machine CM-5". Journal of Parallel and Distributed Computing . 33 (2): 145– 158. doi : 10.1006/jpdc.1996.0033 . ISSN 0743-7315 .
↑ウォーレン、ヘンリー S. (2003)、『ハッカーの喜び』 、アディソン・ウェスリー、 236ページ、 ISBN 978-0-201-91465-8。
↑ Eğecioğlu, O.; Gallopoulos, E.; Koç, C. (1990), "高速かつ実用的な高次ニュートン補間のための並列法", BIT Computer Science and Numerical Mathematics , 30 (2): 268– 288, doi : 10.1007/BF02017348 , S2CID 9607531 。
↑ Eğecioğlu, O.; Gallopoulos, E.; Koç, C. (1989), "Fast computation of divided differences and parallel Hermite interpolation", Journal of Complexity , 5 (4): 417–437 , doi : 10.1016/0885-064X(89)90018-6
↑ Särkkä, Simo; García-Fernández, Ángel F. (2021). "Temporal Parallelization of Bayesian Smoothers" . IEEE Transactions on Automatic Control . 66 (1): 299– 306. arXiv : 1905.13002 . Bibcode : 2021ITAC...66..299S . doi : 10.1109/TAC.2020.2976316 .
↑ボッシュ、ナタナエル;コレンフロス、エイドリアン。ヤグフービ、ファテメ。トロナープ、フィリップ。ヘニング、フィリップ。サーッカ、シモ (2024)。「並列時間確率的数値 ODE ソルバー」。機械学習研究ジャーナル。２５．arXiv : 2310.01145。
↑ Särkkä, Simo; García-Fernández, Ángel F. (2023). "動的計画法と線形二次制御の時間的並列化" . IEEE Transactions on Automatic Control . 68 (2): 851– 866. arXiv : 2104.03186 . Bibcode : 2023ITAC...68..851S . doi : 10.1109/TAC.2022.3147017 .
↑ Särkkä, Simo; García-Fernández, Ángel F. (2025). "HJB方程式の時間的並列化と連続時間線形二次制御" . IEEE Transactions on Automatic Control . 70 (6): 3755– 3770. arXiv : 2212.11744 . Bibcode : 2025ITAC...70.3755S . doi : 10.1109/TAC.2024.3518309 .
↑ Becker, Aaron; Zheng, Gengbin; Kalé, Laxmikant V. (2011). "Load Balancing, Distributed Memory". Encyclopedia of Parallel Computing . Boston, MA: Springer US. p. 1046. doi : 10.1007/978-0-387-09766-4_504 . ISBN 978-0-387-09765-7。
↑ Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). "Load Balancing" (PDF) . Sequential and Parallel Algorithms and Data Structures . Cham: Springer International Publishing. pp. 419–434 . doi : 10.1007/978-3-030-25209-0_14 . ISBN 978-3-030-25208-3。

外部リンク

ワイススタイン、エリック W. 「累積和」 . MathWorld .

[clrs-1] 1 2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill , pp. 168–170 , ISBN 0-262-03293-7。

[cv86-2] Cole, Richard; Vishkin, Uzi (1986)、「最適な並列リストランキングへの応用を伴う決定論的コイン投げ」(PDF)、Information and Control、70 (1): 32–53、doi : 10.1016/S0019-9958(86)80023-7

[lf80-3] 1 2 3 4 5 Ladner, RE; Fischer, MJ (1980)、「並列プレフィックス計算」、Journal of the ACM、27 (4): 831–838、CiteSeerX 10.1.1.106.6247、doi : 10.1145/322217.322232、MR 0594702、S2CID 207568668 。

[tv85-4] 1 2 3タージャン、ロバートE. Vishkin、Uzi (1985)、「効率的な並列双接続アルゴリズム」、SIAM Journal on Computing、14 (4): 862–874、CiteSeerX 10.1.1.465.8898、doi : 10.1137/0214061 。

[Prefix.book.92-5] Lakshmivarahan, S.; Dhall, SK (1994), Parallelism in the Prefix Problem , Oxford University Press , ISBN 0-19508849-2。

[blelloch11-6] Blelloch, Guy (2011), Prefix Sums and Their Applications (Lecture Notes) (PDF) , カーネギーメロン大学。

[callahan1995-7] Callahan, Paul; Kosaraju, S. Rao (1995), "多次元点集合の分解とk近傍法およびn体ポテンシャル場への応用", Journal of the ACM , 42 (1): 67– 90, doi : 10.1145/200836.200853 , S2CID 1818562 。

[8] 「GPU Gems 3」。

[hs1986-9] Hillis, W. Daniel; Steele, Jr., Guy L. (1986 年 12 月). "データ並列アルゴリズム" . Communications of the ACM . 29 (12): 1170– 1183. doi : 10.1145/7902.7903 .

[10] Owens, John D.; Luebke, David; Govindaraju, Naga; Harris, Mark; Krüger, Jens; Lefohn, Aaron E.; Purcell, Timothy J. (2007). "グラフィックスハードウェアにおける汎用計算の調査" (PDF) . Computer Graphics Forum . 26 (1): 80– 113. doi : 10.1111/j.1467-8659.2007.01012.x .

[offman-11] 1 2オフマン、ユウ。 (1962)、 Об алгоритмической сложности дискретных функций、Doklady Akademii Nauk SSSR (ロシア語)、145 (1): 48–51、MR 0168423 英語訳、「離散関数のアルゴリズム的複雑性について」、ソビエト物理学ドクラディ7 : 589–591 1963。

[krapchenko-12] 1 2 Khrapchenko, VM (1967), "並列加算器の加算時間の漸近推定", Problemy Kibernet. (ロシア語), 19 : 107– 122英語訳はSyst. Theory Res. 19 ; 105–122, 1970に掲載。

[13] Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Scan primitives for GPU computing . Proc. 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. pp. 97–106 . 2014-09-03 のオリジナルからアーカイブ済み。2007-11-29に取得。

[14] ヴィシュキン、ウジ (2003)。接頭辞和およびその応用。米国特許第6,542,918号。

[15] シングラー、ヨハネス。「MCSTL: マルチコア標準テンプレートライブラリ」。 2019年3月29日取得。

[SinglerSanders2007-16] Singler, Johannes; Sanders, Peter; Putze, Felix (2007). "MCSTL: マルチコア標準テンプレートライブラリ". Euro-Par 2007 並列処理. Lecture Notes in Computer Science. Vol. 4641. pp. 682–694 . doi : 10.1007/ 978-3-540-74466-5_72 . ISBN 978-3-540-74465-8ISSN 0302-9743

[GramaKumar2003-17] アナンス・グラマ。ヴィピン・クマール。アンシュル・グプタ (2003)。並列コンピューティングの概要。アディソン・ウェスリー。85、86ページ。ISBN 978-0-201-64865-2。

[SandersTraeff2006-18] 1 2 3 Sanders, Peter; Träff, Jesper Larsson (2006). "MPI 用並列プレフィックス (スキャン) アルゴリズム". Recent Advances in Parallel Virtual Machine and Message Passing Interface . Lecture Notes in Computer Science. Vol. 4192. pp. 49–57 . doi : 10.1007/11846802_15 . ISBN 978-3-540-39110-4ISSN 0302-9743

[19] Fenwick, Peter M. (1994), "累積度数表のための新しいデータ構造", Software: Practice and Experience , 24 (3): 327–336 , doi : 10.1002/spe.4380240306 , S2CID 7519761

[20] Shiloach, Yossi; Vishkin, Uzi (1982b), "An O ( n ² log n ) parallel max-flow algorithm", Journal of Algorithms , 3 (2): 128– 146, doi : 10.1016/0196-6774(82)90013-X

[21] Szeliski, Richard (2010), "Summed area table (integral image)", Computer Vision: Algorithms and Applications , Texts in Computer Science, Springer, pp. 106–107 , ISBN 9781848829350。

[22] Vishkin, Uzi (1983), "同時メモリアドレスアクセスを禁止するモデルにおける同時メモリアドレスアクセスの実装", Journal of Algorithms , 4 (1): 45–50 , doi : 10.1016/0196-6774(83)90033-0 , MR 0689265 。

[23] Blelloch, Guy E. (1990). Vector models for data-parallel computing . Cambridge, MA: MIT Press. ISBN 026202313X. OCLC 21761743 .

[24] Leiserson, Charles E. ; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Hillis, W. Daniel ; Kuszmaul, Bradley C.; St. Pierre, Margaret A. (1996 年 3 月 15 日). "The Network Architecture of the Connection Machine CM-5". Journal of Parallel and Distributed Computing . 33 (2): 145– 158. doi : 10.1006/jpdc.1996.0033 . ISSN 0743-7315 .

[25] ウォーレン、ヘンリー S. (2003)、『ハッカーの喜び』 、アディソン・ウェスリー、 236ページ、 ISBN 978-0-201-91465-8。

[26] Eğecioğlu, O.; Gallopoulos, E.; Koç, C. (1990), "高速かつ実用的な高次ニュートン補間のための並列法", BIT Computer Science and Numerical Mathematics , 30 (2): 268– 288, doi : 10.1007/BF02017348 , S2CID 9607531 。

[27] Eğecioğlu, O.; Gallopoulos, E.; Koç, C. (1989), "Fast computation of divided differences and parallel Hermite interpolation", Journal of Complexity , 5 (4): 417–437 , doi : 10.1016/0885-064X(89)90018-6

[28] Särkkä, Simo; García-Fernández, Ángel F. (2021). "Temporal Parallelization of Bayesian Smoothers" . IEEE Transactions on Automatic Control . 66 (1): 299– 306. arXiv : 1905.13002 . Bibcode : 2021ITAC...66..299S . doi : 10.1109/TAC.2020.2976316 .

[29] ボッシュ、ナタナエル;コレンフロス、エイドリアン。ヤグフービ、ファテメ。トロナープ、フィリップ。ヘニング、フィリップ。サーッカ、シモ (2024)。「並列時間確率的数値 ODE ソルバー」。機械学習研究ジャーナル。２５．arXiv : 2310.01145。

[30] Särkkä, Simo; García-Fernández, Ángel F. (2023). "動的計画法と線形二次制御の時間的並列化" . IEEE Transactions on Automatic Control . 68 (2): 851– 866. arXiv : 2104.03186 . Bibcode : 2023ITAC...68..851S . doi : 10.1109/TAC.2022.3147017 .

[31] Särkkä, Simo; García-Fernández, Ángel F. (2025). "HJB方程式の時間的並列化と連続時間線形二次制御" . IEEE Transactions on Automatic Control . 70 (6): 3755– 3770. arXiv : 2212.11744 . Bibcode : 2025ITAC...70.3755S . doi : 10.1109/TAC.2024.3518309 .

[32] Becker, Aaron; Zheng, Gengbin; Kalé, Laxmikant V. (2011). "Load Balancing, Distributed Memory". Encyclopedia of Parallel Computing . Boston, MA: Springer US. p. 1046. doi : 10.1007/978-0-387-09766-4_504 . ISBN 978-0-387-09765-7。

[33] Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). "Load Balancing" (PDF) . Sequential and Parallel Algorithms and Data Structures . Cham: Springer International Publishing. pp. 419–434 . doi : 10.1007/978-3-030-25209-0_14 . ISBN 978-3-030-25208-3。

[ 1 ]

[ 2 ]

[

[

[

[ 6 ]

[ 7 ]

[8]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[

[

[

[

[

[

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]