JPH0748204B2 - Matrix calculation processing method - Google Patents

Description

The present invention relates to a matrix calculation processing method for performing matrix calculation in a vector computer at high speed using a vector accumulator.

[Conventional technology]

Conventionally, as the calculation of the inverse matrix of a matrix and the method of solving simultaneous linear equations, for example, as shown in “Numerical calculation method I for electronic computer I” by Jiro Yamauchi et al. The elimination method is generally known.

The inverse matrix can be calculated by finding X such that A · X = E, where E is the unit matrix, and the simultaneous linear equations AX _j
= E _j (X _j is the j-th column of X, e _j is the j-th column of E), j = 1,2,
…, Solve for n. Therefore, in the following description, P
Calculation of matrix X that satisfies X = Q will be described. Here, P and Q are given matrices of m rows and m columns and m rows and n−m columns, respectively, and X is a matrix of m rows and n−m columns to be obtained.

In the sweep method, For the matrix A, 1) divide the kth row by a _kk . (A _kk is called a pivot) 2) For j = 1,2, ..., m (except j = k), jth
Subtract a _jk times the kth row from the row.

3) The above 1) and 2) are repeated for k = 1, 2, ..., M.

Is calculated.

In the Gaussian elimination method, 1) For j = k + 1, ..., m, a _jk / a from the jth row to the kth row
_kk times.

(A _kk is called a pivot) 2) The above 1) is repeated for k = 1, 2, ..., M-1.

Is calculated.

In both the sweeping method and the Gaussian elimination method, the pivot (a _kk ) at each step must not be "0".
Even if the value is not "0", the pivot value may be extremely small during the calculation. Continuing the calculation as it is is not preferable in terms of calculation accuracy.

Therefore, conventionally, an operation of selecting a pivot has been required.

This operation, for example, when determining the kth pivot,
Instead of unconditionally pivoting a _kk , i = k, k + 1,
Among a _ik of m, the one with the largest absolute value is selected. Then, the row including the element is set as the pivot row, the rows are exchanged between the k-th row and the pivot row, and then the calculation is performed.

There is a vector computer as a computer for performing such matrix calculation at high speed. FIG. 6 is a block diagram showing an example of a vector computer that performs such a conventional matrix calculation processing method. In the figure, 1 is a main memory for storing a matrix to be calculated, and 2 is a calculation processing. An arithmetic unit (CPU) 3 for executing the above is a vector accumulator (VACC) which is composed of a plurality of vector registers and which reads out and holds a matrix to be operated from the main memory 1.

Further, FIG. 7 is shown in Japanese Patent Laid-Open No. 62-138968.
FIG. 8 is a block diagram showing another example of a vector computer that performs such a conventional matrix calculation method, in which reference numeral 5 denotes a scalar accumulator (SACC) for holding scalar values, 6a, 6a.
b is a load bus for reading the data of the main memory 1 to the vector accumulator 3, 7 is a store bus for writing the data of the vector accumulator 3 to the main memory,
8 is a transfer switching circuit for exchanging data between the main memory 1 and the vector accumulator 3 and the scalar accumulator 5 via the load buses 6a and 6b and the store bus 7, and 9 is the vector accumulator 3 and the scalar accumulator 5 Is a calculation switching circuit for exchanging calculation data between the calculation device 2 and the calculation device 2. The same numbers as in FIG. 6 indicate the same items.

Since the processing of calculating the data of the vector register in the vector accumulator 3 by the arithmetic unit 2 via the arithmetic switching circuit 9 is performed at a high speed by the pipeline, the matrix arithmetic processing is first performed from the main memory 1 to the matrix data. The row data is fetched as vector data into the vector register in the vector accumulator 3, the arithmetic operation of the vector data is performed by the arithmetic unit 2, the intermediate arithmetic result is written back to the vector accumulator 3, and finally the final result is written back to the main memory 1. Done by.

Next, a conventional matrix operation processing method will be described with reference to the flowcharts of FIGS. Here, a case will be described as an example where the above-described equation of P · X = Q is solved by the sweeping method.

