ぱたへね

はてなダイアリーはrustの色分けができないのでこっちに来た

並列コンピュータで人材獲得作戦

FPGA Verilog

時代は並列コンピュータのようなので、迷路の問題を解くための並列ハードウェアをVerilogで作ってみました。
元ネタはこちら
http://okajima.air-nifty.com/b/2010/01/post-abc6.html

アルゴリズム

迷路をグラフで表します。
迷路の1マスに1つのプロセッサを割り当てます。
プロセッサは次の事を行います。

  • 1つのプロセッサは１つのscoreを持ちます。
  • scoreの初期値は、全て最大値から始まります。例外的にスタート地点のみ0から始まります。
  • 壁に割り当てられたプロセッサのscoreは、最大値から変化しません。
  • 通路に割り当てられたプロセッサは、上下左右に接続されたプロセッサのscoreのうち、一番小さい物に1足した値を自分のscoreにします。

全てのプロセッサを同時に動作させ、ゴールに割り当てられたプロセッサのscoreが最大値から変化した時が検索の終了です。

簡単に言うと、スタート地点を0として、一歩進んだら1増えるという検索を、上下左右全て並列に行うだけです。通路だけをグラフ化して、プロセッサを割り当てても同じ事ができるのですが、後の回路の自動生成が楽なので、壁にも何もしないプロセッサを割り当てています。

最大値を255として、6マスまで検索したイメージです。

プロセッサの実装

ここはアルゴリズムの肝なので、手でVerilogを書いています。(node.v)

//上下左右からの最小値を求めるｘ
assign 		 min_tmp_a = (score_from_up_i < score_from_down_i) ? score_from_up_i : score_from_down_i;
assign 		 min_tmp_b = (score_from_left_i < score_from_right_i) ? score_from_left_i : score_from_right_i;
assign     min       = (min_tmp_a < min_tmp_b) ? min_tmp_a : min_tmp_b;
	
always @ (posedge clk) begin
	if(reset_x_i == 0)begin   //最初は最大値から
		score_r <= max_score;
	end else if(wall_i)begin  //壁は常に最大値
		score_r <= max_score; 
	end else if(start_i)begin //開始点は0
		score_r <= 0;  
	end else begin            //上下左右の一番小さいscoreに1足した物が自分のscore
		if(min < max_score)begin
			score_r <= min + 1;
		end
	end
end

処理の記述はここだけです。
残りのVerilogは、迷路のデータから自動生成させます。

迷路の実装

今回の迷路は縦13×横26なので、338個のプロセッサを並べます。
手で書くと泣きそうなので、Pythonで生成させました。(make_top.py)

    node u0_0 (.clk_i(clk), .reset_x_i(reset_x),
    .start_i(start_0_0), .goal_i(goal_0_0), .wall_i(wall_0_0),
    .score_from_up_i(score_max_w), .score_from_down_i(score_0_1), .score_from_left_i(score_max_w), .score_from_right_i(score_1_0),
    .score_o(score_0_0), .finish_o(finish_0_0)
     );

    node u1_0 (.clk_i(clk), .reset_x_i(reset_x),
    .start_i(start_1_0), .goal_i(goal_1_0), .wall_i(wall_1_0),
    .score_from_up_i(score_max_w), .score_from_down_i(score_1_1), .score_from_left_i(score_0_0), .score_from_right_i(score_2_0),
    .score_o(score_1_0), .finish_o(finish_1_0)
     );

    node u2_0 (.clk_i(clk), .reset_x_i(reset_x),
    .start_i(start_2_0), .goal_i(goal_2_0), .wall_i(wall_2_0),
    .score_from_up_i(score_max_w), .score_from_down_i(score_2_1), .score_from_left_i(score_1_0), .score_from_right_i(score_3_0),
    .score_o(score_2_0), .finish_o(finish_2_0)
     );

top回路(solver.v)は、テキストから読み込んだ迷路から縦、横のサイズを計算して、プロセッサを自動的に並べます。

初期値としてプロセッサが必要な情報は、「自分自身が壁かどうか、スタート地点かどうか、ゴールかどうか」なので、それぞれのプロセッサに情報を与える必要があります。問題が「入出力はテキストデータ」と指定されているので、こちらもPythonで読み込んで、迷路用のVerilogファイル(maze.v)を自動生成します。

処理結果

自動生成されたハードウェアをVeritakでシミュレーションしてみました。


何が何だかさっぱり分からないので、veritakで各プロセッサのscoreを読み出し、テキストに落としてみました。

255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 
255   0 255   8 255  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29 255 
255   1 255   7 255   9  10 255  14  15 255 255 255 255 255 255 255 255 255 255 255 255 255  29  30 255 
255   2 255   6   7   8 255  16  15  16  17 255 255 255 255 255 255 255 255 255 255 255 255  30  31 255 
255   3   4   5   6 255  18  17  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32 255 
255 255 255 255 255 255 255 255 255 255 255 255 255 255  23 255 255 255 255 255 255 255 255 255 255 255 
255  37  36  35  34  33  32  31  30  29  28  27  26  25  24  25  26  27  28  29  30  31  32  33  34 255 
255 255  37 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 
255  39  38  39  40  41  42 255  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62 255 
255  40  39 255  41  42  43  44  45  46 255 255 255 255 255 255 255 255 255 255 255  60 255  62  63 255 
255  41  40  41  42 255  44  45  46  47  48  49  50  51 255 255 255 255 255 255 255  61 255  63  64 255 
255  42  41  42  43  44  45  46 255  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63 255 
255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255

正しく動いているようです。
スタートからゴールまでの距離分のクロック数で、検索が終了します。この回路が100MHzで動作するとすれば、610nsで検索終了です。並列コンピュータ万歳ですね。

ただ問題は、出力もテキストデータを指定されているので、これを最終的な答えにするのに、もう一度Pythonを使っています。ゴールから、順番に小さい数字を追っていけばよいので簡単ですね。

**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

処理に使ったファイル一式はこちらです。
http://homepage3.nifty.com/~Natsutan/study/maze/maze.zip