High speed processing method of addition including indirect address reference on vector computer, program and vector computer using this program

[Technical field to which the invention belongs] The present invention speeds up numerical simulation used in scientific and technological calculations, and specifically, a high-speed processing method of addition including indirect address reference on a vector computer. The present invention relates to a program and a vector computer using the program. In particular, the present invention is effective when calculating a problem including addition by indirect address reference, which is the target of the present invention, using a vector computer. The problems of interest are extremely widespread in scientific and technological calculations.

BACKGROUND OF THE INVENTION First, a problem including addition by indirect address reference in a conventional vector computer will be described. When adding the elements of another array A to the array F, it is assumed that there is an intermediate array index that determines the position of the addition element, and the addition is performed as shown in the following equation.

[0003] [Number 10] F (index (I)): = F (index (I)) + A (I) (1) Where I is in the range from 1 to N (N is an integer greater than or equal to 2). Are all covered in ascending order (I = 1,2,3, ..., N). Referencing the value of an array via an intermediate array index like F is generally called an indirect address reference.

[0004] Typical examples in which Eq. (1) appears include (1) Histogram calculation in bucket sort, (2) Contribution calculation of particles to the field in the particle problem, and (3) Integral calculation in general. In the example of (2), in the particle problem using the PIC (Particle-In-Cell) method, this calculation is called Charge Deposit, and it is used when calculating the interaction between particles via a field. Equation (1) is sometimes called a regression equation, but in this specification, it is also called a deposit equation derived from Charge Deposit in the PIC method. In the problem of multi-particle system, the calculation cost of the deposit formula is extremely high, and its speed is always desired.

[0005] With a vector computer having a strong computing power, it is generally impossible because the problem of address collision is unavoidable in the vector processing by the conventional method as described below. However, it was possible to instruct the compiler and perform forced vector processing only under special conditions such as the contents of the list of indirect addresses being unique.

[0006] Now, when the calculation of the equation (1) on the vector computer is performed in the order of 1 to N with respect to I, the calculation system of the vector calculator has an arithmetic mechanism for simultaneously calculating in units of K, and the equation. The calculation of (1) is also processed for K at the same time. Now, assuming that K = 4 and the index value is 1,1,1,1, first, the storage device (register) of the arithmetic mechanism has F (index (1)), F (index (2)), F. (index (3)) and F (index (4)) are read from the main memory (hereinafter referred to as "memory"). That is, {F (1), F (1), F (1), F (1)} are stored in the register. Next, K values of A are added at the same time, that is, as a result of the operation, the register values are {F (1) + A (1), F (1) + A (2), F (1) + A ( 3), F (1) + A (4)}. Next, the contents of this register are returned to the memory, and each element is in the order of the memory F (index (1)), F (index (2)), F (index (3)), F ( Since it is recorded in index (4)), the last recorded F (1) + A (4) is written in the part where the index values match, that is, F (1).

[0007] Originally, in the calculation meaning of this formula, the value of F (1) + A (1) + A (2) + A (3) + A (4) is not stored in F (1) as the calculation result. must not. Therefore, the calculation of Eq. (1) on the vector computer is accompanied by incorrect calculation results, and it is necessary to introduce another calculation method to correct the calculation results.

[0008] As one of them, a so-called Retry algorithm has been proposed, in which speculative vector processing is performed on a one-dimensional array to be added, a term having an invalid addition result is detected, and the same processing is repeated again. Has been done. In this method, the addition vector processing is performed using the direct address for F, including the risk of result fraud, and the result fraud term is corrected. For example, refer to the following documents.

[0009] Abe, Y .: Present Status of Computer Simulation at IPP, Proceeding of Supercomputing 88, Vol.II, p.72 (1988), and Hitoshi Murai, Kenji Suematsu, Yoshiki Senoo: High speed on shared memory parallel computer Integer Sorting Algorithm, IPSJ Journal, Vol.39, No.6, p.1595 (1998).

[0010] Further, as a method of avoiding address collision by positively changing the program, a Work Vector algorithm (or perch method) that artificially expands the index on the array F has been proposed (Nishiguchi, A. , Orii, S. and Yabe, T .: Vector Calculation of Particle Code, Journal of Computaional Physics, Vol.61, p.519 (1985)). This is a simple address in the form of index (i) for the above equation (1) strip-mined to vector length K with K work areas (array w (1: m, 1: K)). It is a method to extend the specification like (index (i), j) to completely avoid address matching. That is, it is a method to introduce a two-dimensional working array and completely avoid address collision. ..

