CN102411558B - Vector processor oriented large matrix multiplied vectorization realizing method - Google Patents

Abstract

The invention discloses a vectorized realization method of large matrix multiplication oriented to a vector processor, comprising the following steps: (1) inputting a multiplicand matrix A and a multiplier matrix B; and the multiplier matrix B are transported to the vector storage unit respectively; when transporting, the 1st to nth rows in the multiplier matrix B are sequentially sorted into the 1st to nth columns; (2) the multiplier matrix A and the multiplier The elements in a column of the number matrix B are respectively loaded into K parallel processing units, and multiplied one by one; the result of multiplication is reduced and summed in a designated parallel processing unit; the summation result is used as a result matrix element Stored in the vector storage unit; (3) move forward to the next row of the multiplicand matrix A and the next column of the multiplier matrix B, repeat step (2) until the calculation of all data frames is completed, and the result matrix element is obtained. The resulting matrix C. The invention has simple principle and convenient operation, and can improve calculation efficiency.

Description

A Vectorization Implementation Method of Large Matrix Multiplication Oriented to Vector Processor

technical field

The invention mainly relates to the fields of vector processors and data processing, in particular to a vectorized realization method of multiplication of large matrices.

Background technique

Matrix multiplication operations are involved in many scientific computing tasks and applications, such as image processing, signal encoding and decoding in communication systems, etc. For large-scale matrix multiplication calculation tasks, due to the large number of multiplication and addition operations involved, it is necessary to Takes a lot of computing time. How to implement matrix multiplication operations on processors simply and efficiently has always been a research hotspot in the industry.

On traditional scalar processors, researchers have proposed a variety of effective matrix multiplication implementation methods to reduce the impact of data sorting operations on the completion of the entire matrix multiplication operation. However, with the continuous emergence of high-intensity and real-time computing applications such as high-definition video codecs, 3G wireless communications, and radar signal processing, it is difficult for a single chip to meet the high-density real-time computing needs of such applications, and vector processors have been widely used. As shown in Fig. 1, it is a typical structure of a vector processor, which has a processor, program memory and data memory (both of which can be any accessible memory, including external cache memory, external RAM, etc.). The processor of the vector processor is divided into two parts: the scalar processing part and the vector processing part. Usually, there are K parallel processing units (PE) in the vector processing part. These processing units have their own computing parts and registers. Data interaction through specification instructions, such as data addition and comparison between parallel processing units. The scalar processing unit is mainly responsible for the processing of flow control and logic judgment instructions, while the vector processing unit is mainly responsible for intensive data calculation. The data used for the operation of the vector processing unit is provided by the vector data storage unit. Generally, as shown in FIG. 2 , the number of BANKs (memory banks) of the vector data storage unit is consistent with the number K of processing units of the vector processing unit.

The patent document with the application number "200380107095.7" discloses a patent proposed by Intel Corporation using SIMD registers for efficient multiplication of small matrices, loading the diagonals of the multiplicand matrix A into different registers of the processor, and loading the multipliers The matrix B is loaded into at least one register arranged vertically in sequence. By shifting one element, the multiplication and addition elements in each column of the multiplier matrix B in the register are selectively moved to the front of the column together with the previous element in the shifted column. The diagonals of the multiplicand matrix A are multiplied by the columns of the multiplier matrix B, and their results are added to the resulting sum of the columns of the result matrix C. This method can achieve better results when the size of the matrix is small, but it is difficult to achieve good performance as the size of the matrix gradually increases. Therefore, how to realize efficient large-matrix multiplication operation on vector processors is currently a difficult problem.

Contents of the invention

The technical problem to be solved by the present invention is: aiming at the problems existing in the prior art, the present invention provides a vector processor-oriented large-scale A vectorized implementation of matrix multiplication.

In order to solve the problems of the technologies described above, the present invention adopts the following technical solutions:

A vectorized implementation method for multiplication of large matrices oriented to vector processors, comprising the following steps:

(1) Input the multiplicand matrix A and the multiplier matrix B; the multiplicand matrix A and the multiplier matrix B are transported to the vector storage unit respectively by the DMA controller; during the transport process, the multiplier matrix B is re- Sorting, that is, sorting the 1st to nth rows in the multiplier matrix B into the 1st to nth columns;

(2) Load the elements in one row of the multiplicand matrix A and the elements in one column of the multiplier matrix B into K parallel processing units respectively, and multiply them one by one; Reduction and summation in the processing unit; storing the summation result as a result matrix element in the vector storage unit;

(3) Move forward to the next row of the multiplicand matrix A and the next column of the multiplier matrix B, repeat step (2) until the calculation of all data frames is completed, and a result matrix C composed of result matrix elements is obtained.

As a further improvement of the present invention:

In the handling process, each row of the multiplier matrix A is organized into a data frame, and each column of the multiplier matrix B is organized into a data frame. When the number of elements of the data frame is not equal to the parallel processing in the vector processor When the number of units is a multiple of K, add 0 at the end of the data frame so that the number of elements in each data frame is equal to the multiple of the number K of parallel processing units.

