FPGAで競技プログラミング

ルーターで競技プログラミングという記事をみて、色々なアーキテクチャで競技プログラミングができることを知りました(採点はしてくれませんが)。

紹介されていたTopcoder SRM 596のDiv 1の250点問題をFPGAで解くモジュールを作成してみました。

FPGAに実装する場合のデータの入力としてはI2CあるいはAlteraであればQsysでMPU(NIOS)を用いたデバッガ入力などが考えられます。出力としてはそれと同一、あるいはLCD,7seg等に出力することができます。

ModelSim Altera 10.1bで動作を確認しました。

 以下がコード(２種類)です。合成する場合には

`define FPGA

を追加することでテストベンチ部分が無視され、合成できるようになります。

動作ですがtestモジュールにあるようにwenableを1にしている期間の間にdatainに問題のデータを連続して入力させたのちにwenableを0にします。しばらくするとans_enableが1になり、そのときに出てきたanswerの値が答えになります。

コード(その1)

コード(その2)

入力値の桁がすくない場合にはLook up tableをつかって低遅延、少ないレジスタで計算することができますが、記述は長くなってしまいます。

この手法は一見CPUで実現するのは難しそうですが、ビットを数えるのにはSSEのPOPCNT命令、最上位桁を求めるのにはいったん浮動小数点にキャストして指数部をとってくるという手法を使うと高速に計算できるそうです(ビットを数える・探すアルゴリズム)。

入力

 7,5,8,1,8,6,6,5,3,5,5,2,8,9,9,4,6,9,4,4,1,9,9,2,8,4,7,4,8,8,6,3,9,4,3,4,5,1,9,8,3,8,3,7,9,3,8,4,4,7

 出力

 The answer is 84