Sparse fusion is a compile-time loop transformation and runtime scheduling implemented as a domain-specific code generator. Sparse fusion generates efficient parallel code for the combination of two sparse matrix kernels where at least one of the kernels has loop-carried dependencies. Available implementations optimize individual sparse kernels. When optimized separately, the irregular dependence patterns of sparse kernels create synchronization overheads and load imbalance, and their irregular memory access patterns result in inefficient cache usage, which reduces parallel efficiency. Sparse fusion uses a novel inspection strategy with code transformations to generate parallel fused code for sparse kernel combinations that is optimized for data locality and load balance. Code generated by Sparse fusion outperforms the existing implementations ParSy and MKL on average 1.6X and 5.1X respectively and outperforms the LBC and DAGP coarsening strategies applied to a fused data dependence graph on average 5.1X and 7.2X respectively for various kernel combinations.
翻译:松散的聚变是一种编译时间环变和运行时间排程,作为特定域代码生成器。 松散的聚变为两种稀薄的矩阵内核的组合生成了高效的平行代码, 其中至少有一个内核具有环形依赖性。 可用的实施优化了单个稀散内核。 分别优化后, 稀散内核的不规则依赖模式产生了同步式的间接费用和负载不平衡, 以及它们不规则的内存访问模式导致低效缓存使用, 从而降低平行效率 。 松散的聚变使用带有代码的新型检查战略, 为稀散内核组合生成平行的引信代码, 以优化数据位置和负载平衡 。 松散的聚聚变生成的代码在平均 1. 6X 和 5.1X 上优于现有执行程序, 分别优于 ParSy 和 MKL 和 MKL, 5.1x 的生成的代码, 超越了对各种内核聚变组合分别应用于平均 5. 5A 和 DGP 和 DGP 缩式数据依赖图的策略。