Runtime Composition of Iterations for Fusing Loop-carried Sparse Dependence
Runtime Composition of Iterations for Fusing Loop-carried Sparse Dependence
复制标题
用于融合循环携带稀疏依赖的迭代的运行时组合
DOI：
10.1145/3581784.3607097
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Mehri Dehnavi, Maryam
中科院分区：
文献类型：
--
作者：
Cheshmi, Kazem;Strout, Michelle;Mehri Dehnavi, Maryam
稀疏计算中迭代之间的依赖性导致内存和计算资源的低效使用。本文提出了稀疏融合，这是一种为两个稀疏矩阵内核的组合生成高效并行代码的技术，其中至少一个内核具有循环携带依赖性。现有的实现分别优化各个稀疏内核。然而，由于稀疏内核的不规则依赖模式，这种方法会导致同步开销和负载不平衡，并且由于其不规则的内存访问模式而导致缓存使用效率低下。稀疏融合使用新颖的检查策略和代码转换来生成针对数据局部性和负载平衡进行优化的并行融合代码。对于各种内核组合，稀疏融合的性能比使用 ParSy 和 MKL 的最佳未融合实现平均快 4.2 倍，并且比使用现有调度算法（例如 LBC、DAGP 和波前）的最佳融合实现平均快 4 倍。
Dependence between iterations in sparse computations causes inefficient use of memory and computation resources. This paper proposes sparse fusion, a technique that generates efficient parallel code for the combination of two sparse matrix kernels, where at least one of the kernels has loop-carried dependencies. Existing implementations optimize individual sparse kernels separately. However, this approach leads to synchronization overheads and load imbalance due to the irregular dependence patterns of sparse kernels, as well as inefficient cache usage due to their irregular memory access patterns. Sparse fusion uses a novel inspection strategy and code transformation to generate parallel fused code optimized for data locality and load balance. Sparse fusion outperforms the best of unfused implementations using ParSy and MKL by an average of 4.2× and is faster than the best of fused implementations using existing scheduling algorithms, such as LBC, DAGP, and wavefront by an average of 4× for various kernel combinations.