BSV DCON 2010

CYBERNET社主宰のBluespecデザインコンテスト2010に応募したコードをここに掲載する。

残念ながら入賞することはできなかったのだが、せっかく作成したコードなので、ここで紹介しておきたい。

題材は、ソートプログラムということで、バブルソートのプログラムがサンプルプログラムとして挙げられていた。BSVの文法を見て、C言語等で記述されたアルゴリズムを、ほぼそのままBSVへポーティングできるのではないかという感触を持った。そこでアルゴリズムのHW化の実験という意味で、クイックソートをBSVで記述してみることに挑戦した。Verilogで記述するには面倒すぎて、あまり採用したいとは思わないアルゴリズムである。

まず最初に行うのが、アルゴリズムのコーディングである。最初にクイックソートをC言語で記述してみた。これが以下のプログラムだ。

#include <stdio.h>

#define NUMBER_OF_ELEMENTS 11

void sort(int numbers[], int left, int right);

void printNumbers(int numbers[]);

main()

{

int numbers[NUMBER_OF_ELEMENTS] =

{45, 60, 23, 22, 0, 38, 47, 3, 23, 39, 99};

printNumbers(numbers);

sort(numbers, 0, NUMBER_OF_ELEMENTS - 1);

printNumbers(numbers);

}

void sort(int numbers[], int left, int right)

{

int i, j;

int swapTmp, pivot;

i = left;

j = right;

printf("\n ");

pivot = numbers[(left + right) >> 1];

printNumbers(numbers);

printf(" left = %d, right = %d, pivot = %d\n", left, right, pivot);

do {

while(numbers[i] < pivot) i++;

while(pivot < numbers[j]) j--;

if (i <= j) {

swapTmp = numbers[i];

numbers[i] = numbers[j];

numbers[j] = swapTmp;

i++;

j--;

}

} while (i <= j);

if (left < j) sort(numbers, left, j);

if (i < right) sort(numbers, i, right);

}

void printNumbers(int numbers[])

{

int i;

for (i = 0; i < NUMBER_OF_ELEMENTS; i++) {

printf("%d ", numbers[i]);

}

printf("\n");

}

これは、再帰を使ったプログラムなので、そのままHW化するのは無理がある。そこで、これを以下のように再帰を使わないバージョンに書き換えてみた。

#include <stdio.h>

#define NUMBER_OF_ELEMENTS 11

#define STACK_PUSH 0

#define STACK_POP 1

void sort(int numbers[], int left, int right);

void stackOpr(int operation, int* left, int* right, int* empty);

void printNumbers(int numbers[]);

main()

{

int numbers[NUMBER_OF_ELEMENTS] =

{45, 60, 23, 22, 0, 38, 47, 3, 23, 39, 99};

printNumbers(numbers);

sort(numbers, 0, NUMBER_OF_ELEMENTS - 1);

printNumbers(numbers);

}

/* Quick sort without recursion */

void sort(int numbers[], int left, int right)

{

int i, j;

int swapTmp, pivot;

int empty;

printNumbers(numbers);

stackOpr(STACK_PUSH, &left, &right, &empty); //S1

do {

stackOpr(STACK_POP, &left, &right, &empty); //S2

do {

i = left; j = right; pivot = numbers[(left + right) >> 1]; //S3

printf(" left = %d, right = %d, pivot = %d\n", left, right, pivot);

do {

while(numbers[i] < pivot) i++; //S4

while(pivot < numbers[j]) j--; //S4

if (i <= j) { //S5

swapTmp = numbers[i]; //S5

numbers[i] = numbers[j]; //S5

numbers[j] = swapTmp; //S6

i++; //S6

j--; //S6

}

} while (i <= j); //S7

if (i < right) { //S8

stackOpr(STACK_PUSH, &i, &right, &empty); //S8

}

right = j; //S9

} while (left < right); //S9

} while (empty != 1); //S9

}

void stackOpr(int operation, int* left, int* right, int* empty)

{

static struct {

int left;

int right;

} stackEntity[NUMBER_OF_ELEMENTS];

static int index = 0;

if (operation == STACK_PUSH) {

stackEntity[index].left = *left;

stackEntity[index].right = *right;

index++;

} else if (operation == STACK_POP) {

//POP

*left = stackEntity[index - 1].left;

*right = stackEntity[index - 1].right;

index--;

}

if (index == 0) *empty = 1;

else *empty = 0;

}

void printNumbers(int numbers[])

{

int i;

for (i = 0; i < NUMBER_OF_ELEMENTS; i++) {

printf("%d ", numbers[i]);

}

printf("\n");

}

これをBSV用のコーディングしなおしたのが以下のコードである。

import Vector::*;

import RegFile::*;

`define REGFILE_DEPTH 11

(* synthesize *)

module mkTb(Empty);

Qsort_ifc qs <- mkQsort;

int vals[`REGFILE_DEPTH] = {45, 60, 23, 22, 0, 38, 47, 3, 23, 39, 99};

Reg#(int) cnt <-mkReg(0);

rule r1 (cnt == 0);

qs.start(arrayToVector(vals), 0, `REGFILE_DEPTH - 1);

cnt <= 1;

endrule

rule r2 (cnt == 1);

for (Integer i = 0; i < `REGFILE_DEPTH; i = i + 1)

$write("a[%0d] = %2d, ", i, qs.result[i]);

$display("");

$finish(0);

endrule

endmodule

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

/* Quick Sort */

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

typedef enum {S0, S1, S2, S3, S4, S5, S6, S7, S8, S9} State

