ビトニックソーター

Parallel sorting algorithm

ビトニックソーター

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

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

ソートされたシーケンスは単調なシーケンス、つまり非減少または非増加のシーケンスです。シーケンスが非減少シーケンスと非増加シーケンスから構成される場合、つまり[ ^3] ${\displaystyle m}$ ${\displaystyle x_{0}\leq \cdots \leq x_{m}\geq \cdots \geq x_{n-1}.}$

バイトニックソーターは、バイトニックな入力のみをソートできます。バイトニックソーターは、ソート・バイ・マージ方式（部分解をより大きなソーターを用いてマージする方式）を適用することで、任意のシーケンスをソートできるバイトニックソートネットワークを構築できます。

以下のセクションでは、長さが2の完全累乗である入力シーケンスを必要とするアルゴリズムを元の定式化で示します。したがって、 を となる整数とします。つまり、連続する値 を考慮することで、バイトニックソーターをサイズの小さい順に列挙できることを意味します。 ${\displaystyle n}$ ${\displaystyle k=\log _{2}(n)}$ ${\displaystyle n=2^{k}}$ ${\displaystyle k=1,2,3,\ldots }$

ビトニックソーター

2つの入力を持つ通常のコンパレータ

のバイトニックソーターは単なる比較器です。^[3]これは与えられたボックスレイアウトで示されており、XとYは入力を表し、HとLはそれぞれ高い出力と低い出力を表します。 ${\displaystyle k=1}$ ${\displaystyle (n=2)}$

のソーターを用いることで、より高次のソーターを再帰的に作成することができます。例えば、次のバイトニックソーターを考えてみましょう。^[3] ${\displaystyle k=1}$ ${\displaystyle k=2}$ ${\displaystyle (n=4)}$

ビットニックマージソーター ${\displaystyle n=4}$ ${\displaystyle (k=2)}$

バイトニックソーターは2つの層から構成されます。1つは再結合層で、バイトニック入力を元のシーケンスの半分の長さを持つ2つの新しいバイトニックシーケンスに再結合します。もう1つはバイトニックソート層で、順序 の2つのバイトニックソーターで構成され、各ソーターは前の層で生成された2つのバイトニックシーケンスのいずれかをソートします。この構造は、各コンパレーターがソート対象となるバイトニックシーケンスの2つの半分から常に1つの入力を受け入れるようにすることで、 の値がより高い場合に再帰的に拡張できます。次の図は、これらの接続を模式的に示しています。^[3] ${\displaystyle k-1}$ ${\displaystyle k}$

テスト

ご覧のとおり、入力シーケンスの前半が後半と比較されます。（緑）部分シーケンスの各要素を、対応するインデックスにあるもう一方の（オレンジ）部分シーケンスの要素と比較することで、2つのビットニック部分シーケンスが生成されます。これらの2つのビットニック系列（それぞれ青と赤）は、次の下位ビットニックソーターに入力できます。これは、赤のシーケンスのすべての要素が青のシーケンスのすべての要素よりも高いことが保証されているためです。 ^[3]

バイトニックソーターの正しさ

ケン・バッチャーは論文の中で数学的な証明の概略を示しました。^[3]一般性を失うことなく、ビットニック入力シーケンスは と仮定されます。一般性を失うことなく、シーケンスは逆順に記述できるため、 と仮定できます。 ${\displaystyle a_{1}\leq a_{2}\leq \dots \leq a_{j-1}\leq a_{j}\geq a_{j+1}\geq \dots \geq a_{2n}}$ ${\displaystyle 1\leq j\leq 2n}$ ${\displaystyle n\leq j\leq 2n}$

ケース1： の場合、2つの部分列のすべての要素は小さくなります。この場合、と は、 と を伴い、したがって、 とは自明にバイトニックです。 ${\displaystyle a_{n}\leq a_{2n}}$ ${\displaystyle d_{i}=a_{i}}$ ${\displaystyle e_{i}=a_{n+i}}$ ${\displaystyle 1\leq i\leq n}$ ${\displaystyle d_{i}}$ ${\displaystyle e_{i}}$

ケース2 ：そうでない場合、最初の部分列の要素が2番目の部分列の要素よりも大きいが存在し、の場合はその逆です。これは、特定の に対してと が真であることを意味します。したがって、次のことが分かります 。 ${\displaystyle k}$ ${\displaystyle a_{k}}$ ${\displaystyle a_{k}}$ ${\displaystyle a_{k+1}}$ ${\displaystyle a_{k}\leq a_{k+n}}$ ${\displaystyle a_{k+1}>a_{k+n+1}}$ ${\displaystyle k}$

1 .シーケンスはおよび ${\displaystyle 1\leq i\leq k}$ ${\displaystyle d_{i}=a_{i}}$ ${\displaystyle e_{i}=a_{n+i}}$

2。シーケンスは1の反対として定義され、 ${\displaystyle k<i\leq 2n}$ ${\displaystyle d_{i}=a_{n+i}}$ ${\displaystyle e_{i}=a_{i}}$

原論文では、これらの定義から次のような不等式が導かれると主張している。^[3]

1に続き:

• そのために ${\displaystyle 1\leq i\leq k}$ ${\displaystyle d_{i}\leq d_{i+1}}$
• そのために ${\displaystyle j-n\leq i\leq k}$ ${\displaystyle e_{i}\geq e_{i+1}}$
• そのために ${\displaystyle 1\leq i\leq j-n}$ ${\displaystyle e_{i}\leq e_{i+1}}$

2に続く:

