Optimizing ordered graph algorithms with GraphIt
Optimizing ordered graph algorithms with GraphIt
复制标题
DOI：
10.1145/3368826.3377909
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Yunming Zhang;Ajay Brahmakshatriya;Xinyi Chen;Laxman Dhulipala;Shoaib Kamil;Saman P. Amarasinghe;Julian Shun
中科院分区：
文献类型：
--
作者：
Yunming Zhang;Ajay Brahmakshatriya;Xinyi Chen;Laxman Dhulipala;Shoaib Kamil;Saman P. Amarasinghe;Julian Shun
许多图问题可以使用有序并行图算法来解决，这些算法通过减少冗余工作实现了与无序并行图算法相比的显著加速。本文介绍了一种新的基于优先级的扩展，它是一种用于编写图形应用程序的领域特定语言，以简化高性能并行有序图算法的编写。该扩展允许以动态顺序处理顶点，同时向用户隐藏低级实现细节。我们通过新的程序分析、转换和代码生成来扩展编译器，以产生有序并行图算法的快速实现。我们还引入了桶融合，这是一种新的性能优化，将不同轮的有序算法融合在一起以减少同步开销，在大直径道路网络上比现有最快的有序算法加速1.2×-3倍。有了这个扩展，GraphIt在支持有序算法的最新框架和手工优化实现(Julienne、Galois和GAPBS)上，在六个有序图算法上实现了高达3倍的加速。
Many graph problems can be solved using ordered parallel graph algorithms that achieve significant speedup over their unordered counterparts by reducing redundant work. This paper introduces a new priority-based extension to GraphIt, a domain-specific language for writing graph applications, to simplify writing high-performance parallel ordered graph algorithms. The extension enables vertices to be processed in a dynamic order while hiding low-level implementation details from the user. We extend the compiler with new program analyses, transformations, and code generation to produce fast implementations of ordered parallel graph algorithms. We also introduce bucket fusion, a new performance optimization that fuses together different rounds of ordered algorithms to reduce synchronization overhead, resulting in 1.2×–3× speedup over the fastest existing ordered algorithm implementations on road networks with large diameters. With the extension, GraphIt achieves up to 3× speedup on six ordered graph algorithms over state-of-the-art frameworks and hand-optimized implementations (Julienne, Galois, and GAPBS) that support ordered algorithms.