In FIG. 8, first, the matrices P and Q to be operated are loaded from the main memory 1 into the vector accumulator 3 (step 81). At this time, the row data of the matrix is read as vector data in association with each vector register of the vector accumulator 3. Next, k = 1 is set (step 82), and the pivot is selected according to the flow chart shown in FIG. 9 (step 83). In FIG. 9, in the pivot selection, first, the one having the largest absolute value is selected from a _ik (i = k, k + 1, ..., M), and is set as the pivot value (step 91). If this pivot value is "0", an error will occur (step 92). Next, the pivot row numbers r _k and k are compared (step 93), and if r _k = k, the process returns to the flow of FIG. 8, and if r _k ≠ k (step 94), FIG. The k-th row and the r _k-th row of the matrix are exchanged in accordance with the flowchart shown in, and the process returns to the flow of FIG.

In FIG. 10, the processing method changes depending on the presence / absence of an empty vector register (step 101) in the vector accumulator 3. If there is an empty register, the contents of the vector register corresponding to the kth row data are transferred to the empty register (step 102), and the contents of the vector register corresponding to the r _kth row data are transferred to the kth row. Data is transferred to the vector register corresponding to the row data (step 103). Next, the original kth row data transferred to the empty register is
By transferring to the vector register corresponding to the row data of the r _k-th row (step 104), the row data of the _k-th row and the row data of the r _k-th row are exchanged by the transfer between the registers in the vector accumulator 3.

If there is no empty register, the empty area in the main memory 1 is used to replace the rows as shown in steps 105 to 107. In this case, since the main memory is accessed, the processing speed of the vector computer decreases.

Next, returning to FIG. 8, when the pivot selection in step 83 is performed, the pivot row is divided by the pivot value (step 8
Four). Then, sweeping is performed on all the rows except the pivot row (steps 85 to 87). When all the sweep-out operations are completed, the result on the vector accumulator 3 is stored in the main memory 1 and the operation is completed.

[Problems to be Solved by the Invention]

According to the conventional method, when selecting the pivot, for each row,
A line swap operation may be required. This operation has a problem that the row data in the vector accumulator needs to be exchanged and the processing time is required each time the row data is exchanged.

In addition, the vector accumulator is generally several (s
When the matrix row data is used as vector data and each vector register is associated with the matrix to perform high-speed matrix operation, the row replacement operation is performed as in the conventional method. When necessary, if the number of rows of the matrix is up to s-1 rows, the rows can be exchanged without accessing the main memory. However, if the number of rows of the matrix is s rows, the rows are exchanged to the main memory every time row data is exchanged. There is a problem that access is required and processing performance is deteriorated.

The present invention has been made in order to solve the above problems, and utilizes the calculation processing capability of a vector computer to perform an inverse matrix calculation or a matrix calculation capable of processing a plurality of simultaneous linear equations having the same coefficient at high speed. The purpose is to obtain a treatment method.

[Means for Solving the Problems]

The matrix operation processing method according to the present invention creates a row index table (hereinafter referred to as RI table) for recording the row exchange state of each row when the pivot is selected.

[Action]

By the pivot selection, when the possibility of row replacement occurs, instead of replacing each element of the row, the row number corresponding to the replacement row of the RI table in the present invention is replaced, in the final stage of the operation, The result in the vector accumulator is stored in the main memory while referring to the RI table.

Example of Invention

An embodiment of the present invention will be described below with reference to the drawings. First
In the figure, 1 is a main memory, 2 is an arithmetic unit (CPU) for performing arithmetic processing, 3 is a vector accumulator holding a matrix to be operated, and 4 is the same number of rows (m) as the matrix to be operated. , Instead of swapping the actual rows when the pivot selection creates a need to swap rows,
It is an RI table for replacing the numbers of corresponding rows.

Further, FIG. 2 is an explanatory view showing the exchange of the row numbers of the RI table 4, and FIGS. 3 to 5 show P.
6 is a flowchart of the present invention for obtaining a matrix X that satisfies X = Q.

The matrices to be operated, P and Q, are loaded from the main memory 1 into the vector accumulator 3 (step 30), and then the first pivot selection is performed (steps 31 to 33).
And FIG. 4). In the first pivot selection, a ₁₁ , a
_Select the element with the largest absolute value from ₂₁ , ..., a _m1 ,
The element is set as a pivot, and the row including the element becomes a pivot row (step 41). Now, if a _r1 is selected as the pivot, it is necessary to exchange the first row and the r-th row, but in the present invention, instead of performing the actual row exchange, the first row of the RI table 4 is replaced. And the r-th row is exchanged (step 44). RI
Table 4 shows 1, in order from the first row, before the operation starts.
Since the values of 2, ..., r, ..., m are initially set, the contents of the RI table 4 are sequentially changed from the first row to r, 2, ..., 1, ..., m by the first pivot selection. Become.

