VLSI implementation of Tausworthe random number generator for parallel processing environment
VLSI implementation of Tausworthe random number generator for parallel processing environment
- Author(s): J. Saarinen ; J. Tomberg ; L. Vehmanen ; K. Kaski
- DOI: 10.1049/ip-e.1991.0019
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): J. Saarinen 1 ; J. Tomberg 1 ; L. Vehmanen 2 ; K. Kaski 1
-
-
View affiliations
-
Affiliations:
1: Department of Electrical Engineering, Tampere University of Technology, Tampere, Finland
2: Mathematics Department, Tampere University of Technology, Tampere, Finland
-
Affiliations:
1: Department of Electrical Engineering, Tampere University of Technology, Tampere, Finland
- Source:
Volume 138, Issue 3,
May 1991,
p.
138 – 146
DOI: 10.1049/ip-e.1991.0019 , Print ISSN 0143-7062, Online ISSN 2053-7948
A fast Tausworthe-type random number generator has been implemented as a VLSI circuit on silicon for Monte-Carlo simulation purposes in a parallel multiprocessor system environment. The generator, which has uniform distribution, has been contructed for use as a peripheral device to be connected with each processor unit. General considerations for parallel random number generation are discussed and desirable properties are reviewed as a starting point for a VLSI implementation. The hardware design is based on the maximal length shift register sequences. It involves concurrent architecture in which a single shift operation is equivalent to 16 shifts in the original shift register unit. A new 16-bit random number is generated during each shifting operation. The chip is fully microprocessor bus compatible with a 16-bit bidirectional data bus and three I/O control lines. The methods of shift register sequence segmentation are also reviewed. Practical aspects for parallel processing system purposes are given. The generator has been submitted to a comprehensive set of statistical tests.
Inspec keywords: VLSI; parallel processing; random number generation
Other keywords:
Subjects: Digital arithmetic methods; Semiconductor integrated circuits; Multiprocessing systems
References
-
-
1)
- C.P. Downing . Proposal for a digital pseudorandom number generator. Electron. Lett. , 11 , 435 - 436
-
2)
- Saarinen, J., Kaski, K.: Electronics Laboratory Report 7–86, 1986.
-
3)
- B.J. Collings , G.B. Hembree . Initializing generalized feedback shift register pseudo-random number generators. J. Assoc. Comput. Mach. , 4 , 706 - 711
-
4)
- J.P.R. Tootill , W.D. Robinson , A.G. Adams . The runs up- and down-performance of Tausworthe pseudo-random number generator. J. Assoc. Comput. Mach. , 3 , 381 - 399
-
5)
- K. Binder . (1983) , Applications of the Monte Carlo methods in statistical physics.
-
6)
- N. Zierler , J. Brillhart . On primitive trinomials (mod 2). Inf. Control , 541 - 554
-
7)
- D. Logan , C. Maples , A. Wouk . (1986) Scientific applications and numerical algorithms on the Midas multiprocessor system, New computing environments: parallel, vector and systolic.
-
8)
- S.H. Tsao . Generation of delayed replicas of maximal-length linear binary sequences. Proc. IEE , 11 , 1803 - 1806
-
9)
- P.D. Wasserman . (1989) , Neural computing, theory and practice.
-
10)
- K.P. Yiu . A simple method for the determination of feedback shift register connections for delayed maximal-length sequences. Proc. IEEE , 4 , 537 - 538
-
11)
- K. Binder . (1986) , Monte Carlo methods in statistical physics.
-
12)
- J. Saarinen , K. Kaski , J. Viitanen . A Parallel multi-processor system for Monte Carlo simulations in statistical physics. Rev. Sci. Instrum. , 9 , 2981 - 2991
-
13)
- O. Percus , M. Kalos . Random number generators for MIMD parallel processors. J. Parallel Distrib. Comput. , 477 - 497
-
14)
- J.E. Marshall , B. Ireland , K.J. Latawiec . New method of generation of shifted linear pseudorandom sequences. Proc. IEE , 2
-
15)
- R.C. Tausworthe . Random numbers generated by linear recurrency modulo two. Mat. Comput. , 201 - 209
-
16)
- G. Fox , M. Johnson , G. Lyzenga , S. Otto , J. Salmon , D. Walker . (1988) , Solving problems on concurrent processors; general techniques and regular problems.
-
17)
- A.B. Gardiner . Logic PRBS delay calculator and delayed-version generator with automatic delay-changing facility. Electron. Lett. , 5 , 123 - 125
-
18)
- J.J. Narraway . Probability machines and shift-register sequence segmentation. IEE Proc. G , 5 , 209 - 215
-
19)
- C.M. Rader , L.R. Rabiner , R.W. Schafer . A fast method of generating digital random numbers. Bell Syst. Tech. J. , 2303 - 2310
-
20)
- J. Tomberg , J. Saarinen , K. Kaski . A fast random number generator chip for microprocessor system. Norchip News , 3 - 4
-
21)
- K.S. Sastri . Generation of delayed replicas of linear p-level m-sequences. Int. J. Syst. Sci. , 5 , 409 - 416
-
22)
- K.J. Latawiec . New method of generation of shifted linear pseudorandom binary sequences. Proc. IEE , 8 , 905 - 906
-
23)
- A. Hoogland , J. Spaa , B. Selman , A. Compagner . A special-purpose processor for the Monte Carlo simulation of Ising Spin Systems. J. Computational Physics , 250 - 260
-
24)
- B. Ireland , J.E. Marshall . Matrix method to determine shift-register connections for delayed binary sequences. Electron. Lett. , 21 , 467 - 468
-
25)
- D.H. Green . Nonlinear product-feedback shift registers. Proc. IEE , 4 , 681 - 686
-
26)
- N. Zierler , J. Brillhart . On primitive trinomials (mod 2). Inf. Control , 566 - 569
-
27)
- R.B. Pearson , J.L. Richardson , D. Toussaint . A fast processor for Monte Carlo simulation. J. Comput. Phys. , 241 - 249
-
28)
- M.T.G. Hughes . Transition-matrix construction for pseudorandom binary-sequence generators. Electron. Lett. , 19 , 417 - 419
-
29)
- A.N. van Luyn . Shift-register connections for delayed versions of m-sequences. Electron. Lett. , 22 , 713 - 715
-
30)
- T.G. Lewis , W.H. Payne . Generalized feedback shift register pseudorandom number algorithm. J. Assoc. Comput. Mach. , 3 , 456 - 468
-
31)
- J.E. Marshall , B. Ireland , B.G. Bajoga , K.J. Latawiec . Correspondence to new method of generation of shifted linear pseudorandom binary sequences. Proc. IEE , 4
-
32)
- R.W. Schafer , R.M. Mersereau , T.P. Barnwell . (1983) , TMS32010 user's guide.
-
33)
- P. Fredrickson , R. Hiromoto , T.L. Jordon , B. Smith , T. Warnock . Pseudorandom trees in Monte Carlo. Parallel Comput.
-
34)
- D.E. Knuth . (1981) , The art of computer programming, Vol. 2: Semi-numerical algorithms.
-
35)
- N. Zierler . Primitive trinomials whose degree is a Mersenne exponent. Inf. Control , 67 - 69
-
36)
- N.D. Deans , D.P. Mann . (1982) An Improved generation technique for random number sequences, Mathematics and computers in simulation XXIV.
-
37)
- B.W. Kernighan , D.M. Ritchie . (1978) , The C Programming language.
-
38)
- W.J. Hurd . Efficient generation of statistically good pseudonoise by linearly interconnected shift registers. IEEE Trans. , 2 , 146 - 152
-
39)
- D.G. Maritsas , A.C. Arvillas , A.C. Bounas . Phase shift analysis of linear feedback shift register structures generating pseudorandom sequences. IEEE Trans. , 7 , 660 - 669
-
40)
- R.P. Lippmann . An introduction to computing with neural nets. IEEE ASSP Mag. , 4 - 22
-
41)
- P.D. Roberts , A.C. Davies , S.H. Tsao . Discussion on generation of delayed replicas of maximal-length binary sequences. Proc. IEE , 4 , 702 - 704
-
42)
- Barel, M.: `Fast hardware random number generator for the Tausworthe sequence', Proc. 16th Annual Simulation Symp., 16–18 March 1983, Tampa, Florida, p. 121–135.
-
43)
- S.M. Sze . (1988) , VLSI technology.
-
44)
- A.C. Davies . Further notes on delayed versions of linear binary sequences. Electron. Lett. , 7 , 190 - 191
-
45)
- M.G. Hartley . Development design and test procedure for random generators using chain-codes. Proc. IEE , 1 , 22 - 34
-
46)
- J.R.B. Whittlesey . A comparison of the correlational behavior of random number generators for the IBM 360. Commun. ACM , 641 - 644
-
47)
- University of Washington, Dept. of Computer Science, Seattle, Ousterhout, J.: `Editing VLSI circuits with CAESAR', 1985, VLSI Design Tools Reference Manual, Release 3.0.
-
48)
- D.G. Maritsas , A. Bounas . Direct determination of feedback shift register connections for delayed m-sequences generation. Electron. Lett. , 10 , 308 - 310
-
49)
- J.L. Perry , R.W. Schafer , L.R. Rabiner . A digital hardware realization of a random number generator. IEEE Trans. , 4 , 236 - 240
-
50)
- J.P.R. Tootill , W.D. Robinson , D.J. Eagle . An asymptotically random Tausworthe sequence. J. Assoc. Comput. Mach. , 3 , 469 - 481
-
51)
- J.L. Douce . Delayed versions of m-sequences. Electron. Lett. , 12
-
52)
- A.J. Miller , A.W. Brown , P. Mars . A simple technique for the determination of delayed maximal length linear binary sequences. IEEE Trans. , 8 , 808 - 811
-
53)
- R.W. Hockney , J.W. Eastwood . (1981) , Computer simulations using particles.
-
54)
- S.W. Golomb . (1982) , Shift register sequences.
-
55)
- A.C. Davies . Delayed versions of maximal-length linear binary sequences. Electron. Lett. , 3 , 61 - 62
-
56)
- B. Ireland , J.E. Marshall . Matrix method to determine shift-register connections for delayed binary sequences. Electron. Lett. , 15 , 309 - 310
-
57)
- J.R. Jordan , B. Kiani-Shabestari . Deriving delayed sequences from pseudo-random-noise generators using exclusive NOR feedback. IEE Proc. G , 3 , 89 - 93
-
1)
Related content
