14.5. カーネルの実装（bitonic merge）

戻る		次へ

バイトニックマージは、バイトニックスプリットと比べるとシンプルです。理由は上昇配列と下降配列に並べ替えるスプリットに対して、マージは値の大小によってスワップを繰り返すだけだからです。

以下がマージのアルゴリズムを実装したカーネルのソースです。

int in_range = isless(gid % (distance << 1),distance); //(1)

if(in_range) { //(2)
    uint left = data[gid]; //(3)
    uint right = data[gid+distance]; //(4)
    cmp_mask = left < right ? 1 : 0; //(5)
    data[gid] = select(left,right,cmp_mask); //(6)
    data[gid+distance] = select(right,left,cmp_mask); //(7)
}

(1)	グローバルIDのインデックス空間をdistanceの2倍の要素の範囲で分割して、それがdistanceより小さい場合に真を返します。処理すべき添字は、distanceより小さい値を持つ、グローバルIDの場合とします。
(2)	カーネルは、①でdistanceの2倍で除したグローバルIDの値がdistanceより小さい場合は、処理点から除外。if分岐のカッコ内の処理は効率的でないため、前のステップで計算したフラグをif分岐のカッコに配置します。
(3)	処理点の値をleft変数に保存。
(4)	スワップ点の値をright変数に保存。
(5)	処理点がスワップ点の値より小さい場合はスワップフラグ（cmp_mask）をオンにします。
(6)	スワップフラグ（cmp_mask）がオンの場合にleftとrightをスワップ（入れ替え）します。
(7)	スワップフラグ（cmp_mask）がオンの場合にrightとleftをスワップ（入れ替え）します。

マージの処理ですが、データの要素数が16の場合は以下のような処理過程を行います。dはスワップ距離、gdivは「gid % (distance << 1」に該当します。

merge. d=8, gdiv=0, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=8, gdiv=1, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=8, gdiv=2, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=8, gdiv=3, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=8, gdiv=4, left=10, right=8, data[gid]=10, data[gid+d]=8
merge. d=8, gdiv=5, left=12, right=6, data[gid]=12, data[gid+d]=6
merge. d=8, gdiv=6, left=14, right=4, data[gid]=14, data[gid+d]=4
merge. d=8, gdiv=7, left=16, right=2, data[gid]=16, data[gid+d]=2
merge. d=4, gdiv=0, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=4, gdiv=1, left=10, right=12, data[gid]=12, data[gid+d]=10
merge. d=4, gdiv=2, left=10, right=14, data[gid]=14, data[gid+d]=10
merge. d=4, gdiv=3, left=10, right=16, data[gid]=16, data[gid+d]=10
merge. d=4, gdiv=0, left=10, right=8, data[gid]=10, data[gid+d]=8
merge. d=4, gdiv=1, left=10, right=6, data[gid]=10, data[gid+d]=6
merge. d=4, gdiv=2, left=10, right=4, data[gid]=10, data[gid+d]=4
merge. d=4, gdiv=3, left=10, right=2, data[gid]=10, data[gid+d]=2
merge. d=2, gdiv=0, left=10, right=14, data[gid]=14, data[gid+d]=10
merge. d=2, gdiv=1, left=12, right=16, data[gid]=16, data[gid+d]=12
merge. d=2, gdiv=0, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=2, gdiv=1, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=2, gdiv=0, left=8, right=4, data[gid]=8, data[gid+d]=4
merge. d=2, gdiv=1, left=6, right=2, data[gid]=6, data[gid+d]=2
merge. d=2, gdiv=0, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=2, gdiv=1, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=1, gdiv=0, left=14, right=16, data[gid]=16, data[gid+d]=14
merge. d=1, gdiv=0, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=1, gdiv=0, left=8, right=6, data[gid]=8, data[gid+d]=6
merge. d=1, gdiv=0, left=10, right=12, data[gid]=12, data[gid+d]=10
merge. d=1, gdiv=0, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=1, gdiv=0, left=10, right=10, data[gid]=10, data[gid+d]=10
merge. d=1, gdiv=0, left=4, right=2, data[gid]=4, data[gid+d]=2
merge. d=1, gdiv=0, left=10, right=10, data[gid]=10, data[gid+d]=10

このサンプルプログラムの出力は以下のようになります。

これで整列されていることが確認できました。