JPH0748207B2 - Matrix operation device - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a matrix computing device suitable for computing a matrix (sparse matrix) containing many zero components and a vector.

<Prior Art> When simulating a phenomenon in nature using a computer, a matrix represented by a two-dimensional array is often used as a conversion matrix to perform a primary transformation of a vector represented by a one-dimensional array. For example, the matrix calculation as shown in the following equations (1) and (2) can be given.

y = Wx (1) v ^t = u ^t W (2) where x = (x ₁ , x ₂ , x ₃ , ..., x _M ) ^t is the input vector, y
_{= (Y 1, y 2,} y 3, ..., y N) t is output vector, W = {Wji} is the transformation matrix of N rows and M columns for the linear _{transformation, u = (u 1, u} 2,
u ₃ , ..., u _N ) ^t is the input vector, v = (v ₁ , v ₂ , v ₃ , ..., v _M ) ^t
Indicates an output vector, and (*) ^t indicates a transposed matrix in which rows and columns are interchanged.

A matrix operation device such as a conventional vector processor has a memory for storing data representing each element Wji of the transformation matrix W, and a storage means for storing a calculation algorithm of a product sum of the element Wji and an element of an input vector. The output yj (j = 1, 2, ..., N) at the time of the calculation of the formula (1) is provided according to the following formula (3).

Further, when calculating the equation (2), the output v _i (i = 1, 2, ..., Of each column)
M) is calculated according to the following equation (4).

Note that the calculations of these equations (3) and (4) are schematically shown in FIGS. 16 and 17, respectively.

<Problems to be Solved by the Invention> By the way, in applying the above matrix operation to a real problem, the proportion of zero elements (hereinafter, referred to as “zero elements”) among the elements Wji of the transformation matrix W is It can grow. For example, in a simulation of a neural network, a transmission signal that one neural circuit element group receives from the other neural circuit element group is such that the output of each element of the sender is an input vector x and each element on the sender side receives from the receiver side. It can be considered as a linear transformation y = Wx in which the coupling strength (coupling coefficient) to each element of is a transformation matrix W, but at this time, it is rare that all neural circuit elements are connected. On the contrary, most of the coupling coefficients between the elements, that is, the elements of the transformation matrix W are zero elements (a sparse matrix).
In many cases. This tendency becomes stronger as the neural network becomes larger.

In such a case, the above-mentioned conventional arithmetic processing device treats each element Wj of the conversion matrix W of N rows and M columns as in the case of handling a matrix having many non-zero elements (hereinafter referred to as “non-zero elements”).
It is necessary to allocate and store i as N × M real numbers in the memory as it is, and the multiplication and addition are performed N × M times for each matrix calculation process. Therefore, it is considered that there is a waste of storing and calculating the zero element.

Therefore, with a matrix memory that stores a data string consisting of non-zero elements of a sparse matrix, and an index memory that stores the position information of each non-zero element in the sparse matrix,
A linear conversion method has been proposed which calculates the sum of products of only the non-zero elements of the sparse matrix and the elements of the input vector while referring to the position information of the index memory (Japanese Patent Laid-Open No. 53-53115)
-64439 publication). According to this linear conversion method, the storage amount and calculation amount of the memory can be reduced.

However, in this linear conversion method, since an integer representing a row number and an integer representing a column number are stored as position information in the index memory, in order to read the non-zero element of the matrix memory, the address controller separately uses The address must be specified based on the contents of the index memory. That is, there is a problem that complicated control must be performed to specify the address of the matrix memory.

Therefore, an object of the present invention is to provide a matrix calculation device that can reduce the memory storage amount and calculation amount when performing a large-scale sparse matrix calculation process and can be easily controlled.

<Means for Solving the Problem> In order to achieve the above-mentioned object, the matrix operation device of the present invention provides data for specifying whether each element of a matrix represented by a two-dimensional array is zero or non-zero. Referring to the first memory for storing, the second memory for storing the data representing the content of the non-zero element of the matrix, and the data stored in the first memory, the elements of the matrix are zero. Regarding the discriminating means for discriminating whether or not there is any, and the elements of the matrix discriminated as non-zero by the discriminating means, the second
In the matrix operation device provided with the operation means for multiplying the data stored in the memory and the element of the input vector to obtain the sum of products, in the first memory, the elements having zero in the matrix are consecutive. It is characterized in that an integer representing the number arranged in parallel and an integer representing the number in which non-zero elements are arranged consecutively are stored in the order of each continuous arrangement in the matrix.

