Compiling Graph Applications for GPU s with GraphIt
Compiling Graph Applications for GPU s with GraphIt
复制标题
DOI：
10.1109/cgo51591.2021.9370321
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Ajay Brahmakshatriya;Saman P. Amarasinghe
中科院分区：
文献类型：
--
作者：
Ajay Brahmakshatriya;Saman P. Amarasinghe
图形程序的性能在很大程度上取决于算法、输入图形的大小和结构以及底层硬件的特性。没有一组优化或一个硬件平台可以在所有设置中很好地工作。为了实现高性能，程序员必须仔细选择要使用哪组优化和硬件平台。GraphIt编程语言使程序员可以轻松编写一次算法，并使用调度语言针对不同的输入进行优化。然而，GraphIt目前不支持为GPU生成高性能代码。为了在GPU上实现高性能，程序员必须从头开始用一种低级语言重新实现整个算法，并进行一组完全不同的抽象和优化。我们提出了G2，GraphIt编译器框架的扩展，使用相同的算法规范在CPU和GPU上实现高性能。G2通过一种新的GPU调度语言和编译器显著扩展了GPU图形处理框架的优化空间，该语言和编译器支持结合负载平衡、边遍历方向、活动顶点集创建、活动顶点集处理排序和内核融合优化。G2还引入了两种性能优化，基于边缘的线程扭曲CTA负载平衡（ETWC）和边缘阻塞，以扩展GPU的优化空间。ETWC通过动态地将每个顶点的边划分为块来改进负载平衡，这些块被分配给线程、线程束和CTA以供执行。EdgeBlocking通过重新排序边和限制随机内存访问以适应L2缓存来提高程序的局部性。我们在Pascal和Volta两代NVIDIA GPU上对G2的5种算法和9种输入图进行了评估，结果表明，它在最先进的GPU图形处理框架上实现了高达5.11倍的加速比，并且在90个实验中的66个实验中最快。
The performance of graph programs depends highly on the algorithm, the size and structure of the input graphs, as well as the features of the underlying hardware. No single set of optimizations or one hardware platform works well across all settings. To achieve high performance, the programmer must carefully select which set of optimizations and hardware platforms to use. The GraphIt programming language makes it easy for the programmer to write the algorithm once and optimize it for different inputs using a scheduling language. However, GraphIt currently has no support for generating highperformance code for GPUs. Programmers must resort to re-implementing the entire algorithm from scratch in a low-level language with an entirely different set of abstractions and optimizations in order to achieve high performance on GPUs. We propose G2, an extension to the GraphIt compiler framework, that achieves high performance on both CPUs and GPUs using the same algorithm specification. G2 significantly expands the optimization space of GPU graph processing frameworks with a novel GPU scheduling language and compiler that enables combining load balancing, edge traversal direction, active vertexset creation, active vertexset processing ordering, and kernel fusion optimizations. G2 also introduces two performance optimizations, Edge-based Thread Warps CTAs load balancing (ETWC) and EdgeBlocking, to expand the optimization space for GPUs. ETWC improves load balancing by dynamically partitioning the edges of each vertex into blocks that are assigned to threads, warps, and CTAs for execution. EdgeBlocking improves the locality of the program by reordering the edges and restricting random memory accesses to fit within the L2 cache. We evaluate G2 on 5 algorithms and 9 input graphs on both Pascal and Volta generation NVIDIA GPUs, and show that it achieves up to 5.11× speedup over state-of-the-art GPU graph processing frameworks, and is the fastest on 66 out of the 90 experiments.