A generating system of random-number sequences for a parallel computer system

COMPLETE SPECIFICATION

FOR A STANDARD PATENT

ORIGINAL

<td colspan="2"> Name and Address</td><td rowspan="2"> Fujitsu Limited 1015, Kamikodanaka, Nakahara-ku Kawasaki-shi Kanagawa 211 JAPAN</td>

<td> • · • ·</td><td> of Applicant:</td>

<td> • · · • · · • · · • • ·</td><td> Actual Inventor(s):</td><td> Masahide Fujisaki, Motoi Okuda</td>

<td> • • · • · *</td><td> Address for Service:</td><td> Spruson &amp; Ferguson, Patent Attorneys</td>

<td> • · ·</td><td></td><td> Level 33 St Martins Tower, 31 Market Street Sydney, New South Wales, 2000, Australia</td>

<td></td><td> Invention Title:</td><td> A Generating System of Random-number Sequences for a</td>

<td> « «V • · ·</td><td></td><td> Parallel Computer System</td>

• ·

<img file="AU644306B2_D0001.tif" />

The following statement 1s a full description of this invention, including the best method of performing it known to me/us:5845/4

<td> i -</td><td> r</td><td></td>

<td> « *</td><td></td><td> 1</td>

<td></td><td></td><td> SPECIFICATION</td>

<img file="AU644306B2_D0002.tif" />

<img file="AU644306B2_D0003.tif" />

• · · • · · • · · · • · · ·

<img file="AU644306B2_D0004.tif" />

[TITLE OF THE INVENTION]

A generating system of random-number sequences for a parallel computer system [BACKGROUND OF THE INVENTION] [FIELD OF THE INVENTION]

This invention relates a generating system of random-number sequence for a parallel computer system in which each processor element comprising a parallel computer system can generate at high speed long-period random-number sequences having different lists.

[DESCRIPTION OF THE PRIOR ART]

A data processing system is required to generate at high speed long-period random-number sequences, such as used in computer simulations relying on the Monte Carlo method. In recent years, on the other hand, data processing systems comprising parallel computer systems have been widely used to enhance data processing capabilities. This trend has created the need for each processor element. of a parallel computer system to generate at high speed longer-period random-number sequences having different lists.

Improvements that have heretofore been made, however, are largely directed toward the high-speed generation of random-number sequences on a single vector processor, but few proposals have been made about the method of generating random-number sequences in a parallel computer system.

It is against this background that P. Fredrickson et al. have recently proposed a concept about the method of generating random-number sequences in a parallel computer system (Fredrickson, P., et al., f

<img file="AU644306B2_D0005.tif" />

Pseudo-random trees in Monte Carlo, Parallel Computing, Vol. 1, No. 2 1984, 175-180). On the basis of the concept of pseudo-random trees, this proposal implements the generation of random-number sequences, as a parent processor generates seeds for random-number generation in accordance with the multipl icati*'e or mixed congruential sequence (hereinafter referred to MC-sequence) method using pseudo-random trees, and distributes the seeds to child processors, which in turn generate random-number sequences in accordance with the multiplicative or mixed congruential sequence (MC-sequence) method.

The method of generating random-number sequences proposed by P. Fredrickson et al., which can generate random-number sequences in each processor of a parallel computer system, however, has a drawback in that it can generate only shorter-period random-number sequences because it is based on the multiplicative or mixed congruential sequence method. In a 32-bit computer, for example, only random-number sequences having at most a period of (2^Οώ - 1) can be generated. .

In random-number sequence generation, it is very important to prevent random-number sequences generated by each processor from being correlated with each other. The method of generating random-number se* quences proposed by P. Fredrickson et al., however, has the difficulty in determining coefficient values used for generating pseudo-random trees to prevent this correlation because it imposes additional complex limitations on the coefficient values.

[SUMMARY OF THE INVENTION]

It is therefore an object of this invention to enable .each processor comprising a parallel computer system to generate long-period random-number sequences.

It is another object of this invention to enable each processor comprising a parallel computer system to generate random-number sequences that are not correlated with each other.

It is still another object of this invention to 5 enable each processor comprising a parallel computer to generate random-number sequences at high speed.

To accomplish these objectives, this invention provides a generating system of random-number sequences for a parallel computer system in which each processor 10 of the parallel computer system can generate longperiod random-number sequences that are not correlated with each other.

[BRIEF DESCRIPTION OF THE DRAWINGS]

<td></td><td></td><td> Fig .</td><td> 1</td><td> is a diagram illustrating</td><td> the</td><td> operating</td>

<td></td><td> 15</td><td> principle</td><td> of</td><td> this invention.</td><td></td><td></td>

<td></td><td></td><td> Fig.</td><td> 2</td><td> is a diagram illustrating</td><td> the</td><td> operating</td>

<td></td><td></td><td> principle</td><td> of</td><td> this invention.</td><td></td><td></td>

<td> 9 9 9 9</td><td></td><td> Fig.</td><td> 3</td><td> is a diagram illustrating</td><td> the</td><td> operating</td>

<td> 9 9 9 9 9 9 9 99</td><td></td><td> principle</td><td> of</td><td> this invention.</td><td></td><td></td>

<td> 9 9 9</td><td> 20</td><td> Figs·</td><td colspan="2"> 4A, 4B and 4C are diagrams of</td><td colspan="2"> assistance in</td>

