技術

バイトニックソート

この記事に関連するかもしれない記事

GPUでソートを行う必要があり、GPUソートにおける代表格であるバイトニックソートについて調べた。

ググってみると色んなサイトにソースやアルゴリズムの図が載ってるけど、いまいちよく解らない。
図を見ると概念レベルの事はすぐ分かるけど、図というものの宿命としてそのスペースが限られてるためか、どこの図も要素数8個とかで少なすぎて、要素数を2^nに抽象化した際のアルゴリズムをイメージしづらい。
あと、処理の流れの図が、前半と後半で分けてあって、アルゴリズムが大きく分けて2フェーズからなると勘違いしやすい図も多い。
いやまぁこれはあくまでも私の頭の問題ですけどね。

個人的に一番分かりやすかったのは米Wikipediaのバイトニックソートのページ
ここにも図が載ってるけど、分かりやすかったのは図ではなくて、その下に載ってるPythonのソース。

しかしそのソース、純粋なアルゴリズムの理解にはかなり役立つとはいえ、バリバリ再帰つかってるし、リストを連結したりしてるから、GPUだとどんな流れで処理すればいいのかということが分かりにくい。

ということで、まず再帰とリストの連結を取り除いたバージョンを書いてみて、さらにそこからGPUだとこんな感じになるよねというバージョンを書いてみた。
(ソースは本文の最後に載せてます。)

以下ソースの解説。

WikipediaBitonicSorter がWikipediaに載ってたソースをクラス化したもので、 MyFirstBitonicSorter がその名のとおり私が最初に書いたバイトニックソート(再帰とリストの連結なし)で、 GPULikeBitonicSorter がGPUだとこんな処理の流れになるよねバージョンのバイトニックソートである。

もちろん「GPU Like」という事で実際はCPUで処理を行うけど、同じような処理をCUDAやらOpenCLやらOpenGL向けに書けばちゃんと動くと思う。
ただし、共有メモリを使ったり、メモリアクセスをコアレッシングしたり、スレッドの分岐方向をなるべく揃えたりするような工夫はしてないので、このままGPUに持って行っても性能は出し切れないと思う。
そういう最適化は実際にGPUに持っていった後しかできない。

今回のソースはCPUで動作するので速度を測っても仕方ないんだけど、一応速度を測るようにした。
うちの環境では、要素数 1048576 (1024 * 1024) でどれも3分前後かかる中、組み込み関数のsorted(中身はCで書かれたクイックソートかな?)は2秒弱となかなかのタイムだった。
実際にGPUに持って行ってどのくらいのタイムが出るかそのうち試したい。

import random<br />
import timeit</p>
<p>class WikipediaBitonicSorter(object):<br />
    def __init__(self):<br />
        pass</p>
<p>    def bitonic_sort(self, data):<br />
        self.comparison_count = 0<br />
        self.swap_count = 0<br />
        return self.__bitonic_sort(True, data)</p>
<p>    def __bitonic_sort(self, up, x):<br />
        if len(x)&lt;=1:<br />
            return x<br />
        else:<br />
            first = self.__bitonic_sort(True,x[:len(x)/2])<br />
            second = self.__bitonic_sort(False,x[len(x)/2:])<br />
            return self.bitonic_merge(up,first+second)</p>
<p>    def bitonic_merge(self, up, x):<br />
        # assume input x is bitonic, and sorted list is returned<br />
        if len(x) == 1:<br />
            return x<br />
        else:<br />
            self.bitonic_compare(up,x)<br />
            first = self.bitonic_merge(up,x[:len(x)/2])<br />
            second = self.bitonic_merge(up,x[len(x)/2:])<br />
            return first + second</p>
<p>    def bitonic_compare(self, up, x):<br />
        dist = len(x)/2<br />
        for i in xrange(dist):<br />
            self.comparison_count += 1<br />
            if (x[i] &gt; x[i+dist]) == up:<br />
                self.swap_count += 1<br />
                x[i], x[i+dist] = x[i+dist], x[i] #swap</p>
<p>class MyFirstBitonicSorter(object):<br />
    def __init__(self):<br />
        pass</p>
<p>    def bitonic_sort(self, data):<br />
        self.comparison_count = 0<br />
        self.swap_count = 0</p>
<p>        self.data = data<br />
        chunk_size = 2<br />
        while chunk_size &lt;= len(self.data):<br />
            for chunk_index in xrange(len(self.data) / chunk_size):<br />
                _from = chunk_size * chunk_index<br />
                _to = _from + chunk_size - 1<br />
                self.sort(chunk_index % 2 == 0, _from, _to)<br />
            chunk_size *= 2<br />
        return self.data</p>
