全文 - TRICK

Technical Reports on Information and
Computer Science from Kochi
Vol. 4 (2012), No. 9
GPGPU による並列ソートアルゴリズムの一手法
A Parallel Sorting Algorithm for GPGPU
大菊
祥子 1）
豊永
昌彦 2）
Sachiko Ogiku 1）Masahiko Toyonaga 2）
1） 高知大学理学部
2)高知大学 情報講座
Information Science Division, Faculty of Science, Kochi University
あらまし
本論文は
本論文は，GPGPU を用いた奇偶転置
いた奇偶転置ソート
奇偶転置ソートについ
ソートについ
て評価実験を
評価実験を行い，その後更
その後更なる
後更なる高
なる高速化と
速化と大規模化を
大規模化を
目指して
目指してハイブリッド
してハイブリッド化
ハイブリッド化を提案し
提案し，その効果
その効果の
効果の評価実
験について述
について述べたものである．
べたものである．奇偶転置ソート
奇偶転置ソートは
ソートは，独
立した 2 組を扱うため GPGPU による並列処理
による並列処理に
並列処理に向く．
実験で
実験でレコード数
レコード数 5000 のソートでは
ソートでは単一
では単一スレッド
単一スレッドに
スレッドに
比べて，
べて，多スレッドで
スレッドで約 13 倍の高速化が
高速化が確認できた
確認できた．
できた．
大規模データ
大規模データに
に
対応するため
対応
するため，
，
Shared
メモリを
メモリ
を 使っ
データ
するため
た 高速化と
高速化 とホストとの
ホストとの連携化
との連携化による
連携化 によるマージソート
によるマージソートを
マージソートを
導入することで
導入することで 1,000,000 レコードまで
レコードまで処理
まで処理を
処理を拡張し
拡張し
たところ，
たところ，1,000,000 レコードで
レコードで，ホスト単体処理
ホスト単体処理に
単体処理に
比べて 61 倍の多大な
多大な高速化を
高速化を確認できた
確認できた．
できた．
高速化が確認できた．大規模データに対応するため，
Shared メモリを使った高速化とホストとの連携化に
よるマージソートを導入することで 1,000,000 レコー
ドまで処理を拡張したところ，1,000,000 レコードで，
ホスト単体処理に比べて 61 倍の多大な高速化を確認
できた．
本論文の以降の構成は，第 2 章で準備として用語説
明とソートについて述べる．第 3 章では並列化した奇
偶ソートについて説明する．第 4 章では 3 章で述べた
奇偶転置ソートをさらに高速化，大規模データで扱え
るようにするためにホストとデバイスの連携化を行
った，ハイブリッド化したソートについて述べる．
2．
． ソートについて
ソートについて
キーワード：
，Shared メモ
キーワード：奇偶転置ソート
奇偶転置ソート，
ソート，GPGPU，
リ，スレッド
定義
ソート処理とは例えば与えられた N 個のレコード
で構成されているデータについて，ソートキーに基づ
いてアルファベット順などの一定の基準でレコード
を並べ替える処理をさす．例えばアルファベット昇順
に並び替える処理を例にとれば，各データレコードに
格納されているソートキーが数字ならば 0，1，2，3，
と小さい値から大きい値へデータレコードを順次並
べ変えていく処理に相当する．降順とは，昇順の逆で，
ソートキーに基づいて大きい値から小さい値の順に
データレコードを並び替える処理である．
1．
． はじめに
情報化社会の発達により，インターネット上で膨大
なデータを扱うようになってきた．2011 年 2 月の段
階で南カリフォルニア大学の研究チームは，全世界の
情報量は 295 エクサバイトに達しており，そのうち
94%はデジタル化されている[B3]．今後，クラウド化
などが進展することが予想されており，ネットで扱う
情報量は更なる増加があると予想される．
データ量増加に伴い，従来から利用されてきたデー
タ検索や情報処理を短時間で完了させることが難し
くなる．特に，多大なデータから「キーワード」によ
りデータを効率よく収集加工するための検索やデー
タベースでは，それらの高速処理が必要になる．これ
らの処理の基本はソート技術が鍵である．
近年グラフィック処理プロセッサを汎用計算に用
いる GPGPU が普及している．そのため並列処理を行
う環境が安価で手に入るようになってきた．
本論文は，GPGPU を用いて並列化を行なった奇偶
転置ソートについて評価実験を行い，その後更なる高
速化と大規模化を目指してハイブリッド化を提案し，
その効果の評価実験について述べたものである．奇偶
転置ソートは，独立した 2 組を扱うため GPGPU によ
る並列処理に向く．実験でレコード数 5000 のソート
では単一スレッドに比べて，多スレッドで約 13 倍の
さまざまなソート
さまざまなソート法
ソート法
ソート処理はさまざまなアルゴリズムにおいて前
処理として利用される基本的な処理である．そのため
古くから様々なアルゴリズムが考案されている．例え
ばデータベースなどにおける大量データの処理にお
いては，あらかじめソート処理によりそれぞれのデー
タレコードを昇順あるいは逆順に並べる処理がされ
る．従って，ソート処理の高速化は，さまざまな情報
処理の高速化の鍵となっている．
よく知られたソート法としては，クイックソートが
あげられる．クイックソートはデータの比較と交換回
数が非常に少ないのが特徴で，一般的にランダムに散
らばっているデータに対して，最も効率良く並べ替え
を実行する．クイックソートでは，まず始めに，「ピ
1
ボット」と呼ばれるデータ値を決定する．この値は，
データ全体を 2 つに分割するときに使われる．ピボッ
トは，分割が均等に行われるように選ぶのが望ましい
が，その選択に時間をかけると，かえって並べ替えの
時間を長くしてしまう．ピボットの値とそれぞれの値
を比較して行き，よりも値が小さければその前（配列
のインデックスの小さい方）に，大きければその後ろ
（配列のインデックスの大きい方）に値を格納してい
く．ピボットの値とそれぞれの値を比較して行き，ピ
ボットよりも値が小さければその前（配列のインデッ
クスの小さい方）に，大きければその後ろ（配列のイ
ンデックスの大きい方）に値を格納していく．分割さ
れたそれぞれのデータに対して，同様の処理を繰り返
し行うとソートが完了する．
ラディクスソートは整数で，なおかつ値のデータが
入っていない場合にソートをおこなうことができる．
格納されているデータの値を配列番号に格納するこ
とでソートを完了することができる．この際 O(N)と
なり高速にソートを終えることができる．
先頭まで
先頭まで繰
まで繰り返す
Step1-1．
．以下の
以下の操作を
操作を N-1 回配列の
回配列の最後か
最後か
ら配列の
配列の先頭まで
先頭まで繰
まで繰り返す
Step1-1-1．
．i と i+1 について比較
について比較をする
比較をする
Step1-1-2 ． 比 較 の 結 果 が
data[i]>data[i+1]のとき
のとき交換
のとき交換する
交換する
Step1-2．
．先頭の
先頭の値を固定して
固定して範囲
して範囲を
範囲を狭める
Step2. 終了する
終了する
図 2.3.2 バブルソートの
バブルソートのアルゴリズム
バブルソート法
バブルソート法
バブルソートは，隣り合う二つのデータを比較して，
前の要素の方が大きかったら交換する．データ列の後
方から前方へ向かって全てのデータについて比較及
び交換を行うと，最も小さいデータが先頭にくる．2
回目のソートの対象となるのは 2 番目以降のデータ
である．このソートで，2 番目のデータの位置が決ま
る．このように要素の比較及び交換後方から前方に向
かって繰り返すことで，ソートが完成する．先頭から
要素の位置が固定されていく．この過程が，泡が浮か
び上がって行く様子に似ているので，バブルソートと
名付けられた．バブルソートはソート前のデータの並
びに関係なく， O(N2)になる．
アルゴリズム
アルゴリズムを図 2.3.2 に示し，各ステップの動作
を説明する．まず，Step0 で配列にソートを行うデー
タをいれ，要素数を N とする．Step1-1 では全ての要
素に関して隣接する要素を比較し，小さい要素を小さ
い配列の番号になるように，交換を行う．Step1-1-1
と Step1-1-2 の処理の繰り返しが終了すると配列の先
頭の値が決定する．そのため Step1 で繰り返し行う際
に隣接する要素の比較および交換を行う範囲を狭く
することができる．その比較を行う範囲を狭くする処
理が Step1-2 である．Step1-2 で範囲を限定しながら
Step1-1 の処理を行うと比較を行わなければならない
範囲が狭くる．1 回目 Step1-1-1 と Step1-1-2 の処理を
N-1 回，2 回目は N-2 回，三回目は N-3 回と範囲を狭
くしながら処理を行うと N-1 回目の処理で N-(N-1)回
になる．
このとき処理を終了する Step2 の処理をする．
Step0．
．要素数 N とする
Step1．
．以下の
以下の操作を
操作を N-1 回配列の
回配列の最後から
最後から配列
から配列の
配列の
2
動作例
バブルソートの動作例を図 2.3.3 に示した．上段の
配列は比較および交換の処理を終えたあとの状態を
示しており，下段の配列の横の矢印は比較する配列の
位置を示している．
4 個のデータをバブルソート手法を用いてソート
する過程を説明する．まず，配列の最後から前に向か
って順々に比較を行う．このとき目的としている順番
に並んでいない場合には，交換を行う．ここでは N=4
で一番小さい値を固定するために比較および交換の
処理を N-1 回，つまり 3 回行う．次に 2 番目に小さい
値を固定するために，比較および交換を N-2 回，つま
り今回の場合には 2 回行う．このとき一番小さな値が
格納される場所には既に一番小さい値が格納されて
いるので，繰り返し処理を行う際には比較をする必要
はない．このように処理を単一に行なっていくとソー
トが完了する．
図 2.3.3 バブルソートの
バブルソートの動作例
奇偶転置ソート
奇偶転置ソート法
ソート法
奇偶転置ソートでは奇数と偶数のレコードのペア
の比較を行なっていく．そのとき，奇数が小さい場合
のペアを奇偶番目のペアとして，偶数が小さい場合の
ペアを偶奇番目のペアとする．まず，奇偶番目のペア
で比較を行い，目的としている順番に並んでいない場
合には並び替えを行う．奇遇番目のペアの比較および
交換の処理を順々に行い，配列の最後のペアまで行な
う．続いて，偶奇番目の比較および交換の処理を順々
に行い，配列の最後のペアまで繰り返す．この奇偶番
目の処理を配列の最後のペアまでと偶奇番目の処理
を配列の最後のペアまで行うことを繰り返していく
とソートが終了する．奇偶転置ソートにはフラグを入
れており，並び変えが行われた場合にはフラグをたて
る．フラグの変化がない場合には繰り返しの処理を終
了する．このとき配列に格納されているソートキーが
最悪の順番に並んでいる場合には，O(N2)になる．
合し 1 つにするときに用いられる．マージは，データ
列の先頭同士を比べ小さい方をデータ列から取り出
し，別のデータ列に格納する．また，高速化の手法と
して，2 つの配列のうち片方が配列の最後まで比較お
よび格納が終わった場合，残った配列に格納されてい
る値を比較の処理を行わずに格納することができる．
アルゴリズム
奇偶転置ソートのアルゴリズムを図 2.4.2 に示し，
各ステップの動作を説明する．
アルゴリズム
マージソートのアルゴリズムを図 2.5.2 に示し，各
ステップの動作を説明する．
Step0．
．Flag を 0 とする 要素数 N とする
Step1．
．以下の
以下の操作を
操作を i<N-1 まで繰
まで繰り返す
Step1-1．
．奇数と
奇数と奇数+1
奇数 について比較
について比較をする
比較をする
Step1-2．
．比較の
のとき交換
比較の結果が
結果が data[i]<data[i+1]のとき
のとき交換する
交換する
Step1-3．
．交換が
交換が起こった場合
こった場合のみ
場合のみ flag を 1 にする
Step2．
．以下の
以下の操作を
操作を i<N-1 まで繰
まで繰り返す
Step2-1．
．偶数と
偶数と偶数+1
偶数 について比較
について比較をする
比較をする
Step2-2．
．比較の
のとき交
比較の結果が
結果が data[i]<data[i+1]のとき
のとき交換する
Step2-3．
．交換が
交換が起こった場合
こった場合のみ
場合のみ flag を 1 にする
Step3．
．Step1 と Step2 を交換が
交換が行われなくなるまで繰
われなくなるまで繰り返
し，交換が
交換が行われなくなれば終了
われなくなれば終了する
終了する
図 2.4.2 奇偶転置ソート
奇偶転置ソートの
ソートのアルゴリズム
Step0．
．データを
データを分割する
分割する(例
する 例：二等分)
二等分
Step1．
．分割した
分割したデータ
データをそれぞれ
をそれぞれソート
したデータをそれぞれソートする
ソートする
Step2．
．二つの分割
つの分割された
分割されたデータ
されたデータ列
データ列を結合する
結合する
Step3．
．終了する
終了する
図 2.5.2 マージソートの
マージソートの動作例
マージソートの処理で重要になるのは Step2 に示し
た分割された配列を結合する処理である．ソート済み
の 2 つの配列と結果を格納できる配列があるとする．
分割されたデータを結合するとき，分割された 2 つの
配列はそれぞれソート済みなので，配列の一番小さい
データ決める時，二つの配列の一番小さい配列に格納
された要素を比較する．比較で小さいと判断された場
合には結果を格納できる配列に要素を格納する．次に
先ほど格納しなかった配列の要素と，格納した配列の
次の要素を比較し，小さい配列の要素を格納する．こ
の処理では 2 つの配列を比較して小さい要素を格納
する．格納した配列は配列の番号を 1 つ大きくする．
片方の配列が，配列の最後まで比較し，格納し終わっ
た場合には，もう片方の配列を結果の配列の続きに比
較をすることなくコピーすることができる．2 つの配
列の要素を全て結果を格納できる配列に格納すると，
処理を終了する．
動作例
奇偶転置ソートの動作例を図 2.4.3 に示した．上段の
配列は比較および交換の処理を終えたあとの状態を
示しており，下段の配列の横の矢印は比較する配列の
位置を示している．
図 2.4.3
奇偶転置ソート
奇偶転置ソートの
ソートの動作例
動作例
マージソートの動作例を図 2.5.3 に示した．黒のば
つ印は値が格納されて終わったことを意味し，赤丸で
囲まれた値は残った値を意味する．これから各ステッ
プの動作を説明する．まず，右側の配列と左側の配列
の 2 つのソート済みの配列とマージソートの結果を
格納できる配列が用意する(図 2.5.3 の Step1)．続いて
2 つのソート済みの配列の先頭である右側の配列[B1]
に格納されている 1 と左側の配列[B1]に格納されてい
る 2 を比較し，小さい値 1 を結果を格納する配列に格
納する(図 2.5.3 の Step2)．Step3 で左側の配列[B1]の値
1 の上にばつ印を示したのは，格納が終わり比較の対
象から外れたことを意味している．左側の配列[B1]
は格納が終了したので左側の配列[B2]に格納されて
いる 4 と右側の配列[B1]に格納されている 2 の比較を
行い，小さい値 2 を結果を格納する配列に格納する(図
2.5.3 の Step3)．右側の配列[B1]に格納されていた 2 も
4 個のデータを奇偶転置ソート手法でソートする
過程を説明する．まず，奇数レコードと偶数レコード
の比較を行う．ここでは，配列の 1 に格納されている
3 と配列 2 に格納されている 2 の比較を行い昇順に並
んでいないので並び替えを行う．次に配列 3 に格納さ
れている 4 と配列 4 に格納されている 1 の比較を行い
昇順に並んでいないので並び替えを行う．このように
奇偶番目のレコードの並び替えを配列の最後まで行
なったあと，偶奇番目のレコードの比較と並び替えを
行う．続いて配列 2 に格納されている 3 と配列 3 に格
納されている 1 の比較を行い昇順に並んでいないの
で並び替えを行う．このように処理を単一に行なって
行くとソートが完了する．
マージソート
マージとは，「併合する」，「合併する」という意味
である．マージソートは整列してある 2 つの配列を併
3
格納されたので，比較の対象から外れる．左側の配列
[B2]に格納されている 4 と右側の配列[B2]に格納され
ている 3 を比較し，小さい値 3 を結果を格納する配列
に格納する(図 2.5.3 の Step4)．右側の配列[B2]に格納
されていた 3 も格納されたので，比較の対象から外れ
る．このとき右側の配列がすべて結果を格納する配列
に格納し終わった．そのため赤丸で囲んである，左側
の配列[B2]に格納されていた 4 は，結果を格納する配
列に右側の配列と比較することなく，結果を格納する
配列に格納することができる(図 2.5.3 の Step5)．この
ように片方の配列が最後まで格納し終わると，残った
配列は比較せずにそのまま順々元のままソートされ
たものを移す処理だけですませることができる．
ホストとデバイスの関係を図 3.1.2 に示し，処理の流
れを説明する．まずホスト側で，ソートキーや外部へ
の出力を設定する．デバイス側はソートデータを受け
取り並列に処理を行う．奇偶番目のペアの処理を行う
StepE と偶奇番目のペアの処理を行う StepO を 2 つの
独立したカーネルで行なった．
図 3.1.3
図 2.5.3
マージソートを
マージソートを利用した
利用した大規模対応
した大規模対応
並列化した奇偶ソートを高速化するために Global
メモリよりも高速な Shared メモリを利用することを
検討した．その際 Shared メモリでは同一ブロック内
のスレッドからしかアクセスできないことが問題に
なってくる．そのため分割することによって Shared
メモリを効率よく利用できるように考慮した．まず，
ソートを行うデータを分割する．そして分割されたデ
ータをそれぞれ別のブロックに割り付けしデバイス
で奇偶転置ソートをする．その後，データを結合する
ためにホストで，マージソートを行う．このようにホ
ストとデバイスで役割を分担して，分割したものをソ
ートすることで，並列に処理を行えるというメリット
を取り入れながら，扱えるデータが限られ，シンクロ
が問題になるというデメリットを克服できる．
マージソートの
マージソートの動作例
3．
． 奇偶転置による
奇偶転置による並列
による並列ソート
並列ソート法
ソート法
アルゴリズム
奇偶転置ソートのアルゴリズムを並列化した場合，
奇偶転置ソートとはどのように異なっているかを図
3.1.1 に示し，各ステップの動作を説明する．各ステ
ップは図 2.4.2 に示した奇偶転置ソートとほぼ同じで
ある．Step1 の各処理と Step2 の各処理を並列に一度
に行う．奇数と奇数+1 の比較および交換の処理を，
配列の全てのペアについて一度に行う処理 StepE と
し，偶数と偶数+1 の比較および交換の処理，配列の
全てのペアについて一度に行う処理を StepO とよぶ
ことにする．
アルゴリズム
ハイブリッド化した場合の処理の流れを図 4.1.1 に
示し，各ステップの動作を説明する．はじめにホスト
でデータの分割を行う．分割されたデータをホストか
らデバイスに転送して Step1 と Step2 の各処理をデバ
イスで行う．Step1 と Step2 の繰り返しの処理を Step3
で行う．Step1 から Step3 の処理は並列化を行なった
奇偶ソートの処理と同じである．Step3 が終了すると，
分割されたかたまりごとにソートが完了した状態に
なる．Step3 が終了するとデバイスで行う処理を終了
する．デバイスからホストにデータの転送を行い，並
列化を行なった奇偶ソートが分割されたかたまりご
とに終了したデータをホストが加工できるようにす
る．ホストではかたまりごとにソートされたデータを
マージソートをすることで併合する．ここでは地道に
1 つずつ順番に併合していく方法を検討した．分割さ
れたデータが 1 つに併合したら，終了する．
Step0．
．Flag を 0 とする 要素数 N とする
Step1．
．以下の
以下の操作を
操作を行う
Step1-1．
．奇数と
奇数と奇数+1
奇数 について比較
について比較をする
比較をする
Step1-2．
．比較の
のとき交換
比較の結果が
結果が data[i]<data[i+1]のとき
のとき交換
する
Step1-3．
．交換が
交換が起こった場合
こった場合のみ
場合のみ flag を 1 にする
Step2．
．以下の
以下の操作を
操作を行う
Step2-1．
．偶数と
偶数と偶数+1
偶数 について比較
について比較をする
比較をする
Step2-2．
．比較の
のとき交換
比較の結果が
結果が data[i]<data[i+1]のとき
のとき交換
する
Step2-3．
．交換が
交換が起こった場合
こった場合のみ
場合のみ flag を 1 にする
Step3．
．Step1 と Step2 を交換が
交換が行われなくなるまで繰
われなくなるまで繰
り返し交換が
交換が行われなくなれば終了
われなくなれば終了する
終了する
図 3.1.1
奇偶転置
奇偶転置ソートの
ソートのホストデバイスの
ホストデバイスの構成
並列化した
並列化した奇偶転置
した奇偶転置ソート
奇偶転置ソート
ホストと
ホストとデバイスの
デバイスの構成
4
Step0．
．Flag を 0 とする 要素数 N とする
Step0-2．
．データを
データを分割する
分割する
Step1．
．以下の
以下の操作を
操作をデバイスで
デバイスで行う
Step1-1．
．奇数と
奇数と奇数+1
奇数 について比較
について比較をする
比較をする
Step1-2．
．比較の
のとき交換
比較の結果が
結果が data[i]<data[i+1]のとき
のとき交換する
交換する
Step1-3．
．交換が
交換が起こった場合
こった場合のみ
場合のみ flag を 1 にする
Step2．
．以下の
以下の操作を
操作をデバイスで
デバイスで行う
Step2-1．
．偶数と
偶数と偶数+1
偶数 について比較
について比較をする
比較をする
Step2-2．
．比較の
のとき交換
比較の結果が
結果が data[i]<data[i+1]のとき
のとき交換する
交換する
Step2-3．
．交換が
交換が起こった場合
こった場合のみ
場合のみ flag を 1 にする
Step3．
．Step1 と Step2 を交換が
交換が行われなくなるまで繰
われなくなるまで繰り返
し，交換が
交換が行われなくなればデバイス
われなくなればデバイスの
デバイスの処理を
処理を終了する
終了する
Step4．
．分割された
分割されたデータ
されたデータ列
データ列についてホスト
についてホストで
ホストでマージソート
を行い結合する
結合する
Step5．
．終了する
終了する
図 4.1.1
ハイブリッド化をしたソート結果のグラブの関数
は y=8E-07x+0.0609 を示している．このグラフの関数
の信頼性は R2=0.9996 より先ほどのホスト単体のグラ
フの関数と同様に信頼できる結果である．グラフの関
数よりハイブリッド化を行った場合の処理は O(N)で
最大レコード数の 1,000,000 まで処理を行うことがで
きているという結果が得られた．
表 4.2.2 ホスト単体
ホスト単体と
単体とホストと
ホストとデバイスを
デバイスを用いたソー
いたソー
トの実行時間比較
HOST
1000
2000
5000
10000
20000
40000
80000
100000
200000
500000
800000
1000000
ハイブリッドアルゴリズム
ハイブリッドアルゴリズム
4．
． 実験
(1) 実験環境
実験環境は，Windows7 (32b)で CPU は Intel Core
i5-760(2.8GHz)，GPGPU として GeForce GT 220 を用
い て， プロ グラ ム環 境は CUDA3.2 に よる Visual
studio8.0 の VisualC++を用いた．
スレッド数は 50，ブロック数は「データ数/スレッ
ド数/2」である．実験データは，レコード数 N=1,000
から 1,000,000 の降順のデータを用意した．
表 4.2.1
Hybrid
HOST/Hybris
0.0597
0.00
0.0634
0.00
0.0638
0.05
0.0686
0.11
0.0804
0.30
0.0954
0.85
0.1282
2.31
0.1445
3.28
0.2336
9.66
0.4731
29.33
0.7502
47.08
0.8988
61.53
0
0
0.0029
0.0077
0.0243
0.0808
0.296
0.4735
2.2569
13.8782
35.3168
55.3022
# of data vs. time
cpu/gpu time
60
HOST
HOSTandDEVICE
50
40
並列化した
並列化した奇偶転置
した奇偶転置ソート
奇偶転置ソートの
ソートの動作例
30
グラフィックカード
CPU
メインメモリ(GB)
CUDA
CUDA コア数
グラフィッククロック(MHz)
メモリクロック(MHz)
GeForce GT 220
Intel Core i5-760
2.8GHz
4
Version 3.2
48
625
1360
20
10
N
0
0
200,000
400,000
600,000
800,000
1,000,000
図 4.2.2 ホスト単体
ホスト単体と
単体とホストと
ホストとデバイスを
デバイスを用いたソー
いたソー
トの実行時間比較
(2) 実験結果と
実験結果と考察
大規模データサイズ対応のためホストとデバイス
と連携化(マージソート)で 1,000,000 レコードに対応
した．
ホスト単体での処理に比べて 1,000,000 レコードの
場合には 61 倍高速化が確認できた．レコード数 1,000
から 40,000 までのレコードではホスト単体とハイブ
リッド化したものを比較するとホスト単体で処理を
行ったほうが早いという結果が得られた．これはハイ
ブリッド化したものは処理を行うために準備する時
間がかかるためだと考えられる．図 4.3 を用いてホス
ト単体の処理とハイブリッド化した処理の O を説明
する．
ホスト単体のグラフの関数は y = 6E-11x2 + 7E-0.8 x
－ 0.0119 を示している．グラフの関数の信頼性は
R2=1 より信頼できる．グラフの関数よりホスト単体
は O(N2)であることが確認できる．
# of data vs. time
cpu/gpu time
2
HOST
Hybrid
多項式 (HOST)
線形 (Hybrid)
1.5
2
y = 6E-11x + 7E-08x - 0.0119
2
R =1
1
y = 8E-07x + 0.0609
2
R = 0.9996
0.5
0
N
0
200,000
400,000
600,000
800,000
1,000,000
図 4.3 ホスト単体
ホスト単体と
単体とホストと
ホストとデバイスを
デバイスを用いたソート
いたソート
の実行時間比較
5
5．
． まとめ
奇偶ソートで GPGPU による並列ソートの実装した．
扱えるデータは 20,000 と限られてしまう．単一スレ
ッドに比べて多数のスレッドを用いて並列化をした
場合にはレコード数 5,000 で最大 13 倍の高速化が確
認された．
レコード数 5,000 まではおよそ理想としていた
O(N)になっていることが確認できる．しかし，レコ
ード数が増えるにしたがって，O(N)から外れるとい
う結果になった．
その際，規模が大きなレコードの高速化が課題とな
る．また扱えるレコード数は 20,000 と限られている
ので大規模データへの拡張が課題となる．
そこで提案したのが，並列化した奇偶ソートを高速
化するために Global メモリよりも高速な Shared メモ
リを利用する方法である．その際 Shared メモリでは
同一ブロック内のスレッドからしかアクセスできな
いことが問題になってくる．そのため分割することに
よって Shared メモリを効率よく利用できるように考
慮した．ホストで分割を行い，デバイスで分割された
データをそれぞれ別のブロックで並列に奇偶転置ソ
ートを行う方法を提案した．デバイスで分割したデー
タを処理した後，ホストでマージソートを行い，デー
タを目的とした順番に並べた．
大規模データサイズ対応のため，ホストとデバイス
と連携化(マージソート)で 1,000,000 レコードに対応
した．ホスト単体での処理に比べて 1,000,000 レコー
ドの場合には 61 倍高速化が確認できた．ハイブリッ
ド化を行った場合の処理は O(N)で最大レコード数の
1,000,000 まで処理を行うことができているという結
果が得られた．
謝辞
本研究を科学研究費補助金（課題番号 22500049）と
して助成いただいた独立行政法人日本学術振興会に
感謝いたします．
6
参考文献
[B1]Odd-evenTranspositionSort
http://ww2.cs.mu.oz.au/498/notes/node34.html
[B2]Nvidia CUDA3.2 マニュアル
[B3] 全 世 界 の デ ー タ 量 ｜ 最 新 の 関 心 ニ ュ ー ス
http://gigazine.net/news/20110213_295exabytes/
[B4]大菊祥子, 中井駿介, 豊永昌彦，
“GP-GPU による
並列ソートアルゴリズムの評価,”1-27，平成 23 年度
電気関係学会四国支部連合大会講演論文集 (2011 年 9
月 23 日阿南高専)．
[B5]日本経済新聞記事「クラウドデータセンタ，磁気
テープ記録容量を 44 倍に」
，2010 年 1 月 22 日．