Parallel random number generation for VLSI systems using cellular automata

Abstract

A novel random number generation (RNG) architecture of particular importance in VLSI for fine-grained parallel processing is proposed. It is demonstrated that efficient parallel pseudorandom sequence generation can be accomplished using certain elementary one-dimensional cellular automata (two binary states per site and only nearest-neighbor connections). The pseudorandom numbers appear in parallel from various cells in the cellular automaton on each clock cycle and pass standard empirical random number tests. Applications have been demonstrated in the design and analysis of special-purpose accelerators for Monte Carlo simulation of large intractable systems. In addition, significant advantages in pseudorandom built-in self-test of VLSI circuits using cellular automata based RNGs have been demonstrated.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>