N-Queens

月刊アスキー12月号(2004年)で、N-Queens問題を見かけました。
10年以上前にCASL(情報処理試験専用のアセンブラ)で書いたことがあるのを思い出し、引っぱり出してきました。

queen.csl

CASLの命令なんて覚えていません。調べようとして気がついたのですが、現在はバージョンアップしてCASL2になってるんですね。知りませんでした。
それは置いといて、古い方のCASLの命令が書いてあるページを見つけました。

http://shakosv.sk.tsukuba.ac.jp/~shakojk0/

これを見ながら、queen.cslをCに起こして、さらにアスキーの記事に載っていたソースの(-r)&rというところがすばらしいので取り入れたのが下のソースです。

queen_r.c

短くてそこそこ速いです。最速を目指すためには再帰を展開した方がいいので下のようになります。

queen_f.c

ちょっと長くなってしまいました。でも速いです。
結局記事のソースと大差ないものになりました。

電通大のページ
http://www.yuba.is.uec.ac.jp/~kis/nq/

ん？電通大のは妙に速いな。あ、なるほど。対称性を利用して計算量を減らしてるんだ。
ということでまねしてみました。さらに盤面の大きさを引数で渡せるようにして、ベンチマーク専用ということで表示は省略しました。

queen_h.c

FPGAで解く

ここからが本題です。N-Queens問題をFPGAで解いてみます。
queen_h.cをベースに、Verilogで書きます。なるべくクロック数が少なくなるように構成します。
盤面の１行分を担当する回路を基本ユニットとして、それをN個並べます。
ある行にクイーンを置いて、次の行に移る処理を１クロックで実行します。queen_h.cでは、もしクイーンが置けなくなったら置き直せる行まで１行ずつ戻りますが、HDL版では戻る処理も含めて１クロックで実行できます。

Nの値をいろいろと変えて実験するために、generate文を使えば良さそうですが、case文の条件を可変生成することはできないようなので、perlによる簡単なプリプロセッサを通します。
元のソースがqueen.uで、
`eval $N = 20
のところを変えてu2vを実行するとqueen.vができます。
シミュレーションはiverilogで行います。テストベンチはtest_queen.vです。

ちゃんと動くことが確認できたので、次にスパルタン３スターターキットで実行してみます。
７セグLEDが４桁なので、スライドスイッチの右から２つで４桁ずつ切り替えられるようにして、合計16桁まで確認できるようにします。
回路規模は、N=20のとき、1444スライスでした。
配置配線後の最小周期は18.51nSだったので、オシレータ50MHzをそのまま使って走らせます。
コンフィグ直後から計算が始まって、どんどんカウントアップしていきます。７セグの左側のLEDが点灯し、カウントが止まったら終了です。
結果は以下の通り。電通大のページのN=20のところと同じ結果が得られました。

計算にかかった時間は10時間29分でした。
参考までに、Pen4/2.4G, gcc3.3.1, CFLAGS=-O3では11時間20分かかりました。

queen.tar.gz

スパルタン３スターターキット単体で、付加回路は何もいらないので、お持ちの方は試してみてください。

回路の縮小

上記の例では全ての行に回路を作ったので、どうしても大きくなってしまいます。
そこで、回路は１行分だけとし、使用しているレジスタもできるだけまとめてブロックRAMにすれば、回路が縮小できそうです。
ブロックRAMを使うにあたって、一度に読み書きするビット数を調べると、queen.uでは4Nビットです。
N=20の例では、80ビットになります。
これを減らすことを考えながら元のqueen_h.cをじっくり読むと、l,c,rは行ごとに保存する必要はなく、全体で１セットあればよいことに気がつきます。
ただし、シフトアウトしたものを後で復帰するためにlとrは2Nビット必要です。
残るtは行ごとに保存する必要があります。また、立てたビットの復帰のためにmも行ごとに保存する必要がありますが、mはただ１つのビットのみが１で、残りは０になるので、エンコードしたものを保存すればビット数が減らせます。
まとめると、必要なビット数は、N+log2Nになります（小数点以下切り上げ）。
スパ３のブロックRAMはポートあたり最大36ビットなので、N=31まで対応できるので十分です。

上記を元に書いたのがqueen2.uです。
N=20のとき、314スライスになりました。
配置配線後の最小周期は13.086nSだったので、DCMで75MHzを作って走らせました。
実行にかかった時間は27時間43分でした。
回路が１行分しかないので、queen.uのようにクィーンを置き直せる行を一気に判定できず、１ステップずつ戻る必要があるのと、ブロックRAMが同期読み出しなので、アドレス確定→そのアドレスのデータを読み出し→次のアドレス確定と、１サイクルに２クロックかかってしまうため、どうしても動作は遅くなります。

queen2.tar.gz

回路規模的には、デザインウェーブマガジン１月号付録のXC3S50にも入ります。