Shift-register sequence random number generators on the hypercube concurrent computers

Abstract

We discuss the design of a class of shift-register sequence random number generators for the MIMD parallel computers, and particularly for the hypercube concurrent computers. The simplest implementation is to have each processor generating its own sequence provided that the initial seeds are linearly independent. We generate these initial seeds by using distinct linear congruential generators and finally bit-by-bit-exclusive-or with the system time in microseconds. Our shift-register sequence random number generators are coded in C and run under the CUBIX. The statistical tests are performed on each sequence generated by every single processor as well as on the combined sequence produced by all processors. The tests include chi- square, Kolmogorov-Smirnov, auto-correlation, runlength and n-tuple distribution tests. A statistical test has been devised for testing the sequences of random numbers generated by a MIMD parallel computer. Our test results indicate that our generators do provide independent sequences of random numbers with extremely long periods.

Additional details