Parallel computation of non-deterministic algorithms in vlsi
Peter D. Hortensius · Mspace (University of Manitoba) · 1987
This work examines parallel VLSI implementations of nondeterministic algor¡thms.It is demonstrated that conventional pseudorandom number generators are unsuitable for highly parallel applications.For example, while linear feedback shift registers (LFSR) arê adequate for generat¡on of single pseudorandom bit streams, the bit streams from different cells in the LFSR are highly correlated.Efficient parallel pseu- dorandom sequence goneration can be accomplishsd using cortain classes of elementary one-dimensional cellular automata (two binary states per site and only nearest neighbour connections).The pseudorandom numbers appear in parallel from various cells ¡n the cellular aulomaton on each clock cycle.Extensive study of the properties of these new pseudorandom number generators is made using standard empirical ran- dom number tests, cycle length tests, and implementation considerations.Furthermore, it is shown these particular one-dimensional cellular automata can form the basis of efficient VLSI architectures for computations involved in the Monte Carlo simulat¡on of both lhe percolation and lsing models from statistical mechanics.The architectures provide a spatially-distributed set of pseudorandom numbers which are required in the local nondeterministic decisions at the various sites in lhe array.lt lmplementation of the Domany and Kinzel lsing Computer ...