LoginSignup
8
10

More than 5 years have passed since last update.

@ikwzm

XorShift-Add法による擬似乱数生成回路

Last updated at Posted at 2016-03-29

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ワードは32bit)の乱数を生成します。

  • ジェネリック変数でSEED値を設定できます。

  • 状態テーブルを書き換えることが可能です。

Fig.1 Top-Level Signaling Interface

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クロックで生成する乱数の数を指定します
このパラメータで指定できる数は１以上の整数です
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.2 Generate Timing (L=1)


Fig.3 Generate Timing (L=4)

Fig.3 Generate Timing (L=4)


Resouces and Performance

Xilinx社のFPGAで実装してみた結果を以下に示します。

Performanceの生成速度は１秒間に生成できるワード数(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

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 を用意しています。

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

このような貴重なアルゴリズムを惜しげもなく公開してくださった方々にはひたすら感謝です。

8
10
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
8
10