<td> • 9 9</td><td></td><td colspan="2"> explaining</td><td> a parallel computer system</td><td> to</td><td> which the</td>

<td> 9 9 9 9 9 9 9 9 9</td><td></td><td> generation</td><td colspan="2"> of random-number sequences of</td><td> this</td><td> invention</td>

<td></td><td></td><td colspan="3"> can be applied.</td><td></td><td></td>

<td></td><td></td><td> Fig .</td><td> 5</td><td> shows an example of the</td><td colspan="2"> entire process</td>

* ·

9 of the generation of random-number sequences of invention.

flow this

Fig. 6 shows an example of the flow of the generation of random-number initial values executed by a parent processor element.

Fig. 7 shows an example of the method of distributing random-number initial values to be distributed by a parent processor element to child processor elements.

Fig. 8 shows an example of the flow of the generation of random-number sequences to be executed by the child processor elements.

Fig. 9 shows a typical program for implementing the generation of random-number initial values to be executed by the parent processor element.

Fig. 10 shows a typical program for implementing the transfer of random-number initial values to be executed by the child processor elements.

Fig. 11 shows a typical program for implementing the receiving of random-number initial values to be executed by the child processor elements.

Fig. 12 shows a typical program for implementing the generation of random-number sequences to be executed by the child processor elements.

Figs. 13A and 13B are diagrams of assistance in explaining the prior art.

<img file="AU644306B2_D0006.tif" />

[DETAILED DESCRIPTION OF THE EMBODIMENTS]

Prior to the description of the embodiments of this inVention&gt; the prior art for generating randomnumber sequences as proposed by P. Fredrickson et al., referring to Figs. 13A and 13B.

In the pseudo-random trees proposed by P. Fredrickson et al., it is assumed that X is a given element of the pseudo-random trees, and two elements L(X) and R(X) are defined as

L(X) = (a^X + c^) mod m