<p>    def sort(self, up, _from, _to):<br />
        chunk_size = _to - _from + 1<br />
        if chunk_size == 2:<br />
            self.compare(up, _from, _to)<br />
        else:<br />
            split = 1<br />
            while split &lt; chunk_size:<br />
                sub_chunk_size = chunk_size / split<br />
                for sub_chunk_index in xrange(split):<br />
                    for i in xrange(sub_chunk_size / 2):<br />
                        a = sub_chunk_size * sub_chunk_index + i + _from<br />
                        b = a + sub_chunk_size / 2<br />
                        self.compare(up, a, b)<br />
                split *= 2</p>
<p>    def compare(self, up, a, b):<br />
        self.comparison_count += 1<br />
        if (self.data[a] &gt; self.data[b]) == up:<br />
            self.swap_count += 1<br />
            self.data[a], self.data[b] = self.data[b], self.data[a]</p>
<p>class GPULikeBitonicSorter(object):<br />
    def __init__(self):<br />
        pass</p>
<p>    def bitonic_sort(self, data):<br />
        self.comparison_count = 0<br />
        self.swap_count = 0<br />
        self.launch_kernel_count = 0</p>
<p>        chunk_size = 2<br />
        while chunk_size &lt;= len(data):<br />
            sub_chunk_size = chunk_size<br />
            while sub_chunk_size &gt; 1:<br />
                self.launch_kernel(data, chunk_size, sub_chunk_size)<br />
                sub_chunk_size /= 2<br />
            chunk_size *= 2<br />
        return data</p>
<p>    def launch_kernel(self, data, chunk_size, sub_chunk_size):<br />
        self.launch_kernel_count += 1<br />
        for i in xrange(len(data) / 2):<br />
            self.kernel(data, len(data), chunk_size, sub_chunk_size, i)</p>
<p>    def kernel(self, data, data_size, chunk_size, sub_chunk_size, thread_index):<br />
        half_chunk_size = chunk_size / 2<br />
        chunk_index = thread_index / half_chunk_size</p>
<p>        half_sub_chunk_size = sub_chunk_size / 2<br />
        sub_chunk_index = thread_index / half_sub_chunk_size</p>
<p>        up = chunk_index % 2 == 0<br />
        a = sub_chunk_size * sub_chunk_index + thread_index % half_sub_chunk_size<br />
        b = a + half_sub_chunk_size</p>
<p>        self.comparison_count += 1<br />
        if (data[a] &gt; data[b]) == up:<br />
            self.swap_count += 1<br />
            data[a], data[b] = data[b], data[a]</p>
<p>if __name__ == &quot;__main__&quot;:<br />
    #random.seed(12345)</p>
<p>    data_size = 128 * 128<br />
    trial_count = 3</p>
<p>    data = [random.randint(0, data_size) for i in xrange(data_size)]<br />
    results = []<br />
    times = []</p>
<p>    wbs = WikipediaBitonicSorter()<br />
    times.append(<br />
        timeit.timeit(<br />
            setup = 'from __main__ import results, data, wbs',<br />
            stmt = 'results.append(wbs.bitonic_sort(data[:]))',<br />
            number = trial_count<br />
        )<br />
    )<br />
    print 'wbs.comparison_count = %d' % wbs.comparison_count<br />
    print 'wbs.swap_count = %d' % wbs.swap_count<br />
    print 'wbs time: %f sec' % times[-1]<br />
    print</p>
<p>    mfbs = MyFirstBitonicSorter()<br />
    times.append(<br />
        timeit.timeit(<br />
            setup = 'from __main__ import results, data, mfbs',<br />
            stmt = 'results.append(mfbs.bitonic_sort(data[:]))',<br />
            number = trial_count<br />
        )<br />
    )<br />
    print 'mfbs.comparison_count = %d' % mfbs.comparison_count<br />
    print 'mfbs.swap_count = %d' % mfbs.swap_count<br />
    print 'mfbs time: %f sec' % times[-1]<br />
    print</p>
<p>    glbs = GPULikeBitonicSorter()<br />
    times.append(<br />
        timeit.timeit(<br />
            setup = 'from __main__ import results, data, glbs',<br />
            stmt = 'results.append(glbs.bitonic_sort(data[:]))',<br />
            number = trial_count<br />
        )<br />
    )<br />
    print 'glbs.comparison_count = %d' % glbs.comparison_count<br />
    print 'glbs.swap_count = %d' % glbs.swap_count<br />
    print 'glbs.launch_kernel_count = %d' % glbs.launch_kernel_count<br />
    print 'glbs time: %f sec' % times[-1]<br />
    print</p>
<p>    times.append(<br />
        timeit.timeit(<br />
            setup = 'from __main__ import results, data',<br />
            stmt = 'results.append(sorted(data))',<br />
            number = trial_count<br />
        )<br />
    )<br />
    print 'builtin function sorted time: %f sec' % times[-1]<br />
    print</p>
<p>    for i in xrange(len(results) - 1):<br />
        if results[i] != results[i+1]:<br />
            print 'Result has a difference.'

コメント

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください