Falcon
Falcon
复制标题
DOI：
10.1145/2842618
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Unnikrishnan Cheramangalath;R. Nasre;Y. N. Srikant
中科院分区：
文献类型：
--
作者：
Unnikrishnan Cheramangalath;R. Nasre;Y. N. Srikant
图形算法已经被证明具有足够的并行性，以保持几个计算资源繁忙，甚至在GPU上的数百个核心。不幸的是，调整它们的实现以在由多核CPU和GPU组成的异构系统的特定硬件配置上高效执行是具有挑战性的，耗时的，并且容易出错。为了解决这些问题，我们提出了一个特定领域的语言（DSL），猎鹰，用于实现图形算法，（i）抽象的硬件，（ii）提供结构写显式并行程序在一个更高的水平，（iii）可以与一般的算法，可能会改变图形结构（变形算法）。我们说明了使用我们的DSL实现本地计算算法（不改变图形结构）和变形算法，如Delaunay网格细化，调查传播，动态SSSP的GPU和多核CPU。使用一组基准测试图，我们说明了生成的代码执行接近最先进的手工调优实现。
Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy—even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particular hardware configuration of heterogeneous systems consisting of multicore CPUs and GPUs is challenging, time consuming, and error prone. To address these issues, we propose a domain-specific language (DSL), Falcon, for implementing graph algorithms that (i) abstracts the hardware, (ii) provides constructs to write explicitly parallel programs at a higher level, and (iii) can work with general algorithms that may change the graph structure (morph algorithms). We illustrate the usage of our DSL to implement local computation algorithms (that do not change the graph structure) and morph algorithms such as Delaunay mesh refinement, survey propagation, and dynamic SSSP on GPU and multicore CPUs. Using a set of benchmark graphs, we illustrate that the generated code performs close to the state-of-the-art hand-tuned implementations.