FPGA開発日記

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

VivadoHLSでソートアルゴリズムを実装してみる(マージソートと選択ソート)

Vivado HLSの使い方がだいたい分かってきた。では、普通のプログラムを高位合成でHDLで生成させたらどうなるんだろうか?

再帰が含まれているソートアルゴリズムをHDLで合成できる?

まずはマージソートを実装してみよう。雰囲気的に、マージソートはハードウェアにうまく合いそうな気がする。

以下のサイトのソースプログラムを流用させてもらった。

www1.cts.ne.jp

int temp[MAX_DATA];
void merge_sort(int x[ ], int left, int right)
{
    int mid, i, j, k;

    if (left >= right)
        return;

    mid = (left + right) / 2;
    merge_sort(x, left, mid);
    merge_sort(x, mid + 1, right);

    for (i = left; i <= mid; i++)
        temp[i] = x[i];

    for (i = mid + 1, j = right; i <= right; i++, j--)
        temp[i] = x[j];

    i = left;
    j = right;

    for (k = left; k <= right; k++) {
        if (temp[i] <= temp[j])
            x[k] = temp[i++];
        else
            x[k] = temp[j--];
    }
}

再帰が入っているけど大丈夫かな?コンパイルしてみる。

@E [SYNCHK-74] Recursive functions are not supported: recursion found in the following functions 
               'merge_sort(merge_sort.c:4) --> 'merge_sort'(merge_sort.c:13:5)
@I [SYNCHK-10] 1 error(s), 0 warning(s).
@E [HLS-70] Synthesizability check failed.

やっぱりダメだった。Vivado HLSは再帰をサポートしていないらしい。 まあ、ステートマシンをそのままHDLに直すような安直なことはしてないだろうしなあ。。。再帰の取り込みは難しいと思う。。。

選択ソートを実装してみる

次は再帰の存在しない選択ソートだ。 同じように以下のサイトを参考にさせてもらった。

www1.cts.ne.jp

#define MAX_DATA 128

void select_sort(int num[MAX_DATA])
{
    int i, j, k, min, temp;

    for (i = 0; i < MAX_DATA - 1; i++) {
        min = num[i];
        k = i;
        for (j = i + 1; j < MAX_DATA; j++) {
            if (num[j] < min) {
                min = num[j];
                k = j;
            }
        }
        temp = num[i];
        num[i] = num[k];
        num[k] = temp;
    }
}

コンパイルはできた。生成したVerilogファイルはどうなっているだろう?

module select_sort (
        ap_clk,
        ap_rst,
        ap_start,
        ap_done,
        ap_idle,
        ap_ready,
        num_address0,
        num_ce0,
        num_we0,
        num_d0,
        num_q0
);

parameter    ap_const_logic_1 = 1'b1;
parameter    ap_const_logic_0 = 1'b0;
parameter    ap_ST_st1_fsm_0 = 7'b1;
parameter    ap_ST_st2_fsm_1 = 7'b10;
parameter    ap_ST_st3_fsm_2 = 7'b100;
parameter    ap_ST_st4_fsm_3 = 7'b1000;
parameter    ap_ST_st5_fsm_4 = 7'b10000;
parameter    ap_ST_st6_fsm_5 = 7'b100000;
parameter    ap_ST_st7_fsm_6 = 7'b1000000;
parameter    ap_const_lv32_0 = 32'b00000000000000000000000000000000;
parameter    ap_const_lv1_1 = 1'b1;
parameter    ap_const_lv32_1 = 32'b1;
parameter    ap_const_lv1_0 = 1'b0;
parameter    ap_const_lv32_2 = 32'b10;
parameter    ap_const_lv32_3 = 32'b11;
parameter    ap_const_lv32_4 = 32'b100;
parameter    ap_const_lv7_0 = 7'b0000000;
parameter    ap_const_lv32_6 = 32'b110;
parameter    ap_const_lv32_5 = 32'b101;
parameter    ap_const_lv7_7F = 7'b1111111;
parameter    ap_const_lv7_1 = 7'b1;
parameter    ap_const_lv32_7F = 32'b1111111;
parameter    ap_true = 1'b1;

input   ap_clk;
input   ap_rst;
input   ap_start;
output   ap_done;
output   ap_idle;
output   ap_ready;
output  [6:0] num_address0;
output   num_ce0;
output   num_we0;
output  [31:0] num_d0;
input  [31:0] num_q0;

配列のnumは、単純なceとweの制御信号で取り込みと書き込みを実現しているらしい。 中身は、正直複雑すぎてちゃんと見れていない。シミュレーションして確かめてみたほうが良いかもなあ。