[0011] [Problem to be solved by the invention] Since the Work Vector algorithm (or the perch method) is a method of matching the vector length, which is the unit of vector processing, with the extended dimension, addition invalid terms do not occur, but it is sufficient. In order to obtain excellent performance, the size of the working array used had to be very large.

[0012] On the other hand, the Retry algorithm requires a smaller amount of memory than the Work Vector algorithm (or the perch method), and the sorting problem is that it exhibits its performance when the indirect address reference is sparse (the above (1). ) Is shown by an experiment (see the above literature by Murai et al.). However, when the distribution of indexes is concentrated in a certain range, it has the disadvantage that it is slower than the scalar calculation, so it is not effective for extremely peculiar problems. In addition, the appearance of the result invalid term depends on the degree of duplication of the index value, and when the degree of duplication becomes high, the number of retry additions increases, which causes performance deterioration.

[0013] According to the report by Muramatsu, Mochizuki et al., When the integral formula in the molecular orbital calculation is in the form of formula (1), the Retry algorithm is not effective due to the collision of index values (keys) that occurs at an unavoidable frequency. It is shown. It has also been reported that although the Work Vector algorithm is an effective method, memory usage is a barrier to its application to practical large-scale problems. For details, see Masayuki Muramatsu, Yuji Mochizuki, Tetsuichi Yokura, Yukio Hirahara, Toshiyuki Imamura: Vectorization of DHF Calculations in Relativistic Molecular Orbital Code DIRAC, Jisho Kenpo, Vol.2001, No.49, p. See 43 (2001).

[0014] In summary, the Work Vector algorithm (or perch method) does not generate addition invalid terms, but the size of the working array used must be very large in order to obtain sufficient performance. , In the Retry algorithm, since speculative vector processing was performed on a one-dimensional array, address collisions that cause incorrect addition frequently occurred.

[0015] The subject of the present invention is to avoid calculation errors in addition including indirect address reference on a vector computer, and to reduce the frequency of address collisions without using a large working array and perform addition at high speed. There is.

[Means for Solving the Problem] In the above problem, when an element of another array A is added to an array F, an intermediate array index that determines the position of the addition element exists, and [0017] ] [Equation 11] F (index (I)): = F (index (I)) + A (I), where I is from 1 to N (where N is any integer greater than or equal to 2) Arrays F, A and index are provided in the storage means in a method of high-speed processing on a vector computer for addition including an indirect address reference represented by the above equation, which covers all the ranges up to (1). It is a step of providing L working sequences having the same size as the array F (where L is an integer of 2 or more) in the storage means, and the L working sequences are 2 of W (I, J). Expressed in dimensional notation, the size of the first dimension of W matches the size of the array F, the size of the second dimension is L, and the step of setting 0 to all the elements of the working array W, (2) Using the elements of array A and the elements of working array W, [0018] [Equation 12] W (index (I), mod (I-1, L) + 1: = W (index (I)) , mod (I-1, L) +1) + A (I) (where mod is a function to calculate the remainder), calculate I from 1 to N in order based on the formula , The step to store the result in the corresponding working array W, and (3) stamp (s) with the same size as the working array W₁, s₂The step of providing the array stamp represented by the two-dimensional notation of) in the storage means, and (4) the value of I with respect to the stamp (index (I), mod (I-1, L) +1) in the array stamp. And the step of changing (5) I from 1 to N and determining whether stamp (index (I), mod (I-1, L) +1) matches I. , (6) In the judgment in step (5), stamp (index (I), mod (I-1, L) +1) does not match I N'number of I (where N'is 1 or more (Integer) If it exists, it uses the step of generating a list of the mismatched I and storing it in the storage means as an array list of the number of elements N', and (7) using the elements of the array A and the elements of the working array W. , [0019] [Number 13]<img file="JP3845711B2_D0001.tif" />(Here, mod is a function that calculates the remainder.) A step that calculates list (I) in order from 1 to N'based on the formula expressed by, and stores the result in the corresponding working array W. And (8) the step to store the value of I for stamp (index (list (I)), mod (list (I) -1, L) +1) in the array stamp, and (9) I to 1 Steps to determine whether stamp (index (list (I)), mod (list (I) -1, L) +1) matches I by changing from to N, and step (10) ( If there is an I whose stamp (index (list (I)), mod (list (I) -1, L) +1) does not match I in the judgment in 9), the list of the mismatched I is listed in the array list. There is an I that does not match the stamp (index (list (I)), mod (list (I) -1, L) +1) in the judgment in (11) step (9) and the step to be stored in. The step that repeats steps (7) to (10) until it disappears, and the judgment in (12) step (5) shows that stamp (index (I), mod (I-1, L) +1) is I. If there is no I that does not match, or if there is no I that does not match I in stamp (index (list (I)), mod (list (I) -1, L) +1) in the judgment in step (9) In some cases, it is solved by the method of the invention comprising a step of terminating the process and a program executed by a vector computer.

