这次回顾ECE408 Lecture 20，这次继续介绍并行稀疏方法。

课程主页：

搬运视频：

CSR运行时

块性能由最长的行决定。

基于CSR的SpMV

JDS(Jagged Diagonal Sparse)负载均衡内核设计

根据非零个数对行进行降序排序。跟踪原始行号，以便可以正确生成输出向量。

根据长度对行进行排序(正则化)

CSR到JDS转换

并行SpMV/JDS Kernel

__global__ void SpMV_JDS(int num_rows, float *data, int *col_index, int *jds_row_ptr, int *jds_row_perm, float *x, float *y) {
    int row = blockIdx.x * blockDim.x + threadIdx.x;
    if (row < num_rows) {
        float dot = 0;
        int row_start = jds_row_ptr[row];
        int row_end = jds_row_ptr[row+1];
        for (int elem = row_start; elem < row_end; elem++) {
            dot += data[elem] * x[col_index[elem]];
        }
    	y[jds_row_perm[row]] = dot;
    }
}

JDS vs CSR控制分歧

  • 线程在JDS内核for循环中仍然执行不同次数的迭代
    • 但是，由于排序，相邻线程往往会执行相似数量的迭代；
    • 更好的线程利用率，更少的控制分歧；

JDS vs CSR内存分歧

相邻的线程仍然访问不相邻的内存位置：

带转置的JDS

转置, 用来内存合并

带有转置layout的JDS格式

并行SpMV/JDS_T Kernel

__global__ void SpMV_JDS_T(int num_rows, float *data, int *col_index, int *jds_t_col_ptr, int *jds_row_perm, float *x, float *y) {
    int row = blockIdx.x * blockDim.x + threadIdx.x;
    if (row < num_rows) {
        float dot = 0;
        unsigned int sec = 0;
        while (jds_t_col_ptr[sec+1] - jds_t_col_ptr[sec] > row) {
            dot += data[jds_t_col_ptr[sec]+row] *
            	   x[col_index[jds_t_col_ptr[sec]+row]];
            sec++;
    	}
    	y[jds_row_perm[row]] = dot;
    }
}

案例

大致随机

可能最好与ELL一起使用：

  • 填充服从均匀分布；
  • 稀疏表示是均匀的；

行之间的高方差

最好与ELL/COO一起使用：

  • 大多数情况下使用ELL会带来好处；
  • COO捕获异常值；

非常稀疏

最好与COO一起使用：

  • 计算稀疏；

几乎是下三角矩阵

最好与JDS一起使用：

  • 利用稀疏结构；

带状矩阵

最好与ELL一起使用：

  • 行中的少量差异；

其他格式

  • 对角线(DIA)：用于严格带状/对角线矩阵；
  • 数据包(PKT)：通过重新排序行/列来创建对角子矩阵；
  • 键字典(DOK)：（行/列）到数据的映射；
  • 压缩稀疏列(CSC)：何时使用CSR？
  • Blocked CSR：对块稀疏矩阵有用；
  • 如果稀疏性是动态的，即大型稀疏系统是在运行时动态生成的，情况又如何呢？

稀疏矩阵作为高级算法技术的基础

  • 图通常表示为稀疏邻接矩阵；
    • 广泛用于社交网络分析、自然语言处理等；
  • 分箱技术通常使用稀疏矩阵进行数据压缩；
    • 广泛用于光线追踪、基于粒子的流体动力学方法和游戏；
  • 这些将在ECE508/CS508中涵盖；