XORSHIFT-ADD(XSAdd) Pseudo Random Number Generator
こちらの記事(「XorShift-Add法による擬似乱数生成VHDLパッケージ」 )では XORSHIFT-ADD(XSadd)法で擬似乱数生成するための VHDL のパッケージを紹介しましたが、この記事ではそのパッケージを使って実際に回路を作ってFPGAに実装した例を示します。
ソースコードやFPGAの開発環境などはこちらにあります。
https://github.com/ikwzm/XSadd_Rand_Gen
Overview
Introduction
このIPは XORSHFIT-ADD(XSAdd)法による擬似乱数生成回路です。
こちらを参考に書いてみました。
XORSHIFT-ADD (XSadd): A variant of XORSHIFT
Features
-
XORSHFIT-ADD(XSAdd)法による擬似乱数生成回路です。
-
VHDLで記述しています。
-
論理合成可能です。Xilinx社のVivado、Altera社のQuartusIIで確認済み。
-
1クロックで1〜数ワード(1ワードは32bit)の乱数を生成します。
-
ジェネリック変数でSEED値を設定できます。
-
状態テーブルを書き換えることが可能です。
Fig.1 Top-Level Signaling Interface
Licensing
二条項BSDライセンス (2-clause BSD license) で公開しています。
Specification
Parameter Descriptions
Table.1 Parameter Descriptions
Name | TYPE | Default | Description |
L | Integer | 1 | 1クロックで生成する乱数の数を指定します このパラメータで指定できる数は1以上の整数です |
SEED | Integer | 1234 | 乱数のシード値を指定しますこのシード値を元に状態テーブルが初期化されます |
Port Descriptions
Table.2 Port Descriptions
Name | Type | Width | I/O | Description |
CLK | STD_LOGIC | 1 | in | クロック信号 |
RST | STD_LOGIC | 1 | in | 非同期リセット信号 |
RND_RUN | STD_LOGIC | 1 | in | 乱数生成開始信号 この信号が'1'になってから1クロック後に乱数を出力します TBL_INITが'1'の時、この信号を'1'にしてはいけません |
RND_NUM | STD_LOGIC_VECTOR | 32*L | out | 乱数出力信号 生成された乱数を出力する信号RND_VALが'1'の時のみ有効な値を出力しますRND_VAL='1'かつRND_RDY='1'で次の乱数を生成します |
RND_VAL | STD_LOGIC | 1 | out | 乱数有効信号 RND_NUMから出力された乱数が有効であることを示す信号 |
RND_RDY | STD_LOGIC | 1 | in | 乱数応答信号 RND_NUMの値を取り出したことを示す信号RND_VAL='1'かつRND_RDY='1'で次の乱数を生成します |
TBL_INIT | STD_LOGIC | 1 | in | 状態テーブル・初期化信号 状態テーブルを初期化することを示します状態テーブルを明示的に初期化しない場合はこの信号を'0'にしてください。TBL_INITを'0'にしてから乱数が生成されるまで2クロックの遅れが生じます。 |
TBL_WDATA | STD_LOGIC_VECTOR | 128 | in | 状態テーブル・ライトデータ |
TBL_RDATA | STD_LOGIC_VECTOR | 128 | out | 状態テーブル・リードデータ |
Timing Diagram
Fig.2 Generate Timing (L=1)
Fig.3 Generate Timing (L=4)
Resouces and Performance
Xilinx社のFPGAで実装してみた結果を以下に示します。
Performanceの生成速度は1秒間に生成できるワード数(1ワードは32bit)の理論値です。
Table.3 Resouces and Performance(Xilinx)
Device | Parameter | Resouces | Performance | ||||
Slices | LUT | ||||||
Family | Speed | L | Logic | F/F | Fmax | Generate word/sec | |
Artix-7 | 3 | 1 | 28 | 66 | 106 | 250[MHz] | 250[Mword/sec] |
2 | 49 | 162 | 186 | 250[MHz] | 500[Mword/sec] | ||
3 | 78 | 258 | 283 | 250[MHz] | 750[Mword/sec] | ||
4 | 110 | 372 | 388 | 250[MHz] | 1000[Mword/sec] | ||
5 | 134 | 454 | 495 | 250[MHz] | 1250[Mword/sec] | ||
6 | 159 | 551 | 575 | 250[MHz] | 1500[Mword/sec] | ||
7 | 182 | 664 | 681 | 250[MHz] | 1750[Mword/sec] | ||
8 | 211 | 764 | 797 | 250[MHz] | 2000[Mword/sec] | ||
12 | 344 | 1275 | 1313 | 250[MHz] | 3000[Mword/sec] | ||
16 | 471 | 1759 | 1798 | 250[MHz] | 4000[Mword/sec] | ||
20 | 627 | 2317 | 2359 | 250[MHz] | 5000[Mword/sec] | ||
24 | 798 | 2911 | 2985 | 250[MHz] | 6000[Mword/sec] | ||
28 | 963 | 3566 | 3657 | 250[MHz] | 7000[Mword/sec] | ||
32 | 1102 | 4113 | 4226 | 250[MHz] | 8000[Mword/sec] |
Architecture
Block Diagram
Fig.4 Block Diagram
Source Code Description
ここではXSADD_RAND_GENのソースコードを簡単に説明します。
エンティティ
library ieee;
use ieee.std_logic_1164.all;
entity XSADD_RAND_GEN is
generic (
L : integer := 1;
SEED : integer := 1234
);
port (
CLK : in std_logic;
RST : in std_logic;
TBL_INIT : in std_logic := '0';
TBL_WDATA : in std_logic_vector(127 downto 0) := (others => '0');
TBL_RDATA : out std_logic_vector(127 downto 0);
RND_RUN : in std_logic := '1';
RND_VAL : out std_logic;
RND_NUM : out std_logic_vector(L*32-1 downto 0);
RND_RDY : in std_logic := '1'
);
end XSADD_RAND_GEN;
XSADD_RAND_GEN モジュールの外部とのインターフェース(Parameter と Port)を宣言しています。Parameter と Port の詳細は前節のSpecification を参照してください。
使用するライブラリの宣言
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
library XSADD;
use XSADD.XSADD.all;
architecture RTL of XSADD_RAND_GEN is
アーキテクチャ宣言の前に使用するライブラリを宣言しています。
XSADDパッケージは XORSHIFT-ADD(XSadd)擬似乱数生成用のVHDLのパッケージです。このパッケージに擬似乱数ジェネレーターの各種タイプや関数が定義されています。詳細はこちらの記事(「XorShift-Add法による擬似乱数生成VHDLパッケージ」 )を参照してください。
乱数ジェネレーターの状態を保持するレジスタの宣言と初期値の定義
type STATUS_VECTOR is array(integer range <>) of PSEUDO_RANDOM_NUMBER_GENERATOR_TYPE;
constant RESET_STATUSES : STATUS_VECTOR(L-1 downto 0)
:= (others => NEW_PSEUDO_RANDOM_NUMBER_GENERATOR(TO_SEED_TYPE(SEED)));
signal curr_statuses : STATUS_VECTOR(L-1 downto 0);
XSADD_RAND_GEN では一度に複数の乱数を生成することが出来ます。したがって保持する乱数の状態もその分だけ用意するために配列にしています。
リセット時には SEED parameter で指定されたシード値で内部状態を初期化します。そのための初期値をここで定義しています。
内部信号の宣言
signal random_number : RANDOM_NUMBER_VECTOR(L-1 downto 0);
signal random_valid : boolean;
signal initial_next : boolean;
signal status_valid : boolean;
signal status_ready : boolean;
begin
初期化直後に状態を遷移させるための信号
process(CLK, RST) begin
if (RST = '1') then
initial_next <= TRUE;
elsif (CLK'event and CLK = '1') then
initial_next <= (TBL_INIT = '1');
end if;
end process;
XORSHIFT-ADD(XSadd)では、内部状態を遷移してから乱数を生成します。そのためXSADD_RAND_GEN では、リセット解除直後またはTBL_INIT信号ネゲート直後に、一回だけ状態を遷移させるためのinitial_next信号を用意しています。
乱数ジェネレーターの状態遷移
process(CLK, RST)
variable next_status : PSEUDO_RANDOM_NUMBER_GENERATOR_TYPE;
begin
if (RST = '1') then
curr_statuses <= RESET_STATUSES;
elsif (CLK'event and CLK = '1') then
if (TBL_INIT = '1') then
for i in 0 to 3 loop
next_status.status(i) := unsigned(TBL_WDATA(32*(i+1)-1 downto 32*i));
end loop;
curr_statuses(curr_statuses'high) <= next_status;
elsif (initial_next = TRUE) or
(status_valid = TRUE and status_ready = TRUE) then
next_status := curr_statuses(curr_statuses'high);
for i in curr_statuses'low to curr_statuses'high loop
NEXT_PSEUDO_RANDOM_NUMBER_GENERATOR(next_status);
curr_statuses(i) <= next_status;
end loop;
end if;
end if;
end process;
status_valid <= (initial_next = FALSE and TBL_INIT = '0' and RND_RUN = '1');
ここでは乱数ジェネレーターの現在の状態を保持するレジスタの初期化と更新を行います。
同期リセット(RST)信号のアサート時には SEED で指定された初期値をレジスタにセットします。
TBL_INIT信号のアサート時にはTBL_WDATAの値をレジスタにセットします。
initial_next信号のアサート時(リセット信号のネゲート直後またはTBL_INIT信号のネゲート直後)、または後段の乱数生成器が次の乱数を生成するタイミングで、乱数ジェネレーターの状態を次の状態に更新します。
乱数ジェネレータが乱数を生成出来るようになった時、status_valid信号をアサートします。なお、リセット時またはTBL_INIT信号のアサート時のレジスタ初期化時、および、リセット信号のネゲート直後またはTBL_INIT信号のネゲート直後の乱数ジェネレータ更新時は、乱数を生成出来ないのでstatus_valid信号はアサートされません。
乱数生成器
process(CLK, RST) begin
if (RST = '1') then
random_valid <= FALSE;
random_number <= (others => (others => '0'));
elsif (CLK'event and CLK = '1') then
random_valid <= status_valid;
if (status_valid = TRUE and status_ready = TRUE) then
for i in curr_statuses'range loop
random_number(i) <= GENERATE_TEMPER(curr_statuses(i));
end loop;
end if;
end if;
end process;
status_ready <= ((random_valid = FALSE) or
(random_valid = TRUE and RND_RDY = '1'));
ここでは乱数ジェネレーターの現在の状態から乱数を生成します。
random_valid信号は生成した乱数が有効であることを示します。具体的には、status_valid信号がアサートされた時つまり乱数ジェネレータが乱数を生成出来るようになった時、random_valid信号をアサートします。
status_valid信号がアサートされた時、乱数を生成してrandom_numberレジスタにセットします。ただし、乱数を出力している状態(random_valid信号がアサートされている状態)でRND_RDY信号がネゲートされている場合は、random_numberレジスタは前の乱数の値を保持したまま、次の乱数は生成しません。
次の乱数を生成するタイミングと同時に前段の乱数ジェネレータの状態を次の状態に更新します。status_ready信号はそのタイミングを示します。
出力信号の生成
RND_VAL <= '1' when (random_valid = TRUE) else '0';
RND_NUM_GEN: for i in 0 to L-1 generate
RND_NUM(32*(i+1)-1 downto 32*i) <= std_logic_vector(random_number(i));
end generate;
TBL_RDATA_GEN: for i in 0 to 3 generate
TBL_RDATA(32*(i+1)-1 downto 32*i) <= std_logic_vector(curr_statuses(L-1).status(i));
end generate;
end RTL;
ここでは生成した内部信号(random_valid信号、random_numberレジスタ)および乱数ジェネレーターの現在の状態を外部ポートに出力します。
Simulation
GHDLによるシミュレーション
GHDLのバージョン
GHDLのバージョンは0.29です。
GHDLのホームページはこちら(http://ghdl.free.fr)
Makefile
シミュレーション用に Makefile を用意しています。
GHDL=ghdl
GHDLFLAGS=--mb-comments
WORK=XSADD
TEST_BENCH = test_bench \\
$(END_LIST)
all: $(TEST_BENCH)
clean:
rm -f *.o *.cf $(TEST_BENCH)
test_bench: xsadd.o xsadd_rand_gen.o test_bench.o
$(GHDL) -e $(GHDLFLAGS) $@
-$(GHDL) -r $(GHDLRUNFLAGS) $@
test_bench.o: ../../src/test/vhdl/test_bench.vhd xsadd_rand_gen.o
$(GHDL) -a $(GHDLFLAGS) --work=work $<
xsadd.o: ../../src/main/vhdl/xsadd.vhd
$(GHDL) -a $(GHDLFLAGS) --work=$(WORK) $<
xsadd_rand_gen.o: ../../src/main/vhdl/xsadd_rand_gen.vhd xsadd.o
$(GHDL) -a $(GHDLFLAGS) --work=$(WORK) $<
シミュレーションの実行
$ cd sim/ghdl
$ cd make
ghdl -a --mb-comments --work=XSADD ../../src/main/vhdl/xsadd.vhd
ghdl -a --mb-comments --work=XSADD ../../src/main/vhdl/xsadd_rand_gen.vhd
ghdl -a --mb-comments --work=work ../../src/test/vhdl/test_bench.vhd
../../src/test/vhdl/test_bench.vhd:174:18:warning: function "to_dec_string" is never referenced
ghdl -e --mb-comments test_bench
ghdl -r test_bench
xsadd_init(1234)
32-bit unsigned integers r, where 0 <= r < 2^32
1823491521 1658333335 1467485721 45623648
3336175492 2561136018 181953608 768231638
3747468990 633754442 1317015417 2329323117
688642499 1053686614 1029905208 3711673957
2701869769 695757698 3819984643 1221024953
110368470 2794248395 2962485574 3345205107
592707216 1730979969 2620763022 670475981
1891156367 3882783688 1913420887 1592951790
2760991171 1168232321 1650237229 2083267498
2743918768 3876980974 2059187728 3236392632
xsadd_init([0x0a, 0x0b, 0x0c, 0x0d])
32-bit unsigned integers r, where 0 <= r < 2^32
138a38f9 b396fa84 a55a2ee8 24b7ed06
f0bae2fe d8ace1a7 d4b09a3f d7fcf441
fc55ee1b 5b4ab585 d4bf254b 5b0f77ba
31161b97 b21ccc3b ab418bfb 4cc8476a
06a1a28f cb1f50c6 f0ba2ed3 7907f372
3256d76c d843e864 d63a60b7 eff88358
ddc3b083 b5734b65 f08d644d e5f6c809
95bf2ae3 e5867758 f260d462 39d244dc
b9fbb8d7 63e8f3d9 b34ea936 8fe4ee75
8803c8f1 d74e420e a5c14d22 20be253f
../../src/test/vhdl/test_bench.vhd:373:9:@530ns:(assertion failure): Run complete...
./test_bench:error: assertion failed
./test_bench:error: simulation failed
Makefile:14: recipe for target 'test_bench' failed
make: [test_bench] Error 1 (無視されました)
最後にエラーが出てるように見えますが、これはassert(FALSE)でシミュレーションを終了しているためです。
Vivadoによるシミュレーション
Vivadoのバージョン
Vivado 2015.4
Vivado プロジェクトの作成
すでにプロジェクトを作っている場合は省略してください。
プロジェクトを生成するためのTclスクリプトを用意しています。
sim/vivado/create_project.tcl
上記のTclスクリプトをVivado で実行するとプロジェクトが作成されます。
Vivado > Tools > Run Tcl Script > create_project.tcl
シミュレーションを実行
Vivado > Open Project > xsadd_rand_gen.xpr
Flow Navigator > Run Simulation > Run Behavioral Simulation
Synthesis and Implementation
Vivadoによる論理合成
Vivadoのバージョン
Vivado 2015.4
Vivado プロジェクトの作成
すでにプロジェクトを作っている場合は省略してください。
プロジェクトを生成するためのTclスクリプトを用意しています。
fpga/xilinx/vivado2015.4/xsadd_rand_gen/create_project.tcl
上記のTclスクリプトをVivado で実行するとプロジェクトが作成されます。
Vivado > Tools > Run Tcl Script > create_project.tcl
デバイスはとりあえずxc7a15tcsg324-3を指定しますが、変更したい場合は、create_project.tcl を修正してください。
Synthesis
Flow Navigator > Run Synthesis
Implementation
Flow Navigator > Run Implementation
QuartusIIによる論理合成
QuartusIIのバージョン
Quartus Prime 15.1
QuartusII用のプロジェクト
fpga/altera/15.1/xsadd_rand_gen.qpf
Acknowledgments
このような貴重なアルゴリズムを惜しげもなく公開してくださった方々にはひたすら感謝です。