高性能计算导论 Lab 3

稀疏矩阵-矩阵乘 大作业 实验报告

实现方法

preprocess

• 不同矩阵数据集的稀疏度不同, 计算稀疏矩阵 $A$ 平均每行非零元的个数.
  • 若平均每行非零元数较低:
    • 由每个线程块处理 $\mathbf{A}$ 中 64 个非零元.
    • 利用共享内存存储 $\mathbf{A}$ 中非零元素所在行号.
    • 根据 $K$ 的大小设置为 SPARSE_32 或 SPARSE_256 模式.
  • 若平均每行非零元数较高:
    • 由每个线程块处理 $\mathbf{A}$ 中 1 行非零元.
    • 根据 $K$ 的大小设置为 DENSE_32 或 DENSE_256 模式.
• 初始化 vout 为 0, 确保输出结果的正确性.

run

• 每个线程块负责计算:
  • SPARSE_32 模式: $\mathbf{A}$ 中 64 个非零元与 $\mathbf{B}$ 中 1 列元素的乘积.
  • SPARSE_256 模式: $\mathbf{A}$ 中 64 个非零元与 $\mathbf{B}$ 中 4 列元素的乘积.
  • DENSE_32 模式: $\mathbf{A}$ 中 1 行非零元与 $\mathbf{B}$ 中 1 列元素的乘积.
  • DENSE_256 模式: $\mathbf{A}$ 中 1 行非零元与 $\mathbf{B}$ 中 2 列元素的乘积.
• 每个线程块设置 32 个线程, 将上面的计算任务分摊到每个线程, 让同一个 Warp 内线程进行相同的工作.
• 设置共享内存存储稀疏矩阵 $\mathbf{A}$ 的元素, 在线程块内充分利用寄存器资源.
• 手动展开循环, 并改用位移运算实现 $2$ 幂次乘法运算, 提高计算效率.

运行结果

• $K = 32$ 时, 运行时间及加速比如下:
• 平均吞吐量为 $4.52845\times 10^{9}$ nnz/s, 有 13 个达到加速比要求.

测试集	spmm_cusparse/us	spmm_opt/us	加速比
arxiv	750.658	462.133	1.624
collab	1281.46	651.966	1.966
citation	16443	9276.09	1.773
ddi	641.326	277.533	2.311
protein	24664.9	8190.62	3.011
ppa	18381.8	10251.1	1.793
reddit.dgl	48559	21516.1	2.257
products	55819.7	32036.7	1.742
youtube	3643.61	2425.85	1.502
amazon_cogdl	125240	53800.3	2.328
yelp	6574.59	3602.06	1.825
wikikg2	7138.26	3230.56	2.210
am	3741.58	2243.36	1.668

• $K = 256$ 时, 运行时间及加速比如下:
• 平均吞吐量为 $6.44827\times 10^{8}$ nnz/s, 有 10 个达到加速比要求.

测试集	spmm_cusparse/us	spmm_opt/us	加速比
arxiv	2990.24	2694.47	1.110
collab	5204.38	4437.61	1.173
citation	78943.5	69097.1	1.143
ddi	1562.93	1587.49	0.985
protein	80862.7	67908.9	1.191
ppa	84946.6	80882.5	1.050
reddit.dgl	202263	182988	1.105
products	258319	247208	1.045
youtube	14394.4	14886.4	0.967
amazon_cogdl	517165	435827	1.187
yelp	29985.7	26834.4	1.117
wikikg2	16638.8	19490.7	0.854
am	13388.7	12281.9	1.090