FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://sites.google.com/site/fpgadevelopindex/

高位合成でソーティングネットワークを試す(バイトニックソートの合成試行)

バイトニックソートは、マージソートの並列と言われており、並列プログラミングにおいては良く使われている(らしい)。 前回の単純選択ソートは、シーケンシャルに最小値を選んで、それを順番に交換していくのだった。 では、ソフトウェアの世界において並列化がし易いと言われるバイトニックソートを高位合成するとどうなるのだろう?

C言語におけるバイトニックソートの実装

バイトニックソートの本体

WikipediaでのJavaの実装を参考にした。サブルーチンが呼ばれないように、一つのルーチンにまとめている。

Bitonic sorter - Wikipedia, the free encyclopedia

#define DATA_NUM 128

void bitonic_sort (const int logn, int array[DATA_NUM]) {
  for(int p = 0;p < logn; p++) {
    for(int q = 0;q <= p; q++) {
      int d = 1 << (p-q);
      for(int i = 0; i < DATA_NUM; i++) {
        int up = ((i >> p) & 2) == 0;
        if ((i & d) == 0 && (array[i] > array[i | d]) == up) {
          int t = array[i]; array[i] = array[i | d]; array[i | d] = t;
        }
      }
    }
  }
}

テストパタンの実装

これは前回の単純選択ソートの実装とほとんど同一だ。printfでソート結果を確認してみよう。

#include <stdio.h>
#include <stdlib.h>

#define MAX_DATA 128
#define LOG_N    7

int main(void)
{
    int i;
    int x[MAX_DATA];

    for(i = 0; i < MAX_DATA; i++) {
        x[i] = rand();
    }

    printf("Before Sorting\n");
    for (i = 0; i < MAX_DATA; i++)
        printf("%d\t", x[i]);

    bitonic_sort (LOG_N, x);

    printf("After sorting\n");
    for (i = 0; i < MAX_DATA; i++)
        printf("%d\t", x[i]);

    return 0;
}

Vivado-HLSで合成してみる

VivadoHLS 2015.4で合成してみる。ターゲットはZynq ZedBoardだ。

f:id:msyksphinz:20151215014214p:plain

選択ソートと比較すると、その使用リソース量は多めだ。

f:id:msyksphinz:20151215014258p:plain

サイクル数の計測

[Run C/RTL Cosimulation]で、そのサイクル数を測定してみよう。

128個の整数値をソーティングしたときの結果だ。

種類 サイクル数
選択ソート 16892
Bitonicソート 9031

バイトニックソートの方が半分程度高速だね。

ここまでの計測で本日は終了。次は、実際にどのような構成になっているのか見てみよう。