[0020] In the above task, when an element of another array A is added to the array F, there is an intermediate array index that determines the position of the addition element. [0021] [Equation 14] F (index] (I)): = F (index (I)) + A (I), where I covers the entire range from 1 to N (where N is any integer greater than or equal to 2) in ascending order. In a vector computer that processes additions including indirect address references represented by the above equation at high speed, the storage means for storing the arrays F, A and index and the storage means are working sequences of the same size as the array F. L (where L is an integer of 2 or more) are provided, and the L working array is represented by the two-dimensional notation of W (I, J), and the size of the first dimension of W is an array. It matches the size of F, the size of the second dimension is L, all the elements of the working array W are set to 0, and the storage means is stamped with the same size as the working array W. (s₁, s₂An array stamp represented by the two-dimensional notation of) is provided. (1) Using the elements of the array A and the elements of the working array W, [0022] [Equation 15] W (index (I), mod With (I-1, L) + 1: = W (index (I), mod (I-1, L) +1) + A (I) (where mod is the function that calculates the remainder) Calculate based on the expressed formula, store the result in the corresponding working array W, and (2) for stamp (index (I), mod (I-1, L) + 1) in the array stamp. Store the value of I, (3) change I from 1 to N in the first judgment, and whether stamp (index (I), mod (I-1, L) +1) matches I Judge whether or not, (4) In the first judgment, stamp (index (I), mod (I-1, L) +1) does not match I N'number of I (where N'is 1) If it exists, a list of the mismatched I's is generated and stored in the storage means as an array list with the number of elements N', and (5) the elements of the array A and the elements of the working array W are used. , [0023] [Number 16]<img file="JP3845711B2_D0002.tif" />(Here, mod is a function that calculates the remainder.) Based on the formula expressed by, the list (I) is calculated in order from 1 to N', and the result is stored in the corresponding working array W. (6) Store the value of I for stamp (index (list (I)), mod (list (I) -1, L) +1) in the array stamp, and (7) in the second judgment, I Is changed from 1 to N to determine whether stamp (index (list (I)), mod (list (I) -1, L) +1) matches I, and (8) 2nd If there is an I whose stamp (index (list (I)), mod (list (I) -1, L) +1) does not match I in the judgment of, the list of the mismatched I is stored in the array list. , (9) From the above (7) until there is no I whose stamp (index (list (I)), mod (list (I) -1, L) +1) does not match I in the second judgment Repeat the process up to (10), and (10) if there is no I whose stamp (index (I), mod (I-1, L) +1) does not match I in the first judgment, or the second The present invention includes an arithmetic control means for terminating processing when there is no I whose stamp (index (list (I)), mod (list (I) -1, L) +1) does not match I in the determination. It is solved by a vector computer.

[0024] Therefore, by introducing a two-dimensionally expanded working array, specifying the location of the working array using the remainder term according to the size of the expanded working array, and performing addition, the addition result by vector processing is invalid. The number of terms that becomes is reduced.

Further, a two-dimensional working array having the same type as the working array is prepared, and it is detected by using the above-mentioned remainder term whether the addition result by specifying the location of the working array is reflected in the memory, and the detected term is used. On the other hand, the same addition process is repeated until there are no invalid terms as a result.

[0026] Then, the frequency of address collisions is alleviated by making the array to be the target of speculative vector processing into a two-dimensional array.

[Embodiments of the Invention] First, it is assumed that the deposit equation (1) in the column of the conventional technique is described by the program shown in Table 1.

