ハードウェアで素数を数える

> 素数を数えて落ち着くんだ... <a name='more'></a> VHDLで素数を数え上げる回路を記述する. # ソフトウェアプログラム まずはC言語でどのようにするか調べる. 大抵のアルゴリズムはソフトウェアではすでに作られていて, HDLでは作られていないということが多い. なのでソフトウェア言語からHDLに翻訳するのが一番の近道. [素数を求めるプログラム - TSG http://www.tsg.ne.jp/TT/tsg/c/mansaku/P01.html](http://www.tsg.ne.jp/TT/tsg/c/mansaku/P01.html) こちらのサイトを参考にC言語でプログラミングする. 素数を数え上げるアルゴリズムは以下のようになるらしい. 1. 3以上の奇数($i$)を提示 1. $3 \le j \le \sqrt{i}$の奇数で割れるか($i \mod j = 0$) 1. $i \mod j \neq 0$をすべて満たすとき素数 ポイントは - 奇数のみを数える - 割るのは$\sqrt{i}$までで良い ということ. ほぼ上記のサイトまんまで作ったCのソースが下. 今後のために`out.dat`に数え上げた素数を保存している. # VHDL さてVHDLで記述する. まずはCプログラムをどのように置き換えるのが良いか考えてみる. ## どうやって割り算するか? 上記のCプログラムをVHDLに置き換えるときに問題になるのは$i \mod j$の導出である. そこで各素数の約数のときパルスを出す回路を作り, そのパルスが全て`H`でないものを素数とする. 以下のタイムチャートでは3, 5, 7の約数のときにパルスを出力する回路を作った. パルスが`H`になっていない11, 13, 17, 19が確かに素数である. <img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdc2TrIJhVZnpHzMYRGXv5hDHpmoQLYdE4u-yD6tLdfu-lGFiSwZ_mukgmyw_z-SBwLQfpgBpHnIZ9T3VlCtdcR6LWhfjT4_nGtYFySpRCXkXtabOsYS-zJJkH1WmntpcfCh6iDDxREtRl/s1600/wavedrom_20190317.png" data-original-width="80%" /> ## 演算速度 この回路では当然割り算を行っていないため, 上記のCプログラムよりも早い. 演算速度はただCLKの周波数だけに依存して, 100[MHz]のCLKを使って100M（一億）までの素数を数え上げるのにかかる時間は1秒である. このアルゴリズムでこれ以上早く数え上げるには約数をとばすしかない. ## 回路規模 問題なのが回路規模. 100Mまでの素数を数え上げるためには10kまでの素数のカウンタがそれぞれ必要になる. 具体的には1228個のカウンタを並列に動かことになる. また数え上げる数が大きくなるほどカウンタの大きさも大きくなるため, 加速度的に回路規模は大きくなってしまう. 上記のCプログラムではかかる時間が加速度的に増えていくが, それとのトレードオフになっている. ## VHDLソース Cプログラムで数え上げた素数を種として1Mまでの素数を数え上げる. 素数の種を最大値とするカウンタをすべて作るだけだ. モジュールの入出力は以下の表の通り. | 信号名 | I/O | 論理 | 内容 | | --------- | :--- | :--- | ---------- | | CLK | I | P | クロック | | nRST | I | N | リセット | | STR | I | P | 演算開始 | | BUSY | O | P | 演算ビジー | | VALID | O | P | データ有効 | | DAT[31:0] | O | P | データ | あとは外部にモジュールを追加してメモリに保存するなり, シリアルに保存するなりすればいい. 以下がVHDLソース. 10kまでの素数をすべて羅列していて無駄に長いので中略している. 中略なしソースはリポジトリのリンク参照. [https://github.com/toms74209200/PRIME_CNT](https://github.com/toms74209200/PRIME_CNT) シミュレーションした結果が以下の通り. <img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhKFLMNtyRJnJYnGGItuu9m3-Kww2-mTJBBp0243ZQuG1GxI17zg_sI8I8xP5NILOx59U9nSexrFndaOQ9GpDhyphenhyphenAS1_J5kE14aPjr99Bzj3I-9DSHxW9joJIJLZ4UbMneg1TY2JrKvOcaPG/s1600/prime_2019-03-17203549.png" width="80%" data-original-height="207" /> 見ての通り, 1を除外していないので1もデータとして出力されてしまっている. ちなみにQuartus prime v18.0でコンパイルした結果は以下の通り. コンパイルにめちゃくちゃ時間がかかるので思いつきでコンパイルしてはいけない. 無駄に何回かコンパイルしたが, だいたい15分くらいかかっている. ```text +----------------------------------------------------------------------------------+ ; Flow Summary ; +------------------------------------+---------------------------------------------+ ; Flow Status ; Successful - Mon Mar 18 10:36:51 2019 ; ; Quartus Prime Version ; 18.0.0 Build 614 04/24/2018 SJ Lite Edition ; ; Revision Name ; PRIME_CNT ; ; Top-level Entity Name ; PRIME_CNT ; ; Family ; Cyclone 10 LP ; ; Total logic elements ; 50,136 / 119,088 ( 42 % ) ; ; Total combinational functions ; 50,136 / 119,088 ( 42 % ) ; ; Dedicated logic registers ; 19,681 / 119,088 ( 17 % ) ; ; Total registers ; 19681 ; ; Total pins ; 37 / 278 ( 13 % ) ; ; Total virtual pins ; 0 ; ; Total memory bits ; 0 / 3,981,312 ( 0 % ) ; ; Embedded Multiplier 9-bit elements ; 0 / 576 ( 0 % ) ; ; Total PLLs ; 0 / 4 ( 0 % ) ; ; Device ; 10CL120YF484I7G ; ; Timing Models ; Final ; +------------------------------------+---------------------------------------------+ +--------------------------------------------------------------------------------------------------------------------------+ ; Flow Elapsed Time ; +----------------------+--------------+-------------------------+---------------------+------------------------------------+ ; Module Name ; Elapsed Time ; Average Processors Used ; Peak Virtual Memory ; Total CPU Time (on all processors) ; +----------------------+--------------+-------------------------+---------------------+------------------------------------+ ; Analysis & Synthesis ; 00:02:29 ; 1.0 ; 5191 MB ; 00:02:43 ; ; Fitter ; 00:04:52 ; 1.2 ; 6187 MB ; 00:10:04 ; ; Assembler ; 00:00:06 ; 1.0 ; 4828 MB ; 00:00:06 ; ; Timing Analyzer ; 00:00:21 ; 1.4 ; 5397 MB ; 00:00:27 ; ; Total ; 00:07:48 ; -- ; -- ; 00:13:20 ; +----------------------+--------------+-------------------------+---------------------+------------------------------------+ ``` さすがにこんなに大きなFPGAは持っていないので, そのままの大きさでは実装できなかった. 速度と回路規模のトレードオフがよくわかる回路だと思う.