Matrix multiplication in a vector processing system

• US 7,337,205 B2
• Filed: 04/25/2005
• Issued: 02/26/2008
• Est. Priority Date: 03/21/2001
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Sazegari, Ali
• Primary Examiner(s): MALZAHN, DAVID H
• Application Number:
  US11/113,035
• Publication Number:
  US 20050193050A1
• Time in Patent Office: 1,037 Days
• Field of Search: 708/607
• US Class Current: 708/607
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/30109 having multiple operands in a single register

Abstract

To perform multiplication of matrices in a vector processing system, partial products are obtained by dot multiplication of vector registers containing multiple copies of elements of a first matrix and vector registers containing values from rows of a second matrix. The dot products obtained from this dot multiplication are subsequently added to vector registers which form a product matrix. Each matrix can be divided into submatrices to facilitate the rapid and efficient multiplication of large matrices, which is done in parts by computing partial products of each submatrix. The matrix multiplication avoids rounding errors as it is bit-by-bit compatible with conventional matrix multiplication methods.

Claims

1. A method for performing a conversion on a media signal, comprising the steps of:

multiplying a first, m×

n matrix with a second, n×

m matrix in a vector processing computer system, wherein at least one of said first and second matrices contains values representative of said media signal, by;

(a) replicating m copies of a value in a given row and column of said first matrix and storing said copies in a vector register;

(b) dot multiplying the values in said vector register with the values in a row of said second matrix that corresponds to said given column of said first matrix;

(c) adding the values obtained by step (b) to the contents of a result register; and

(d) repeating steps (a)-(c) for each column of said first matrix to generate and store the values for a corresponding row of a product matrix in said result register wherein said product matrix comprises values representative of the converted media signal.

2. The method of claim 1, further including the step of repeating steps (a)-(d) for each row of said first matrix to generate and store the values for respective rows of said product matrix in corresponding result registers.

3. A vector processing computer system, comprising:

a first group of vector registers that respectively store multiple copies of individual values in a given row of a first matrix to be multiplied;

a second group of vector registers that contain values of a second matrix to be multiplied; and

a vector processor that dot multiplies the values in said first group of vector registers with the values of said second group of vector registers and adds the resulting product values to a third group of vector registers corresponding to a product matrix.

4. The system of claim 3, wherein said process or performs the multiplication in a manner such that vector registers in said first group containing multiple copies of each value from a single row of said first matrix are multiplied with vector registers from said second group that are associated with a row of said second matrix that corresponds to a column of said first matrix from which said multiple copies are obtained.

5. The system of claim 4, wherein said processor adds the values obtained by dot multiplying vector registers from the first group of vector registers having values from a single row of said first matrix to vector registers of said third group that correspond to the same row of the product matrix as the row from which the values were taken from said first matrix.

6. A computer-readable medium containing a program performing a conversion on a media signal, the program causing a computer to execute the steps of:

multiplying a first, m×

n matrix with a second, n×

m matrix in a vector processing computer system, wherein at least one of said first and second matrices contains values representative of said media signal, by;

(a) replicating the value of each element of a first matrix to form corresponding vectors each having a number of elements corresponding to the number of columns in a second matrix, and storing said vectors in a first set of registers;

(b) storing the value of the elements of each row of said second matrix as corresponding vectors in a second set of registers;

(c) multiplying a vector in one of said first set of registers with a vector in one of said second set of registers such that the vector in one of the first set of registers multiplied with a vector in one of the second set of registers is selected from a single row within the first matrix, and adding the resulting products as a vector in one of a set of third registers corresponding to the rows of a product matrix equivalent to the row from which the element stored in the vector of the first set of registers is taken; and

(d) iteratively repeating step (c) for each vector in said first set of registers, wherein values in said set of third registers represent the converted media signal.

7. The computer-readable medium of claim 6, wherein step (c) comprises multiplying a vector whose values are elements contained in a given column of the first matrix with a vector containing values of elements contained in the corresponding row of the second matrix.