[0028] [Table 1]<img file="JP3845711B2_D0003.tif" />[0029] Here, it is assumed that n is the total number of addition elements (array a), m is the upper limit of the domain of f, and the range of the array index also matches [1: m] (n, m). 1). Further, the value of the array index is called a key, and in the present specification, the total number of values that this key can take is called the index distribution, and the total number is represented by the symbol l (lowercase letter L). l means the average value of the overlap of index values, and can be considered to correspond to the reciprocal of density (m / density), that is, the degree of overlap of indexes. The hardware vector register length for vector processing is N_VAnd use the notation "//" to represent the vector in the program. In particular, a vector with elements from n to m is represented by / n: m /. Furthermore, as the calculation performance of the deposit formula (1), the value obtained by dividing n by the program execution time, that is, the number of elements that can be added per unit time (seconds) is used, and it is expressed as EPS (Elements Per Second).

Next, the processing concept of the deposit equation (1) according to the present invention in the column of the prior art will be described. Prepare L working arrays (L is an integer of 2 or more) of the same size as the array F, and describe them in two-dimensional notation like W (I, J) here. However, the size of the first dimension of W matches the size of F, and the size of the second dimension is L.

[0031] 0 is set in advance for all the elements of W. Next, [0032] [number 17] W (index (I), mod (I-1, L) + 1: = W (index (I), mod (I-1, L) +1) + A ( I) Execute the equation represented by (2). Here, mod is a function for calculating the remainder. As an example for explanation, assume the case of L = 3. In the present invention, L is It is not limited to 3, and can take any number of 2 or more. {A (1), A (2), A (3), A (4)} is stored in the register, and it can be written to the memory. , A (4) is recorded in W (1,1), A (2) is recorded in W (1,2), and A (3) is recorded in W (1,3). Next, the one-dimensional part of W The sum of all the sums of which is p and the elements of F (p) are added and stored in F (p). That is, the following equation [0033] [Equation 18] F (p): = F (p) + W Calculate (p, 1) + W (p, 2) + W (p, 3).

As a result, {F (1) + A (2) + A (3) + A (4), F (2), F (3), F (4)} is calculated in the array F. Recorded as. This value does not show the correct value considering the meaning of the original formula.

The correct values are {F (1) + A (1) + A (2) + A (3) + A (4), F (2), F (3), F (4)}. As a result of the above, fraud has occurred. As a result, fraud is detected as shown below. Prepare an array stamp of the same size as W. The array stamp is stamp (s)₁, s₂) In two-dimensional notation.

[0036] [Equation 19] W (index (I), mod (I-1, L) + 1: = W (index (I), mod (I-1, L) +1) + A (I) Following the addition process in (2), the value of I is assigned to stamp (index (I), mod (I-1, L) +1). Since this assignment operation is written to the memory after the data is once stored in the register, only the term whose stamp (index (I), mod (I-1, L) +1) matches I is the correct addition processing value. Will be reflected. Therefore, I is changed from 1 to N, a list of I whose stamp (index (I), mod (I-1, L) + 1) is not I is created, and the addition corresponding to the list is redefined. In other words, if the created new list is list and the number of elements is N', then [0037] [number 20] F (index (list (I))): = F (index (list (I))) + A The formula for (list (I)) should be calculated correctly from 1 to N'in order. This formula replaces the notation of I in the original problem with list (I), and adds a process to indirectly refer to the value of the variable list when reading / writing from memory to the register. The main processing can be used as described above. That is, by recursively executing the above method, all the terms with invalid results can be added and the correct value can be reflected in the result.

[0038] As a concrete process, I is replaced with list (I) in the equation (2), and stamp (index (list (I)), mod (list (I) -1, L) +1) is I. Iteratively calculates until there are no Is that do not match.

[0039] FIG. 1 shows the concept of correction of a result fraudulent term according to the present invention. In FIG. 1, the upper part shows the calculation process, and the lower part shows the process of detecting an invalid result term. The part surrounded by the dotted line shows the characteristic part of the writing operation from the register of the vector computer to the memory, which is the premise of using the Retry algorithm. The shaded part of the list vector index () in Fig. 1 is the part where the result is normal, and the number of successful writes to f (l) is 3. On the other hand, as a result, the number of fraudulent leftovers is 1. Since the method of the present invention is located between the Retry algorithm and the Work Vector algorithm, the algorithm of the present invention is also referred to in the present specification as the Retry-WV algorithm. Table 2 shows an example of the Retry-WV algorithm of the present invention.

[0040] [Table 2]<img file="JP3845711B2_D0004.tif" />[0041] Next, in order to facilitate the understanding of the present invention, a description will be given using specific numerical values with reference to FIGS. 2 to 12, but this description is merely an example and does not limit the present invention. Absent. The processes shown in FIGS. 2 to 12 are executed by an arithmetic control device (not shown) of a vector computer.

As shown in (0) of FIG. 2, the arrays f and a and the intermediate array index are provided in the memory, the number m of the elements of the array f is 4, and the array a and the intermediate array index It is assumed that the number of elements n is 4 and the numerical values as shown in the figure are stored in the elements of each array as the initial state. First, a working array having the same size as the array f, that is, a size of 4, is preformed in L = 3, that is, three memories. This working array is represented by the two-dimensional notation of w (I, J). Here, I takes a value from 1 to 4, and J takes a value from 1 to 3. Each element of the working array w stores 0 as an initial state as shown in (0) of FIG. Next, an array stamp having the same size as the working array w is formed in advance in the memory. This array stamp is stamp (s)₁, s₂) In two-dimensional notation. The value of each element of the array stamp may be an arbitrary number as an initial state, and x shown in each element of the array stamp of FIG. 2 (0) means that it represents an arbitrary number.