R(X) = (a^X + CpJ mod m where x mod y represents the remainder obtained by dividing an integer x by an integer y. If an initial value Xq is given in accordance with this definition, a tree as shown in Fig. 13A is generated. The successors taken from the right side, starting from a given node of this tree, are called the right-hand series in the tree. A left-hand branch of a particular node, as shown in Fig. 13B is taken up to form a new righthand series, starting from the left-hand branch.

P. Fredrickson et al. proposed a method of gener35

<img file="AU644306B2_D0007.tif" />

ating random-number sequences from each processor on the basis of a method in which a parent processor generates elements constituting a left-hand branch, in accordance with the pseudo-random trees, and the generated elements are distributed to child processors, which in turn generate a right-hand series from the distributed elements.

However, since the method of generating randomnumber sequences proposed by P. Fredrickson et al. is in accordance with the mixed or multiplicative congruential sequence (MG-sequence) method, as noted earlier, only shorter-period random-number sequences can be generated, and strict limiting conditions have to be imposed to prevent sequences from being correlated with each other.

Next, embodiments of this invention will be described. First, the outline of this invention will be described in accordance with embodiments illustrating the operating principles of this invention as shown in Figs. 1 through 3. Then, this invention will be described in detail according to more specific embodiments .

Fig. 1 illustrates an embodiment showing the operating principle of this invention applied to a distributed memory type parallel computer system.

In the figure, reference numeral 1 refers to a parent processor element; 2-i (1^ i k) to child processor elements; and 4 to a communication network. In the configuration shown in this figure, any one child processor element 2-i may act as a parent processor element 1.

The parent processor element 1 comprises a means for generating random-number initial values 10 and a means for distributing random-number initial values 11. The random-number initial value generating means 10 generates p X v X k pieces of random-number initial • ft ft • ft ft ft ft • ft · · • · • · · • ft • · · ft ft ft ft • ft ft · • · · · ft · ft ft ft ft · • ft • · · values. The random-number initial values can be generated by the multiplicative or mixed congruential sequence (MC-sequence) method, or by the maximum shift register sequence (hereinafter referred to sequence) method, which will be described later, a combination of both. The initial than 0.

means 11 length as Mor by generated random-number values may be essentially any values, other The random-number initial value distributing distributes p X v pieces each of the randomnumber initial values generated by the random-number initial value generating means 10 to the child procescommunication network 4, sor elements 2-i via the parameter of the primitive X*³· + 1 prescribing sequence generation and v is defined as the Mmethod value the n-th power (n = a natural operat2-i is and q is expressed by a parameter of polynomial, the avoiding overlapping.

Here, p is defined as a irreducible polynomial X^ + sequence random-number (Tausworthe sequence); obtained by raising 2 to number); or if the vector length of the vector ing mechanisms of the child processor elements expressed by a , the aforementioned primitive irreducible then v should preferably be a Value satisfying q X v &gt; a , or (p - q) X v &gt; number of child processor elements random numbers. When the child condition k is the generate elements

2-i have no value v is set to 1.

be the smallest value mentioned conditions a ;

2-i and that processor vector operating mechanisms, the Furthermore, v should preferably among those satisfying the aforeto improve the efficiency of generating random-number initial values.

As for the ·M-sequence random-number generating method, refer to I. DeAk, Uniform number generators for parallel computers, 15 155-164.

A child processor element 2-i, on the other sequence random hand , (1990) comprises a random-number initial value receiving means

20-i and a random-number generating means 21-i. The random-number initial value receiving means 20-i receives random-number initial values distributed to its own element by the parent processor element 1.

The random-number random-number random-number generating means 21-i generates a new value A_n (n £ ρ X v + 1_;, using the initial values received by the random number initial value receiving means 20-i, more prefer10 ably, in accordance with the bit-by-bit logical opera tions of random-number values A_n__py and A_n__qy when the parameter v satisfying the condition q X v &gt; a is used, or in accordance with bit-by-bit logical opera tions for random-number values A_n__py and A_n__pv+^_v when the parameter v satisfying the condition (p - q) X v

<img file="AU644306B2_D0008.tif" />

Here, more desirably the condition q X v &gt; a is required to be satisfied when q &gt; (p - q) holds; and the condition (p - q) X v &gt; a is required to be satisfied when q &lt; (p - q) holds And, the random-number generating means 21-i more preferably uses an exclusive-OR operation as the bit-by-bit logical operation.

When employing this configuration, the randomnumber initial value generating means 10 of the parent processor element 1 generates ρ X v X k pieces of random-number initial values, while the random-number initial value distributing means 11 distributes ρ X v pieces each of the generated random-number initial values to each child processor element 2-i, avoiding overlapping, that is, in a predetermined order, or in accordance with a predetermined regularity to avoid overlapping. the random-number initial value receiving means 20-i of each child processor element 2-i receives random-number initial values distributed to its own element by the parent processor element 1, whereas the

<img file="AU644306B2_D0009.tif" />

random-number generating means 21-i generates randomnumber sequences using the received random-number initial values.

Random-number generating processing by this random-number generating means 21-i is executed in accordance with the M-sequence random-number sequence generating method.

In the M-sequence method of random-number sequence generation, if exclusive-OR operations are used as bitby-bit logical operations, with p pieces of randomnumber initial values of A| and A_p given, random-number sequences from the term (p + 1) and thereafter are generated in accordance with the following recurrence formula derived from the primitive irreducible polynomial X^p + X^ + 1 (modulo 2):

A_n = EOR (A_n__p, A_n__q) — Eq. (1).

Or, random-number sequences from the term (p + 1) and thereafter are generated in accordance with the following recurrence formula derived from a primitive irreducible polynomial X^p + X&lt;^p_q) + 1”:

A_n - EOR (A_n__p, A_n__p+q) Eq. (2) since it has been proved that the primitive irreducible polynomial X^p + X^q + 1 is equivalent to the X^p + _x(p-q) _{+ lt}

When Eq. (1) is used, in which A_p+|. is generated from A μ. and A_p+j_&lt;__q, the number of random numbers that can be generated at one time using p pieces of randomnumber initial values A-^ - A_p becomes k = q where p + k - q = p holds. When Eq. (2) above is used, on the other hand, in which Α_ρ+|_ζ is generated from and ^k+q’ ^he number of random numbers that can be generated at one time using p pieces of random-number initial values A-^ - A_p becomes k = (p - q) where k + q = p'' holds. That is, it is more desirable in terms of random-number generating efficiency to generate random numbers in accordance with Eq. (1) so long as q &gt; (p

- q) holds, and bo generate random numbers in accordance with Eq. (2) so long as (p - q) &lt; q holds.

In this way, the random-number generating means

21-i can generate only q pieces of random numbers at one time when the recurrence formula of Eq. (1) is used. When the recurrence formula of Eq. (2) is used, only (p - q) pieces of random numbers can be generated at one time. This poses some problems in that even if a Vector operating mechanism has a capability of gener10 ating a pieces of random numbers at one time, that capability is never used if the value q or (p - q) is smaller than the vector length a of the vector operating mechanism of the child processor elements 2-i, and

<img file="AU644306B2_D0010.tif" />

<img file="AU644306B2_D0011.tif" />

thus random numbers cannot be generated at high speed.

Eying at the fact that random number sequeroes from the term (p X v + 1) and thereafter can be generated in accordance with the following recurrence formula derived from these primitive irreducible polynomials when ρ X v pieces of random-number initial values of Aoi Ap_V are given, since it has been proved that the primitive 'rreducible polynomial X^p + X^q ·+ 1 (modulo 2) is equivalent to (X^p + X^q + l)^v (modulo 2) or (X^p+ χ(ρ~9.) + i)^v (modulo 2):

A_n = EOR (A_n__pv, A_n__rv) --- Eq. (3) where r = q or (p - q)

EOR operation may be other logical operations.

The random-number generating means 21-i generates random numbers at high speed in accordance with the 30 method of Μ-sequence random-number generation method.

That is, the random-number generating means 21-i can generate q X v pieces of random numbers at one time from ρ X '/ pieces of random-number initial values of A| - A_pv by using the recurrence formula of Eq. (3) 35 with q used as the value r, as is evident from the

<img file="AU644306B2_D0012.tif" />

t · · description relating to Eq. (1) above, and thereafter random numbers can be efficiently generated in increments of q X v pieces. By using the recurrence formula of Eq, (3) with (p - q) as the value r, on the other hand, (p - q) X v pieces of random numbers can be generated at one time from p X v pieces of randomnumber initial values of - A_pv, and thereafter random numbers can be efficiently generated in increments of (p - q) X v pieces, as is apparent from the description relating to Eq. (2) above.

Thus, the random-number generating means 21-i generates random numbers at high speed in accordance with the M-sequence random-number sequence generating method, more preferably by generating random-number sequences from the term (p X v + 1) and thereafter, using the vector length a as a generation unit, in accordance with the recurrence formula of Eq. (3) where r = q holds by selecting such a value v that q X v can become larger than the vector length a ; or by generating random-number sequences from the term (p X v + 1) and thereafter, using the vector length a as a generation unit, in accordance with the 1 currence formula of Eq. (3) where r = (p - q) holds by selecting such a value v that (p - q) X v becomes larger than the vector length a .

Essentially, either of q or (p - q) can selected as r, but any smaller v value is more appropriate because the random-number initial value generating means 10 of the parent processor element 1 must generate p X. v X k pieces of random-number initial values. It follows from this that it is desirable to select q as r when q &gt; (p - q) holds, and it is desirable to select (p - q) as r when (p - q) &gt; q” holds.

Furthermore, as long as the condition r X v &gt; a is met, any value obtained by raising 2 to the n-th power (n - a natural number) may be used as v, but it

1»

<td> •</td><td></td>

<td> •</td><td> ··</td>

<td> • «</td><td> •</td>

<td> •</td><td> ♦ ·</td>

<td></td><td> •</td>

<td> •</td><td> •</td>

<td></td><td> •</td>

<td> •</td><td> •</td>

<td> ··</td><td> •</td>

<td></td><td> • ·</td>

<td> •</td><td></td>

<img file="AU644306B2_D0013.tif" />

is similarly desirable to use the least value as v among those satisfying this condition since the randomnumber initial value generating ans 10 of the parent processor element 1 must generate p X v X k pieces of random-number initial values.

Furthermore, even if the condition r X v &gt; a is nut met, high-speed random-number generation can be accomplished if v assumes a value larger than 1 because the vector operating mechanisms of the child processor elements 2-i are used more efficiently than with the v value being 1. Needless to say, when the condition r &gt; a is met from the very beginning, the value v is set to 1.

In this way, this invention employs such a configuration that each child processor element 2-i generates random-number sequences in accordance with the M-sequence random-number sequence generating method.

An embodiment shown in Fig. 2 is that illustrating the operating principle of this invention applied to a shared- memory type parallel computer system. In this embodiment, a shared memory 5 is used as a communication mechanism that can be accessed by both the parent processor element 1 and the child processor elements 2i, in place of the communication network 4 used in the embodiment shown in Fig. 1.

In this embodiment, the parent processor element 1 comprises the random-number initial value generating means 10 described with reference to Fig. 1, and a new random-number initial value writing means 12, while a child processor element 2-i comprises the random-number generating means 21-i described with reference to Fig. 1, and a new random-number initial value reading means

22-i .

In this embodiment having such a configuration, the random-number initial value generating means 10 of the parent processor element 1 generates p X v X k

<img file="AU644306B2_D0014.tif" />

pieces of random-number initial values, while the random-number initial value writing means 12 writes p X v X k pieces of the generated random-number initial values in the shared memory 5. The random-number initial value reading means 22-i reads p X v pieces each of p X v X k pieces of the random-number initial values written in the shared memory 5 while avoiding overlapping with other child processor elements 2-i. The random-number generating means 21-i generates random-number sequences in accordance with the maximum length shift register sequence (M-sequence) method using p X v pieces of random-number initial values.

In this way, each child processor element 2-i of a parallel computer system generates random-number sequences in accordance with the M-sequence random-number sequence generating method.

The embodiment shown in Fig. 2 employs such a configuration that the parent processor element 1 generates random-number initial values, as in the embodiment shown in Fig. 1. This invention, on the other hand, can employ such a configuration that each processor element required to generate random-number generation generates random-number initial values by itself.

Fig. 3 illustrates the operating principle of an embodiment of this invention having such a configuration. In the figure, 3-i (1^ i k) is a processor element required to generate random numbers.

In this embodiment having such a configuration, each processor element 3-i comprises a random-number initial value generating means 30-i having the same function as the random-number initial value generating means 10 described with reference to Fig. 1, a new random-number initial value extracting means 31i, and a random-number generating means 32-i having the same function as the random-number generating means 2135 i described in Fig. 1.

With this configuration, the random-number initial value generating means 30-i of each processor element 3-i generates p X v X k pieces of random-number 5 initial values as in the case of the random-number

<img file="AU644306B2_D0015.tif" />

initial value generating means 10 shown in Fig. 1; the random-number initial value extracting means 31-i extracts p X v pieces of the random-number initial values to be allocated to itself from among p X v X k pieces of the generated random-number initial values, avoiding overlapping with other processor elements 3-i; and the random-number generating means 32-i generates random-number sequences in accordance with the M-sequence random-number sequence generating method using the extracted random-number initial values.

In this way, each processor element 3-i of a parallel computer system generates random-number sequences in accordance with the M-sequence random-number sequence generating method. This configuration eliminates the need for executing communication processing for random-number generation among the processor elements 3-i. Consequently, this configuration can employ both a shared memory and a communication network.

In the following, this invention will be described in more detail, taking more specific examples of the embodiment shown in Fig. 1.

This invention can be applied to any types of parallel computer systems. It can be applied, for example, to a distributed-memory type parallel computer system connected via a communication network, as shown in Fig. 4A, or to a shared-memory type parallel computer system using a memory in common, as shown in Fig. 4B, or to a hybrid type parallel computer system having physical or logical shared memories connected via a communication network, as shown in Fig. 4C. Symbol PE in the figure denotes a processor element.

<img file="AU644306B2_D0016.tif" />

Fig. 5 shows the entire process flow executed by the parent processor element 1 and the child processor elements 2-i, as described in Fig. 1. The left side of the figure indicates the processing executed by the parent processor element 1, and the right side the processing executed by the child processor elements 2i. .

As shown in the figure, the parent processor element 1 first executes preprocessing in Step 1 for generating random-number initial values that serve as seeds for random-number sequences generated in the child processor elements 2-i, and generates those random-number initial values in Step 2. In Step 3, the generated random-number initial values are broadcast to the child processor elements 2-i via a communication network, etc., and finally in Step 4, postprocessing is executed to complete the entire processing.

The child processor elements 2-i, on the other hand, first receive in Step 5 the information on the processor number of its own element and the information on the total number of the child processor elements from the operating system. Then, after that part of processing not involving the use of random numbers is executed in Step 6, the random-number initial values allocated to it are received from among the randomnumber initial values transferred from the parent processor element 1 in Step 7.

In Step 8, the random-number sequences to be used by its own element are generated using the received random-number initial values, and that part of processing involving the use of the generated random-number sequences is executed in Step 9. Then, whether or not there is a request for the use of random numbers is judged in Step 10. If there is a request for using random numbers in the Step-10 judgment, processing is returned to Step 8, and if there is no request for using random numbers, processing proceeds to Step 11 where that part of processing not involving the use of random numbers is executed tc complete the entire processing .

Fig. 6 shows the detailed process flow of generating random-number initial values executed by the parent processor element 1.

When generating random-number initial values, the parent processor element 1 first sets p X v X k as the variable lp in Step 20, as shown in the process flow of Fig. 6, and then sets q or (p - q), whichever is the greater, as a new q value (that had previously been described as r) . Furthermore, the parent processor element 1 sets q X v X k as the variable 1., in •J.

accordance with this new q, and 4999 as the variable

A. As noted earlier, p and q are defined as parameters of the primitive irreducible polynomial X^p + X^q + 1 that prescribes the M-sequence random-number generation, and v is defined as a value obtained by raising 2 to the n-th power (n = a natural number). If the vector length of the vector operating mechanisms of the child processor elements 2-i is expressed by a , the value k satisfying the condition q X v &gt; a is the number of the child processor elements 2-i generating random numbers.

Next, A|(i = 2 ~ 2 X lp) values are calculated in Step 21 in accordance with ^Ai ^{= A}i-1 ^{X 137371}·

Thus, 2 X lp pieces of (i = 1 - 2 X l_p) values are determined from this calculation processing and the A| that is set to 4999.

Then, one of in the range of i = 1 ~ l_p is selected in Step 22, and A£ _{+ lp} corresponding to it is also selected, and the processing for replacing the selected with a new one by combining the higherorder 16 bits of the selected A| with the iower-order bits of the selected pieces of new A| (i = mixing Aj_ with A_{i +} -£_p.

^i+lp executed· That is, l_p1 ~ lp) values are generated by The method of generating random numbers up to this is in accordance with the multipli10 cative or mixed congruential (MC-sequence) method.

In Step 23, Α·^ρ₊-^ is calculated in accordance with bit-by-bit exclusive-OR operation of A·^ and ^Alp+l-lq» and ^Alp+2 calculated in accordance with bit-by-bit exclusive-OR operation of Ag and ^Aip+2-lq’ ^usiⁿ§ ^Ai (i =

<td colspan="2"> 1 ~ lp) generated in Step</td><td> 22,</td><td> in accordance</td><td> with the</td><td> bl-</td>

<td colspan="4"> sequence random-number sequence generating</td><td> method,</td><td> and</td>

<td> in accordance</td><td> with</td><td></td><td></td><td></td><td></td>

<td> A£ = EOR</td><td> (^Ai-lp’ ^Ai-</td><td> lq)</td><td></td><td></td><td></td>

<td></td><td> where EOR</td><td> is</td><td> bit-by-bit</td><td> exclusive</td><td> -OR</td>

<td> operation.</td><td></td><td></td><td></td><td></td><td></td>

<td> In this way,</td><td> by repeating</td><td> the</td><td> calculations</td><td>^{of A}lp+k</td><td> in</td>

accordance with bit-by-bit exclusive-OR operation of A^ and A^p₊^_jL_q) newly defined A^ (i = l_p + 1 ~ l_p + 2 X lq) values.