<Operation> Referring to the data stored in the first memory by the discriminating means, when the element of the referred matrix is zero, the next element is continuously referred without performing any calculation. Then, when the referenced element is not zero, the data stored in the second memory by the computing means is multiplied by the element corresponding to this data of the input vector.
This sum of products is calculated for one row or column to be one element of the output vector. Then, this calculation is performed for each row or each column to obtain all the elements of the output vector.

When the matrix calculation process is performed in this way, for example, when the non-zero element occupies k% of all elements (N × M real numbers) of the matrix, the first element for storing the element of the matrix is stored. The memory capacity of memory 2 is N × M × k / 10 in real numbers.
It will be 0. Further, the number of times multiplication and addition are performed per matrix operation processing is N × M × k / 100. Therefore, when the ratio of non-zero elements is small (k is small), the storage amount of elements of the matrix and the calculation amount of the arithmetic processing are reduced.

Moreover, the first memory stores an integer representing the number of consecutive zero elements in the matrix and an integer representing the number of consecutive non-zero elements in each matrix. Since the contents are stored in the order of arrangement, the addressing is easily performed when reading the contents of the second memory. That is, when the first memory is sequentially scanned by, for example, a pointer, and an integer representing the number of non-zero elements arranged is detected, the contents of the non-zero elements stored in the second memory are sequentially represented by this integer. Just read the data. In this manner, the addressing of the second memory is easily performed by advancing the content detection of the first memory and the content reading of the second memory in parallel. As a result, the control of this matrix operation device is easily performed.

<Embodiment> Hereinafter, the matrix calculation device of the present invention will be described in detail with reference to an embodiment.

FIG. 1 shows a first matrix operation device which is the basis of the present invention. This matrix operation device includes a CPU (central processing unit) 1, a ROM 2 for storing a predetermined calculation algorithm,
A first memory 11 and a second memory 12 that store information about a transformation matrix W, and an input vector x = (x ₁ , ..., Xj,
, X _M ) ^t or u = (u ₁ , ..., uj, ... u _N ) ^t , and the output vector y = (y ₁ , ..., yj, ...
An output device 22 for outputting information of y _N ) ^t or v = (v ₁ , ..., Vj, ..., V _M ) ^t is provided.

The CPU 1 receives data representing each element of the input vector x from the input device 21, refers to the first memory 11 and the second memory 12, and according to the calculation algorithm stored in the ROM 2, the input vector x Alternatively, the linear transformation of u can be calculated and the data representing the output vector y or v can be output to the output device 22. As shown in FIG. 7, the input device 21 uses the elements xi of the input vector x.
Represents an input buffer 302 capable of holding data representing the data, a pointer (instruction value xp) 306 pointing to each data XTxp (xp = 1, 2, ..., M) of the input buffer 302, and each element uj of the input vector u. An input buffer 304 that can hold data and each data UTup (up = 1, 2, ...) Of this input buffer 304
N) indicating a pointer (instruction value up) 308. The output device 22 includes an output buffer 303 which can also hold data representing each element tj of the output vector y and also serves as a product-sum operation buffer, and each data YTyp of this output buffer 303.
A pointer (instruction value yp) 307 that points to (yp = 1, 2, ..., N),
An output buffer 305 which also serves as a product-sum operation buffer capable of holding data representing each element vi of the output vector v, and a pointer (instruction value vp) pointing to each data VTvp (vp = 1, 2, ... M) of this output buffer 305 It consists of 309. In addition, 301 in FIG. 7 represents each element Wji of the conversion matrix W by a two-dimensional array as an example in order to explain the function of this matrix operation device. In the figure, "0" represents a zero element with Wji = 0, and "W" represents a non-zero element with Wji ≠ 0. Further, pi represents the number of zero elements arranged in the row direction, and qi represents the number of non-zero elements arranged in the row direction. As shown in FIG. 2, the first memory 11 stores an index table 401 that stores an integer that represents the number of zero elements of the conversion matrix W that are consecutively arranged, and each data ITip of the index table 401. Pointer (instruction value ip) that points to (ip = 1,2, ...) 40
It consists of 3. On the other hand, as shown in FIG. 3, the second memory 12 stores a coefficient memory 402 in which data representing the contents of non-zero elements of the conversion matrix W are stored in order, and each data WTWp of the coefficient memory 402. (Wp = 1,2, ...) Pointer (instruction value wp) 404.