Next, as shown in (1) of FIG. 2, each element of the array index is read into a preset variable-length register 1 in the order of arrangement. As shown in (2) of Fig. 3, the extended address is calculated. That is, the value representing the second dimension of w in the variable-length register 2 provided in advance is I = 1,2,3 (in the general form, 1,2, ..., L) in the form of ascending repetition. It is stored. In this example, as shown in the figure, 1,2,3,1 are stored in the positions from the top to the bottom of the register 2. Next, a two-dimensional address of w (I, J) is generated as shown in the figure by using each element whose position corresponds to the register 1 and the register 2, and is stored in the register 1.

Next, as shown in (3) of FIG. 3, the indirect address of the working array is read. That is, the elements of the working array w corresponding to the two-dimensional address of w (I, J) represented by each element of the register 1 are read out in order, and are stored in the register 2 in that order as shown in the figure.

As shown in (4) of FIG. 4, the array a () is read. That is, each element of the array a () is read out in order and stored in a preset variable-length register 3 as shown in the figure.

Next, as shown in (5) of FIG. 4, the working array and the array a () are added. That is, the elements of the working array w read into the register 2 in step (3) and the elements of the array a () read into the register 3 in step (4) are added at the corresponding positions, as shown in the figure. Store in register 2.

Next, as shown in (6) of FIG. 5, indirect address writing to the working array w of the addition result is performed. That is, the elements of register 2 that correspond positionally to the elements of register 1 are sequentially stored at the positions of the two-dimensional addresses of w represented by the elements of register 1. Therefore, the top "1" of register 2 is first stored in w (1,1), then the second "3" from the top of register 2 is stored in w (1,2), and then the register. The third "5" from the top of 2 is stored in w (1,3). Further, the last "7" of the register 2 is stored in w (1,1), which already stores the "1", as shown in the figure, that is, overwritten. That is, the element of w (1,1) becomes "7", and "1" of register 2 is not written to w as a result.

[0048] As shown in (7) of FIG. 5, confirmation preparation of the addition result and order writing are performed. That is, the numbers up to the number of elements stored in the register 2, that is, the numbers up to 4, 1,2,3,4 here are stored in the register 2 in ascending order as shown in the figure. Next, the element of register 2 corresponding to the element is read and written to the two-dimensional address of stamp represented by the element of register 1. Therefore, the top "1" of register 2 is first stored in stamp (1,1), then the second "2" from the top of register 2 is stored in stamp (1,2), and then the register. The third "3" from the top of 2 is stored in stamp (1,3). Further, the last "4" of the register 2 is stored, that is, overwritten as shown in the stamp (1,1) that already stores the "1". That is, the element of stamp (1,1) becomes "4", and "1" of register 2 is not written to stamp as a result.