These repeated calculations are possible up to k = 1 where the equation 1 + k - 1 = 1 holds as the jl xr SI Jr first stage of calculation is made by using A^ (i - 1 ~ lp) generated in Step 22 since the last number of A^ generated in Step 22 is A^p That is, new A^ (i = l_p + 1 ~ 1_ + 1 ) values are generated in the first stage, V Si using A^ (i = 1 ~ l_p) generated in Step 22.

Next, in the second stage where calculation is mad·., by including the newly generated A^ (i = l_p + 1 lp + lq)» calculation is possible up to k = 2 X lq where the equation l_n + k - 1 = 1 + 1 holds since the last number of A^ generated in the second stage is ^Alp+lq’ That is, in the second stage, new A^ (i = l_p + lq + 1 ~ lp + 2 X lq) values are generated following the values generated in the first stage, including A^ (i = 1 + 1 ~ lp + lq) generated in the first stage.

In this way, additionally mixed A^ values are determined in this Step 23 by calculating newly defined A| (i = lp + 1 ~ lp + 2 X 1^) values from the A^ (i = 1 * lp) generated in Step 22.

As will be described later, those actually used as random-number initial values are A; (i = 2 X 1 + 1 ~ ·*· M.

lp + 2 X 1^) which are l_p pieces behind this determined (i = l_p + 1 ~ l_p + 2 X 1^).

