Chapter 21. Bitonic Sort（バイトニックソート）

Prev		Next

Table of Contents

バイトニックソートは「Ken Batcher」が考案した並列ソートアルゴリズムです。完成度の高い並列化が可能なため、基数整列（radix sort）と同様にGPUでの整列アルゴリズムに適しています。

パフォーマンス上では、Radix Sortより劣りますが、一旦理解ができるようになると直感的に説明ができるようになることはアルゴリズムとしては大きな利点と言えるかと思います。

また並列コアを一定して使用させることができるため、最適化する余地が少ないことが、基数配列と比べて好まれる要因ともなっているようです。

バイトニック配列（またはシーケンス、シークエンス等）は以下の２つの式で表すことができます。

配列の要素はある一定の要素（配列の最大値）まで上昇し、そこから下降していきます。

もしくは配列の要素はある一定の要素（配列の最小値）まで下降し、そこから上昇していきます。

バイトニックソートは、このバイトニック配列を２つのバイトニック配列にする「バイトニック分割（Bitonic Split）」を行い、片方は少ない値、もう片方は大きい値をとる配列に分割し、それを繰り返します。

バイトニック分割を具体的に行なう場合は、バイトニック配列の添字（インデックス）を２つに分けます。そして２つに分けた配列の各要素を以下の式で比較します。

この式が成立するときは、値をスワップ（入れ替え）します。

ではバイトニック分割の一例を見てみましょう。以下の「Bitonic Split（１）」（Table 21.1, “Bitonic Split（１）”）では、8つの配列要素を、各４つのバイトニック配列に分割しています。

Table 21.1. Bitonic Split（１）

この例では以下の不等式によって、各要素のスワップ（入れ替え）を行います。

左半分【3,7,6,5】は上昇形態、【78,66,12,98】は下降形態となります。

「Bitonic Split（２）」（Table 21.2, “Bitonic Split（２）”）では、２つのバイトニック配列を４つに分割します。

Table 21.2. Bitonic Split（２）

以下の不等式とスワップが行なわれます。

このようにバイトニック分割を繰り返すことによって、整列化した配列に並び替えます。