Next, as shown in (8) of FIG. 6, confirmation of the addition result / reading of the writing result is performed. That is, the elements stored in the two-dimensional address of the stamp represented by the element of the register 1 are read in order and read into the register 3. Therefore, the element "4" of stamp (1,1) is at the top of register 3, and the element "2" of stamp (1,2) is at the top of register 3 from the top of register 3. The element "3" of stamp (1,3) is read third, and the element "4" of stamp (1,1) is read at the end of register 3 as shown in the figure.

[0050] As shown in (9) of FIG. 6, the addition result is confirmed and the result invalid term is detected. That is, each element of the register 3 and each element of the register 2 are compared with each other whose positions correspond to each other, a match / mismatch is determined, and the determination result is stored in the register 3 as shown in the figure. In the illustrated example, x represents a mismatch and represents a match. The element of register 2 that corresponds to the element of register 3 that represents the mismatch is stored in the variable length array list () provided in the memory in advance as an invalid term as a result of detection. Here, as shown in the figure, only the top element "1" of the register 2 is inconsistent, so it is stored in the first list (). If there are multiple mismatched elements, they are stored in list () in the order in which they are stored in register 2. Further, as will be described later, if there is no inconsistent element, writing to list () is not performed, and list () is left in the "empty (from)" state.

Next, all the registers are cleared. As shown in (10) of Fig. 7, the array list is read for retry. That is, as shown in the figure, each element of list () is read into register 2 in order.

Next, as shown in (11) of FIG. 7, the indirect address reading of the intermediate array index is performed. That is, the elements at the index () position represented by the elements of register 2 are read into register 1 in order.

Then, the retry is repeated from step (2) until list () is no longer generated, that is, list () becomes "empty (from)". Hereinafter, retries similar to steps (2) to (8) will be described with II added to the beginning of each step.

Following step (11) in FIG. 7, the extended address is calculated as shown in II- (2) in FIG. That is, in the same manner as in step (2) of FIG. 3, the values representing the second dimension of w in register 2 are in ascending order of I = 1,2,3 (in general form, 1,2, ..., L). It is stored in a repeating form. Here, since there is only one element in register 1, only 1 is stored in register 2 as shown in the figure. Next, the two-dimensional address of w (1,1) is generated and stored in the register 1 as shown in the figure by using the elements whose positions correspond to each other in the register 1 and the register 2.

Next, as shown in II- (3) of FIG. 8, the indirect address of the working array is read. In the same manner as in step (3) of FIG. 3, the element "7" of the working array w corresponding to the two-dimensional address of w (1,1) represented by the element of register 1 is read and stored in register 2. To.

As shown in II- (4) of FIG. 9, the array a () is read. That is, in the same manner as in step (4) of FIG. 4, each element of the array a () is read out in order by the number of elements of the register 2 (here, 1), so that only "1" is read in the register 3 as shown in the figure. Is stored.

Next, as shown in II- (5) of FIG. 9, the working sequence and the sequence a () are added. That is, in the same manner as in step (5) of FIG. 4, the element of the working array w read into register 2 in step II- (3) (here, only "7") and the register in step II- (4). The elements of the array a () read into 3 (here, only "1") are added at the corresponding positions, and "8" is stored in the register 2 as shown in the figure.

Next, as shown in II- (6) of FIG. 10, indirect address writing to the working array w of the addition result is performed. That is, in the same manner as in step (6) of FIG. 5, the elements of register 2 that are positionally corresponding to the elements of register 1 are sequentially stored at the positions of the two-dimensional addresses of w represented by the elements of register 1. Therefore, here, "8" of register 2 is stored in w (1,1). As a result, "1" of a (1), which was not added in the previous calculation, is added.

As shown in II- (7) of FIG. 10, confirmation preparation of the addition result and order writing are performed. That is, in the same manner as in (7) of FIG. 5, the number up to the number of elements stored in the register 2, that is, the number 1 up to 1 here, is stored in the register 2 in ascending order as shown in the figure. Next, the element of register 2 corresponding to the element is read and written to the two-dimensional address of stamp represented by the element of register 1. Therefore, "1" of register 2 is stored in stamp (1,1).

Next, as shown in II- (8) of FIG. 11, confirmation of the addition result / reading of the writing result is performed. That is, in the same manner as in step (8) of FIG. 6, the elements stored in the two-dimensional address of the stamp represented by the element of register 1 (here, only (1,1)) are read in order and read into register 3. Is done. Therefore, the element "1" of stamp (1,1) is read at the top of register 3 as shown in the figure.

