Bitonic sorting in compute shaders

BitonicSortCS.fx

//
// Debug:   fxc /E cs_main /T cs_5_0 /Fh (output) /Od /Vn g_BitonicSortCS /Zi (this)
// Release: fxc /E cs_main /T cs_5_0 /Fh (output) /O1 /Vn g_BitonicSortCS (this)
//

// スレッド数
#define THREADS_X  512
// ソート要素数
#define ELEMENTS_TO_SORT  ( 1 << 10 )


// 入出力バッファ
RWBuffer< int > SortingBuffer : register( u0 );


[ numthreads( THREADS_X, 1, 1 ) ]
void cs_main( uint3 GroupID : SV_GroupID,
              uint3 GroupThreadID : SV_GroupThreadID,
              uint  GroupIndex : SV_GroupIndex,
              uint3 DispatchThreadID : SV_DispatchThreadID )
{
    //
    // GPUSorting アプリケーションではバイトニックソートを行うにあたり、
    // ELEMENTS_TO_SORT / 2 スレッドをディスパッチする必要がある。
    //
    // ただし 1 スレッドグループで実行できる最大スレッド数は DirectX11 で 1,024 であるため、
    // 1 スレッドグループで実行するスレッド数は THREADS_X で固定しておき、
    // 1 スレッドが複数の比較を行うことで処理する。
    // (なお ELEMENTS_TO_SORT は少なくとも THREADS_X * 2 以上である必要がある)
    //

    for ( uint i = 2; i <= ELEMENTS_TO_SORT; i <<= 1 )
    {
        for ( uint j = i >> 1; j > 0; j >>= 1 )
        {
            for ( uint k = GroupIndex; k < ELEMENTS_TO_SORT >> 1; k += THREADS_X )
            {
                uint l = k / j * j + k;

                if ( k & ( i >> 1 ) )
                {
                    // 降順
                    if ( SortingBuffer[ l ] < SortingBuffer[ l + j ] )
                    {
                        int temp               = SortingBuffer[ l ];
                        SortingBuffer[ l ]     = SortingBuffer[ l + j ];
                        SortingBuffer[ l + j ] = temp;
                    }
                }
                else
                {
                    // 昇順
                    if ( SortingBuffer[ l ] > SortingBuffer[ l + j ] )
                    {
                        int temp               = SortingBuffer[ l ];
                        SortingBuffer[ l ]     = SortingBuffer[ l + j ];
                        SortingBuffer[ l + j ] = temp;
                    }
                }
            }

            // 比較ステージ 1 段ごとに足並みを揃える
            DeviceMemoryBarrierWithGroupSync();
        }
    }
}