Compared with the prior art, the present invention has the advantages of:

The vectorized implementation method of the vector processor-oriented large matrix multiplication of the present invention realizes the data reordering of the multiplier matrix B in the process of data transfer by the DMA controller, and also makes full use of the multiplicity of vector components in the vector processor. A large number of operations of the same type can be performed by a parallel processing unit that can perform the same operation at the same time, thereby greatly improving the efficiency of computing matrix multiplication, and the steps are simple and easy to implement.

Description of drawings

Figure 1 is a schematic diagram of a typical vector processor structure.

FIG. 2 is a schematic structural diagram of a vector data storage unit in the vector processor of FIG. 1 .

Fig. 3 is a schematic diagram of the overall flow of the present invention.

FIG. 4 is a schematic diagram of implementing reordering of B elements of the multiplier matrix by using a DMA controller in Embodiment 1 of the present invention.

Fig. 5 is a schematic diagram of the storage form of elements of the multiplicand matrix A and the multiplier matrix B in the vector data storage unit shown in Fig. 2 in embodiment 2 of the present invention; Fig. 5 (1) is in embodiment 2 of the present invention The storage form schematic diagram of the element of multiplicand matrix A in the vector data storage unit shown in Fig. 2; Fig. 5 (2) is the vector shown in Fig. 2 for the element of multiplier matrix B in the embodiment of the present invention 2 Schematic diagram of the storage form in the data storage unit.

FIG. 6 is a schematic diagram of loading multiplicand matrix A (16×16) and multiplier matrix B (16×16) into K parallel processing units according to Embodiment 2 of the present invention.

Fig. 7 is a schematic diagram of implementation steps of matrix multiplication of multiplicand matrix A (16×16) and multiplier matrix B (16×16) in Embodiment 2 of the present invention.

Fig. 8 is a schematic diagram of the storage form of elements of the multiplicand matrix A and the multiplier matrix B in the vector data storage unit shown in Fig. 2 in Embodiment 3 of the present invention; Fig. 8 (1) is in Embodiment 3 of the present invention The storage form schematic diagram of the element of the multiplicand matrix A in the vector data storage unit shown in Fig. 2; Fig. 8 (2) is the vector shown in Fig. 2 for the element of the multiplier matrix B in the embodiment of the present invention 3 Schematic diagram of the storage form in the data storage unit.

FIG. 9 is a schematic diagram of loading multiplicand matrix A (26×22) and multiplier matrix B (22×27) into K parallel processing units according to Embodiment 3 of the present invention.

Fig. 10 is a schematic diagram of implementation steps of matrix multiplication of multiplicand matrix A (26×22) and multiplier matrix B (22×27) in Embodiment 3 of the present invention.

Detailed ways

The present invention will be described in further detail below in conjunction with the accompanying drawings and specific embodiments.

Example 1:

As shown in Fig. 3, the vectorized implementation method of multiplication of large matrices oriented to vector processors of the present invention comprises the following steps:

1. Input the multiplicand matrix A and the multiplier matrix B; the multiplicand matrix A and the multiplier matrix B are respectively transported to the vector storage unit through the DMA controller. During the transport process, as shown in Figure 4, the multiplier The matrix B is reordered, that is, the 1st to nth rows in the multiplier matrix B are sequentially sorted into the 1st to nth columns.

Through the configuration of the DMA controller, each row of the multiplicand matrix A can be organized into a data frame, each column of the multiplier matrix B can be organized into a data frame, and the entire multiplier matrix B can be divided into p data frames. When the number of elements in the data frame is not equal to the multiple of the number K of parallel processing units in the vector processor, add 0 at the end of the data frame so that the number of elements in each data frame is equal to the multiple of the number K of parallel processing units.

2. Load the elements in a row of data frames of the multiplicand matrix A and a column of data frames of the multiplier matrix B into K parallel processing units, and multiply them one by one; the result of the multiplication is in a specified parallel processing unit Reduction and summation in the processing unit; the summation result is stored as a result matrix element in the vector storage unit.

3. Move forward to the next row of the multiplicand matrix A and the next column of the multiplier matrix B, repeat steps 2 to 3 until the calculation of all data frames is completed, and a result matrix C composed of result matrix elements is obtained.

For the operation of multiplying the multiplicand matrix A of m*n by the multiplier matrix B of n*p, the matrix C of m*p can be obtained. It can be expressed in mathematical formula as: (0≤i<m, 0≤j<p). The element C _ij of the result matrix C is calculated by the dot product operation of the corresponding row element A _ik of the multiplicand matrix A and the corresponding column element B _kj of the multiplier matrix B.

Example 2:

As shown in Fig. 7, adopt the vectorization realization method of the multiplication of large matrix facing vector processor of the present invention, the calculation scale is that the matrix of 16 * 16 is multiplied by the matrix of 16 * 16 in scale (the number of vector processing units K is 8), including the following steps:

1. As shown in Figure 6, input the multiplicand matrix A (16×16) and the multiplier matrix B (16×16); transfer the multiplicand matrix A and the multiplier matrix B to the vector storage unit through DMA, this process Realize the reordering of multiplier matrix B in (the reordering method is the same as embodiment 1), the storage mode of multiplicand matrix A and multiplier matrix B in vector unit is as shown in Figure 5 (1) and Figure 5 (2) .

2. Load the elements of one row of the multiplicand matrix A and the elements of one column of the multiplier matrix B into the vector processing unit. Since the scales of the multiplicand matrix A and the multiplier matrix B are both 16×16, they need to be divided into two times will be loaded by multiplier matrix A and multiplier matrix B. The corresponding elements loaded into the vector processing unit are multiplied. Since the number of vector processing units is 8, and the numbers of multiplicand elements and multiplier elements are 16 respectively, the multiplication operation in this step should be performed twice.

3. Use the reduction instruction to add the results calculated by each vector processing unit in step 2, and reduce the result to the designated processing unit X. The same operation of this step should also be performed twice.

4. Add the above two results obtained in the X unit to obtain a result matrix element and store it in the vector storage unit.

5. Move forward to the next row of the multiplicand matrix A and the next column of the multiplier matrix B, and repeat steps 2 to 4 in the above process to obtain the entire result matrix C=A×B.

Example 3:

As shown in Fig. 10, the vectorized implementation method of multiplication of large matrices oriented to vector processors of the present invention, the calculation scale is 26 × 22 matrix multiplied by 22 × 27 matrices (the number of vector processing units K is 8 ), including the following steps:

1. As shown in FIG. 9, the multiplicand matrix A and the multiplier matrix B are transferred to the vector storage unit by DMA, and the reordering of the multiplier matrix B is realized in this process (the reordering method is the same as in embodiment 1), and the The multiplicand matrix A and the multiplier matrix B are complemented with 0, and the storage methods of the multiplicand matrix A and the multiplier matrix B in the vector unit are shown in Figure 8(1) and Figure 8(2).

2. Load the elements of one row of the multiplicand matrix A and the elements of one column of the multiplier matrix B into the vector processing unit. Here, the rows of the multiplier matrix A and the columns of the multiplier matrix B have been filled with 0, so To be divided into 3 times will be loaded by multiplier matrix A and multiplier matrix B. The corresponding elements loaded into the vector processing unit are multiplied. Since the number of vector processing units is 8, and the number of multiplicand elements and multiplier elements is 24 after complementing 0, the multiplication operation in this step should be 3 Second-rate.

3. Use the reduction instruction to add the results calculated by each vector processing unit in step 2, and reduce the result to the designated processing unit X. The same operation of this step should also be performed 3 times.

4. Add the above three results obtained in the X unit to obtain a result matrix element and store it in the vector storage unit.

5. Move forward to the next row of the multiplicand matrix A and the next column of the multiplier matrix B, and repeat steps 2 to 4 in the above process to obtain the entire result matrix C=A×B.

According to the specific structure and instruction set of the vector processor, a simple and efficient code can be written according to the above steps to realize the multiplication of large matrices. The method of the present invention is simple and easy to understand for programmers, and is beneficial for programmers to code and realize.

The above descriptions are only preferred implementations of the present invention, and the protection scope of the present invention is not limited to the above-mentioned embodiments, and all technical solutions under the idea of the present invention belong to the protection scope of the present invention. It should be pointed out that for those skilled in the art, some improvements and modifications without departing from the principle of the present invention should be regarded as the protection scope of the present invention.

Claims (1)

1. A vectorized implementation method for multiplication of large matrices for vector processors, characterized in that it comprises the following steps: (1) Input the multiplicand matrix A and the multiplier matrix B; transfer the multiplicand matrix A and the multiplier matrix B to the vector storage unit through the DMA controller; Sorting, that is, sorting the 1st to nth columns in the multiplier matrix B into the 1st to nth rows; In the handling process, each row of the multiplier matrix A is organized into a data frame, and each column of the multiplier matrix B is organized into a data frame. When the number of elements of the data frame is not equal to the parallel processing in the vector processor When the number of units is a multiple of K, add 0 at the end of the data frame so that the number of elements in each data frame is equal to the multiple of the number K of parallel processing units; (2) Load the elements in one row of the multiplicand matrix A and the elements in one row of the multiplier matrix B into K parallel processing units, and multiply them one by one; Reduction and summation in the processing unit; storing the summation result as a result matrix element in the vector storage unit; (3) Move forward to the next row of the multiplier matrix B, repeat steps (2) and (3) until the calculation of one row of the multiplicand matrix A and all the rows of the multiplier matrix B is completed, and a row of elements of the result matrix C is calculated ; (4) Move forward to the next row of the multiplicand matrix A, and repeat steps (2) (3) (4) until the calculation of all rows of the multiplicand matrix A is completed, and all row elements of the result matrix C are obtained.