Generating system of random-number sequences for a parallel computer system

• US 5,327,365 A
• Filed: 08/20/1992
• Issued: 07/05/1994
• Est. Priority Date: 08/23/1991
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Okuda, Motoi, Fujisaki, Masahide
• Primary Examiner(s): NGUYEN, LONG
• Application Number:
  US07/932,687
• Time in Patent Office: 684 Days
• Field of Search: 364/717
• US Class Current: 708/254
• CPC Class Codes: G06F 2207/581 Generating an LFSR sequence, e.g. an m-sequence; sequence may be generated without LFSR, e.g. using Galois Field arithmetic
• CPC Class Codes: G06F 2207/583 Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register
• CPC Class Codes: G06F 7/586 using an integer algorithm, e.g. using linear congruential method

Abstract

In a parallel computer system comprising a plurality of processor elements, a parent processor element generates random-number initial values, and distributes the random-number initial values to child processor elements using a communication mechanism or a shared memory; and child processor elements conduct processing to generate random-number sequences in accordance with the maximum length shift register sequence (M-sequence) method using the distributed random-number initial values as seeds.

Claims

1. A method of generating random-number sequences in a parallel computer system comprising a plurality of processor elements, said method comprising:

defining a first set of processor elements required to generate random numbers and defining a second set of processor elements, coupled to said first set of processor elements and operable for generating random-number initial values;

generating, by one of said second set of processor elements, p×

v×

k pieces of random-number initial values, wherein p is a parameter of a primitive irreducible polynomial prescribing random-number generation, v is a predetermined value not less than 1, and k is a number of said first set of processor elements

allocating to said first set of processor elements respective random-number initial values; and

generating random numbers A_n, by one of said first set of processor elements, through bit-by-bit logical operation of random-number values A_n-pv and A_n-rv using p×

v pieces allocated thereto from said p×

v×

k pieces of said generated random-number initial values, wherein q is defined as a parameter of a primitive irreducible polynomial prescribing random-number generation, r is defined as one of q and (p-q), and n is defined as being greater than or equal to p×

v+1.

2. A method of generating random-number sequences in a parallel computer system as set forth in claim 1 wherein said bit-by-bit logical operation is an exclusive-OR operation.

3. A method of generating random-number sequences in a parallel computer system as set forth in claim 1, wherein r is defined as the greater value one of q and (p-q).

4. A method of generating random-number sequences in a parallel computer system as set forth in claim 1, wherein if a vector length of a vector operating mechanism of one of said first set of processor elements is expressed by α

, v is selected from among values (r×

v) which are larger than α

.

5. A method of generating random-number sequences in a parallel computer system as set forth in claim 4 wherein v is selected as the minimum value greater than α

from among values (r×

v).

6. A method of generating random-number sequences in a parallel computer as set forth in claim 4 wherein one of said first set of processor elements generates random-number sequences in increments of said vector length α

of said vector operating mechanism.

7. A method of generating random-number sequences in a parallel computer system as set forth in claim 1 wherein v is an exponentiated-2 value.

8. A method of generating random-number sequences in a parallel computer system as set forth in claim 1 wherein one of said second set of processor elements generates random-number initial values using one of the maximum length shift register sequence (M-sequence) method singly, and a combination of the M-sequence random-number sequence generating method and mixed congruential sequence generating method.

9. A method of generating random-number sequences in a parallel computer as set forth in claim 1 wherein one of the second set of processor elements is configured to function as one of the first set of processor elements.

10. A method of generating random-number sequences in a parallel computer as set forth in claim 1 wherein one of the second set of processor elements arranges and transfers generated random-number initial values to one of the first set of processor elements using communication means coupled to said plurality of processor elements, said one of the second set of processor elements obtains random initial values by selectively receiving random-number initial values allocated to said one of the second set of processor elements in accordance with a predetermined regularity from among said transferred random-number initial values.

11. A method of generating random-number sequences in a parallel computer system as set forth in claim 1 wherein one of a second set of processor elements writes generated random-number initial values into a shared memory area, coupled to said plurality of processor elements, that can be accessed by other of said plurality of processor elements, and one of a first set of processor elements obtains random-number initial values by accessing the shared memory area, and selectively reads random-number initial values allocated to said one of said first set of processor elements.

12. A method of generating random-number sequences in a parallel computer system comprising a plurality of processor elements, interconnected and generating random-number initial values, said method comprising:

defining a first set of processor elements, selected from said plurality of processor elements and each thereof required to generate random numbers;

generating p×

v×

k pieces of random-number initial values, by each of said plurality of processor elements and in accordance with a first algorithm wherein p is a parameter of a primitive irreducible polynomial prescribing random-number generation, v is a predetermined value not less than 1, and k is a number of said first set of processor elements;

allocating to said first set of processor elements respective said random-number initial values;

extracting, by said first set of processor elements, p×

v pieces of the respective random-number initial values allocated thereto; and

generating, by said first set of processor elements, random numbers A_n through bit-by-bit logical operation of random-number values A_n-pv and A_n-rv using p×

v pieces of said extracted random-number initial values, wherein if q is defined as a parameter of a primitive irreducible polynomial prescribing random-number generation, r is defined as one of q and (p-q), and n is ≧

p×

v+1.

13. A method of generating random-number sequences in a parallel computer system as set forth in claim 12 wherein said bit-by-bit logical operation is an exclusive-OR operation.

14. A method of generating random-number sequences in a parallel computer system as set forth in claim 12 wherein r is defined as the greater value one of q and (p-q).

15. A method of generating random-number sequences in a parallel computer system as set forth in claim 12 wherein if a vector length of a vector operating mechanism of one of said first set of processor elements is expressed by α

, v is selected from among values (r×

v) which are larger than α

.

16. A method of generating random-number sequences in a parallel computer system as set forth in claim 12 wherein v is an exponentiated-2 value.

17. A method of generating random-number sequences in a parallel computer system as set forth in claim 12 wherein one of said plurality of processor elements generates random-number initial values using one of the maximum length shift register sequence (M-sequence) method singly, and a combination of the M-sequence random-number sequence generating method and mixed congruential sequence generating method.