JPH06119368A - Relaxation method simultaneous equation analysis computer - Google Patents

Abstract

(57) [Summary] [Object] The present invention relates to the analysis of linear simultaneous equations, and particularly to a dedicated computer suitable for the analysis of large-scale equations using the relaxation method. The SOR method and the Gauss-Seidel method are used as the analysis algorithms of the relaxation method. The purpose is to realize a method that can handle high-performance algorithms such as. [Configuration] Computation elements PE ₁ , PE ₂ , ..., PE _N are connected in a ring shape, and each computation element is made to compute all variables of the simultaneous equations. The number of iterations until convergence is reduced by transferring the value of the variable calculated by itself to the adjacent calculation element of and using new values one after another in the iterative calculation of the relaxation method.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to analysis of linear simultaneous equations, and more particularly to a dedicated computer suitable for analysis of large-scale equations using a relaxation method.

[0002]

2. Description of the Related Art Since many engineering analyzes result in the analysis of linear simultaneous equations, the analysis of large-scale linear simultaneous equations is important for application. For this reason, studies have been conducted to speed up analysis by using a multiprocessor and dedicated hardware.

Methods for solving linear simultaneous equations include methods known as LU decomposition method and relaxation method. Large linear simultaneous equations often show sparseness in which most matrix elements are zero in their matrix representation.

The LU decomposition method is known to cause fill-in in which non-zero elements increase during analysis when analyzing such a sparse matrix. The relaxation method is an iterative method that performs analysis by iterating operations using the properties of a matrix. The relaxation method is particularly useful for large-scale linear simultaneous equations because it does not cause fill-in. Well-known methods include the Gauss-Jacobi method, the Gauss-Seidel method, and the SOR method.

In the Gauss-Jacobi method, simultaneous equations are expressed as Ax = b
Then, x (k + 1) = {b− (A−D) x (k)} / D, where D is a diagonal matrix of diagonal elements of A, and x (k) is the k-th position of x Is an approximate solution by iterating. The Gauss-Jacobi method is simple but has a large number of iterations and is not commonly used for single processor analysis. However, since each element of x can be analyzed independently, it is suitable for analysis by a multiprocessor.

The Gauss-Seidel method is similarly expressed as follows: x (k + 1) = {b-Lx (K + 1) -Ux (k)} / D, where L is the lower left half element of A Lower triangular matrix,
U is an upper triangular matrix composed of elements in the upper right half of A, and D is a diagonal matrix composed of diagonal elements of A. In the Gauss-Seidel method, the term related to L is the value calculated in the iterative step,
Propagation of this calculated value is a problem to realize with multiprocessor.

If a dense matrix is assumed, it is necessary to sequentially calculate each element of x (k + 1), and it is difficult to achieve the effect of parallelization. The SOR method accelerates the convergence of the Gauss-Seidel method by overcorrection at each step of the Gauss-Seidel method iteration. The correction amount of overcorrection varies depending on the target matrix, and it is difficult to determine the correction amount. Other features are based on the Gauss-Seidel method, but it is known that a very high speed can be achieved by using an appropriate correction amount.

Conventionally, when the relaxation method is carried out by a multiprocessor, the graph structure described by the linear simultaneous equations is divided and each processor is made to calculate. In order to divide and execute the calculation of the relaxation method, it is necessary to communicate between the processors as many as the number of edges of the graph cut for the division.

In the Gauss-Seidel method, it is necessary to communicate the latest calculation results among the divided processors, which is difficult to realize in a multiprocessor. Further, due to the order of calculation, even a multiprocessor may be serialized. There were many. The SOR method has the same characteristics as Gauss-Seidel.

Therefore, the Gauss-Jacobi method, which has a large number of iterations and is inferior in performance but is easy to realize, is often used. The SOR method has been implemented by a multiprocessor for specific problems such as discretized analysis of Laplace equation.

Conventional dedicated hardware is Koike: CAD machine; Ohmsha, pp.181-187, Murakami, Tanaka: Nonlinear network analysis based on iterative method and examination of hardware; Tournament, 1702, Urano, Tanaka: Computer for large-scale nonlinear network analysis based on relaxation method; IEEJ, CAS85-3
2 (1985), Ping-Sheng Tseng: A Systolic Array Paralle
lizing Compiler ； Kluwer Academic Publishers (1990)
Etc.

[0012]

Generally, in a multiprocessor system, minimization of communication is required, and the optimization problem of division is a difficult problem.

In the above-mentioned conventional technique, the Gauss-Jacobi method is often used in order to secure parallelism. However, it is possible to realize a general-purpose method that can use a high-performance algorithm such as the SOR method or the Gauss-Seidel method as an analysis algorithm for the relaxation method. It has been demanded.

When increasing the number of processors to improve performance, it is required that the connection form between the processors is simple.

[0015]