The same applies to the pivot selection from the second time to the m-1th time. When the first row becomes the pivot row in the kth pivot selection as shown in FIG. 2, the first row of the RI table 4 is selected. The contents R ₁ of the eye and the contents R _k of the kth row are exchanged.

By using this RI table 4, it is necessary to exchange n elements in one row exchange.
It can be done by exchanging only one element. What if m
-If the row exchange is required every time the pivot is selected once, it is not necessary to perform the element exchange for (m-1) · n times. Further, since the RI table is provided in the area other than the vector accumulator 3, it is not necessary to have an empty vector register for row exchange in the vector accumulator 3,
All vector registers in the vector accumulator 3 can be used as storage locations for row data.

After the pivot selection and the sweep-out for all rows other than the pivot row have been performed for 1 to m rows, the vector accumulator 3 still has the result without row exchange, so referring to the RI table 4, The processing results are stored in the main memory 1 in the correct row order (step 38). That is, as shown in FIG. 5, if had entered the R _k in the k-th row of the RI table 4, the element group of the R _k rows of the matrix in the vector accumulator 3 matrix in the main memory 1 second Store at line k.

Further, in the above-described embodiment, the case where X that satisfies PX = Q is obtained by using the sweeping method has been described, but the present invention can be applied to the Gaussian elimination method and other operations that require a row or column exchange operation of a matrix. .

〔The invention's effect〕

As described above, according to the present invention, since the RI table indicating the row exchange state is installed, in the matrix operation requiring the row exchange operation, it is not necessary to exchange all the element groups forming the exchange row, and the RI table Since it is only necessary to exchange one element among the elements, the calculation time can be shortened and high-speed matrix calculation can be performed. In addition, since the RI table is provided in the area other than the vector accumulator, when the matrix row data is used as vector data and each vector register is made to correspond, and a high-speed matrix operation is performed by the pipeline, there is a space for row exchange. It is not necessary to have a vector register in the vector accumulator, and all vector registers in the vector accumulator can be used as storage locations for row data.

[Brief description of drawings]

FIG. 1 is a block diagram showing a matrix calculation processing method according to an embodiment of the present invention, FIG. 2 is an explanatory diagram of a table for recording a row exchange state according to the present invention, and FIGS. 6 and 7 are block diagrams showing the configuration of a vector computer for performing a conventional matrix calculation processing method, and FIGS. 8 to 10 are flowcharts of the sweeping method by the conventional method. is there. In the figure, 1 is a main memory, 2 is an arithmetic unit, 3 is a vector accumulator, and 4 is an RI table. In the drawings, the same reference numerals indicate the same or corresponding parts.

Claims (1)

[Claims] 1. A matrix operation processing method by a vector computer including a main memory, a vector accumulator for holding element data of a matrix read from the main memory, and an operation device for operating a matrix, in which row or column is exchanged. When a table for recording the state is provided and rows or columns are exchanged, instead of exchanging the element data of the above vector accumulator, the numerical value corresponding to the row or column to be exchanged is recorded in the above table, and the vector after the operation is calculated. Replace the element data of the accumulator according to the record in the above table,
A matrix operation processing method characterized in that the original rows or columns are written in the main memory.