Apparatus and method for allocating shared storage areas to parallel processors for multiplication of sparse matrix and vector

1. A non-transitory computer-readable storage medium storing therein a memory allocating program that causes a computer to perform a process comprising:

assigning calculation of a first submatrix included in a matrix to a first thread and calculation of a second submatrix included in the matrix to a second thread, the matrix including zero elements and non-zero elements;

comparing the first and second submatrices as to where in the matrix the non-zero elements of the first submatrix reside and where in the matrix the non-zero elements of the second submatrix reside, the comparing including comparing row positions of the non-zero elements of the first submatrix with row positions of the non-zero elements of the second submatrix, so as to determine whether the first and second submatrices conflict in terms of row positions of the non-zero elements thereof; and

allocating at least one shared storage area for storing a single column vector calculated by the first and second threads, when the comparing finds that all the non-zero elements of the first submatrix reside in different rows of the matrix from any non-zero element in the second submatrix, such that the first thread writes first vector elements calculated by using the non-zero elements of the first submatrix into a first portion of the shared storage area, while the second thread writes second vector elements calculated by using the non-zero elements of the second submatrix into a second portion of the shared storage area, without exclusive control between the first and second threads.

2. The non-transitory computer-readable storage medium according to claim 1 , wherein:

the matrix is a symmetric matrix; and

the process further includes

assigning calculation of a third submatrix included in the matrix to the first thread and calculation of a fourth submatrix included in the matrix to the second thread, the third submatrix being at a symmetrical position to the first submatrix, the fourth submatrix being at a symmetrical position to the second submatrix, and

allocating a shared storage area to be used for the third and fourth submatrices to the first and second threads irrespective of the result of the comparing.

3. The non-transitory computer-readable storage medium according to claim 1 , wherein the comparing includes dividing rows or columns of the matrix into a plurality of groups, determining whether a non-zero element exists in each of the groups with respect to each of the first and second submatrices, and comparing, on a group-by-group basis, the first submatrix with the second submatrix in terms of existence or absence of a non-zero element.

4. The non-transitory computer-readable storage medium according to claim 1 , wherein the process further includes, when the matrix is represented in a compressed column storage format, extracting a submatrix that does not include overlapping columns with the first submatrix, from the matrix as the second submatrix.

5. A parallel operation method executed by a computer capable of executing a plurality of threads in parallel, the method comprising:

assigning, by a processor of the computer, calculation of a first submatrix included in a matrix to a first thread and calculation of a second submatrix included in the matrix to a second thread, the matrix including zero elements and non-zero elements;

comparing, by the processor, the first and second submatrices as to where in the matrix the non-zero elements of the first submatrix reside and where in the matrix the non-zero elements of the second submatrix reside, the comparing including comparing row positions of the non-zero elements of the first submatrix with row positions of the non-zero elements of the second submatrix, so as to determine whether the first and second submatrices conflict in terms of row positions of the non-zero elements thereof; and

allocating, by the processor, at least one shared storage area for storing a single column vector calculated by the first and second threads, when the comparing finds that all the non-zero elements of the first submatrix reside in different rows of the matrix from any non-zero element in the second submatrix, such that the first thread writes first vector elements calculated by using the non-zero elements of the first submatrix into a first portion of the shared storage area, while the second thread writes second vector elements calculated by using the non-zero elements of the second submatrix into a second portion of the shared storage area, without exclusive control between the first and second threads.

6. An information processing apparatus comprising:

a plurality of processors configured to be capable of executing a plurality of threads in parallel; and

a memory configured to store vectors to be respectively used in calculations by the threads, wherein

one of the plurality of processors is configured to perform a process including:

assigning calculation of a first submatrix included in a matrix to a first thread and calculation of a second submatrix included in the matrix to a second thread, the matrix including zero elements and non-zero elements;

comparing the first and second submatrices as to where in the matrix the non-zero elements of the first submatrix reside and where in the matrix the non-zero elements of the second submatrix reside, the comparing including comparing row positions of the non-zero elements of the first submatrix with row positions of the non-zero elements of the second submatrix, so as to determine whether the first and second submatrices conflict in terms of row positions of the non-zero elements thereof; and

allocating at least one shared storage area in the memory for storing a single column vector calculated by the first and second threads, when the comparing finds that all the non-zero elements of the first submatrix reside in different rows of the matrix from any non-zero element in the second submatrix, such that the first thread writes first vector elements calculated by using the non-zero elements of the first submatrix into a first portion of the shared storage area, while the second thread writes second vector elements calculated by using the non-zero elements of the second submatrix into a second portion of the shared storage area, without exclusive control between the first and second threads.