8. A computer-readable medium containing a program for performing a conversion on a media signal, said program causing a processing system to execute the steps of:

calculating the product of a first matrix and a second matrix in a vector processing system, wherein said first matrix is stored in a plurality of first vector registers, said second matrix is stored in a plurality of second vector registers, and wherein at least one of said first and second matrices contains values representative of said media signal, by;

(1) selecting a vector register corresponding to a row of said first matrix;

(2) storing multiple copies of a value from the register selected in step (1) in a vector register, wherein the value from the vector register selected in step (1) has a specific index within the vector register selected in step (1);

(3) calculating the dot product of the vector register containing multiple copies of a single value that was stored in step (2) and the vector register containing elements from the row number of the second matrix which corresponds to the index of the element stored within the vector register in step (2);

(4) adding the dot product calculated in step (3) to one of a third group of vector registers that form a product matrix whose values represent the converted media signal, by adding the dot product value in the register corresponding to the row of the product matrix that is equivalent to the row of the first matrix that corresponds to the vector register selected in step (1); and

(5) repeating steps (2) through (4) for each of the elements contained within the register selected in step (1)

(B) processing the at least one audio and/or video signal using a value stored.

9. The computer-readable medium of claim 8 wherein said program causes the vector processing system to execute the further step of repeating steps (1) through (5) for each of the registers corresponding to each row of the first matrix.

10. The computer-readable medium of claim 9, wherein said step of storing multiple copies of a value from the register selected in step (1) further comprises storing the multiple copies in a vector register having the same number of elements as the number of elements of each row of said second matrix.

11. The computer-readable medium of claim 9, wherein said third group of vector registers corresponding to said product matrix is initialized by storing initial values of each element within the third group of vector registers.

12. The computer-readable medium of claim 11, wherein said initialization occurs by storing the value zero in each location of each vector of said third group of vector registers.

13. A computer-readable medium containing a program for processing at least one of an audio and/or video performing conversion of a media signal, said program executing the steps of:

(1) calculating the product of a first matrix and a second matrix in a vector processing system, wherein at least one of said first and second matrices contains values representative of said media signal, by;

(a) dividing each of said first and second matrices into a plurality of submatrices;

(b) assigning values of each submatrix associated with said first and second matrices to respective pluralities of first and second vector registers, in a manner such that each of said first plurality of vector registers corresponds to an individual row of a submatrix of said first matrix, and each of said second plurality of vector registers corresponds to an individual row of a submatrix of said second matrix;

(c) selecting a vector register corresponding to a row of a submatrix of said first matrix;

(d) storing multiple copies of a value from the register selected in step (c) in a vector register, wherein the value from the vector register selected in step (c) has a specific index within the selected vector register;

(e) calculating the dot product of the vector register containing multiple copies of a single value that was stored in step (d) and the vector register containing elements from the row number of each submatrix of the second matrix which corresponds to the index of the element stored within the vector register in step (d);

(f) adding the dot product calculated in step (e) to one of a third group of vector registers that form a product matrix, wherein said product matrix contains values representative of the converted media signal by adding the dot product value in the register corresponding to the row of the submatrix within the product matrix that is equivalent to the row of the first matrix that corresponds to the vector register selected in step (c);

(g) repeating steps (d)-(f) for each of the elements contained within the register selected in step (c); and

(h) repeating steps (c)-(g) for each of the registers corresponding to each row of each submatrix of the first matrix

(2) processing the at least one audio and/or video signal using the value.

14. The computer-readable medium of claim 13 wherein said step of storing multiple copies of the value from the register selected in step (c) in a vector register further comprises storing the multiple copies in a vector register having the same number of elements as the number of elements of each row of each submatrix of the second matrix with which it is multiplied.

15. The computer-readable medium of claim 13 wherein said third group of vector registers corresponding to a product matrix is initialized by storing initial values of each element within the third group of vector registers.

16. The computer-readable medium of claim 13 wherein said steps of calculating and adding are performed simultaneously via an integrated vector processing function.