• そのために ${\displaystyle k<i\leq 2n}$ ${\displaystyle d_{i}\geq d_{i+1}}$
• そのために ${\displaystyle k<i\leq 2n}$ ${\displaystyle e_{i}\leq e_{i+1}}$

両方から： ${\displaystyle e_{n}\leq e_{1}}$

論文によれば、シーケンスとシーケンスは実際にはビットニックであると主張している。^[3] ${\displaystyle d_{i}}$ ${\displaystyle e_{i}}$

ビトニックソートネットワーク（ビトニックマージソート）

バイトニックソートネットワークは、複数のバイトニックソーターを用いて構築されます。これらのバイトニックソーターは再帰的に用いられ、減少と増加の2つの単調なシーケンスを作成し、次のステージに渡します。これにより、次のステージのバイトニック系列が作成され、このバイトニック系列を次のステージの単調なシーケンスとして使用することができます。バイトニックソートネットワークの次の例を考えてみましょう。^[3] ${\displaystyle n=4}$

テスト

バイトニックソートネットワークは、バイトニックソーター1台とソーター2台を用いて構築できます。2台のソーターは、バイトニックソーターへのバイトニック入力を生成するために、降順または昇順にソートされたシーケンスを作成します。低次のバイトニックソートネットワークは、主に2台のプレソーターに用いられるため、バイトニックソーターからバイトニックソートネットワークを再帰的に定義することができます。上記の例では、2台のバイトニックソートネットワークはネットワークであり、したがって単なる比較器です。^[3]次の図は全体的なスキームを示しています。 ${\displaystyle k=2}$ ${\displaystyle k=2}$ ${\displaystyle k=k_{prev}-1}$ ${\displaystyle k=1}$

テスト

この全体的なスキームでは、ソーターに2のべき乗のシーケンスの入力が必要です。ただし、例えばセンチネル値を使用することで、この影響を軽減できる可能性があります。

擬似コード

以下の擬似コードはソート処理を記述したものです。コードでは、aはソート対象の配列、lowはソート対象となるサブ配列の最初の項目のインデックス、kはcountこの関数呼び出しでソートされるサブ配列の項目数です。はサブ配列を昇順/降順のどちらでソートするかを決定する ブールdirection値です。

関数呼び出しはbitonicSort(a, 0, n, 1)をソートするために使用されますa。ここでnは 内の項目数ですa。

関数bitonicMerge(a, low, count, direction)は count > 1の場合 k ← カウント / 2 // 半分の要素を比較して交換する i ← lowからlow + k - 1 まで実行します // a の 2 つの要素がソートの方向に対して順序どおりでないかどうかを判断します。 if (direction == 1 AND a[i] > a[i + k]) OR (direction == 0 AND a[i] < a[i + k]) THEN a[i]とa[i + k]を交換する // 両方の半分を再帰的にマージする bitonicMerge (a、低、k、方向) bitonicMerge (a、低 + k、k、方向)// これは入力サイズが 2 の累乗の場合にのみ機能します。関数bitonicSort(a, low, count, direction)は count > 1の場合 k ← カウント / 2 // 前半/後半を昇順/降順に並べ替える ビットニックソート(a, low, k, 1) ビットニックソート(a, low + k, k, 0) // シーケンス全体を希望の順序で結合する bitonicMerge (a, low, count, direction)

複雑

このセクションでは、ソーターには以前と同じように入力要素があると想定します。 ${\displaystyle n=2^{k}}$

バイトニックソーティングネットワークにおける各再帰は、バイトニックソーターと次の再帰から構成される次元のソーターを追加します。両方のサブソーターは並列に実行できるため、両方のサブソーターの各レベルに対して1つのレベルのみが追加されます。したがって、各バイトニックソーターは、1つの再結合層と、その再帰のための低次元バイトニックソーターを持ちます。これにより、バイトニックソーターごとに 次元が存在します。したがって、この構成のレベルの合計は次のようになります。 ${\displaystyle k_{next}=k_{prev}-1}$ ${\displaystyle k_{next}}$ ${\displaystyle k}$ ${\displaystyle \sum _{i=1}^{k}i}$

この合計はガウスの和の公式を使って減じることができる。 ${\displaystyle \sum _{i=1}^{k}i={\dfrac {1}{2}}k(k+1)}$

したがって、各比較を並列に実行できるレベルの数は次のように与えられます。^[3]これにより、比較を並列に実行できると仮定できます。 ${\displaystyle {\dfrac {1}{2}}k(k+1)}$ ${\displaystyle {\mathcal {O}}(k^{2}+k)={\mathcal {O}}(k^{2})={\mathcal {O}}((\log _{2}n)^{2})}$ ${\displaystyle n}$

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

参照

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

参考文献

1. Megha, Jain; Sanjay, Kumar; VK, Patle (2015年3月). 「Bitonic Sorting Algorithm: A Review」. International Journal of Computer Applications . 113 (13): 40– 43. Bibcode :2015IJCA..113m..40J. doi : 10.5120/19890-1930 . 2025年5月14日閲覧。
2. ランコビッチ、ヴカシン;コス、アントン。ミルティノヴィッチ、ヴェリコ（2013年7月）。 「Maxeler Dataflow スーパーコンピューティング システムでの Bitonic Merge Sort の実装」(PDF)。インターネットリサーチに関する IPSI BGD トランザクション。9 (2): 5 ～ 10 。2025 年5 月 14 日に取得。
3. Batcher, KE (1968年4月30日). 「ソーティングネットワークとその応用」. 1968年4月30日～5月2日開催の春季合同コンピュータ会議 - AFIPS '68 (春季) 議事録. pp.  307– 314. doi :10.1145/1468075.1468121.

外部リンク

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Bitonic_sorter&oldid=1310574338"