Sparse matrix vector multiplication
US9830302B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Apr 13, 2015 |
| Grant date | Nov 28, 2017 |
| Priority date | — |
| Expiry date | May 31, 2035 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/16
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Systems and methods for multiplying a sparse matrix by a vector using a single instruction multiple data (SIMD) architecture are provided. An example method includes sorting rows of the sparse matrix by a number of non-zero elements in the rows to generate sorted rows. The sorted rows are split to generate groups of the sorted rows. The number of rows in each group of the sorted rows is equal to the number of rows updated in parallel. The method allows for packing the sorted rows in each of the groups to generate packed rows. Each of the packed rows within the same group has the same length. Per clock cycle, C elements of the packed rows and data for selecting elements of the vector are provided to computational units in the SIMD architecture, where C is the number of computational units.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.