发明名称 |
Sparse matrix data structure |
摘要 |
Various embodiments relating to encoding a sparse matrix into a data structure format that may be efficiently processed via parallel processing of a computing system are provided. In one embodiment, a sparse matrix may be received. A set of designated rows of the sparse matrix may be traversed until all non-zero elements in the sparse matrix have been placed in a first array. Each time a row in the set is traversed, a next non-zero element in that row may be placed in the first array. If all non-zero elements for a given row of the set of designated rows have been placed in the first array, the given row may be replaced in the set of designated rows with a next unprocessed row of the sparse matrix. The data structure in which the sparse matrix is encoded may be outputted. The data structure may include the first array. |
申请公布号 |
US9367519(B2) |
申请公布日期 |
2016.06.14 |
申请号 |
US201314015894 |
申请日期 |
2013.08.30 |
申请人 |
MICROSOFT TECHNOLOGY LICENSING, LLC |
发明人 |
Strauss Karin;Fowers Jeremy;Ovtcharov Kalin |
分类号 |
G06F7/00;G06F17/16 |
主分类号 |
G06F7/00 |
代理机构 |
|
代理人 |
Swain Sandy;Minhas Micky |
主权项 |
1. A method for encoding a sparse matrix into a data structure, the data structure including a first array, the method comprising:
on a computing system including a computation device including a plurality of parallel processing units:
receiving the sparse matrix;traversing a set of designated rows of the sparse matrix according to a deterministic sequence until all non-zero elements in the sparse matrix have been placed in the first array, wherein the sparse matrix is utilized by the computation device to perform a computation, and wherein a number of designated rows in the set corresponds to a number of parallel processing units of the computation device;each time a row of the set is traversed according to the deterministic sequence, placing a next non-zero element in that row in the first array, wherein each row in the set has a first non-zero element placed in the first array before a second element from that row is placed in the first array;if all non-zero elements for a given row of the set of designated rows have been placed in the first array, replacing the given row in the set of designated rows with a next unprocessed row of the sparse matrix; andoutputting, to a storage device of the computing system, the data structure in which the sparse matrix is encoded. |
地址 |
Redmond WA US |