Method for Performing Arithmetic Operations Using a Multi-Core Processor

• US 20080183792A1
• Filed: 11/27/2007
• Published: 07/31/2008
• Est. Priority Date: 01/25/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Inoue, Hiroshi
• Granted Patent: US 8,200,735 B2
• Time in Patent Office: Days
• US Class Current: 708/520
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78

Abstract

A data processing system for performing a matrix calculation is disclosed. The data processing system includes a multi-core processor with multiple processing elements each having a processor and a local memory. The data processing system includes a system memory, a first and second readout units, a first and second arithmetic unit, and an output unit.

Claims

1. A data processing system includes a multi-core processor with a plurality of processing elements each having a processor and a local memory, said data processing system comprising:

a system memory for storing a value matrix in which non-zero elements of an input matrix are arranged, and a position matrix including elements each indicating positions of said non-zero elements of said input matrix;

a first processing element having a first local memory for storing a first sub-vector that is a part of said input vector;

a second processing element having a second local memory for storing a second sub-vector that is another part of said input vector;

a first readout unit configured to read out matrix elements sequentially one by one from said value matrix and from said position matrix stored in said system memory, and to store said read out matrix elements in said first local memory as newly-read matrix elements;

a first arithmetic unit in said first processing element configured to multiply two matrix elements every time a matrix element is read out by said first readout unit, wherein one of said two matrix elements corresponds to the position of a non-zero element indicated by each of said matrix elements read out from said position matrix in said first sub-vector, and the other of said two matrix elements being a non-zero element read out from said value matrix in said first sub-vector;

a second readout unit configured to read out a matrix element of said value matrix and said position matrix from said first local memory, and to store said matrix element in a second local memory as a newly-read matrix element every time an arithmetic operation is performed by said first arithmetic unit;

a second arithmetic unit in said second processing element configured to multiply two matrix elements every time a matrix element is read by said second readout unit, wherein one of said two matrix elements corresponds to a position of a non-zero element indicated by each of said matrix elements read from said position matrix in said second sub-vector, and the other of said two elements being a non-zero element read from said value matrix in said second sub-vector; and

an output unit in said second processing unit configured to generate each matrix element of a vector to indicate a product of said input matrix and said input vector based on results of said arithmetic operations performed by said first and second arithmetic units, and to store said matrix element in said system memory.

2. The data processing system of claim 1, wherein each of said first and second local memories includes

a first storage region for storing a read out matrix element;

a second storage region for storing a matrix element being used for an arithmetic operation; and

a third storage region for storing a matrix element that has already been used for an arithmetic operation.

3. The data processing system of claim 2, wherein said first readout unit reads out matrix elements sequentially one by one from said system memory and then stores a newly-read matrix element in said first storage region by replacing a matrix element previously stored in said first storage region with said newly-read matrix element.

4. The data processing system of claim 3, wherein said first arithmetic unit

reads out a matrix element from said first storage region and stores said matrix element in said second storage region;

performs an arithmetic operation by using said matrix element stored in said second storage region in parallel with a process in which the fist readout unit reads another matrix element to said first storage region for the next arithmetic operation; and

reads out said matrix element from said second storage region and stores the read matrix element in a third storage region on condition of completion of said arithmetic operation.

5. The data processing system of claim 4, wherein said second readout unit, in parallel with the next arithmetic process performed by said first arithmetic unit, reads out a matrix element from said third storage region in said first local memory and stores said matrix element in said first region of said second local memory by replacing a matrix element previously stored in said first storage region.

6. The data processing system of claim 5, wherein said second arithmetic unit reads out a matrix element from said first storage region of said second local memory, and stores said matrix element in said second storage region, and performs an arithmetic operation by using said matrix element stored in said second storage region in parallel with a process in which said second readout unit reads a matrix element for the next arithmetic operation.

7. The data processing system of claim 6, wherein

said first arithmetic unit further calculates a total value of products of an element of said first sub-vector and each of said non-zero elements of said value matrix, and further stores said calculated total value in said third storage region,

