素数を数えて落ち着くんだ...

VHDLで素数を数え上げる回路を記述する.

ソフトウェアプログラム

まずはC言語でどのようにするか調べる. 大抵のアルゴリズムはソフトウェアではすでに作られていて, HDLでは作られていないということが多い. なのでソフトウェア言語からHDLに翻訳するのが一番の近道.

素数を求めるプログラム - TSG http://www.tsg.ne.jp/TT/tsg/c/mansaku/P01.html
こちらのサイトを参考にC言語でプログラミングする.

素数を数え上げるアルゴリズムは以下のようになるらしい.

3以上の奇数( $i$ )を提示
$3 \le j \le \sqrt{i}$ の奇数で割れるか( $i \mod j = 0$ )
$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が確かに素数である.

演算速度

この回路では当然割り算を行っていないため, 上記の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までの素数をすべて羅列していて無駄に長いので中略している. 中略なしソースはリポジトリのリンク参照.

	-- =====================================================================
	-- Title : Prime number counter
	--
	-- File Name : PRIME_CNT.vhd
	-- Designer : toms74209200 <https://github.com/toms74209200>
	-- Created : 2019/03/14
	-- Copyright : 2019 toms74209200
	-- License : MIT License.
	-- http://opensource.org/licenses/mit-license.php
	-- =====================================================================
	library ieee;
	use ieee.std_logic_1164.all;
	use ieee.std_logic_unsigned.all;

	entity PRIME_CNT is
	port(
	-- System --
	CLK : in std_logic; --(p) Clock
	nRST : in std_logic; --(n) Reset

	-- Control --
	STR : in std_logic; --(p) Start pulse
	BUSY : out std_logic; --(p) Calculation busy
	VALID : out std_logic; --(p) Data valid

	-- Data --
	DAT : out std_logic_vector(31 downto 0) --(p) Data
	);
	end PRIME_CNT;

	architecture RTL of PRIME_CNT is

	-- Parameter --
	constant CalcMax : std_logic_vector(31 downto 0) := X"05F5_E0FF"; -- Calculation max 99,999,999
	constant PrimeMax : integer := 1227; -- ROM max prime order

	-- Internal signals --
	signal busy_i : std_logic; --(p) Calculation busy
	signal valid_i : std_logic; --(p) Data valid
	signal dat_i : std_logic_vector(DAT'range); --(p) Data
	signal cnt_pls : std_logic_vector(0 to PrimeMax); --(p) Prime counter pulse

	-- Data array --
	type PrimeDatType is array(0 to 1227) of std_logic_vector(15 downto 0);
	signal ary_prime_cnt : PrimeDatType;

	-- ROM table --
	constant rom_prime : PrimeDatType :=
	(
	X"0003",
	X"0005",
	X"0007",
	~~
	X"26EF",
	X"26F5"
	);

	begin
	-- ***********************************************************
	-- Busy flag
	-- ***********************************************************
	process (CLK, nRST) begin
	if (nRST = '0') then
	busy_i <= '0';
	elsif (CLK'event and CLK = '1') then
	if (dat_i = CalcMax) then
	busy_i <= '0';
	elsif (STR = '1') then
	busy_i <= '1';
	end if;
	end if;
	end process;

	BUSY <= busy_i;


	-- ***********************************************************
	-- Prime number counter
	-- ***********************************************************
	process (CLK, nRST) begin
	for i in cnt_pls'range loop
	if (nRST = '0') then
	ary_prime_cnt(i) <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (busy_i = '1') then
	if (dat_i = rom_prime(i)) then
	ary_prime_cnt(i) <= rom_prime(i);
	elsif (ary_prime_cnt(i) = rom_prime(i)) then
	ary_prime_cnt(i) <= X"0001";
	else
	ary_prime_cnt(i) <= ary_prime_cnt(i) + 1;
	end if;
	else
	ary_prime_cnt(i) <= (others => '0');
	end if;
	end if;
	end loop;
	end process;

	ARY_CNT_PLS : for i in cnt_pls'range generate
	cnt_pls(i) <= '1' when (ary_prime_cnt(i) = rom_prime(i)-1) else '0';
	end generate;


	-- ***********************************************************
	-- Data counter
	-- ***********************************************************
	process (CLK, nRST) begin
	if (nRST = '0') then
	dat_i <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (busy_i = '1') then
	if (dat_i = CalcMax) then
	dat_i <= X"0000_0001";
	else
	dat_i <= dat_i + 2;
	end if;
	else
	dat_i <= X"0000_0001";
	end if;
	end if;
	end process;


	-- ***********************************************************
	-- Data
	-- ***********************************************************
	DAT <= dat_i when (valid_i = '1') else (others => '0');


	-- ***********************************************************
	-- Data valid
	-- ***********************************************************
	valid_i <= '1' when (busy_i = '1' and cnt_pls = 0) else '0';

	VALID <= valid_i;


	end RTL; --PRIME_CNT

view raw PRIME_CNT_norom.vhd hosted with ❤ by GitHub

https://github.com/toms74209200/PRIME_CNT

シミュレーションした結果が以下の通り.

見ての通り, 1を除外していないので1もデータとして出力されてしまっている.

ちなみにQuartus prime v18.0でコンパイルした結果は以下の通り. コンパイルにめちゃくちゃ時間がかかるので思いつきでコンパイルしてはいけない. 無駄に何回かコンパイルしたが, だいたい15分くらいかかっている.

+----------------------------------------------------------------------------------+
; 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は持っていないので, そのままの大きさでは実装できなかった. 速度と回路規模のトレードオフがよくわかる回路だと思う.

toms.log

2019/03/18

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

ソフトウェアプログラム

VHDL

どうやって割り算するか?

演算速度

回路規模

VHDLソース

0 件のコメント:

コメントを投稿

人気の投稿