ビトニックソーター

ビトニックソーター

8 つの入力を持つビトニック ソート ネットワーク。
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O(\log ^{2}(n))}$パラレルタイム
最高の パフォーマンス	${\displaystyle O(\log ^{2}(n))}$パラレルタイム
平均的 なパフォーマンス	${\displaystyle O(\log ^{2}(n))}$パラレルタイム
最悪の場合の 空間複雑度	${\displaystyle O(n\log^{2}(n))}$非平行時間
最適	いいえ

ビットニックマージソートは、ソートのための並列アルゴリズムです。ソートネットワークを構築する構築法としても使用されます。このアルゴリズムは、ケン・バッチャーによって考案されました。結果として得られるソートネットワークはコンパレータで構成され、遅延は です。ここで、 はソートするアイテムの数です。^{[1]このため、典型的な}GPUなど、同期して実行される多数の並列実行ユニットを含むアーキテクチャ上で多数の要素をソートする場合によく使用されます。 ${\displaystyle O(n\log^{2}(n))}$${\displaystyle O(\log ^{2}(n))}$${\displaystyle n}$

ソートされたシーケンスは、単調に減少しない（または増加しない）シーケンスです。バイトニックシーケンスは、何らかの に対してとなるシーケンス、またはそのようなシーケンスの循環シフトです。 ${\displaystyle x_{0}\leq \cdots \leq x_{k}\geq \cdots \geq x_{n-1}}$${\displaystyle k,0\leq k<n}$

とします。 ${\displaystyle p=\lfloor \log _{2}n\rfloor }$${\displaystyle q=\lceil \log _{2}n\rceil }$

構築アルゴリズムから、並列比較のラウンド数は で与えられることが明らかです。 ${\displaystyle q(q+1)/2}$

したがって、比較器の数は制限されます( が2 の累乗である 場合の正確な値が確立されます)。${\displaystyle c}$${\displaystyle 2^{p-1}\cdot p(p+1)/2\leq c\leq \lfloor {n/2}\rfloor \cdot q(q+1)/2}$${\displaystyle c}$${\displaystyle n}$

比較の絶対数は通常 Batcher の奇数偶数ソートよりも多くなりますが、ビットニック ソートの連続操作の多くは参照の局所性を保持するため、実装はキャッシュ フレンドリーになり、実際にはより効率的になります。

以下は 16 個の入力を持つビットニック ソート ネットワークです。

16 個の数字は左端の入力として入り、16 本の水平ワイヤに沿ってスライドし、右端の出力から出ます。ネットワークは、最大の数字が下になるように要素をソートするように設計されています。

矢印は比較子です。2 つの数字が矢印の両端に到達すると、矢印が大きい方の数字を指しているかどうかが比較されます。順番が逆の場合は、入れ替えられます。色付きのボックスは説明用であり、アルゴリズムには影響しません。

すべての赤いボックスは同じ構造になっています。上半分の各入力は、すべての矢印が下向き (濃い赤) または上向き (薄い赤) になっている状態で、下半分の対応する入力と比較されます。入力がバイトニック シーケンス (単一の非減少シーケンスの後に単一の非増加シーケンスが続く、またはその逆) を形成する場合、出力は 2 つのバイトニック シーケンスを形成します。出力の上半分はバイトニックで、下半分はバイトニックになります。上半分のすべての要素は、下半分のすべての要素以下 (濃い赤の場合) または逆 (薄い赤の場合) になります。この定理は明白ではありませんが、さまざまな入力がどのように比較されるかについてのすべてのケースを慎重に検討することで、ゼロ 1 原理を使用して検証できます。バイトニック シーケンスは、2 つ以上の "10" または "01" サブシーケンスを含む 0 と 1 のシーケンスです。

