Elixir: a system for synthesizing concurrent graph programs
Elixir: a system for synthesizing concurrent graph programs
复制标题
Elixir：一个用于综合并发图程序的系统
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
K. Pingali
中科院分区：
文献类型：
--
作者：
Dimitrios Prountzos;R. Manevich;K. Pingali
机器学习和网络分析等新应用领域的算法使用“不规则”数据结构，如图、树和集合。在这些问题域中编写高效的并行代码是非常具有挑战性的，因为它需要程序员做出许多选择：给定的问题通常可以通过几个算法来解决，每个算法可能有许多实现，并且算法和实现的最佳选择不仅取决于并行平台的特性，还取决于输入数据的属性，例如图的结构。一种解决方案是允许应用程序员试验不同的算法和实现，而无需从头开始编写每个变体。自动调整以找到最佳变体是一个更雄心勃勃的解决方案。这些解决方案需要一个系统，用于从高级规范自动产生高效的并行实现。Elixir，本文中描述的系统，是实现这一宏伟目标的第一步。应用程序员编写规范，其中包括一个操作符，它描述了要执行的计算，以及执行这些计算的时间表。Elixir使用复杂的推理技术从这些规范中生成高效的并行代码。
我们使用Elixir自动生成三个不规则问题的许多并行实现：广度优先搜索，单源最短路径和介数中心计算。我们的实验表明，生成的最佳变体可以与其他研究小组的手写代码竞争;对于某些输入，它们甚至优于手写版本。
Algorithms in new application areas like machine learning and network analysis use "irregular" data structures such as graphs, trees and sets. Writing efficient parallel code in these problem domains is very challenging because it requires the programmer to make many choices: a given problem can usually be solved by several algorithms, each algorithm may have many implementations, and the best choice of algorithm and implementation can depend not only on the characteristics of the parallel platform but also on properties of the input data such as the structure of the graph. One solution is to permit the application programmer to experiment with different algorithms and implementations without writing every variant from scratch. Auto-tuning to find the best variant is a more ambitious solution. These solutions require a system for automatically producing efficient parallel implementations from high-level specifications. Elixir, the system described in this paper, is the first step towards this ambitious goal. Application programmers write specifications that consist of an operator, which describes the computations to be performed, and a schedule for performing these computations. Elixir uses sophisticated inference techniques to produce efficient parallel code from such specifications.
We used Elixir to automatically generate many parallel implementations for three irregular problems: breadth-first search, single source shortest path, and betweenness-centrality computation. Our experiments show that the best generated variants can be competitive with handwritten code for these problems from other research groups; for some inputs, they even outperform the handwritten versions.