JPS6155706B2 - - Google Patents

Description

[Detailed description of the invention]

The present invention relates to a parallel processing computer for high-speed calculations, which has a simple configuration, can incorporate a large number of processors, and is highly efficient. Conventionally, as is typically seen in explicit difference decomposition methods for partial differential equations, each grid point or several adjacent grid points are collected, assuming that the calculation procedure at all grid points is the same. Several multicomputers or multiprocessors are known that are based on the concept of having one processor handle processing for each block. Of these, two-dimensional array processor-type SIMD computers (such as ILLIAC), in which all processors completely synchronize and execute microinstructions with the same number of steps under the central control of a control unit, have very limited computation capabilities. However, when it comes to other calculation methods, the connection structure is inconvenient in terms of data transfer between distant processors and centralized management, and it is not very efficient. Next, several methods have been proposed to provide shared memory and a common bus to allow direct data transfer between all processors, and to reduce bus contention and memory contention by time-sharing bus systems, cross-bus switch systems, or multi-processor systems. They are processed in the form of port memory systems, but each has the disadvantages that the bus control is complicated and efficiency is reduced, the amount of hardware is enormous, and the memory is expensive. Furthermore, in order to avoid memory contention, an equivalent amount of shared memory is provided in the private memory area of each processor, memory updates are performed using a broadcasting function, and calculation processing is performed independently by each processor, a combination of SIMD and MIMD. There are shape calculators (such as the SMS201 for weather forecasts), but their uses are extremely limited. From the user's point of view, the present invention is designed to facilitate the use of the ADI method, split operator method, etc. in the numerical solution of partial differential equations. This was done based on the knowledge that it is more efficient to perform calculations for each one-dimensional array of grid points, and that a one-dimensional array configuration is efficient and appropriate for matrix operations and FFT calculations. The other is the architecture, which is a crossbar type network that enables direct data transfer between arbitrary processors, but central management is required to minimize the amount of hardware involved. In order to improve efficiency on the processor side, it is possible to use buffer memory that has its own transfer function instead of using
It was based on the idea of creating a DMA channel. In the compound computer of the present invention, in a hierarchical architecture consisting of one main processor and a plurality of N slave processors, each having its own private memory, it is possible to send and receive data during parallel processing between the slave processors. For this purpose, a two-dimensional buffer memory with N rows and N columns is provided and connected to a DMA channel provided on the processor side. The basic bus connection method of the computer of the present invention will be explained with reference to the drawings. Figures 1 and 1A show its basic form and functional model, where the main processor is MU and the slave processor is AU-j (j=0,
1, ......, N-1) and preferably FIFO type buffer memory as BM-(i, j) (i, j=
0, 1, ......, N-1). In Fig. 1, the MU data bus includes all BM-(i,
j) (i, j = 0, 1, ......, N-1), and the data bus of each AU-j is connected to the j-th BM
- (i, j) (i=0, 1......, N-1) and j-th column BM-(j, k) (k=0, 1,......,
N-1). Furthermore, when using FIFOs as the BM, all of these FIFOs are preferably provided with a circulating data bus returning from the output side to the input side. When looking at each BM-(i, j), as shown in Figure 2, two types of data buses from AU-i and AU-j are connected to the input side through gates, and the output side is , each connected to the same data bus that entered the input side through separate gates. However, in the embodiment shown in Fig. 2, a bus and a
A data bus for circulation when using FIFO as BM is also added. The circular data bus is intended to be used at the same time as the data bus to the MU. And when there is no need for circulation, the bus is designed to turn off. When this circulation bus sends intermediate results to the MU during the sequential calculation process, the same data continues to be sent to the MU.
It is used when it is convenient to leave it in the FIFO, such as when it is used for calculations in AU. Obviously, a parallel computer with the above-mentioned path building allows for direct data transfer between an MU and any AU, and between any AUs, greatly expanding its versatility. Moreover, data can be converted simultaneously between any AU comrades, making it efficient. When exchanging data between AU-i and AU-j, AU-i
Send data to (i, j), then BM-
The operation of receiving data from (j, i) and the AU
-j sends data to BM-(j, i), and then receives data from BM-(i, j), which are performed completely in parallel. More importantly,
Each side does not have to be directly concerned with the progress of the other side's processor; they only have to watch the data appear in the BM that stands between them. Moreover, the OUTPUT READY signal indicating the appearance of the data is
Since the DMA controller receives the data, the processor only has to proceed with other calculations until the data is actually needed, making good use of the advantages of the asynchronous method. In addition, because it is an asynchronous system that eliminates a centralized management system, it inherently requires fewer signal lines, and even though it is a crossbar type path building that does not have a common bus, each BM can be externally connected. Since there are at most three types of data buses connected to each other, the amount of hardware required is relatively small, which opens the door to increasing the number of processors. Next, in order to facilitate understanding of the parallel processing operation of this computer, an overview of the parallel program and its processing will be explained. In this case, the two-dimensional array data to be handled is when the grid point coordinates are (I, J) (I, J = 1, 2, 3...N-1,
N), represented by the letter U, is a variable that should normally be expressed as U(I, J). Figure 1A shows the slave processor group shown in Figure 1.
AU−0,……AU−(N−1) is buffer
When each buffer memory BM is made to correspond to each grid point (I, J) by the connection structure via the matrix [BM-(i, j)], the AU that handles each row (J) of the grid point - columns (rows of solid circles);
This shows a functional model in which each row (I) of grid points can be seen as an AU row (row of broken-line circles). However, i and j representing numbers or coordinates in the slave processor AU and buffer memory BM are integers from 0 to N-1,
It should be noted that since the grid point coordinates I and J are integers from 1 to N as described above, i=I-1 and j=J-1, respectively. Therefore, the two-dimensional array variable has each grid point (I, J)
, the row position (I=1, 2......) is determined by the J (=j+1)th slave processor AU in the column.
N) U(I, /J/) which means handling data, and U(/I/, J which means handling data in column J by the I (=i+1)th slave processor AU in the row) ) is expressed as Thereby, parallel operations are performed by one slave processor for all grid points in any row position and all grid points in any column position. For example, the parallel processing program is as follows. PDO 10 J=1, N DO 20 I=1, N 20U(/I/, J)=U(I+1,/J/) +U(I-1,/J/) 10 CONTINUE, Here, PDO is Indicates the PARALLELDO statement,
It instructs that the executable statements up to label number 10 be processed in parallel for each row position by a set of AU-j (j=J-1) corresponding to the movement range of index J.
The DO statement for index I is a standard process commonly performed by the designated slave processors. All array variables on the right side of the expression that appear in the above PDO statement must be of the form U (*, /J/) (however, if they are in a column position, they will be of the form U (/I/, *)) . This is a constraint that clearly directs parallel operation. Also, on the left side there is a U (/
I/, J), in which the "=" operation for assignment includes data transfer via buffer memory. In the above assignment statement, all slave processors in column (solid line) positions in Figure 1A have label number 20.
Each time the calculation result of the right side of the equation is obtained, each slave processor stores the buffer memory (i, j) at the corresponding row position.
Write into the group (i=0, 1, ......, N-1). Once the specified vertical processor writes to the buffer memory as described above, all the vertical processors collect the contents of the buffer memory connected to each other when viewed from the horizontal row (indicated by the broken line) position in FIG. 1A, and thereby {U(/I/,
J)}. Thus, in the column position of FIG. 1A, one can move to, for example, the following program. PDO 30 I=1, N DO 40 J=1, N 40U (/I/, J) = U (/I/, J+1) +U (/I/, J-1) 30 CONTINUE In this example, the assignment statement is It has become something that does not involve The parallel processing operation of the present invention is as described above,
Hereinafter, embodiments of the device configuration of the present invention will be described in detail. Examples A prototype example will be presented to confirm the effects of the present invention. In this example, an 8-bit microprocessor F8 (manufactured by Fairchild Inc. and Mostek Inc., USA), which was judged to be convenient for implementing the prototype of the present invention among commercially available microcomputers, was used. An outline of the overall configuration is shown in FIG. The main processor MU and 16 units are shown. main processor
MU and 16 slave processors AU-j (j=0,
1, 2, ......, F - hexadecimal representation) and buffer memory BM - (i, j) of a two-dimensional array of 16 rows and 16 columns.
It consists of a group of FIFOs that make up the MU is
CPU3850, DMI3852 (dynamic memory interface), two DMA3854 (direct memory access), PIO3861 (veriferal I/O), 4K byte ROM and 8K byte RAM
It consists of One DMA controls data transmission and reception with the slave processor, and the other DMA is an I/O processor (this prototype uses the F8 software development board SDB-50 MK79019).
Control data transmission and reception with. PIO is provided for MU to directly input/output data and to accept interrupt requests from AU. In addition, all AUs have the same configuration, each with a CPU, DMI, DMA (1 unit), and 2K byte ROM.
and 4K bytes of RAM. and,
Each FIFO memory is 64 words x 4 bits
It is made by connecting two FIFO3341A in parallel. The main parts of the overall configuration and bus connections of this embodiment are shown in FIG. In the figure, for example,
It can be seen that the buses from MU, AU-F, AU-O, and the circulation bus are connected to FIFO (O, F). A circuit implementing the bus connection method for each FIFO memory shown in Figure 2 is depicted in Figure 4.
The logic for opening and closing the gate is shown in the center of the diagram. This logic is also used to open and close signal lines between the processor and FIFO. Data shift-in requests (SI REQ) or data shift-out requests (SO REQ) to FIFO-(i, j) come from the three involved processors MU, AU-j, and AU-i, but SI REQ and SO REQ is becoming accepted quite independently. The logic for SI REQ is organized on the left side of the center of Figure 4, and the logic for SO REQ is organized on the right side. In both cases, when one processor is sending and receiving data to and from this FIFO, the logic requests are no longer being accepted. An isopt ready (IR) or output ready (OR) signal is sent to the processor that accepts the request. The FIFO is
It inputs or outputs data at the same time it receives the XFER signal. Each processor's SI REQ and SO REQ signals are routed to port 1 (P1) on the CPU.
It is created from the data to be latched to. M.U.
When you want to exchange data with FIFO-(i, j) (P1), put a hexadecimal 2-digit number 'ij' between _{7 and 0} . When AU-j wants to exchange data with FIFO-(ij) (P1), put 'oi' between _{4 and 0} . Similarly, when AU-j exchanges data with FIFO-(j, i), put '1i' in (P1) _{4 to 0} . This data must be latched before the processor instructs the DMA controller to start. SI by that data
The logic for creating the FEQ and SO REQ signals is shown in FIG. In this figure, the parts surrounded by dotted lines are each placed on one board. REQ−
The j-board is a group of FIFOs (FIFO-(i,
j) (i = 0, 1, 2, ......, F) and the FIFO group in the jth column (FIFO - (j, i) (i = 0, 1,
2......This is a board that carries the logic to create the SI REQ and SO FEQ signals sent to F)). The FIFO group itself is collected in each row and placed on one board. Other signals sent and received between the MU and each AU-j are exchanged through port 0 (P0) on the CPU. The details are depicted in Figure 6. here,
The hexadecimal number 'j' of the processor AU-j with which you want to exchange signals is latched in (P0) _{3 to 0} of the MU. In addition, when we put 1 in (P0) ₆ , we promise to instruct AU-j to start calculation, and when we put 1 in (P0) ₄ , we instruct it to return to the state of loading the program again. I promise to do it. Also MU
When (P0) receives 1 at ₇ , it is understood that a signal indicating the end of calculation has been sent from AU-j. Next, M.U.
When (P0) ₅ is set to 1, it means that the same instruction is given to all slave processors at the same time, regardless of the value of (P0) _{3 to 0} . On the other hand, on the U-j side,
Placing 1 in (P0) ₇ is to notify the MU that calculation has finished, and placing 1 in (P0) ₅ is to request an interrupt to the MU. Also,
(P0) If you receive a 1 at ₆ , you will understand that you have received an instruction to start calculation, and if you receive a 1 at (P0) ₄ , you will stop the calculation.
It is assumed that the instruction to return to the program loading state has been obtained. Reference calculation example Here is a calculation example using this prototype example.
The effects of the computer of the present invention will be described by comparing it with calculations performed by the CPU (in this case, calculations performed only by the MU). Note that the calculation time below is calculated by following a program created in machine language. Before that, the basic cycle and basic routine processing time of each processor incorporated in this embodiment computer will be listed. The maximum clock speed of the F8 CPU is 2MHz, and when operated with this clock, the clock cycle is 500ns. There are short and long machine cycles, 2 μs (4 clock cycles) and 3 μs (6 clock cycles), respectively. Each instruction cycle is
It consists of a combination of these machine cycles, ranging from the shortest 2 μs to the longest 13 μs.
Note that during each machine cycle, the CPU refreshes the RAM and performs DMA transfers during the remaining time when it is not reading or writing memory, so the DMA transfer speed is fast, approximately 1 time per machine cycle.
A transfer of bytes takes place. In reality, the width varies depending on the refresh mode and the type of instruction, and the transfer time for one byte ranges from a minimum of 2 μs to a maximum of 5 μs. Now, assume that all floating point operations are performed with a length of 4 bytes (1 byte for the exponent and 3 bytes for the mantissa). The microprogram for floating point arithmetic is
All processors have it in their memory ROM. The calculation execution time of some of these subroutines will be listed below. Floating addition/subtraction has a width depending on the case, and is 26 μs to 1600 μs, but assuming a normal case, it is about 1 ms at a larger scale. Also, floating multiplication (Booth method) takes 3.5 ms, and floating division (pull-off method) takes 4 ms. Floating point number transfer between registers takes 20 μs, and transfer between memory registers takes 32 μs. Also, it typically takes 20 μs to transfer one word of floating point number through the FIFO (when it is never stopped in the FIFO), which is about the same as a register-to-register transfer within the CPU. However, there is a difference in the time it takes to set the numbers before jumping to the subroutine that performs these transfers, and it takes 17μ before going to the register-to-register transfer.
s, 25μ to go to register/memory transfer
s, it takes only 53 μs to go to the memory-to-memory transfer via the FIFO (in this case, it also includes instructions to the DMA controller). Next, although not directly related to the effect, we will consider the software convenience of data transfer via the FIFO buffer memory. In other words, FIFO 2
Dedicated memory corresponding to the dimensional array is provided in the RAM of the MU and all AUs. MU's RAM contains
A 16 x 16 two-dimensional array of memory is secured, and each node has a capacity of 4 words (16 bytes) (this is expressed as a 4-word deep memory, and each word has a capacity of 4 words (16 bytes)). Number m=0, 1, 2,
(Give 3). Allocate byte addresses 2000 to 2FFF for the 4096 bytes required for this purpose. and FIFO
-(i,j) corresponds to a length of 4 words from 2ijo to 2ijF. On the other hand, the RAM of AU-j has a cross-arranged FIFO-(i, j) directly connected to it.
(i = 0, 1, ......, F) and FIFO - (i, k)
(k = 0, 1, ......, F), two one-dimensional array memories are secured, and a depth of 8 words is prepared at each point (each word is Add number m = 0, 1, ......, 7). Allocate byte addresses 1COO to 1FFF for the 1024 bytes required for this purpose. Of these, 1COO~
1DFF address is FIFO-(i,j)(i
= 0, 1, ......, F), 1EOO ~
FIFO-(i, k) (k
=0, 1, ......, F). and
'1COO+20× corresponds to FIFO−(i,j)
FIFO- with a length of 8 words i~1CIF+20×i'
(j, k) corresponds to '1EOO+20×k~
It is 8 words long (1EIF + 20 x k') (7th,
(See Figures 8 and 9). In the following, the symbol (( We will use m=・)).
Furthermore, in the case of AU, among the cross-shaped memories,
The memory on the horizontal line will be called the row memory, and the memory on the vertical line will be called the column memory. Calculation example 1 (Matrix product) Two 16-by-16-column matrices A and B are given to dedicated memories ((m=0)) and ((m=1)) in the MU, and the matrix product AB Calculate the result ((m=0))
shall be placed in In order to perform this calculation using the AU group, each row of A is sent to the row memory ((m=0)) of the corresponding AU (jth row of A {a}i=
0, 1, ......, F to AU-j). Next, for each column of B, locate all the corresponding columns.
Put it in FIFO (serial). (in the kth column
FIFO-(k, i) (i=0, 1, . . . , F) is filled with the elements of the kth column of B.
In this case, each FIFO is filled with just 16 words.) AU−j is k=0, 1, ......, F
In this order, the data of FIFO-(k, j) is received and

Calculate [Formula] and store the result in the row memory ((m=1)). This calculation will be performed in parallel by all AUs. Finally, each
It is sufficient to transfer all of the AU's row memory ((m=1)) to the MU's dedicated memory ((m=0)). The time required for the above calculation is 1.27 seconds. Of this, each AU takes 1.20 seconds to calculate the sum of 16 products, which accounts for the majority of the time. For comparison, the above calculation is performed using MU instead of parallel processing.
If a single process is performed with only
It will be 19.4 seconds. Therefore, (parallel processing time)/(single processing time)=1/15.3. Using 16 AUs
Since the speed is increased by 15.3 times, the efficiency ratio is 0.95 (=
15.3/16). Calculation example 2 (Gaussian elimination method for simultaneous linear equations) 16-element simultaneous linear equations Assume that the problem is to solve , and the AU row memory ((m=0)) corresponding to each row of the coefficient matrix A={aji} is given in advance. jth row {aji}i of matrix A
= 0, ......, F is the row memory of AU-j〓m=
0)) is given. Then, when the data on the right side of the equation {bj}j=0, 1, ......, F is given to a certain location in the MU (for example, addresses IBCO to IBFF), solve the equation and find the solution {xi}i =0, 1,
......, F are stored in the same location.
In order to solve this problem using Gaussian elimination, first, {bj}j=0, 1, ......, each component bj of F is fixed at a fixed location in AU−j (for example, IEOO~IE03
address). After transfer, calculations are performed only on the AU side, but here we evaluate the calculation time assuming that no special pivoting is required during deletion and calculations simply continue. Now, in order to eliminate the unknown x ₀ , we need the coefficients (a ₀₁ /a ₀₀ , a ₀₂ /a ₀₀ , . . .
..., a _0F /a ₀₀ , b ₀ /a ₀₀ ) with AU-0, and convert the result from AU-1 to AU-
Send to all up to F. At this time, AU−j(j
= 1, 2, ......, F), use FIFO-
It is preferable to use (j, 0) (j=1, 2, . . . , F). All AUs that receive it perform elimination calculations in parallel. Next, in order to eliminate the variable x ₁ , coefficient calculation is performed in AU-1 and sent to all from AU-2 to AU-F. The AU that receives it performs elimination calculations in parallel. Repeat this operation sequentially.
When AU-F determines the value of x _F from the formula arrived at last, it moves on to calculation of substitution of this value, but in that case, the value of x _F is transferred to all AU-E to AU-0 in order, and each In this case, we perform the substitution calculation for x _F. Next, determine the unknown x _E in AU-E, transfer the value to AU-D to AU-0 in order,
Upon receiving this, the AU immediately completes the substitution calculation for x _E. In this way, we perform sequential substitution calculations, and at that time, we use the known xj values for all
While transferring to AU-k (k=j-1, j-2, ......, 0), AU-(j-1) that obtained its value
It is possible to immediately perform calculations to determine x _j-1 at the same time. In addition, the values of the obtained solutions can be sent to the MUs sequentially starting from the AU where the calculation has been completed. The time required for the above calculation is 887 ms. On the other hand, the time required for single processing of the same problem using only MU is 7277ms. Therefore, (parallel processing time)/(single processing time)=1/8.2, and the efficiency ratio is 0.51 (=8.2/16). In this case, the efficiency ratio drops to 0.51, which is unavoidable because the Gaussian elimination algorithm inherently has a large proportion of serial parts. Calculation example 3 (FFT calculation) To the extent necessary to explain how to perform FFT calculation using the parallel processing computer of the present invention,
The original algorithm will be described. The formula for handling discrete Fourier transforms is Defined by However, here, for simplicity, N=
2〓 (γ is a natural number). In the FFT calculation method, in order to find {X(n)} from {x ₀ (k)}, {x ₀ (k)} → {x ₁ (k)} → ...... → {x _l (k)} →……Take the step of {x〓(k)}. Here, to calculate {x _l (k)} from {x _l-1 (k)}, a set of paired equations is required. Use. Here, the value of p is expressed by expressing the index k as a binary digit of γ bits, then shifting this binary digit to the right by γ-l bits, filling the upper γ-l bits with 0, and then changing the bit order. is equal to the value of the binary digit that is repeated over and over again. In order to obtain {X(n)} from the finally obtained {x〓(k)}, when the value obtained by reversing the bit order of the binary representation of n is expressed as n)=
x〓(). (*) The calculation of formula is specifically It is done in the form of When this algorithm is executed only by MU, calculations are performed for each pair of x _l (k) and x _l (k') according to formula (*), so k = 0, 1, 2, If you follow the order, you may arrive at something that has already been calculated, but you can just skip that and move on. For example, when N = 16 (γ = 4), to find {x ₁ (k)}, if you calculate up to k = 0, 1, 7,
The calculation for k=8,...,F has already been completed. We will explain how to execute the above algorithm on a group of AUs using parallel processing as much as possible. First, we will discuss the case where a numerical table of COS values and SIN values that will be required during the process is prepared in advance. If AU−k is responsible for the calculation of x _l (k), then the number pair k and
Processors AU-k and AU-k′ (*
*) calculations are processed in parallel. In fact, AU−
At the same time that k' sends the x _l-1 (k') value to FIFO-(k', k), AU-k sends x _l-1 (k) to FIFO-(k, k'). And AU−k′ is x _l from FIFO−(k, k′)
₋₁ (k) and at the same time AU−k receives FIFO−
From (k', k), receive x _l-1 (k'). Next, AU−k′ calculates TR and sends the result to FIFO−
At the same time as sending to (k', k), AU-k calculates TI and sends the result to FIFO-(k, k'). Each processor also receives TI or TR via its corresponding FIFO. Finally, the AU
-k' determines the value of x _l (k'), and AU-k determines the value of x _l (k). These operations form all pairs (k, k′)
simultaneously and in parallel, and l=1,
2, . . . , γ are calculated sequentially. Now, if you want to calculate the COS value and SIN value each time you need them, instead of giving them in a numerical table, use the CORDIC
It is convenient to use the law. This is because this algorithm is also successfully computed by using the pair AU−k and AU−k′ (CORDIC
The calculation of the method itself will be described in Calculation Example 4 below). The calculation time when using 16 AUs with N=16 is listed below. (i) When tables of COS and SIN values are prepared in advance Calculation using only MU takes 690ms. On the other hand, the MU gives data to the AU group, and then
The time it takes to have the AU group perform calculations and return the final results to the MU is 60ms. Therefore, (parallel processing time)/(single processing time)=1/11.5, and the efficiency ratio is 0.72 (=11.5/16). (ii) When calculating the COS value and SIN value using the CORDIC method each time it is necessary, the calculation time for MU alone is 2600ms,
When calculating by AU group, it is 244ms. Therefore, (parallel processing time) / (single processing time) = 1/10.66, and the efficiency ratio is 0.67 (=
10.66/16). In the above result, the efficiency ratio in case (i) is about 0.72 because calculations performed only with MUs are skipped, whereas calculations performed with AU groups are performed successfully in pairwise calculations. This is because, although this speeds up, efficiency is reduced by the time required for transfer (the calculation time skipped is 0). In the case of (ii), the efficiency ratio is further reduced because the CORDIC method is not a fully parallelized algorithm. Calculation example 4 (Calculation of COS and SIN values using the CORDIC method) What was required for the FFT calculation in calculation example 3 was cos.
The values were pπ/8 and sinpπ/8 (0p7).
Here, when p is given, it is assumed that a pair of two units, AU-k and AU-k', calculates these values based on the CORDIC method. For 4p7, the relational expression cos
pπ/8=−cos8−p/8π and sinpπ/8=sin8−
If p/8π is used, it is sufficient to calculate for 0p3. In this case, the algorithm is as follows. Initial value x ₀ = 0.60725293501……, y ₀ = 0, v ₀ = pπ/
Every 8, perform the following iterative calculation for n = 0, 1, 2, ......, 16 (complete method) (The number n = 16 is decimal and has an accuracy of about 5 digits. (Because it is good.) (i) If v _o 〓0, then x _o+1 = x _o −2 ^-n y _o , y _o+1 = y _o +2 ^-n x _o , v _o+1 = v _o −γ _o , (ii) If v _o <0, then x _o+1 = x _o +2 ^-n y _o , y _o+1 = y _o -2 ^-2 x _o , v _o+1 = x _o + γ _o However, here γ _o = arctan2 ^-n (n=0, 1,
2, ......, 16) are prepared.
The finally obtained x ₁₇ and y ₁₇ are each cos pπ/8
and sin pπ/8. If we were to implement this algorithm for the pair AU−k and AU−k′, we would have AU−k perform calculations to determine {x _o+1 , and AU−k′ to perform calculations to determine {y _o+1 }. shall be taken as a thing. The initial value and the values of {γ _o } and {v _o } are maintained in all AUs, and the calculation of {v _o+1 } is executed in both AUs (it is assumed that the calculation is performed in only one and then in the other). (This is because it is slightly faster than the transfer method.) At this time, the calculation time for one p is 47.7 ms. On the other hand, the time required to calculate the above algorithm using only a single MU is 60 ms. Therefore, (parallel processing time) / (single processing time) = 1/1.2,
The efficiency ratio is 0.6 (=1.2/2). The efficiency ratio remains at 0.6 because the calculation of {v _o+1 } cannot be divided between two processors. This also leads to what was stated at the end of calculation example 3. Calculation example 5 (Example of ADI method - finite difference method of Navier-Stokes equations) If the Navier-Stokes equations that describe the two-dimensional flow of an incompressible viscous fluid are expressed using the flow function Ψ and vorticity ζ, ∂ ζ/∂t+∂Ψ/∂y∂ζ/∂x−∂Ψ/∂x∂ζ/
∂y=1/RΔζ (R is the Reynozzle number) ζ=−ΔΨ. Now, a square hollow area 0<x, y
<1, boundary conditions Ψ=0 and ∂Ψ/∂x(0, y)=∂Ψ/∂x(1, y)=0, ∂Ψ/∂y(x, 0) =0 ∂Ψ/∂y(x, 1)=U. The initial conditions are Ψ=0 and ζ=0, which correspond to the resting state. This is a model to see how the fluid in the cavity is driven at a uniform velocity U on one open side. Here is an example of a finite difference method that approximately solves the above system of partial differential equations that falls within the scope of the ADI method.
Divide each side of the square area 0<x, y<1 into 15 equal parts, create a mesh with grid spacing h=1/15, and divide the grid points (x
The unknown function values on _i , _yj )=(ih,jh) are expressed as _ζi , _j , etc. Also, let the time step width be τ, and the time t
The value at =nτ is further expressed as ζ ⁿ _i , _j , etc. using a superscript index. The following symbol is used for the difference quotient: Δ _1h ζ _i , _j = 1/h ² (ζ _i+1 , _j −2ζ _i , _j +ζ _i-1 , _j
), Δ _2h ζ _i , _j = 1/h ² (ζ _i , _j+1 −2ζ _i , _j +ζ _i , _j-1
), δ _1h ζ _i , _j = 1/2h (ζ _i+1 , _j −ζ _i-1 , _j ), δ _2h ζ _i , _j = 1/2h (ζ _i , _j+1 −ζ _i , _{j -1} ), In fact, the difference algorithm used as a calculation example is as follows: With J = 15

【table】

[Table] Here, the superscript index r of Ψ indicates the number of internal iterations, the number of iterations is R _o+1 , and the iteration parameter is τ ⁿ⁺¹ 〓. In order to realize the above algorithm using the AU group, the set of values corresponding to each j in the first half of the ζ calculation (1) is

[Formula] (i = 1, 2, ......, J- 1)
It is also possible to have AU-j do this and solve the simultaneous equations in the second half (2) where the values corresponding to each j {ζ ⁿ⁺¹ _j , _k (k=1, 2, ......J-1) are unknowns. Let AU-j do it. Similar assignments are made in (3) and (4) when solving for Ψ. In the following, the calculation time required to perform one time step n+n-1 will be considered. Now, we focus on AU−j and write {ζ
ⁿ _i , _j }, {Ψ ⁿ _i , _j } (i=0, 1, 2, ......
, J)
and {ζ ⁿ _j , _k }, {Ψ ⁿ _j , _k } (k=0, 1,
……
..., J) are held. And each
For AU-i (i=1, ......, J-1), {h ₂ Δ _2
h ζ ⁿ _i , _j }, {2hδ ₂ hζ ⁿ _i , _j }{2hδ ₂ hΨ ⁿ _i
, _j } (j=
1, 2, ......, J-1) are also held. Note that each AU-i is {ζ ⁿ _i , _j } and {Ψ
It is easy to calculate the above difference value as long as you know the values of ⁿ _i , _j } (in contrast, its
Even if AU-i has the same data, h ₂ Δ _1h
ζ ⁿ _i , _j , 2hδ _1h ζ ⁿ _i , _j etc. cannot be calculated immediately.
This is because AU-i itself does not hold the value of ζ ⁿ _i±1 , _j ). Now, let me explain the steps. (i) First, AU-j is all AU-i (i=1,
2, ......, J-1) respectively FIFO-
(i, j) through {h ² Δ _2h ζ ⁿ _i , _j , 2hδ _2h ζ
Receive the values of ⁿ _i , _j , 2hδ _2h Ψ ⁿ _i , _j }. Then,

[Formula] The coefficients of equation (1) and the values on the right-hand side are all determined. In particular, the value of ( ) on the right side (and A
ⁿ _i , _j ) will be used again when solving equation (2), so it is retained in memory. And {τ/8h ² ×2hδ _1h Ψ ⁿ _i , _j }(i=1, 2,...
..., calculate the value of J-1) and store it. (ii) AU−j solves equation (1) using the double sweep method,

[Formula] Determine (i = 0, 1, ......, J). At that time, at the reverse sweep stage

[Formula] is determined in the order of i = J, J-1, J-2, ......, 0, but it is not possible to have all of them.

【formula】 is determined one by one, the set of values {

[Formula] τ/8h ² ·2hδ _1h Ψ _i , _j , A ⁿ _i , _j } is sent to FIFO-(i, j) through the DMA channel. (iii) Then AU−j stores all FIFO−(j, k)
(k=1, 2, ......, J-1) respectively {

Receive the value of [Formula] τ/8h ² ·2hδ _1h Ψ _j , _k , A _j , _k }.
Then, {ζ ⁿ⁺¹ _j , _k }(k=0, 1,...
,
This means that we know all the coefficients and values of the right-hand side of simultaneous equation (2) regarding J). Therefore, this equation is solved again using the double sweep method. Then, the set of values {ζ ⁿ⁺¹ _j , _k , h ² Δ _2h Ψ ⁿ _j , _k } is DM
Each FIFO − (j, k) (k=1,
2, ......, J-1) (of course, h ² Δ
_2h Ψ ⁿ _j , _k is calculated in advance). (iv) Furthermore, AU−j is all FIFO−(i, j)
The values of {ζ ⁿ⁺¹ _i , _j , h ² Δ _2h Ψ ⁿ _i , _j } are received from (i=1, 2, ......, J-1), respectively. Combined with the already held {Ψ ⁿ _i , _j }, equation (3)
The value of ( ) on the right side of (write it as B ⁿ⁺¹ , ⁰ _i , _j )
is decided. So, by using the double sweep method again

[Formula] Determine (i=0, 1, 2, ......, J). Then, the set of values {B ⁿ⁺¹ , ⁰ _i , _j ,

[Formula] } for each FIFO-(i, j) (i=1, 2,...
..., J-1). (v) AU−j is all FIFO−(j, k) (k=
1, 2, ......, J-1) respectively {B
ⁿ⁺¹ , ^0j _{, k} ,

[Formula] }, solve equation (4), {Ψ ⁿ⁺¹ , ¹ _j , _k }
decide. and the set of values {h ² Δ _2h Ψ ⁿ⁺¹ , ¹ _j , _k , Ψ
ⁿ⁺¹ , ¹ _j , _k } as FIFO-(j, k) (k=1, 2,
…
..., send it to J-1). (vi) Again AU−j is all FIFO−(i, j)
Receive {h ² Δ _2h Ψ ⁿ⁺¹ , ^{1 i} , _j , Ψ n+1 , ^{1 i} , _j } from (i=1, ₂ , ......, _J -1), respectively, and right-hand B ⁿ⁺¹ of equation (3). , ¹ _i , _j and solve it.

Determine [Formula]. And also (B ⁿ⁺¹ , ¹ _i , _j ,

[Formula] } is sent to each FIFO-(i, j). (vii) Same operation as below (v) → Same operation as (vi) →……→
By repeating the same action as (v), {Ψ
ⁿ⁺¹ _j , _k = Ψ ⁿ⁺¹ , ^Rn+1 _j , _k , } are determined. However, in the last operation (v), the set of values {ζ ⁿ⁺¹ _j , _k , h ²
Δ
_2h ζ ⁿ⁺¹ _j , _k , 2hδ _2h ζ ⁿ⁺¹ _j , _k , 2hδ _2h Ψ ^n
+1 _j , _k , Ψ
_o+1j , _k } respectively as FIFO-(j, k) (k=1, 2,
......, J-1) to return to (i) of the entire loop. To perform the actions described here, hold or
There are several types of data to be transferred, and the dedicated memory in the AU mentioned above is used to store them (see Figure 9). Each position has a capacity of 8 words deep, and numbers m=0, 1, 2, . . . , 7 are assigned to them.
FIG. 10 shows an example specifically showing which word each piece of data is allocated to. FIG. 10 also shows which values are sent to and received from the FIFO during the iterative calculation performed by one AU-j. In FIG. 10, H-R indicates the type of value received in each row memory in AU-j. H-S indicates the type of value sent to the FIFO from each of the same row memories. VR indicates the value accepted into each column memory, and VS indicates the value sent out from each column memory. From the top: H-R, H-S→V-R, V
-S→HR-R, H-S→……→VR, V-S
It is shown that one step of n→n+1 is completed by repeated calculation of . However, values without diagonal lines in the sending state (S) simply indicate that they are to be held, and values without diagonal lines in the receiving state (R) indicate that they are already being held. It shows. The calculation time required for one step in the above algorithm is 3875 ms, assuming that the number of internal iterations R _o+1 is 5. If the same calculation is performed using only MU, it will take 54156ms. Therefore, (parallel processing time)/(single processing time) = 1/13.8, and the efficiency ratio is 0.99 (=13.8/14) (in this case, the number of processors AU in actual operation is 14). This is a high efficiency ratio. In actual parallel processing, the transfer time through the FIFO is 18 μs/
It's about one word, and even if you put them together, it's the whole
This is because it is only 0.5%, which means that most of the actual calculation part is processed in parallel. The above results are for parallel processing using 14 AUs, but this can be generalized to Q AUs.
Using AU, when the number of internal iterations is R,
The calculation time required to advance one step is (74.1
+40.3R) Q+1.0R+15.0ms (If R=5
275.6Q+20.0ms). When calculating only with MU, (73.1 + 39.9R) Q ² + (16.2 + 0.2R) Qms
(If R=5, it will be evaluated as 272.6Q ² +17.2Qms.
From this, if Q becomes a large value, it will be approximately (74.1 + 40.3R) Qms when using AU groups, and approximately (73.1 + 39.9R) Q ² ms when using only MUs (in this case, Q means that one side is Q + 1 This corresponds to thinking on an equally divided grid point). Therefore, (parallel processing time)/(single processing time)=1/0.988Q (when R=1), and if R also increases, it becomes =1/0.99Q.
Therefore, the efficiency ratio is still 0.99. When solving a nonlinear partial differential equation like this example using the ADI method, the calculations processed by each AU are sufficiently complex and obviously require a lot of time compared to the time required for transfer, so the efficiency ratio is extremely low. This may give the impression that the equation is high, but the following example shows that the efficiency ratio does not fall below 0.99 even for Poisson's equation, which has a simple equation itself. Calculation example 6 (Application example of ADI method - finite difference method of Poisson equation) The equation ΔΨ=-ζ for Ψ in the second half of the Navier-Stokes equation considered in calculation example 5 is nothing but a Poisson equation. Therefore, it is sufficient to extract only the internal iteration part of the Ψ calculation in the latter half of the previous difference algorithm. Then, when calculating with the AU group, it takes 2822 ms for 5 repetitions, and 39095 ms when repeating MU only 5 times. Therefore, (parallel processing time)/(single processing time)=1/13.85, and the efficiency ratio is 0.99 (=13.85/14). Calculation example 7 (When solving the same Poisson equation as in calculation example 6 using a simple iterative method) The handling algorithm is Ψ ⁿ⁺¹ _i , _j = Ψ ^r _i , _j +τ〓/h ² (Ψ ^r _i+1 , _j +Ψ ^r _i−1 , _j +Ψ ^r _i , _j+1 +Ψ ^r _i , _j−1 −
4Ψ ^r _i , _j )+τ〓ζ _i , _j (r=0, 1, 2, ......). In order to achieve this with AU groups, the following (i)
You can repeat step (ii) as many times as necessary. (i) AU−j is all FIFO−(i, j) (i=
1, 2, ......, J-1) respectively, the value Ψ
^r _i , _j+1 +Ψ ^r _i , _j+1 is received. Calculate the right side of the above equation and use the result as {Ψ ^r+1 _i , _j } for each FIFO−
(i, j) (i=1, 2, ......, J-1). (ii) Then AU−j stores all FIFO−(j, k)
(k=1, 2, ......, J-1) to the value Ψ
Receive ^r+1 _j , _k , sum Ψ _r+1j , _k+1 +Ψ ^r+1
Find _j , _k-1 and apply it to each FIFO-(j, k) (k=1, 2,...
..., J-1). The calculation time required for five iterations is 992ms.
On the other hand, when performing simple iterative calculations using only MU, the calculation time is 13469ms for 5 iterations. Therefore, (parallel processing time)/(single processing time)=1/13.58, and the efficiency ratio is 0.97 (=13.58/14). For reference, the calculation time when iterating R times with Q AUs is generally 14.1QRms, and the calculation time when using only MUs is 13.7Q ² Rm.
s is 1/0.97Q, and it can be seen that the efficiency ratio is generally 0.97. Calculation example 8 (When solving the same Poisson equation as in calculation example 6 using the Gauss-Seidel method) The handling algorithm is Ψ ^r+1 _i , _j = 1/4 (Ψ ^r+1 _i-1 , _j +Ψ _ri+1 , _j +Ψ ^r+1 _i , _j-1 +Ψ ^r _i , _j+1 )+h ₂ ζ,
_j (r=0, 1, 2, ......). When realizing this in the AU group, the set of unknowns for each j {Ψ ^r+1 _i , _j } (i=1, 2, 3
,
......, J-1) shall be calculated by AU-j. At that time, for example, AU-2 is Ψ ^r+1 ₁ , ₂
To find , Ψ ^r+1 ₂ , ₁ must already be calculated. Therefore, if AU-1 determines Ψ ^r+1 ₂ , ₁ , it is first passed through FIFO-(2, 1) to AU-
After sending it to 2, AU-1 goes on to calculate Ψ ^r+1 ₃ , ₁ , and at the same time AU-2 goes on to calculate Ψ ^r+1 ₂ , ₂ , and so on, Ψ ^r+1 _i , _j The value of is i
+j will be determined in a wave-like manner from the lower number to the higher number. Looking at the operation of AU-j,
In order to determine the values of Ψ ^r+1 _i and _j , FIFO−(j, j+
1) to get the value of Ψ ^r _i , _j+1 , then FIFO−
After obtaining Ψ ^r+1 _i , _j-1 via (j, j-1) and calculating the right side of the above equation, the value is set as Ψ ^r+1 _i , _j and then FIFO-(
j
-1, j) and FIFO-(j+1, j) can be repeated in the order of i=1, 2, . . . , J-1. Once this is done, continue with {Ψ ^r+2 _i , _j } (i=
1, 2, ......, J-1). As seen above, this calculation does not need to use all of the FIFO buffer memory, but only the ones that line up on the tridiagonal line. If the above calculation is repeated R times with Q AUs, the calculation time is 8.6 (R+1) Qms. If the same calculation is performed on MU, it will take (7.8Q ² +0.05Q) Rms, and (parallel processing time) / (single processing time) = 1/
(0.907Q+0.0058)(1+1/R) ^-1 , and if Q and R are slightly larger, it becomes ≈1/0.907Q, and the efficiency ratio becomes 0.907. The reason why the efficiency ratio is lower than that of the ADI method is because of the Gaussian
This is because the Seidel method is originally a serial algorithm and cannot perform complete parallel processing. As shown above, especially in calculation examples 5 to 8, when solving a difference approximation equation of a partial differential equation using an iterative solution method,
It was found that the computer of the present invention has high performance with an efficiency ratio of 0.9 to 0.99. Among them, in the case of ADI method, Q
It turns out that if you use a standalone AU, you can get a machine that has Q times the performance with almost no waste.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an example of the basic arrangement state of the parallel processing computer of the present invention, and FIG.
A function diagram showing how the slave processor group in the basic arrangement shown in the figure has horizontal and vertical functions via a two-dimensional array buffer.
A wiring diagram showing the connection style of the data bus in the buffer memory, FIG. 3 is a schematic diagram of a parallel processing computer that is an embodiment of the present invention, and FIG. 4 is a detailed example circuit of the bus connection shown in FIG. 2. Figure 5 is a diagram showing an embodiment of a logic circuit for generating the SI REQ and SO REQ signals in Figure 4, and Figure 6 is a logic circuit showing exchange of transmitted and received signals between the main processor and each slave processor. Figures 7 to 9 are diagrams showing examples of byte address assignment in each processor.
Figure 0 shows the Navier-Stokes equation of calculation example 5.
FIG. 3 is a diagram showing data allocation and data transmission/reception format in the ADI solution method. MU...Main processor, AU...Slave processor, FIFO...FIFO serial memory.

Claims (1)

[Claims] 1. In a parallel processing computer that has a hierarchical architecture consisting of a one-dimensional array of one main processor and a plurality of N slave processors, between the main processor MU and each slave processor AU, and between any two A buffer memory BM group consisting of a two-dimensional array of N rows and N columns is provided for data transfer between slave processors of the same processor, and the slave processors AU are provided with numbers i=0, 1, 2,
……, attach N-1 and the buffer memory
BM has two-dimensional array number (i, j), i, j = 0,
When adding 1,......,N-1, the number (i,
A parallel processing computer characterized in that two types of data buses connected to slave processors numbered i and j are input to the memory of j), and the output side also has a connection style connected to the two types of buses.