赤いボックスが組み合わさって、青いボックスと緑のボックスが形成されます。このようなボックスはすべて同じ構造になっています。赤いボックスが入力シーケンス全体に適用され、次に結果の各半分に適用され、次にそれらの各結果の各半分に適用され、というように続きます。すべての矢印は下向き (青) または上向き (緑) です。この構造はバタフライ ネットワークとして知られています。このボックスへの入力がビットニックである場合、出力は昇順 (青) または降順 (緑) で完全にソートされます。数字が青または緑のボックスに入ると、最初の赤いボックスがその数字をリストの正しい半分にソートします。次に、数字は小さな赤いボックスを通過し、その半分内のリストの正しい 4 分の 1 にソートされます。これは、正確に正しい位置にソートされるまで続きます。したがって、緑または青のボックスの出力は完全にソートされます。

緑と青のボックスが組み合わさって、ソート ネットワーク全体が形成されます。任意の入力シーケンスに対して、最大のものが下になるように正しくソートされます。緑または青の各ボックスの出力はソートされたシーケンスになるため、隣接するリストの各ペアの出力は、一番上のボックスが青で一番下のボックスが緑であるため、バイトニックになります。青と緑のボックスの各列は、N 個のソートされたシーケンスを受け取り、それらをペアで連結して N/2 バイトニック シーケンスを形成します。次に、その列のボックスによってソートされ、N/2 個のソートされたシーケンスが形成されます。このプロセスは、各入力を 1 つの要素のソートされたリストと見なして開始され、最後の列でそれらを 1 つのソートされたリストにマージするまで、すべての列にわたって続行されます。最後のステージは青だったため、この最終リストでは、最大の要素が下になります。

上の図の緑のボックスはそれぞれ、青いボックスと同じ操作を実行しますが、ソートの方向が逆になります。したがって、緑のボックスはそれぞれ青いボックスに置き換えることができ、その後にすべてのワイヤが反対の位置に移動するクロスオーバーを配置できます。これにより、すべての矢印が同じ方向を指すようになりますが、水平線が直線になることはなくなります。ただし、同様のクロスオーバーを任意の赤いブロックからの出力の下半分の右側に配置すると、ソートは正しく機能します。これは、バイトニック シーケンスの逆はバイトニックであるためです。赤いボックスの前後にクロスオーバーがある場合は、内部で再配置して 2 つのクロスオーバーをキャンセルし、ワイヤが再び直線になるようにすることができます。したがって、次の図は上の図と同等であり、緑のボックスはそれぞれ青いボックスとクロスオーバーになり、オレンジ色のボックスはそれぞれ 2 つのクロスオーバーを吸収した赤いボックスになります。

すべてのコンパレータが同じ方向にソートするため、矢印は描画されません。青と赤のブロックは、前と同じ操作を実行します。オレンジのブロックは、入力の下半分と出力の下半分のシーケンス順序が逆になっている赤のブロックに相当します。これは、ビットニック ソート ネットワークの最も一般的な表現です。前の解釈とは異なり、要素は論理的に順序付けされたままなので、この表現を 2 のべき乗以外のケースに拡張するのは簡単です (各比較とスワップでは、大きい方のインデックスが範囲外の場合はすべて無視されます)。

以下は、配列の長さが2の累乗の場合のビットニックマージソートの再帰のない実装である。^[2]

    // 長さ n の配列 arr が与えられると、このコードはそれをその場でソートします
// すべてのインデックスは 0 から n-1 までですfor ( k = 2 ; k <= n ; k *= 2 ) // k は反復ごとに 2 倍になりますfor ( j = k / 2 ; j > 0 ; j /= 2 ) // j は反復ごとに半分になり、小数部は切り捨てられますfor ( i = 0 ; i < n ; i ++ ) l = bitwiseXOR ( i , j ); // C 系言語では、これは "i ^ j" ですif ( l > i ) if ( ( bitwiseAND ( i , k ) == 0 ) AND ( arr [ i ] > arr [ l ]) OR ( bitwiseAND ( i , k ) != 0 ) AND ( arr [ i ] < arr [ l ]) )要素arr [ i ]とarr [ l ]を交換します    
              
                  
                   
                     
                   
                               
                                 
                               

• バッチャ奇偶マージソート
• ペアワイズソーティングネットワーク

• このアルゴリズムについての議論
• NISTの参照コード
• アニメーション画像と実際のコードを使ったチュートリアル