Kinetic Dependence Graphs
Kinetic Dependence Graphs
复制标题
动力学相关图
DOI：
10.1145/2694344.2694363
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
K. Pingali
中科院分区：
文献类型：
--
作者：
M. A. Hassaan;Donald Nguyen;K. Pingali
任务图或依赖图在运行时系统中使用，以安排任务以进行并行执行。在诸如密集线性代数和信号处理之类的问题域中，可以通过静态分析从程序中生成依赖图。但是，在诸如Graph Analytics之类的新兴问题域中，程序中任务之间的一组任务和依赖性是运行时值的复杂函数，无法静态确定。在本文中，我们介绍了一种在此类程序中利用并行性的新方法。此方法基于一个称为“动力学依赖图”（KDG）的数据结构，该数据结构由依赖图和更新规则组成，该规则会逐步更新图表，以反映任务完成时依赖性结构的变化。我们已经实施了一个简单的编程模型，该模型允许程序员以高水平的抽象编写这些应用程序，并且在Galois系统中[15]中的运行时间自动构建KDG并并行执行程序。在否则难以并行化的一系列程序中，我们在许多情况下获得了40个内核的加速度，在许多情况下超过了第三方实施。
Task graphs or dependence graphs are used in runtime systems to schedule tasks for parallel execution. In problem domains such as dense linear algebra and signal processing, dependence graphs can be generated from a program by static analysis. However, in emerging problem domains such as graph analytics, the set of tasks and dependences between tasks in a program are complex functions of runtime values and cannot be determined statically. In this paper, we introduce a novel approach for exploiting parallelism in such programs. This approach is based on a data structure called the kinetic dependence graph (KDG), which consists of a dependence graph together with update rules that incrementally update the graph to reflect changes in the dependence structure whenever a task is completed. We have implemented a simple programming model that allows programmers to write these applications at a high level of abstraction, and a runtime within the Galois system [15] that builds the KDG automatically and executes the program in parallel. On a suite of programs that are difficult to parallelize otherwise, we have obtained speedups of up to 33 on 40 cores, out-performing third-party implementations in many cases.