格式
- COO 格式用三个数组分别存储非零元的行索引、列索引和值
- CSR 格式在 COO 格式的基础 上，将存储非零元行索引的数组压缩为行偏移数组，其长度固定为矩阵的行数加一， 数组中的第 i 个元素代表矩阵前 i 行的非零元总数，该数组可以快速定位第 i 行的第一个非零元在列索引数组和值数组中的位置。
- CSC 格式将 CSR 格式对行索引数组的压缩改为对列索引数组的压缩，其将列索引的数组压缩为列偏移数组，其长度固定为矩阵的列数加一，数组中的第 i 个元素代表矩阵前 i 列的非零元总数
CSR 格式因其与按行计算方法的适配性，是目前研究工作中最受欢迎的格式
计算方法
内积
外积
按列计算
按行计算
行计算方法因其与 GPU 并行计算架构的高度兼容性而显得尤为突出
计算步骤
大小预测
渐进法
无法保证下限
估计法
无法保证下限
精确法
符号阶段 + 数值阶段
上限法
直接根据结果矩阵的中间结果数量来分配内存空间，其优点就是计算速度较快且易于实现，但缺点也很明显，会分配大量冗余的内存空间，甚至超过设备内存容量，导致运算失败
负载均衡
负载均衡是指将矩阵计算的任务划分为多个子任务，然后将子任务合理地分配给各个计算单元，使尽可能少的计算单元处于空闲状态，这样能使任务得到快速的并行处理，进而提高计算效率。
1D 划分
对矩阵 A 按照行或列进行划分，划分后矩阵变成多个行/列块，每个计算单元负责处理矩阵 A 的一个行/列块以及对应的矩阵 B 的计算，生成结果矩阵对应行/列块的值
2D 划分
将矩阵 A 同时按行和列进行划分，形成多个子块
3D 划分
不仅将矩阵 A 按行和列划分，同时将矩阵 B 也分块
超图划分
二分图划分
结果累加
将存储在设备上的中间结果进行合并累加，并在压缩排序后就可以形成结果矩阵。不同算法中间结果累加的效率与矩阵的压缩比大小有关，中间结果的总数除以结果矩阵非零元的总数，就是矩阵的压缩比。
ESC 算法
分为扩展、排序和压缩三个阶段。扩展阶段将所有的中间结果存储到临时数组当中，排序 阶段对所有的中间结果进行排序，压缩阶段将排序后的数组进行合并累加，生成最终 结果。ESC 对于具有较少中间结果数量或者压缩比较小的矩阵性能较好，但通常需要 大量的临时内存，此外，当处理具有较大压缩比的矩阵时，其排序阶段的开销十分昂 贵
基于哈希的算法
用哈希表来存储中间结果，利用哈希散列将非零元映射到哈希表的各个位置，然后进行结果累加或者冲突处理
基于合并的算法
使用有序列表存储中间结果，并使用类似于归并排序的算法
稠密累加方法
将中间结果的存储和累加都放到稠密数组中进行, 相较于基于哈希的算法，稠密数组无需进行哈希散列，也不必处理冲突，但其会分配冗余的内存空间，所以基于稠密数组的方法仅在非零元非常密集的输出行中能取得较高性能
本文采用 OpSparse 分配结果矩阵内存空间的思想，在初始化阶段就为结果矩阵的行偏移数组分配内存空间(结果矩阵 C 的行数等于输入矩阵 A 的行数，所以读入矩阵 A 后这部分内存空间大小就可知)。由 于 OpSparse 采用精确法计算，所以初始化阶段用该内存空间存储结果矩阵每行中间 结果数量，用于符号阶段的计算。而符号阶段计算后同样使用该内存空间存储结果矩 阵每行的非零元数量，这样减少了全局内存的使用，节省了部分内存分配时间
在哈希累加阶段，目前主流算法并没有实现哈希表的填充率与哈希冲突次数 的平衡，虽然在 spECK 和 OpSparse 中对该问题有所探讨，但仍然存在更优的解决方案
在初始化阶段和符号阶段，OpSparse 采用十分耗时的原子操 作来统计结果矩阵每行的非零元相关信息，本文尝试以线程规约技术优化此操作，减 少原子操作次数，提升访存效率
上限法没有符号阶段，而是在经过数值阶段以后才能确定结 果矩阵非零元数量的精确值，所以数值阶段后需要进行一次压缩操作，去掉冗余的内 存空间，才能形成结果矩阵的最终结果。压缩过程不仅需要结果矩阵每行的非零元数 量，还需要每行的中间结果数量，即上限法分配的内存空间，才能确定结果矩阵中每 行的起始位置与偏移量。所以相较于精确法，上限法在初始化阶段要多分配一个大小 为结果矩阵行数的数组，即一个数组用于存储结果矩阵每行的中间结果数量，另一个数组存储结果矩阵每行实际的非零元数量。
精确法的符号阶段
其他方法的分组