SUMMARY OF THE INVENTION The above-mentioned problems of the prior art are N for analyzing an m-dimensional linear simultaneous equation by a relaxation method.
Number of calculation elements, and each calculation element has a communication means for communicating with one or more specific calculation elements, and at each specific step in the calculation of the relaxation method, each calculation element has m linear equations. One different specific linear equation is analyzed, and the analysis result is transferred by the communication means to each specific one or a plurality of calculation elements, and each transferred calculation element is analyzed in the next step. This can be solved by providing a linear simultaneous equation analysis computer by the relaxation method, which is characterized by performing the next analysis using the result.

Another object of the present invention is to provide a computer system for analyzing linear simultaneous equations by the relaxation method, characterized in that the communication means is composed of N unidirectional transfer paths each connecting two specific calculation elements. Solvable.

[0017]

In the linear simultaneous equation analysis computer of the present invention, each of N calculation elements holds all information of simultaneous equations.
Therefore, high-speed relaxation method operation by Gauss-Seidel method can be executed in each calculation element, and the latest calculated values of other calculation elements sent by communication means are used for calculation, which is faster than Gauss-Seidel method. Is realized.

Further, the linear simultaneous equation analysis computer of the present invention does not require division of the equations into processors, which is required in the conventional multiprocessor, and the division optimization problem does not occur. In addition, the plurality of calculation elements transfer the result calculated by each of them to only a specific calculation element. Therefore, the communication route can be simplified and the communication can be minimized.

[0019]

1 is a block diagram of an embodiment of a computer for analyzing linear simultaneous equations according to the relaxation method of the present invention. Computational element (below
Called PE) PE ₁ .... PE _N are connected and communicate in a ring by a unidirectional data line. A gateway processor that communicates with the host computer (Host CPU) in the ring
There is a GE to set up each PE, send commands, and determine convergence.

For simplification of the following description, the linear simultaneous equations are regarded as the nodal equations in the circuit analysis, and the nonzero elements in the matrix expression of the equations are regarded as the branch conductances in the circuit. Even if viewed in this way, the generality of the equation is not lost. Generally, when circuit analysis is performed by a multiprocessor, communication between processors becomes a problem.

It is desirable to use a system that secures parallelism and requires a small amount of hardware for communication. In the linear simultaneous equation analysis computer of this embodiment, processor elements PE connected to each other by one-way data transfer lines are arranged in a ring shape. Each PE transfers the calculated node voltage to the adjacent PE via this data transfer line every time it calculates one node voltage by the Gauss-Seidel method.

Each PE uses the voltage transferred from the neighbor in addition to the voltage calculated by itself in the calculation of the node voltage, so that it is possible to perform the calculation using a newer calculated value than the usual Gauss-Seidel method.

One iteration of the Gauss-Seidel method ends when each PE finishes calculating all node voltages of the circuit graph. As described above, communication is performed by the number of PEs at each step of the Gauss-Seidel method, but in the linear simultaneous equation analysis computer of the present embodiment, the communication destination is limited to a specific 1PE, so the communication hardware is used. Is less burdensome.

Further, since only the transfer between adjacent PEs is performed, it is considered that the communication time is sufficiently short as compared with one step of the Gauss-Seidel method including the product-sum operation. In the linear simultaneous equation analysis computer of this embodiment, all PEs calculate all nodes of the circuit. Therefore, each PE has a local memory that stores all node voltages and branch conductances.

The execution of the Gauss-Seidel method in the PE of this embodiment will be described. The node equation of the circuit is Ax = b, the elements of the matrix A are aij, the elements of the vectors x and b are xi,
It is expressed as bi.

Calculation of the voltage xi of a certain node i requires the voltage xj of the node j connected to the node by a branch and the conductance aij of the branch. The calculation of the voltage at one node is defined as one step of the Gauss-Seidel method. Node j,
The steps of calculating the voltage xi of the node i connected to l and m are as follows.

Xi (k + 1) = {bi-xj (k) * aij-xl (k + 1) * ail-xm (k + 1) * aim} / aii where j> i, l, m < Assume i. The PE sequentially executes each step of the Gauss-Seidel method from preset nodes. At that time, the node voltage calculated by the i−1th PE is used. The node voltage calculated by itself is sent to the i + 1th PE. That is, the voltages at the other nodes used in the calculation step are not limited to the voltages calculated by the self PE.

The respective PEs are preliminarily set in the calculation order so that the same node is not calculated at the same time, and the PEs are not simultaneously executed to calculate the nodes connected by the branches of the circuit graph. Set it.
Since this calculation order differs depending on the equation to be analyzed, the calculation order is determined each time a new analysis is performed.

In the computer of the present invention, the determination of the calculation order is important for ensuring the performance, but a certain degree of performance improvement is ensured even if the order is not strictly guaranteed. The calculation order is determined by the following algorithm, for example.

Select one node and call it number 1. If there are unnumbered nodes, repeat the following. Connect unnumbered nodes with new numbers by connecting branches in the circuit graph.

Next, the operation of the computer of the present invention will be described by taking the DC analysis of the circuit shown in FIG. 2 as an example. Each branch of the circuit shown in FIG. 2 is a 1 ohm resistor. The nodal equation of this circuit can be expressed as a matrix as follows. For ease of explanation, the calculation order of each PE is set according to the node number.

