インデックスソート

[←]　[↑]　[→]

---

前項の「奇偶転置ソート」はデータ自体を移動しているが、移動しなくても順番だけわかればよいので、総当たりで各ペアの大小を調べて、自分より小さいものの個数を順番(インデックス)にすればよい。

ちなみに、この方法ではデータ数は偶数でなくてもよい。

◇

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

/* sort.h*/

#ifndef SORT_H

#define SORT_H

#include <ap_int.h>

static const int N=10; // データ数

static const int WN=4; // N-1のビット幅

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

typedef ap_uint<WN> num_t;

void sort_hls

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

  ,num_t num[N] // (o) 入力データの順番(0から小さい順)

  );

#endif

/* sort.cpp */

/*

 * 配列din[N]に対して小さい順に0から番号num[N]を振る

 * 値が等しいときはインデックスの小さい方を先にする

 */

#include "sort.h"

void sort_hls

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

  ,num_t num[N] // (o) 入力データの順番(0から小さい順)

  ) {

  #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=num register

  #pragma HLS aggregate variable=num compact=bit

  #pragma HLS array_reshape variable=num complete

 bool less[N][N];

#pragma HLS array_reshape variable=less complete

  #pragma HLS pipeline II=1 style=flp

/* (1) 総当たりで比較する */

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

    less[i][i] = 0;

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

      less[i][j] = (din[i] > din[j])? 1:0;

      less[j][i] = !less[i][j];

    }

  }

/* (2) din[i]より小さい要素の個数をnum[i]に格納する */

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

    num[i] = 0;

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

      num[i] += less[i][j];

    }

  }

}

◇◇

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

/* main.cpp */

#include <iostream>

#include "sort.h"

using namespace std;

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

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

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

void check_result(dat_t din[N],num_t num[N]) {

  dat_t dout[N];

  cout << endl;

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

    dout[num[i]] = din[i];

  }

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

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

         << " din=" << din[i] << " num=" << num[i];

    cout << " 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];

  num_t num[N];

/* 単調増加 */

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

    din[i] = i+1;

  }

  sort_hls(din,num);

  check_result(din,num);

/* 単調減少 */

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

    din[i] = N-i;

  }

  sort_hls(din,num);

  check_result(din,num);

/* 全部同じ */

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

    din[i] = 2;

  }

  sort_hls(din,num);

  check_result(din,num);

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

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

    din[i] = i+1;

  }

  din[N-1] = 1;

  sort_hls(din,num);

  check_result(din,num);

  return 0;

}

◇◇◇

このCコードを合成したら次のようになった。奇遇転置ソートより回路規模は小さい。

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

レイテンシ： 1クロック

II：　1クロック

LUT：　1598個

FF：    44個

---

[←]　[↑]　[→]