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化するのに非常に向いているという確信を持つことができた。