said second readout unit further reads out said total value from said third storage region of said first local memory, and stores said total value in said first storage region by replacing a total value previously stored in said first storage region of said second local memory,

said second arithmetic unit reads out said total value stored in said first storage region of said second local memory, stores said read total value in said second storage region, calculates a total value of products of an element of said second sub-vector and each of said non-zero elements of said value matrix, adds said calculated total value to said total value stored in said second storage region, and then stores the resultant total value in said third storage region of said second local memory, and

said output unit reads out said total value from said third storage region of said second local memory and stores said total value as each element of a vector indicating said product of said input matrix and said input vector.

8. The data processing system of claim 1, wherein in parallel with an arithmetic operation in which said first arithmetic unit multiplies an element of said first sub-vector and another element of said value matrix, said second arithmetic unit performs an arithmetic operation of multiplying an element of said second sub-vector and another element of said value matrix.

9. The data processing system of claim 1, wherein said data processing system is configured to calculate a product obtained by multiplying an input matrix by an input vector from a right side of said matrix, wherein

said value matrix is a matrix formed by creating row vectors each having anon-zero element included in each of the rows of said input matrix, and by arranging said row vectors;

said position matrix is a matrix formed by creating row vectors each having elements indicating values of the positions of non-zero elements included in each of the rows of said input matrix, and by arranging said row vectors;

said multi-core processor includes a classification unit configured to scan the position matrix stored in said system memory, and to classify each of said rows of said input matrix into first to third categories, said first category indicating a row including a non-zero element to be multiplied by elements included in said first sub-vector and said second sub-vector, said second category indicating a row including a non-zero element to be multiplied by an element included in said first sub-vector, and said third category indicating a row including a non-zero element to be multiplied by an element in said second sub-vector;

said first readout unit sequentially reads out matrix elements of a predetermined number of rows among rows each corresponding to any one of said first and second categories, from each of said value matrix and said position matrix stored in said system memory;

said second readout unit reads out matrix elements of a row corresponding to said row of said first category in said matrix element and said position matrix from said first local memory, and further reads out matrix elements of a row corresponding to said row of said third category in said matrix element and said arrangement element stored in said system memory; and

said output unit generates each element of a vector indicating a product on said basis of said results of arithmetic operations performed by said first and second arithmetic units on said row of said first category, said result of an arithmetic operation performed by said first arithmetic unit on said row of said first category, and said result of an arithmetic operation performed by said second arithmetic unit on said row of said third category, and stores said created element in said system memory.

10. A method for calculating a product of an input matrix and an input vector using a multi-core processor having a plurality of processing elements each having a processor and a local memory, said method comprising:

storing in a system memory a value matrix in which non-zero matrix elements of said input matrix are arranged, and a position matrix for indicating positions of said non-zero elements;

storing in a first local memory of a first one of said processing elements a first sub-vector that is a first part of said input vector;

storing in a second local memory of a second one of said processing elements a second sub-vector that is second part of said input vector;

sequentially reading out matrix elements from said value matrix and from said position matrix within said system memory, and storing said read out matrix elements in said first local memory as newly-read matrix elements;

multiplying two elements in said first processing element every time a matrix element is being read out, wherein one of said two elements corresponds to the position of a non-zero element indicated by each of said matrix elements read out from said position matrix in said first sub-vector, and the other of said two elements being a non-zero element read out from said value matrix in said first sub-vector;

reading out a matrix element of said value matrix and said position matrix from said first local memory and storing said matrix element in said second local memory as a newly-read matrix element every time said multiplying is being performed;

multiplying two matrix elements in said second processing element every time a matrix element is being read out from said first local memory, wherein one of said two matrix elements corresponds to the position of a non-zero element indicated by each of said matrix elements read from said position matrix in said second sub-vector, and the other of said two matrix elements being a non-zero element read from said value matrix in said second sub-vector; and

generating each matrix element of a vector indicating a product of said input matrix and said input vector based on results from said two multiplying operations.