FPGA DE0-CVを、間違って二重に注文した人から買い取った。ちょっとプログラムを書いて、LEDを光らせたり、スイッチに反応させたりするのも楽しいけれど、それならもっと安いArduinoでもできるので、どうせならばFPGAの計算能力を活かしたい。競技プログラミングでは、すぐに思いつく解法では間に合わなくて、がんばってもっと速いアルゴリズムを考えるという流れが多い。FPGAは単純な処理の並列計算が得意なので、FPGAを使いこなせれば、簡単な解法で問題が解けて有利になるのではないかと考えた。結局、あまり役には立たなさそうだったけど、色々と試したので書いておく。
問題の選択
コンテストで使うことを考えると、そもそも書いたプログラムを手元で実行するコンテストでないといけない。Google Code Jam（GCJ）はその形式。しかも、GCJは1個の問題にsmallとlargeの2個の入力がある。smallの解法をそのままFPGAに実装してlargeが解ければとても面白い。と思ってGCJの過去問を探してみたけど、都合の良い問題が無かった。smallは指数時間のアルゴリズムで解けて、largeはそれを多項式時間に直すという問題が多かった。100倍や1000倍高速化するくらいでは追いつかない。100倍程度の速度で解けるか解けないかが変わるというのは、ユーザーの手元でプログラムを実行する形式では不適当なのかもしれない。
そのくらいの高速化で解けるかどうかが変わる問題ということで、AtCoder Beginner Contest 038の「D - プレゼント」を選んだ。AtCoderはサーバーでプログラムを実行する形式なので、FPGAで実際に問題を解くことはできない。AtCoderにFPGAを置いてほしい。
問題の解法
箱を何個入れ子にできるかという問題。各箱に他の箱を何個入れられるかを覚えておく。箱aの中に箱bを入れることができて、箱bの中に他の箱をk個入れられるのならば、箱aにはk+1個の箱を入れられる。これをn回繰り返せば良い。Pythonで書くとこんな感じ。
N = input()
w = [0]*N
h = [0]*N
for i in range(N):
w[i],h[i] = map(int, raw_input().split())
n = [1]*N
for i in range(N):
for j in range(N):
for k in range(N):
if w[j]<w[k] and h[j]<h[k]:
n[k] = max(n[k], n[j]+1)
print hex(max(n))
$O(n^3)$。箱を事前にソートしておけば無駄な探索を減らせて、$O(n^2)$になり、部分点が取れる。満点を取る方法は本家の解説に書いてある。
$O(n^3)$の解法のjかkのループは並列に実行することができる。FPGAで並列に計算をすれば、この解法でも$O(n^2)$時間で解ける。これを実装してみた。
参考書
ググればAlteraのマニュアルも、Verilog HDLの解説も出てくるのだけど、素人過ぎて全体像が分からない。とりあえず、↓の本を買った。
入出力の方法
出力は、数値が1個だけなので、7セグLEDに出せば良い。
問題は入力。コンパイルにはけっこう時間が掛かるので、プログラムに入力を埋め込むのはいまいち。まさかFPGAボードのスイッチをポチポチして問題を入力するわけにはいかない。実装が簡単なのでシリアル通信が定跡らしいが、DE0-CVには付いていない。
Nios IIというFPGAで動くCPUがあるらしい。このCPUではCで書いたプログラムが動かせて、Cのコードからはマクロを呼び出すだけで、FPGA側の変数の読み書きができる。また、PCからはデバッガ経由で標準入出力が扱えるので、これを使うことにした。
Qsys
Alteraの開発ツールに付属するQsysというソフトで、このCPU部分を作る。コードを書く必要は一切無くて、ライブラリを並びて、線を繋ぐだけ。nios2_gen2というのが本体。あとは、onchip_memoryとjtag_uart、出力用のpio。入力のクロックをpllに入れて100Mhzにし、出力のclkをその他のライブラリのクロックに繋ぐ。nios2_gen2のdata_masterを他のs1などに繋ぐ。メモリから命令を読み込むので、instruction_masterもメモリに繋ぐ。
「FPGAスタータ・キットDE0で始めるVerilog HDL」にはメモリは16KBで足りると書いてあるが、これはCのライブラリをSmall C Libraryにした場合。Small C Libraryには入力用の関数が無い（どこかのドキュメントにはscanfなどが無いと書かれていて、getsならあるかと思ったけど、無かった）ので、Smallではないライブラリにする必要があって、128KBくらい必要だった。
Cプログラム
IOWR_32DIRECTというマクロでFPGA側に値を書き込めるらしい。
プログラムは、標準入力から読み取って、箱の幅と高さを書き出すだけ。幅だけを書き出して時点でFPGA側から読み取られても困るので、書き込みが終わったかどうかを表わす変数も用意した。本当はFPGA側で読み取りが完了したかどうかも調べる必要があるだろうけど、今回は毎クロック読み込んでいるので、CPU側の実行が次に進むよりも読み取る方が早いはず。nの値は渡していていない。FPGA側は読み込んだ分だけ処理を実行するようになっている。
#include "alt_types.h"
#include "altera_avalon_pio_regs.h"
#include "sys/alt_irq.h"
#include "system.h"
#include <stdio.h>
#include <unistd.h>
int main()
{
printf("Hello from Nios II!\n");
int N, i;
scanf("%d", &N);
printf("N=%d\n", N);
for (i=0; i<N; i++)
{
int w, h;
scanf("%d%d", &w, &h);
printf("w=%d, h=%d\n", w, h);
IOWR_32DIRECT(PIO_AVAIL_BASE, 0, 0);
IOWR_32DIRECT(PIO_WIDTH_BASE, 0, w);
IOWR_32DIRECT(PIO_HEIGHT_BASE, 0, h);
IOWR_32DIRECT(PIO_AVAIL_BASE, 0, 0xffffffffu);
}
IOWR_32DIRECT(PIO_AVAIL_BASE, 0, 0);
return 0;
}
FPGA側プログラム
効率が良いかどうかとかは知らないが、とりあえず動くものを書くだけならば、思っていたほど難しくなかった。
alwaysの中以外では変数に代入するのではなく、等式が成り立つものを繋げていく。関数型言語っぽい。alwaysの中も上から順に実行されるのではなく、全ての代入が同時に行われる。処理によってはこちらのほうが書きやすそう。
Verilog HDLのfor文は、内容が順番に実行されるのではなく、中身が展開される。BoostのBOOST_PP_REPEATみたいな感じ。
alwaysとifでネストが深くなって嫌だったけど、これはこう書くしかないらしい。
always @(negedge rst) x <= 1'd0;
— kusanoさん@がんばらない (@kusano_k) 2016年7月18日
always @(posedge clk) x <= 1'd1;
これで、「xの配線をどうしたら良いか分からない」的なエラーになるのか。なるほど。
プログラムの中身は単純で、幅か高さが変化していたら、読み込んで初期化する。後は1クロックごとに相手の箱を変えながら、箱の中に相手の箱が入るかを調べるだけ。
module present(clk, rst, hled0, hled1, hled2, hled3, hled4, hled5);
input clk;
input rst;
output [6:0] hled0;
output [6:0] hled1;
output [6:0] hled2;
output [6:0] hled3;
output [6:0] hled4;
output [6:0] hled5;
parameter N = 100;
wire [31:0] width;
wire [31:0] height;
wire [31:0] avail;
reg [31:0] width_prev;
reg [31:0] height_prev;
reg [31:0] w [0:N-1];
reg [31:0] h [0:N-1];
reg [31:0] n [0:N-1];
reg [31:0] count;
reg [31:0] answer;
integer i;
present_core u0 (
.clk_clk (clk),
.reset_reset_n (rst),
.pio_width_external_connection_export (width),
.pio_height_external_connection_export (height),
.pio_avail_external_connection_export (avail)
);
always @(negedge rst or posedge clk) begin
// 初期化
if (rst==1'd0) begin
for (i=0; i<N; i=i+1) begin
w[i] <= 32'd0;
h[i] <= 32'd0;
n[i] <= 32'd0;
end
count <= 32'd0;
answer <= 32'd0;
end else begin
// 入力が前回と変化していれば値を読み込む
if (avail[0] != 32'd0 &&
(width != width_prev || height != height_prev)) begin
width_prev <= width;
height_prev <= height;
w[0] <= width;
h[0] <= height;
n[0] <= 32'd1;
for (i=1; i<N; i=i+1) begin
w[i] <= w[i-1];
h[i] <= h[i-1];
n[i] <= 32'd1;
end
count <= 32'd0;
answer <= 32'd0;
end else begin
// サイズが有効な箱を比較して、中に入れられるならば入れる
for (i=0; i<N; i=i+1) begin
if (w[i] != 32'd0 &&
w[count] != 32'd0 &&
w[i] > w[count] &&
h[i] > h[count] &&
n[i] < n[count]+1)
n[i] <= n[count]+1;
end
if (answer < n[count])
answer <= n[count];
count <= count<N-1 ? count+1'b1 : 32'd0;
end
end
end
function [6:0] led;
input [3:0] v;
begin
case (v)
4'h0: led = 7'b1000000;
4'h1: led = 7'b1111001;
4'h2: led = 7'b0100100;
4'h3: led = 7'b0110000;
4'h4: led = 7'b0011001;
4'h5: led = 7'b0010010;
4'h6: led = 7'b0000010;
4'h7: led = 7'b1011000;
4'h8: led = 7'b0000000;
4'h9: led = 7'b0010000;
4'ha: led = 7'b0001000;
4'hb: led = 7'b0000011;
4'hc: led = 7'b1000110;
4'hd: led = 7'b0100001;
4'he: led = 7'b0000110;
4'hf: led = 7'b0001110;
default: led = 7'b0;
endcase
end
endfunction
assign hled0 = led(answer[ 3: 0]);
assign hled1 = led(answer[ 7: 4]);
assign hled2 = led(answer[11: 8]);
assign hled3 = led(answer[15:12]);
assign hled4 = led(answer[19:16]);
assign hled5 = led(answer[23:20]);
endmodule
w[i] > w[count]（countは値が変化する）みたいな書き方をすると、全てのwを配線で結ぶ必要があってダメなのかと思っていたが、特に問題は無いらしい。RTLがなんかすごいことになっていたけど。
一応、そのような比較を無くして、各変数が決まった変数とだけ比較されるものも書いてみた。w1とw2を用意して、w2のほうをクロックごとに回転させている。単に使用ゲート数が増えただけだった。
module present(clk, rst, hled0, hled1, hled2, hled3, hled4, hled5);
input clk;
input rst;
output [6:0] hled0;
output [6:0] hled1;
output [6:0] hled2;
output [6:0] hled3;
output [6:0] hled4;
output [6:0] hled5;
parameter N = 100;
wire [31:0] width;
wire [31:0] height;
wire [31:0] avail;
reg [31:0] width_prev;
reg [31:0] height_prev;
reg [31:0] w1 [0:N-1];
reg [31:0] h1 [0:N-1];
reg [31:0] n1 [0:N-1];
reg [31:0] w2 [0:N-1];
reg [31:0] h2 [0:N-1];
reg [31:0] n2 [0:N-1];
reg [31:0] count;
reg [31:0] answer;
integer i;
present_core u0 (
.clk_clk (clk),
.reset_reset_n (rst),
.pio_width_external_connection_export (width),
.pio_height_external_connection_export (height),
.pio_avail_external_connection_export (avail)
);
always @(negedge rst or posedge clk) begin
// 初期化
if (rst==1'd0) begin
width_prev = 32'd0;
height_prev = 32'd0;
for (i=0; i<N; i=i+1) begin
w1[i] <= 32'd0;
h1[i] <= 32'd0;
n1[i] <= 32'd0;
w2[i] <= 32'd0;
h2[i] <= 32'd0;
n2[i] <= 32'd0;
end
count <= 32'd0;
answer <= 32'd0;
end else begin
// 入力が前回と変化していれば値を読み込む
if (avail[0] != 32'd0 &&
(width != width_prev || height != height_prev)) begin
width_prev <= width;
height_prev <= height;
w1[0] <= width;
h1[0] <= height;
n1[0] <= 32'd1;
w2[0] <= width;
h2[0] <= height;
n2[0] <= 32'd1;
for(i=1; i<N; i=i+1) begin
w1[i] <= w1[i-1];
h1[i] <= h1[i-1];
n1[i] <= 32'd1;
w2[i] <= w1[i-1];
h2[i] <= h1[i-1];
n2[i] <= 32'd1;
end
count <= 32'd0;
answer <= 32'd0;
end else begin
// サイズが有効な箱を比較して、中に入れられるならば入れる
for (i=0; i<N; i=i+1) begin
if (w1[i] != 32'd0 &&
w2[i] != 32'd0 &&
w1[i] > w2[i] &&
h1[i] > h2[i] &&
n1[i] < n2[i]+1)
n1[i] <= n2[i]+1;
end
// w2, h2, n2を回転させる
// countが0のときはn1をn2にコピー
w2[0] <= w2[N-1];
h2[0] <= h2[N-1];
n2[0] <= count!=32'd0 ? n2[N-1] : n1[N-1];
for (i=1; i<N; i=i+1) begin
w2[i] <= w2[i-1];
h2[i] <= h2[i-1];
n2[i] <= count!=32'd0 ? n2[i-1] : n1[i-1];
end
if (answer < n2[0])
answer = n2[0];
count <= count<N-1 ? count+1'b1 : 32'd0;
end
end
end
function [6:0] led;
input [3:0] v;
begin
case (v)
4'h0: led = 7'b1000000;
4'h1: led = 7'b1111001;
4'h2: led = 7'b0100100;
4'h3: led = 7'b0110000;
4'h4: led = 7'b0011001;
4'h5: led = 7'b0010010;
4'h6: led = 7'b0000010;
4'h7: led = 7'b1011000;
4'h8: led = 7'b0000000;
4'h9: led = 7'b0010000;
4'ha: led = 7'b0001000;
4'hb: led = 7'b0000011;
4'hc: led = 7'b1000110;
4'hd: led = 7'b0100001;
4'he: led = 7'b0000110;
4'hf: led = 7'b0001110;
default: led = 7'b0;
endcase
end
endfunction
assign hled0 = led(answer[ 3: 0]);
assign hled1 = led(answer[ 7: 4]);
assign hled2 = led(answer[11: 8]);
assign hled3 = led(answer[15:12]);
assign hled4 = led(answer[19:16]);
assign hled5 = led(answer[23:20]);
endmodule
実行結果
ゲート数が足りなくて、Nの最大値を100くらいにしかできなかった。せめて1000にできれば、部分点は取れるのだけど……。100くらいなら↑のPythonスクリプトでも1秒で答えが出る。
Nios II Software Build Tools for Eclipseのコンソールではなぜかクリップボードから貼り付けることができない。ここに書いてあるように、altera_lite\16.0\quartus\bin64に入っているNios2-terminal.exeを使った。一度Eclipseから実行すればプログラムはFPGAボードに転送されているので、Nios2-terminal.exeを起動してFPGAボードのリセットボタンを押すと、プログラムが開始する。リダイレクトで流し込んでも上手く行かなかったので、DOS窓にクリップボードから貼り付けた。
100
96646 44074
750 91098
93927 58223
67157 8394
76649 23681
3082 78878
34609 62329
61582 14856
18310 11442
1462 48676
96491 6457
54109 46590
60147 8893
57901 26959
55644 64464
48104 35524
24916 93352
45339 53017
1930 50811
579 14377
47283 37735
5418 58753
16401 55734
14425 93731
77098 95694
14123 30540
3959 27679
80652 17735
15458 95472
15456 83389
4107 38619
34960 34171
81647 47594
78290 47085
81735 88157
43960 78107
81475 29568
12388 18563
43606 11947
52980 82943
48521 81774
65640 64105
34535 70266
80995 15717
90800 26934
15485 84048
72013 79357
44668 7078
39525 4774
28614 3800
50672 8767
93283 69939
31699 94506
6623 25743
7300 42631
20190 39665
70486 88736
50052 81854
36126 85869
51504 70242
17469 58452
30178 81286
53435 49959
77333 54904
33376 13094
62451 92535
84234 6975
32529 171
67470 63829
75791 14828
21704 43278
73673 20712
82284 38121
87429 96003
53749 92107
42204 68528
84691 83877
9287 26032
41026 85783
27675 11374
37535 21389
71624 58751
5250 87744
44056 77689
16533 30792
7333 39500
42892 68280
47959 40052
47797 28127
36953 60050
20607 51887
92968 45742
66832 65985
80135 72556
66071 10372
36664 79407
6520 14002
90537 58802
98017 75359
99568 29862
を貼り付けて、0x11という答えが出たのが最初の写真。成功🎉🎉🎉🎉
実行中の様子を見ていると、一瞬だが、数字が増えていって0x11になるのが目で見える。10000クロックで答えが出るはずなので、50MHzならば0.0002秒。本当にこの速さなら、目には見えないはず。おそらくFPGAへの入力の転送がボトルネック。
何かと面倒だし、このFPGAボードだと今回の例でも100並列くらいだし、素直にアルゴリズムを工夫してPCで解いたほうが楽そう。