Thus, the parent processor element 1 generates random-number initial values by executing the process flow shown in Fig. 6.

p X v pieces each of the generated random-number initial values are distributed to k pieces of the child processor elements 2-i in accordance with a predetermined rule, taking care to avoid overlapping. There can be various distributing methods, such as that of taking p X v pieces of random-number initial values from the top of l_p (= p X v X k) pieces of the generated initial values to sequentially distribute to each child processor element 2-i, for example, or that of taking random-number initial values one by one from the top of lp pieces of the generated random-number initial values, as shown in Fig. 7.

In this way, the parent processor element 1 distributes a combination of p X v pieces of randomnumber initial values that do not overlap with each other to the child processor elements 2-i.

Each child processor element 2-i generates randomnumber sequences required for data processing in accordance with the process flow shown in Fig. 8 using p X v pieces of random-number initial values addressed to its own element notified by the parent processor element 1.

That is, the child processor element 2-i first sets p, q, v and ma values in Step 30. As described in the process flow shown in Fig. 6, p is defined as a parameter of the primitive irreducible polynomial χΡ + + 1 conceived by the parent processor element 1, q as parameter q or (p - q), whichever is the larger, of this primitive irreducible polynomial, v as a value obtained by raising to the n-th power (n = a natural number), or a value satisfying the condition q X v &gt; a. if the vector length of the vector operating mechanisms of the child processor elements 2-i is expressed by a , k as the number of the child processor elements 2-i generating random numbers, and ma as a natural number prescribing the amount of random numbers to be generated.

