奇偶転置ソート

[←]　[↑]　[→]

---

並列ソートとしてよく知られているものに「奇偶転置ソート」がある。これは、偶数個のデータに対して

偶ペア (0,1)(2,3)...(N-2,N-1) の入替と、奇ペア　0,(1,2)...(N-3,N-2),N-1の入替を、N/2回繰り返す方法である。

ちなみに奇数個の場合は、入力データの最後尾を最大値に固定しておけばよい。

◇

この動作をすなおにCコードで書くと次のようになる。

/* sort.h*/

#ifndef SORT_H

#define SORT_H

#include <ap_int.h>

static const int N=10; // データ数(偶数であること)

typedef ap_uint<8>  dat_t;      // データ型

void sort_hls

  (dat_t din[N]         // (i) 入力データ

  ,dat_t dout[N]        // (o) 小さい順に並べ替えたデータ

  );

#endif

/* sort.cpp */

/*

 * 偶数個の配列din[N]を小さい順に並べ替えてdout[N]に出力する

 */

#include "sort.h"

void sort_hls

  (dat_t din[N]         // (i) 入力データ

  ,dat_t dout[N]        // (o) 小さい順に並べ替えたデータ

  ) {

  #pragma HLS interface ap_ctrl_none port=return

  #pragma HLS interface ap_hs port=din

  #pragma HLS aggregate variable=din compact=bit

  #pragma HLS array_reshape variable=din complete

  #pragma HLS interface ap_hs port=dout register

  #pragma HLS aggregate variable=dout compact=bit

  #pragma HLS array_reshape variable=dout complete

dat_t e[N];

  #pragma HLS array_reshape variable=e complete

 dat_t o[N];

#pragma HLS array_reshape variable=o complete

  #pragma HLS pipeline II=1 style=flp

/* (1) 入力 */

  for(int i=0; i<N; i++) {

    e[i] = din[i];

  }

/* (2) ソート */

  for(int j=0; j<N/2; j++) {

/* 偶ペアを入替 (0,1)(2,3)...(N-2,N-1) */

    for(int i=0; i<N-1; i+=2) {

      if(e[i+1] < e[i]) {

        o[i]   = e[i+1];

        o[i+1] = e[i];

      } else {

        o[i]   = e[i];

        o[i+1] = e[i+1];

      }

    }

/* 奇ペアを入替 0,(1,2)...(N-3,N-2),N-1 */

    e[0] = o[0];

    for(int i=1; i<N-1; i+=2) {

      if(o[i+1] < o[i]) {

        e[i]   = o[i+1];

        e[i+1] = o[i];

      } else {

        e[i]   = o[i];

        e[i+1] = o[i+1];

      }

    }

    e[N-1] = o[N-1];

  }

/* (3) 出力 */

  for(int i=0; i<N; i++) {

    dout[i] = e[i];

  }

}

◇◇

このCコードは次のテストベンチで検証してある。

/* main.cpp */

#include <iostream>

#include "sort.h"

using namespace std;

/*****************************

 * サブルーチン - 結果チェック

 *****************************/

void check_result(dat_t din[N],dat_t dout[N]) {

  cout << endl;

  for(int i=0; i<N; i++) {

    cout << "--i=" << i

         << " din=" << din[i]

         << " dout=" << dout[i];

    if(i!=N-1 && dout[i]>dout[i+1]) cout << "[FAIL]";

    cout << endl;

  }

}

/******************

 * メインルーチン

 ******************/

int main(int argc,char *argv[]) {

  dat_t din[N];

  dat_t dout[N];

/* 単調増加 */

  for(int i=0; i<N; i++) {

    din[i] = i+1;

  }

  sort_hls(din,dout);

  check_result(din,dout);

/* 単調減少 */

  for(int i=0; i<N; i++) {

    din[i] = N-i;

  }

  sort_hls(din,dout);

  check_result(din,dout);

/* 全部同じ */

  for(int i=0; i<N; i++) {

    din[i] = 2;

  }

  sort_hls(din,dout);

  check_result(din,dout);

 /* 単調増加で最後が最初と同じ */

  for(int i=0; i<N-1; i++) {

    din[i] = i+1;

  }

  din[N-1] = 1;

  sort_hls(din,dout);

  check_result(din,dout);

  return 0;

}

◇◇◇

このCコードを合成したら次のようになった。

クロック周期： 6.19ns　(制約8ns)

レイテンシ： 4クロック

II：　1クロック

LUT：　1293個

FF：   330個

---

[←]　[↑]　[→]