System and method for efficient sparse matrix processing
A system and method for efficient sparse matrix processing are provided in one embodiment. A compressed representation of a sparse matrix, the sparse matrix including one or more non-zero entries in one or more of a plurality of portions of the matrix, is obtained by at least one server including one or more streaming multiprocessors, each of the streaming multiprocessors including one or more graphics processing unit (GPU) processor cores. Each of the portions are assigned into one of a plurality of partitions based on a number of the non-zero entries in that portion. For each of the partitions, a predefined number of the GPU processor cores are assigned for processing each of the portions assigned to that partition based on the numbers of the non-zero entries in the portions assigned to that partition. For each of the partitions, each of the portions associated with that partition are processed.
1. A system for efficient sparse matrix processing, comprising:
at least one server comprising one or more streaming multiprocessors, each of the streaming multiprocessors comprising a plurality of graphics processing unit (GPU) processor cores, the at least one server configured to:
access a compressed representation of a sparse matrix, the sparse matrix comprising non-zero entries in a plurality of portions of the matrix;
assign each of the portions into one of a plurality of partitions based on a number of the non-zero entries in that portion; and
for each of the partitions, assign by the at least one server a predefined number of the GPU processor cores in one or more of the streaming multiprocessors for processing each of the portions assigned to that partition based on the numbers of the non-zero entries in the portions assigned to that partition; and
process with the assigned predefined number of the GPU processor cores each of the portions associated with that partition.
2. A system according to claim 1 , wherein the predefined number of the GPU processing cores execute one or more warps of processing threads to process one of the partitions, the at least one server further configured to:
associate each of the warps with an identifier;
rank each of the portions in that partition;
assign each of the warps to process one of the portions based on the identifier of that warp and the rank of that portion.
3. A system according to claim 2 , wherein a number of the threads in the warp is one of 32 and 64.
4. A system according to claim 2 , the at least one server further configured to:
associate each of the threads within that warp with a further identifier;
associate each of the non-zero entries within that portion with an index based on a position of that non-zero entry within the portion; and
assign each of the threads in the warp to process one of the non-zero entries based on the further identifier of that thread and the index of that non-zero entry.
5. A system according to claim 4 , the at least one server further configured to:
perform a local sharing of results of the processing performed by all processing threads in the warp.
6. A system according to claim 1 , wherein the predefined number of the GPU processing cores execute one or more blocks of processing threads to process one of the partitions, the at least one server further configured to:
associate each of the blocks with an identifier;
rank each of the portions in that partition;
assign each of the blocks to process one of the portions based on the identifier of that block and the rank of that portion.
7. A system according to claim 6 , the at least one server further configured to:
associate each of the threads within that block with a further identifier;
associate each of the non-zero entries within that portion with an index based on a position of that non-zero entry within the portion; and
assign each of the threads in the block to process one of the non-zero entries based on the further identifier of that thread and the index of that non-zero entry.
8. A system according to claim 6 , the at least one server further configured to:
perform a local sharing of results of the processing performed by all processing threads in the block.
9. A system according to claim 1 , wherein the processing comprises at least one of matrix-vector multiplication and sparse matrix transpose vector multiplication.
10. A system according to claim 1 , wherein the portions that comprise between 1 and 31 of the non-zero entries are assigned to one of the partitions, the portions that comprise more than 31 and less than 1024 of the non-zero entries are assigned to a second one of the partitions, and the portions that comprise a number of the non-zero entries that is equal to or more than 1024 are assigned to a third one of the partitions.
11. A method for efficient sparse matrix processing, comprising:
accessing by at least one server comprising one or more streaming multiprocessors, each of the streaming multiprocessors comprising a plurality of graphics processing unit (GPU) processor cores, a compressed representation of a sparse matrix, the sparse matrix comprising non-zero entries in a plurality of portions of the matrix;
assigning by the at least one server each of the portions into one of a plurality of partitions based on a number of the non-zero entries in that portion;
for each of the partitions, assigning by the at least one server a predefined number of the GPU processor cores in one or more of the streaming multiprocessors for processing each of the portions assigned to that partition based on the numbers of the non-zero entries in the portions assigned to that partition; and
for each of the partitions, processing by the assigned predefined number of the GPU processor cores each of the portions associated with that partition.
12. A method according to claim 11 , wherein the predefined number of the GPU processing cores execute one or more warps of processing threads to process one of the partitions, further comprising:
associating by the at least one server each of the warps with an identifier;
ranking by the at least one server each of the portions in that partition;
assigning by the at least one server each of the warps to process one of the portions based on the identifier of that warp and the rank of that portion.
13. A method according to claim 12 , wherein a number of the threads in the warp is one of 32 and 64.
14. A method according to claim 12 , further comprising:
associating by the at least one server each of the threads within that warp with a further identifier;
associating by the at least one server each of the non-zero entries within that portion with an index based on a position of that non-zero entry within the portion; and
assigning by the at least one server each of the threads in the warp to process one of the non-zero entries based on the further identifier of that thread and the index of that non-zero entry.
15. A method according to claim 14 , further comprising:
performing by the at least one server a local sharing of results of the processing performed by all processing threads in the warp.
16. A method according to claim 11 , wherein the predefined number of the GPU processing cores execute one or more blocks of processing threads to process one of the partitions, further comprising:
associating by the at least one server each of the blocks with an identifier;
ranking by the at least one server each of the portions in that partition;
assigning by the at least one server each of the blocks to process one of the portions based on the identifier of that block and the rank of that portion.
17. A method according to claim 16 , further comprising:
associating by the at least one server each of the threads within that block with a further identifier;
associating by the at least one server each of the non-zero entries within that portion with an index based on a position of that non-zero entry within the portion; and
assigning by the at least one server each of the threads in the block to process one of the non-zero entries based on the further identifier of that thread and the index of that non-zero entry.
18. A method according to claim 16 , further comprising:
performing by the at least one server a local sharing of results of the processing performed by all processing threads in the block.
19. A method according to claim 11 , wherein the processing comprises at least one of matrix-vector multiplication and sparse matrix transpose vector multiplication.
20. A method according to claim 11 , wherein the portions that comprise between 1 and 31 of the non-zero entries are assigned to one of the partitions, the portions that comprise more than 31 and less than 1024 of the non-zero entries are assigned to a second one of the partitions, and the portions that comprise a number of the non-zero entries that is equal to or more than 1024 are assigned to a third one of the partitions.