Next, p X v pieces of random-number initial values notified by the parent processor element 1 in Step 31. Hereinafter p X v pieces of the received random-number initial values will be written as (i = 1 ~ p X v) for the sake of brevity.

In Step 32, Bp_V+| is calculated in accordance with the bit-by-bit exclusive-OR operation of and B_pv+i_ _qv, and B_pv+2 is calculated in accordance with the bitby-bit exclusive-OR operation of B2 and Bp_V+2_gv’ ^usi-ⁿS the random-number initial value B^ (i = 1 - p X v) received in Step 31 in accordance with the same recurrence formula as the aforementioned Eq. (3) derived by expanding the maximum length shift register sequence (M-sequence) method.

Bi = EOR (Bi__pv, Bi__qv) --- Eq. (4).

By repeating these calculations until Bp_V+_maqv obtained, new random-number sequences Bi (i = p X v + 1 ~ p X v+maX qX v) are generated.

More specifically, the calculation processing of the random-number sequences (i = p X v + 1 ~ p X v + ma X q X v) is carried out by calculating Bi (i = p X v+l~pX v+qX v)in the first stage, calculating Bi (i = p X V+l+qX v - p X v+2X qX v) in the second stage, calculating Bi (i = p X v+ 1 + 2 XqXv~pXv+3XqXv) in the third stage, and up to the ma stage, in accordance with the vector operating mechanism of the child processor element 2-i.

In this way, by using the recurrence formula of Eq. (4), the child processor elements 2-i can generate random-number sequences at high speed, making full use. of the vector operating mechanism of its own element. It is for this reason that this invention generates random-number sequences using the expanded recurrence formula of Eq. (4), not by using general Eq. (1) or the recurrence formula of Eq. (2) that prescribe the Msequence random-number sequence generating method. This has previously been described in detail in the description of the reason for the introduction of the recurrence formula of Eq. (3).

To describe more exactly, the child processor elementr 2-i carry out processing so that it generates random-number sequences in increments of the vector length a of the vector operating mechanism, as will be described later, instead of generating random-number sequences in increments of q X v pieces at each stage, in Step 32 of the process flow in Fig. 8,

Thus, this invention employs such a configuration that long-period, non-correlated random-number sequences can be generated at high speed because each child processor element 2-i of a parallel Computer system generates random-number sequences in accordance with the expanded M-sequence method, while making the full use of the vector operating mechanism.

Figs. 9 through 12 show examples of detailed programs for implementing the aforementioned process flow.

Fig. 9 shows an example of a program for implementing the generation of random-number initial values to be executed by the parent processor element 1; Fig.

• a · t&gt; ·· «»···· *····« • 9 ·♦ · « β · • ··

4* · • · · • ·· ···· • · · ·« a shows an example of a program for implementing the transfer of random-number initial values to be executed by the parent processor element 1; Fig. 11 shows an example of a program for implementing the receiving of random-number initial values to be executed by the child processor elements 2—i; and Fig. 12 shown an example of a program for implementing the generation of. random-number sequences to be executed by the child processor elements 2-i.

