CPU版Bitonic Sort

December 30th, 2009 by yakiimo02 in Demo, DirectX11

はじめに

DirectX 11勉強の第一段として、CPU版Bitonic Sortを実装してみました。Bitonic Sortは並列化にむいているアルゴリズムらしいですが、DirectX 11 Direct ComputeとNvidia Cudaのサンプル実装が公開されています。

1) Nvidia Cuda SDK sample
http://developer.download.nvidia.com/compute/cuda/sdk/website/samples.html#bitonic

2) DirectX SDK DX11 Direct Compute sample
http://msdn.microsoft.com/en-us/library/ee416561%28VS.85%29.aspx

自分のbitonic sortデモのバイナリとソースコードは記事の最後の方に置いています。

Bitonic Sort Demoの動画

DirectX11ハードがない人用にbitonic sortデモの動画をyoutubeにアップしました。ランダム化されたunsigned longをメンバーとして持つStructuredBufferが昇順にソートされ、同じデータがその後、降順にソートされます。再帰版も実装されていますが、動画のデモではloop版のbitonic sortが利用されています。

Bitonic Sort情報サイト

もうすでにネットにはbitonic sortに関する情報を教えてくれる、いいサイトが複数あります。下のサイトは特にお薦めです。

1. http://www.t-pot.com/program/90_BitonicSort/index.html
t-potのbitonic sortサンプルです。サンプルではpixel shaderを利用してbitonic sortが実装されています。bitonic sortアルゴリズムの説明が図解付きで分かりやすいです。

2. http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
t-potでも紹介されていますが、bitonic sortアルゴリズムを詳しく説明しています。

3. http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm
自分のデモはこのサイトの説明とサンプルコードをベースに実装しました。再帰版とループ版のbitonic sortが分かりやすく、丁寧に説明されています。DirectX SDKの DX11 compute shader bitonic sortサンプルのbit演算の意味を最初よく理解できなかったけど、このページの説明を読んで大分、分かるようになりました。

Bitonic Sortソースコード

// loop from Merge( 2 ) to Merge( nCount )
for( int nMergeSize=2; nMergeSize<=nCount; nMergeSize=nMergeSize*2 )
{
// Merge( nCount ) requires log2( nCount ) merges. Merge( nCount/2 ) -> Merge( 2 )
for( int nMergeSubSize=nMergeSize>>1; nMergeSubSize>0; nMergeSubSize=nMergeSubSize>>1 )
{
// compare and swap elements
for( int nElem=0; nElem<nCount; ++nElem )
{
int nSwapElem = nElem^nMergeSubSize;
// check to make sure to only swap once
if( nSwapElem > nElem )
{
// sort in increasing order
if ( ( nElem & nMergeSize ) == 0 && m_data[ nElem ]>m_data[ nSwapElem ] ) {
Swap( nElem, nSwapElem );
}
// sort in descending order
if ( ( nElem & nMergeSize ) != 0 && m_data[ nElem ]<m_data[ nSwapElem ] ) {
Swap( nElem, nSwapElem );
}
}
}
}
}

bitonic sortデモのloop版のソースから抜粋です。３重にネストされたループでbitonic sortが実装されています。昇順にデータがソートされます。

Bitonic Sortのオーダー

Big-O記法のオーダー

bitonic sortのBig-O記法のオーダーは
$O(n \cdot log_{2}(n)^{2})$
です。

漸化式
bitonic sortの漸化式は
$T(n) = log_{2}(n)+T(n/2)$
です。

漸化式を展開すると
$T(n) = log_{2}(n)+log_{2}(n/2)+log_{2}(n/4)+log_{2}(n/8)+\ldots+1$
になり

logの基本的性質のe.g. $log_{2}(n/2)=log_{2}(n)-log_{2}(2)=log_{2}(n)-1$ を適用すると
$T(n) = log_{2}(n)+log_{2}(n)-1+log_{2}(n)-2+log_{2}(n)-3+\ldots+1$
になり

最後に等差級数の式を適用すると
$T(n) = \frac{log_{2}(n)\cdot(log_{2}(n)+1)}{2}$
になります。

漸化式からBig-O記法のオーダーへ
上の漸化式はコード上では外ループ２つの処理に相当します。これに加えて、全データに対して比較を行う内部のループがあるので、漸化式のオーダーがデータ数のnで乗算され、bitonic sortのオーダーは
$O(n \cdot log_{2}(n)^{2})$
になります。

Bitonic Sortアルゴリズム

Bitonic Sortアルゴリズム自体の説明は上のBitonic Sort情報サイトを見てください。

Bitonic Sortのパラレリズム

ループ版bitonic sortの一番内側のループで比較とスワップされる対象データは完全に独立しています。扱うデータに依存関係がないので、この部分の比較とスワップ処理を別スレッドで並列に実行する事が可能です。Nvidia CudaやDirectX SDKのbitonic sortサンプルでは、この部分の処理をgpuスレッドで並列化しています。分かりやすい並列化対象箇所が存在しますが、GPGPUでの実際のbitonic sort実装はgpu thread groupが同時にアクセス可能なshared memoryに比較とスワップ対象のデータが乗らない可能性がある事によって、複雑になってしまいます。同じthread groupに所属している場合のみ、同じshared memoryにアクセスする事が可能ですが、DirectX10クラスのcompute shader 4_xでは一つのthread groupに最大768個のthreadのみが所属する事が可能で、DirectX11クラスのcompute shader 5_0では一つのthread groupに最大1024個のthreadのみが所属する事が可能です。DirectX SDKのbitonic sortサンプルでは、常に比較とスワップ対象が同じ共有メモリに存在するように、データ配列を前処理のcompute shaderで転置する事で、実装を実現しています。

Bitonic Sortデモ

自分のDirectX11を利用したcpu版bitonic sortデモの簡単な説明です。再帰版とループ版の両方のbitonic sortを実装しました。実装はhttp://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htmの分かりやすい説明を参考に行いました。
DirectX11で新しく登場したStructuredBufferにデータを保存してソートしていますが、中間テクスチャに転送しなくても、直接StructuredBufferの内容をPixel Shaderが読み込み、データを描画する事が可能でした。ページの頭の方に表示されている動画はこのデモの動画です。

Source Code & Binary
http://yakiimo3d.codeplex.com/releases/view/41051

最後に

Yakiimo3D初のDirectX 11記事でした。compute shader版のbitonic sortの実装も大方終わっているので、いつか記事にしてサイトにアップしたいです。Thanks for reading!

. This entry was posted on Wednesday, December 30th, 2009 at 2:25 PM and is filed under Demo, DirectX11. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Yakiimo3D