The index table 401 and the coefficient memory 402 are created as follows. The transformation matrix W3 shown in FIG.
Each row of 01 is sequentially examined from left to right from the first row, and data representing the content (real number) of the non-zero element is stored in the coefficient memory 402 while zeros arranged on the left side of the non-zero element. An integer (pi + 1) obtained by adding 1 to the number of elements pi is represented by n-bit data and stored in the index table 401 (hereinafter, simply referred to as "registering an integer"). If the element on the left of the non-zero element is a non-zero element, pi = 0
Therefore, the integer to be registered is 1. When qi non-zero elements are lined up, (qi-1) integers 1 are continuously registered in the index table 401. When the end of each line is reached, the end-of-line symbol delim (delim = 2 ⁿ -1) is registered. If the end of line is a zero element, the number of the array of zero elements including the zero element at the end of the line (1 if the zero elements are not aligned and the next element on the left is a nonzero element) is not registered, but the end-of-line symbol delim
To register. By the way, when an integer is represented by n-bit data (1 word) in this way, the integer that can be represented is up to (2 ⁿ −1), and the integer (2 ⁿ −1) is as described above. Since it is used for the line delimiter delim,
After all, the integer that can be expressed by one word is up to (2 ⁿ -2). Therefore, when (2 ⁿ −2) or more zero elements are arranged, the number is expressed by using two words or more and registered as follows. For example, if the number of zero elements arranged is pi, then pi + 1 = (2 ⁿ −2) a + b a, b can be expressed as an integer 0 ≦ a 0 ≦ b <(2 ⁿ −2), then (a + 1) Express using words. That is, the data of a words is (2 ⁿ −2), and the data of the last one word is b.

As described above, this matrix operation device uses the number pi in which the zero elements of the conversion matrix W are lined up and the line end symbol delim as an index to perform the following operation processing.

When the equation (1) is calculated as the linear transformation of the input vector x, it is calculated according to the calculation algorithm shown in FIG.