deriving (Bits, Eq);

interface Qsort_ifc;

method Action start(Vector#(`REGFILE_DEPTH, int) v, bit[15:0] l, bit[15:0] r);

method Vector#(`REGFILE_DEPTH, int) result();

endinterface

module mkQsort(Qsort_ifc);

Reg#(bit[15:0]) left <- mkReg(0);

Reg#(bit[15:0]) right <- mkReg(0);

Reg#(bit[15:0]) i <- mkReg(0);

Reg#(bit[15:0]) j <- mkReg(0);

Reg#(int) swapTmp <- mkReg(0);

Reg#(int) pivot <- mkReg(0);

Reg#(int) empty <- mkReg(0);

Reg#(State) state <- mkReg(S0);

Vector#(`REGFILE_DEPTH, Reg#(int)) numbers <- replicateM(mkReg(0));

Stack_ifc#(bit[31:0]) stack <- mkStack;

rule s1rule (state == S1);

stack.enq({left, right});

state <= S2;

endrule

rule s2rule (state == S2);

bit[31:0] tmp;

tmp = stack.top;

left <= tmp[31:16];

right <= tmp[15:0];

stack.deq;

state <= S3;

endrule

rule s3rule (state == S3);

int pv;

i <= left;

j <= right;

pv = numbers[(left + right) >> 1];

pivot <= pv;

state <= S4;

$display(" left = %d, right = %d, pivot = %d", left, right, pv);

endrule

rule s4rule (state == S4);

Bool c1;

if (numbers[i] < pivot) begin

i <= i + 1;

c1 = False;

end else

c1 = True;

if (pivot < numbers[j])

j <= j - 1;

else if (c1)

state <= S5;

endrule

rule s5rule (state == S5);

if (i <= j) begin

swapTmp <= numbers[i];

numbers[i] <= numbers[j];

state <= S6;

end else

state <= S7;

endrule

rule s6rule (state == S6);

numbers[j] <= swapTmp;

i <= i + 1;

j <= j - 1;

state <= S7;

endrule

rule s7rule (state == S7);

if (i <= j)

state <= S4;

else

state <= S8;

endrule

rule s8rule (state == S8);

if (i < right)

stack.enq({i, right});

state <= S9;

endrule

rule s9rule (state == S9);

right <= j;

if (left < j)

state <= S3;

else begin

if (!stack.isEmpty)

state <= S2;

else

state <= S0;

end

endrule

method Action start(Vector#(`REGFILE_DEPTH, int) v,

bit[15:0] l, bit[15:0] r) if (state == S0);

writeVReg(numbers, v);

left <= l;

right <= r;

state <= S1;

endmethod

method Vector#(`REGFILE_DEPTH, int) result() if (state == S0);

return readVReg(numbers);

endmethod

endmodule

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

/* Stack */

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

interface Stack_ifc #(type dataType);

method Action enq(dataType data);

method Action deq();

method dataType top();

method Bool isEmpty();

endinterface

(* synthesize *)

module mkStack(Stack_ifc#(bit[31:0]));

Vector#(`REGFILE_DEPTH, Reg#(bit[31:0])) content <- replicateM(mkReg(0));

Reg#(int) ap <- mkReg(0);

method Action enq(bit[31:0] data);

content[ap] <= data;

ap <= ap + 1;

endmethod

method Action deq();

ap <= ap - 1;

endmethod

method bit[31:0] top();

return content[ap - 1];

endmethod

method Bool isEmpty();

if (ap == 0) return True;

else return False;

endmethod

endmodule

変換するにあたり、まずプログラムのハードウェアでの並列処理を検討した。

Cの1行をBSVの1ステートで実行していってもいいのだが、せっかくHW化するなら高速化を追及したいということで、ソースコードを眺めながら、並列処理できそうな部分を、ひとつのステートとしてグルーピングした。

検討結果として、先ほどのCのソースコートのそれぞれの行の右に、対応するステートをコメントとして入れてある。

リソース競合がおこる部分は、同じステートにはできないので、分割しなければならない。たとえば、Cプログラム中のS5ではswapTmpに値を代入しているが、その2行下では、numbers[j]にswapTmpの代入している。これは同じステート内で処理してしまうとレーシングになるので、2つのステートに分割している。

今回は、S1からS9までの、9ステートで処理することにした。これに、非動作時のS0ステートを入れて、合計10ステートとする。

後は、このCプログラムをBSVに手変換するだけだ。レジスタ(FF)については、Cソースで変数宣言されているものと、ソート関数への引数のleft, rightを宣言する。

ソートアルゴリズム本体は1ステート1ルールとして、ほぼ機械的に変換できる。

たとえば、S8ステートは、C言語では以下のとおりだが、

if (i < right) { //S8

stackOpr(STACK_PUSH, &i, &right, &empty); //S8

}

BSVでは以下のようになる。

rule s8rule (state == S8);

if (i < right)

stack.enq({i, right});

state <= S9;

endrule

CプログラムとBSVを各ステート毎につき合わせてみれば、対応関係がよくわかると思う。

実際にコーディングしてみた感想だが、CからBSVへの変換は、本当にあっさりとできてしまった。BSVでは、定義したステート毎に必要な処理と、次へのステートへの遷移条件が書けるので、記述がとても直感的で、わかりやすい。今回が初めてのBSVのコーディングであったにもかかわらず、CからBSVへの作業はほんの数時間で完了してしまった。

当初の予想通り、BSVは、ソフトウェアで記述されたアルゴリズムを、そのままHW化するのに非常に向いているという確信を持つことができた。