As shown in II- (9) of FIG. 11, the addition result is confirmed and the result invalid term is detected. That is, in the same manner as in step (9) of FIG. 6, the element "1" of the register 3 and the element "1" of the register 2 are compared, a match / mismatch is determined, and the determination result of "match" is shown in the figure. Is stored in register 3. Here, since there is no "mismatch" element, writing to list () is not performed, and list () is cleared to the "empty (from)" state.

Since list () is not generated, the process proceeds to step (12) in FIG. In step (12), the sum calculation of the working array w is performed. That is, each element of the array f is in the register 1, each element of the first column of the working array w is in the register 2, each element of the second column of the working array w is in the register 3, and the third of the working array w. Each element of the column is read into the register 4 provided in advance. Then, as shown in the figure, the elements corresponding to each other in the position of each register are added and stored in the register 1.

Next, as shown in (13) of FIG. 12, each element of the register 1 is stored in the array f. In the present invention, in steps (12) and (13), the elements of the array f and the working array w may be directly used, and the elements corresponding to each other may be added and stored in the array f. The result of adding each element corresponding to the position of the array f and the working array w may be stored in the array f.

[0064] The performance measurement results when the present invention is used are shown below. As a condition at the time of measurement, the size of array F is set to 2.¹⁴(= 16,384), add 2 elements²¹(= 2,097,152). The results of plotting the EPS value (the number of addable elements per second) when the index distribution (l) is changed by a power of 2 are shown in FIGS. 13 to 14. The value of the intermediate array index is NPB (NAS Parallel Benchmark) (Bailey, D., Harris, T., Saphir, W., Wijngaart, R., Woo, A., and Yarrow, M .: NAS Parallel Benchmarks 2.0, It is generated using the pseudo-random number generation routine of Problem IS included in Technical Report NAS-95-020, (1995)). As with IS, the average of four consecutive uniform random number sequences was used as the index value. In addition, in order to prevent the value of the addition element a (:) from affecting the performance, it is simplified to 1 in this experiment. With this setting, this experiment is essentially equivalent to performing the same histogram calculation as problem IS.

[0065] Each graph shows the results of the Work Vector algorithm of K = 16, the Work Vector algorithm of K = 64, the Retry algorithm, and the Masking algorithm of the present invention. Here, the value shown in parentheses in the heading portion of each curve is the value of K. Note that K = 16 is the upper limit of the work sequence that can be acquired by a general large-scale application, and K = 64 is an example of a work area that usually exhibits the required performance.

[0066] FIG. 13 shows the experimental results of the vector computer SX-4 (manufactured by Nippon Electric Co., Ltd.). SX-4 is a relatively short vector register (N)_VIt is a vector computer equipped with = 256). Indirect addressing load-stores also fall into the fast category.

FIG. 14 shows the experimental results of the vector computer VPP5000 (manufactured by Fujitsu Limited). The target machine is a vector computer equipped with a long vector register and having a high-speed load-store of the indirect address method.

[0068] The Retry-WV algorithm of the present invention has a conventional number of key indexes "l", that is, the degree of index overlap is in the range of about 20 to about 1000 in FIG. 13 and about 90 or more in FIG. It can be seen that it shows higher performance than the Work Vector algorithm and Retry algorithm of.

[Effect of the Invention] In the conventional Retry method, addition is performed with F as it is and correction of an invalid result term is performed without introducing the working array W, and the addition process is directly performed on F. Therefore, the index value. Due to this (actually, depending on the degree of duplication of index values), many results were incorrect, but in the present invention, the work array W expanded in two dimensions and the calculation formula for its addition position (index (I), mod) The occurrence of fraud can be reduced by (I-1, L) +1). Further, in the method of the present invention, the frequency of address collisions can be reduced, that is, the frequency of result frauds can be reduced as compared with the conventional method, so that the number of reprocessing of fraudulent terms is reduced, and as a result, the total processing time is reduced. Can be shortened and high-speed addition processing can be realized.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 shows a concept of correction of result fraudulent terms according to the present invention.

FIG. 2 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 3 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 4 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 5 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 6 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 7 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 8 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 9 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 10 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 11 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 12 is a part of a processing flow example for explaining the processing according to the present invention.

FIG. 13 is a diagram showing an example of performance measurement results when the present invention is used.

FIG. 14 is a diagram showing an example of performance measurement results when the present invention is used.