First, as shown in step S ₁ , each pointer 403, 404, 30
Set the indicated values of 6,307 to ip, wp, yp = 1 and xp = 0 respectively,
The data YTyp (yp = 1, ..., M) of the output buffer 303 is set to 0 (initialization). Next, the data ITip the index table 401 is judged whether it is a line terminator delim (= 2 ⁿ -1) and (S _2), and line feed if the end of the line (S ₃₎ to. If it is not the end of the line, move it in the direction of the line by ITip (S ₅ ), and then ITip
Is determined to be the maximum number (2 ⁿ −2) (S ₆ ).
If it is the maximum number, the next data of the index table 401 is examined (S ₇ ). If not the maximum number, the product WTwp × XT
xp is added to YTyp (S ₈ ), the instruction value wp is advanced by 1 so that the next data in the coefficient memory 404 can be output, and the next data in the index table 401 is examined (S ₉ ). Then, returning to step S ₂ , ITip again delimits the line terminator.
If it is the end of the line, a line feed (S ₃ ) is performed, and when the search up to the Nth line is completed, this operation is ended.

When the linear transformation equation (2) of the input vector u ^t is calculated, it is calculated according to the calculation algorithm shown in FIG. 9 by the same procedure as the above calculation.

By performing the arithmetic processing in this manner, for example, when the ratio of non-zero elements among all the elements (N × M real numbers) of the conversion matrix W of N rows and M columns is k%, the elements of this matrix W are The storage amount of the coefficient memory 402 for storing is a real number of N × M × k / 100, while the storage amount of the index table 401 is an integer of about N × M × k.
/ It will be 100 pieces. Therefore, it is possible to reduce the storage amount of the elements of the conversion matrix W when the ratio of non-zero elements is small (when k is small). In addition, the matrix calculation process 1
The number of times of multiplication and addition is N × M × k /
The number of calculations is 100, and the calculation amount can be reduced when k is small.

Next, a second matrix operation device which is the basis of the present invention will be described.

This matrix operation device has an index table 411 shown in FIG. 4 in place of the index table 401 of the first matrix operation device. Other configurations are the same as those of the first matrix operation device. The index table 411 is created as follows. Similar to the index table 401, an integer (pi + 1) obtained by adding 1 to the number pi of the array of zero elements
To register. However, if the zero element continues from the end of the line to the beginning of the next line without using the end-of-line symbol delim, the number of arrangements of zero elements at the end of the line and the number of arrangements of zero elements at the beginning of the next line is added to 1
Add and register. For example, the transformation matrix W301 shown in FIG.
For the end of the first line and the beginning of the second line of, the integer (p ₂ + p ₃ +
Register 1).

When calculating the linear transformation equations (1) and (2) of the input vector x and the input vector u ^t , respectively, as shown in FIG. 10 and FIG.
Follow the calculation algorithm shown in Fig. 11. For the sake of simplicity, the same symbols are used for each data and instruction value as in the first matrix operation device (the same applies to the third and fourth matrix operation devices described later). Although the procedure is almost the same as that of the first matrix operation device, in the case of the calculation of the equation (1), xp and M are compared to detect the end of the line, and if xp> M, it is determined that the line has changed. (S ₂₅ ) and then advance yp by int (xp / M) (S ₂₆ ). In the case of calculation of formula (2), vp
Do this using. Note that int (*) indicates the integer part of the value of the expression in parentheses.

Next, a third matrix operation device embodying the present invention will be described.

This matrix operation device has an index table 421 shown in FIG. 5 in place of the index table 401 of the first matrix operation device. Other configurations are the same as those of the first matrix operation device. The index table 421 registers the number qi of non-zero element sequences in addition to the number pi of zero element sequences. That is, when the non-zero elements are lined up, unlike the first matrix operation device and the second matrix operation device, (qi−1) integers 1 are not individually registered, but integers are regarded as one data. Register qi. Then, the most significant bit of n bits per word is used to distinguish whether it is the number pi of arrangements of zero elements or the number qi of arrangements of non-zero elements. When zero elements or non-zero elements continue from the end of the line to the beginning of the next line, an integer (pi + pi ₊₁ ), which is the number of those sequences,
Register (qi + qi _{+ 1} ). In this case, the data amount of the index table can be reduced as compared with the first matrix operation device and the second matrix operation device.

When equations (1) and (2) are calculated as the linear transformation of the input vector x and the input vector u ^t , they are shown in FIG. 12 and FIG.
Calculation processing is performed according to the calculation algorithm shown in FIG. Although the procedure is substantially the same for the first matrix operation device and the second matrix operation device, it is determined whether ITip indicates a zero element or a non-zero element (S ₅₃ , S ₇₄ ), and zero is determined. When elements are shown, the difference is that xp or vp is skipped by that number (S ₅₄ , S ₇₅ ). When non-zero elements are shown, the sum of products of the input XTxp and the coefficient WTwp is calculated by that number (S _{57 to} S ₆₁ , S _{78 to} S ₈₂ ). However, the second
Similar to the matrix operation device of (1), it is determined whether the line end is reached in the middle by comparing the value of xp or vp with the value of M (S ₆₀ , S ₈₀ ).

In this way, when the contents of the index table 421 are detected,
By advancing the reading of the contents of the second memory 12 in parallel, the addressing of the second memory can be easily performed. As a result, the matrix operation device can be easily controlled.

Next, a fourth matrix operation device embodying the present invention will be described.

This matrix operation device has an index table 431 shown in FIG. 6 in place of the index table of the first matrix operation device. Other configurations are the same as those of the first matrix operation device. The index table 431 registers the number qi of non-zero element sequences separately from the number pi of zero element sequences, as in the third matrix operation device. However, at the end of the line, the maximum value of either the number of zero elements or the sequence of non-zero elements is registered as the line end symbol delim. When the line end ends with a zero element or a sequence of zero elements, 1 or the number of sequences is not registered, and the line end symbol delim is registered. In this case, the data amount of the index table can be reduced as compared with the first matrix operation device and the second matrix operation device.

When calculating the linear transformation equations (1) and (2) of the input vector x and the input vector u ^t , respectively, as shown in FIG. 14 and FIG.
Calculation processing is performed according to the calculation algorithm shown in FIG. The third matrix operation device differs from the third matrix operation device only in that the end of line symbol delim is used to determine (S ₉₃ , S ₁₀₄ ).

In this way, detecting the contents of the index table 431,
By advancing the reading of the contents of the second memory 12 in parallel, the addressing of the second memory can be easily performed. As a result, the matrix operation device can be easily controlled.

In addition, in each of the first to fourth matrix calculation devices, each row of the conversion matrix W is scanned from left to right, but of course, the rows may be scanned in the column direction.

<Effects of the Invention> As is clear from the above, the matrix operation device of the present invention is
A first memory that stores data that specifies whether each element of a matrix represented by a two-dimensional array is a zero element or a nonzero element; and a second memory that stores data that represents the contents of the nonzero elements of the matrix. , With reference to the data stored in the first memory, the discriminating means for discriminating whether or not the element of the matrix is zero, and the element of the matrix discriminated by the discriminating means to be non-zero, Since the arithmetic means for multiplying the data stored in the second memory and the elements of the input vector to obtain the sum of products is provided, when performing the arithmetic processing of a large-scale sparse matrix, non-zero elements in the conversion matrix are included. When the ratio occupied by k is k%, the memory storage amount and calculation amount can be reduced to k%.

Moreover, the first memory stores an integer representing the number of consecutive zero elements in the matrix and an integer representing the number of consecutive non-zero elements in each matrix. Since the contents are stored in the order of arrangement, the address can be easily specified when reading the contents of the second memory. That is, when the first memory is sequentially scanned by, for example, a pointer, and an integer representing the number of non-zero elements arranged is detected, the contents of the non-zero elements stored in the second memory are sequentially represented by this integer. Read the data. In this way, by performing the content detection of the first memory and the content reading of the second memory in parallel, the second memory can be easily
The memory can be addressed. As a result, the matrix operation device can be easily controlled.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of a matrix operation device of the present invention, FIGS. 2, 4, 5, and 6 are views showing an index table of the matrix operation device, and FIG. FIG. 7 is a diagram showing a coefficient memory of the arithmetic unit, FIG. 7 is a diagram showing input / output buffers, pointers and elements of the transformation matrix W of the matrix arithmetic unit, and FIGS. 8 to 15 are calculation algorithms of the matrix arithmetic unit. Flow chart, Figure 16 and Figure
FIG. 17 is a diagram schematically showing calculation by a conventional matrix calculation device. 1 ... CPU, 2 ... ROM, 11 ... first memory, 12 ... second memory, 21 ... input device, 22 ... output device, 301 ...
… Conversion matrix W, 302,308 …… Input buffer, 303,305 ……
Output buffer, 401,411,421,431 ... Index table, 402 ... Coefficient memory, 306,307,308,309,403,404 ...
… A pointer.

Claims (1)

[Claims] 1. A first memory for storing data specifying whether each element of a matrix represented by a two-dimensional array is zero or nonzero, and data representing the contents of the nonzero elements of the matrix. A second memory to store the data, and a determination unit that determines whether the element of the matrix is zero with reference to the data stored in the first memory, and the determination unit determines that the matrix is not zero. In the matrix operation device having an operation means for multiplying the data stored in the second memory and the element of the input vector with respect to the elements of the matrix to obtain the sum of products, the first memory is the matrix In which an integer representing the number of consecutive zero elements and an integer representing the number of non-zero consecutive elements are stored in the order of each consecutive row in the matrix. Matrix computing device.