稀疏矩阵与cuSPARSE
1.稀疏矩阵
1.1.定义
定义中有个关键点：稀疏矩阵通常是指的非零元素占比不超过5%，即稀疏度大于95%。
矩阵的稀疏度对于矩阵压缩比以及性能有很大的影响
1.2.存储方式
主要的稀疏矩阵存储方式可以参见这篇博文 稀疏矩阵存储格式总结+存储效率对比:COO,CSR,DIA,ELL,HYB
对于随机稀疏矩阵，可以对比各种存储方式的压缩比 
（数值越小说明压缩率越高，即存储效率越高）
2.cuSPARSE
2.1.简介
cuSPARSE是Nvidia的用于计算稀疏矩阵的线代运算高性能库，运行在基于CUDA Toolkit的显卡，其主要功能有：
- Level 1: 稀疏向量与稠密向量运算
- Level 2: 稀疏矩阵与稠密向量运算
- Level 3: 稀疏矩阵与稠密矩阵运算
- 稀疏矩阵与稀疏矩阵的运算
- 其他：各种存储形式的矩阵转换 和 csr格式的压缩
2.2.特征向量搜索的cuSPARSE实现
在机器视觉、NLP领域，非结构化数据会量化成大规模的特征向量，由于特征化算法差异，会生成大量稀疏特征向量，故而在特征检索的方面，可以用稀疏矩阵来压缩存储和加速计算。
本文示例中采用CSR格式来存储稀疏矩阵
2.2.1. 流程
- 特征库加载到显存
- 使用cusparseSnnz 和 cusparseSdense2csr/cusparseSdense2csc将存储在显存中的稠密矩阵转换成稀疏矩阵
- 使用cusparseXcsrgemmNnz 和 cusparseScsrgemm计算另个稀疏矩阵的乘法
- 将所得结果的稀疏矩阵转换成稠密矩阵
- 返回搜索结果
2.2.2. 示例代码
https://gist.github.com/snowwalf/ccdb6c6324b7933125800dc37add409c
2.3.性能比对
特征维度=512 特征精度=float32 底库数目=100W 搜索batch=10 round=500，单卡P4
稀疏矩阵采用CSR存储： 显存 = 2特征数目稀疏度2K + 特征数目4
| 稀疏度 | cuBLAS时延 | cuSPARSE时延 | 稀疏矩阵：稠密矩阵性能比 |
|---|---|---|---|
| 0.99 | 0.0210732s | 0.00159799s | 13.1873 |
| 0.95 | 0.0188551s | 0.00230333s | 8.18605 |
| 0.9 | 0.0210468s | 0.00246604s | 8.53466 |
| 0.8 | 0.0208215s | 0.00291173s | 7.15091 |
| 0.7 | 0.0207451s | 0.0113726s | 5.38902 |
| 0.6 | 0.0208009s | 0.0127621s | 1.82903 |
| 0.5 | 0.0207802s | 0.0189049s | 1.0992 |
| 0.4 | 0.020857s | 0.0187537s | 1.11215 |
| 0.3 | 0.020747s | 0.0185469s | 1.11862 |
| 0.2 | 0.0212511s | 0.0185057s | 1.14836 |
| 0.1 | 0.0209569s | 0.0382298s | 0.548183 |
| 0 | 0.0204215s | 0.0394001s | 0.518311 |