This circuit is analyzed with _three PE PE ₁ , PE ₂ and PE ₃ . The calculation order of each PE is PE ₁ : 5,6,1,2,3,4 PE ₂ : 3,4,5,6,1,2 PE ₃ : 1,2,3,4,5,6 To do. Each PE performs analysis by the Gauss-Seidel method while communicating with each other according to this calculation order. The node voltage transferred by the communication means can be used in the next step. Each PE operates synchronously at each step.

The calculation steps of PE ₁ are as follows. 1.x5 = x3 + x4 + x6 '2.x6 = x1' + x2 + x5 3.x1 = 1 + x2 '+ x6 4.x2 = x1 + x3' + x6 5.x3 = x2 + x4 '+ x5 6. The calculation steps of x4 = x3 + x5 'PE ₂ are as follows.

1.x3 = x2 + x4 '+ x5 2.x4 = x3 + x5' 3.x5 = x3 + x4 + x6 '4.x6 = x1' + x2 + x5 5.x1 = 1 + x2 '+ The calculation steps of x6 6. x2 = x1 + x3 '+ x6 PE ₃ are as follows.

1.x1 = 1 + x2 '+ x6 2.x2 = x1 + x3' + x6 3.x3 = x2 + x4 '+ x5 4.x4 = x3 + x5' 5. x5 = x3 + x4 + x6 '6 x6 = x1' + x2 + x5 Each PE performs one Gauss-Seidel iteration in 6 steps.

The value shown as xi 'in the above step indicates that the calculated value of another PE transferred by the communication means is used. The value set as xi is the calculated value of the PE itself, and the value stored in the local memory is used. The calculation result is stored in the local memory and transferred to the adjacent PE.

This calculation step is repeatedly executed until the calculated values converge. In this example, the number of iterations until convergence was 425 when one PE was used, but it was 21 for two PEs.
The number of iterations until convergence was reduced to 5 times and 218 times with 3 PE units, which was faster than the case with only 1 unit. In the case of 3 PEs, the condition of the above calculation order is not satisfied, so 2
Performance has not been improved compared to the case of a stand.

When the computer of this embodiment is applied after discretizing the partial differential equation known as the Laplace equation into 30 × 30, if the performance when one PE is 1, the number of PEs is 4, 8 and 15 At that time, performances of 3.98 times, 7.99 times, and 14.98 times were obtained respectively.

When the computer of this embodiment was applied to the non-linear circuit simulation, the PE number-performance curve as shown in FIG. 3 was obtained. The non-linear problem is a target of the computer of the present invention because it can result in a problem for solving a solution of linear simultaneous equations by a method known as Newton's method. FIG. 3 shows a case where the static memory (SRAM) and the adder (ADDR) are analyzed.

In the present embodiment, the communication is performed once for each calculation step, but if the communication means has a margin, it is possible to transfer more calculated values. For example, the PE can reflect a plurality of calculated values in the next calculation step by first transferring the value calculated by itself and then directly transferring the value transferred from the neighbor.

Since the computer of the present invention has a limited communication volume, a shared memory is used instead of a dedicated communication path.
It is also easy to communicate between PEs. Further, the calculation element PE of this embodiment executes the Gauss-Seidel method, but the Gauss-Seidel method does not form the essence of the present invention, and the use of the SOR method or other relaxation methods does not exceed the scope of the present invention. .

[0042]

According to the present invention, in a computer having a plurality of calculation elements, a high-performance linear equation analysis computer can be realized with a small amount of communication between the respective calculation elements. Especially La
In the problem of finding the solution of the place equation, we achieved about 15 times the performance improvement with 15 PEs. Furthermore, it has been shown that the computer of the present invention can be used to increase the speed even for nonlinear problems.

[Brief description of drawings]

FIG. 1 is a configuration diagram of a computer according to an embodiment of the present invention.

FIG. 2 is a circuit diagram of an example.

FIG. 3 is a diagram showing performance curves of an example of an example of the present invention.

[Explanation of symbols]

PE ₁ , PE _2, ..., PE _N Computation element GE gateway processor

Claims (4)

[Claims] 1. N-computation elements each of which analyzes an m-dimensional simultaneous equation by a relaxation method, and communication means for communicating the N computation elements with specific one or more computation elements. The N calculation elements sequentially execute m operation steps of the relaxation method for analyzing m equations corresponding to the m-dimensional simultaneous equations, and each calculation is performed in a specific step of the m steps. The element analyzes one different specific equation out of m equations, each calculation element transfers the analysis result to each one or more specific calculation elements by the communication means, and each calculation element receives each transfer. Is a simultaneous equation analysis computer by the relaxation method, characterized in that the subsequent steps are executed using the analysis results received. 2. The simultaneous equation analysis computer according to claim 1, wherein the communication means comprises a one-way transfer path connected to at least two specific calculation elements. 3. The relaxation equation simultaneous equation analysis computer according to claim 1, wherein said communication means comprises a memory connected to at least two specific calculation elements. 4. The simultaneous equation analysis computer according to claim 1, wherein the simultaneous equations are linear simultaneous equations.