In the following, the contents of these programs will be described.

In the program shown in Fig. 9 for implementing the process flow shown in Fig. 6, the part © is a program portion corresponding to Step 20 in the process flow of Fig. 6, which instructs the setting of various parameter information. In this program portion, the value k is set to 2·'·θ, that is, the number of the child processor elements 2-i is set to 1024, the value p is set to 284, and the value q at 143.”

Since r = MAX (q, p - q) = q = 143. in accordance with 'the value q, this value q is used as a new value q. Furthermore, in view of the fact that the newly defined q must satisfy q X p &gt; 512 given that the vector length C! of the vector operating mechanism of the child processor element 2-i is 512, the value v is set to 2^ = 4.

In the part © , furthermore, the definitions l_pand 1 , and the sequence IRANSU consist of 4-byte SI data items, and it is set that the maximum (l_p + 2 X ) pieces of data values are stored, as described in SI ·

Step -23 of the process flow of Fig. 6. The value of the variable TANE prescribing the value A-^ is set to 4999 and the data IX having a value of FF00 used for extracting the higher-order 16 bits of A|, and the data IY having a value of 00FF used for extracting the lower-order 16 bits of A£₊^_p are also set.

In the program shown in Fig. 9, the part (5) is a program portion corresponding to Step 21 of the process flow of Fig. 6, which calculates 2 (i = 1 ~ 2 X lp) values to store from the top of the sequence IRANSU

X lp pieces of A^ them sequentially in accordance with ft····* • ft ^Ai = ^Ai-1 ^X 137371. .

The part (3) is a program portion corresponding to Step 22 of the process flow of Fig. 6, which extracts the higher-order 16 bits of A^ by the bit-by-bit AND operation of the (i = 1 ~ 1 ) stored in the data IX and the sequence IRANSU, extracts the lower-order 16 bits of A^ by the bit-by-bit AND operation of the A£₊^p (i = 1 ~ lp) stored in the data IY and the sequence

IRANSU, and calculates l_p pieces of new A^ (i = 1 ~ l_p) values in accordance with the bit-by-bit OR operation of the extracted higher-order 16 bits of A^ and che lower-order 16 bits of A^₊ip to store them sequentially from the top of the sequence IRANSU.

The part @ is a program portion corresponding to

Step 23 of the process flow of Fig. 6, which calculates ^Alp+1 i^{n accor}dance with the bit-by-bit exclusive-OR operation of the A| and ^Aip+i-iq stored in the sequence IRANSU to store them in the lp + l-th element of the sequence IRANSU, calculates A-^_p+2 in accordance with the bit-by-bit exclusive-OR operation of the A2 and ^Alp+2-lq stored i-ⁿ the sequence IRANSU to store them in the 1_ + 2-th element of the sequence IRANSU, and

It finally calculates A^p₊2^_q in accordance with the bitby-bit stored exclusive-OR operation of the A2^_q in the sequence IRANSU to store them in the l_q-th element of the sequence IRANSU.

the part @ is a program portion pieces of new A^ (i = l_p + 1 ~ l_p+ l-th element to the lp + 2 X and A_lp+lqⁿⁱP Thus , ^Xq the for storing 2 + 2 X l_q) in

-th eleme· ·- of the sequence IRANSU.

tl·

As is evident from the contents of the program of Fig. 9 described above, the parent processor element 1 generates random-number initial values in accordance with the multiplicative or mixed congruential (MCsequence) method and the maximum length shift register sequence (M-sequence) method by executing the program of Fig. 9. .

The random-number initial values generated bv the parent processor element 1 are distributed regularly by p X v pieces to the child processor elements 2-i in accordance with the programs shown in Figs. 10 and 11. The distributing programs shown in Figs. 10 and 11 employ such a method that the parent processor element 1 arranges and notifies the random-number initial values generated to all the child processor elements 2i, and that the child processor elements 2-i selectively receive in accordance with a predetermined rule the random-number initial values distributed to them.

The program shown in Fig. 10 is a program executed by the parent processor element 1, which instructs the transfer of the designated random-number initial values in the generated sequence IRANSU to all the child processor elements 2-i. The first argument of the SEND instruction of the subroutine executing transfer processing represents the leading address of the sequence to be transferred, and the second argument the number of bytes to be transferred from the leading address.

In this program, it is disclosed that starting from the 2 X + l-th random-. .Umber of the sequence IRANSU, l_p pieces of initial values (the data length of one initial value random-number random-number initial value is 4 bytes) from that top random-number initial value are transferred to all the child processor elements 2-i. That is, the parent processor element 1 transfers l_p pieces of random-number initial values A^ from behind the random-number initial values

<img file="AU644306B2_D0017.tif" />

(i = 1 + 1 - lp + 2 X 1^) generated by the program of Fig. 9 to all the child processor elements 2-i.

On the other hand, the program of Fig. 11 which implements the processing of 'Step 31 in the process 5 flow shown in Fig. 8 is a program which is executed by the child processor elements 2-i, and instructs to selectively receive the random-number initial values distributed to its own element from the random-number initial values transferred from the parent processor 10 element 1.

•ft····

The first argument of the RECV instruction of the sub-routine in the part (4) for executing receiving processing represents the top address of the sequence in which the received random-number initial values are stored. The second argument represents the number of bytes up to the start of receiving in the X direction (in the directior processor number in Fig. 7). The third argument represents the number of bytes frora the preceding received part to the next received part in the X direction. The fourth argument represents the number of bytes owned by a unit of the X-direction received part. For example, it indicates that four bytes are one unit of received parts. The fifth argument represents the total number of bytes in the part received in the X-direction. For example, it indicates that four bytes when the total number of units is one unit.

The sixth argument represents the number of lines of the start-to-receive part in the Y direction (another direction .in Fig. 7). The seventh argument represents the number of lines from the preceding received part to the next received part in the Y direction. If it is zero, it indicates a continuous line. The eighth argument represents the number of lines owned by one unit of the part received in the Y-direction. If it is 1, it indicates that the received part exists in one line. The ninth argument represents the total number of lines in the part received in the Y direction. For example, when ρ X v pieces are received, it indicates p X v.

The program shewn in Fig. 11 is complex because of its general-purpose configuration, but a simpler program can implement a special-purpose configuration.

In this program, it is disclosed that the part ® defines the parameter information and the sequence IR storing ρ X v pieces of received random-number initial values, then the part (2) obtains its own processor element number ncid, the part @ obtains the total number k of the child processor elements, and the RECV instruction of the part ® sequentially receives up to ρ X v pieces of random-number initial values, by skipping k pieces from the top random-number initial values designated by its own processor element number ncid. With this program, each child processor element 2-i receives the fandom-number initial values transferred by the parent processor element 1 in accordance with the process shown in Fig. 7.

In the program of Fig. 12 executing the processing of Step 32 in the process flow shown in Fig. 8, the part Q) is a program portion for instructing the setting of various parameter information. In this program portion, the value ma is set to 3, and the value p is set to 284, the value q to 143 and the value v to ”4 corresponding to the program thown in Fig. 9. Moreover, the sequence IR in which ρ X v pieces of received random-number initial values are stored, and the sequence JR in which 512 X ma pieces of generated random-number sequences are stored are defined. The maximum vector length making vector operation possible is q X v pieces, that is, 572 pieces, but the maximum storable capacity of the sequence JR is defined as 512 X ma pieces in cases where the vector length a of the vector operating mechanism is optimized at 512, for example .

The program portion that implements the processing of Step 32 in the process flow shown in Fig. 8 is the part @ , which generates random-number sequences.

The calculation of random-number sequences here is such that in the first stage, i = pX v + 1 ~ p X v. + 512 pieces are calculated using B^ = EOR (B^_p_V, ), or more specifically in accordance with the vector operating mechanism of the child processor element 2-i. In the second stage, i = p X v+ 1 + 512 ~ p X v + 2 X 512 pieces are calculated, then i = p X v+l+2X 512 ~ p X v + 3 X 512 pieces are calculated in the third stage, and this calculation is carried’ out up to the ma-th stage using the vector length a (512 in this case) of the vector operating mechanism.

The program of the part (g) is provided so that the top bit value indicating a code is always kept indicating 0, that is, positive by shifting the generated random-number value rightward by one bit. When a random number from 0 to 1 is used, the processing of dividing the elements of the sequence JR *31 storing the generated random-number sequences by 2 is carried out.

In this way, random-number generation of this invention is implemented in accordance with the program examples shown in Figs. 9 through 12.

As described above, this invention employs such a configuration that each child processor element 2-i of a parallel computer system generates random-number sequences in accordance with the maximum length shift register sequence (M-sequence) method. By adopting the M-sequence random-number sequence generating method, each child processor element 2-i can generate randomnumber sequences having such a period as long as (2^P 35 ft • ft • ·· • a · * ·· ······ • e ••«ft·· * · • ft · • · · • ··

1) at its maximum, and generates random-number sequences that are not correlated with each other, without such a difficulty as multiplicative or mixed congruential (MC-sequence) method.

Since a configuration of making the maximum use of the vector operating mechanisms in applying the maximum length shift register sequence (M-sequence) method, the. child processor elements 2-i can generate random-number sequences at high speed. And yet, this high-speed random-number sequence generation can be positively performed because communication processing between the parent processor element 1 and the child processor elements 2-i is not requested except for the transfer of random-number initial value data. In addition, adoption of the configuration described with reference to Fig. 3 can implement a configuration requiring no communication nrocessing for generating random numbers between processor elements 3-i.

• ·

<td></td><td> •</td>

<td> •</td><td> ·· • 4 ··</td>

<td></td><td> „ ·</td>

<td></td><td> •</td>

<td></td><td> , ·</td>

<td></td><td> 4</td>

<td></td><td> 4 * • 4 ··</td>

<td></td><td> 6</td>

<td> 9 · ·</td><td></td>

<td> « · · • 4«</td><td> 7</td>

<td> »«··</td><td></td>

<td> 4 0 4 • 4 4</td><td> 8</td>

<td></td><td> 9</td>

<td> • ·· « · · 4 4 4</td><td> 10</td>

<td> ···· • 4</td><td rowspan="2"> 11</td>

<td> • 444</td>

<td> 4444 • ·</td><td> 12</td>

<td> ···</td><td> 13</td>

<td> 4 4 4 4 4 · 4 44</td><td></td>