Towards systematic parallel programming of graph problems via tree decomposition and tree parallelism
Towards systematic parallel programming of graph problems via tree decomposition and tree parallelism
复制标题
DOI：
10.1145/2502323.2502331
复制
发表时间：
2013-09
期刊：
影响因子：
--
通讯作者：
Qi Wang;Meixian Chen;Yu Liu;Zhenjiang Hu
中科院分区：
文献类型：
--
作者：
Qi Wang;Meixian Chen;Yu Liu;Zhenjiang Hu
许多图优化问题，如最大加权独立集问题，是NP-难的。对于具有数十亿条边或顶点的大规模图，这些问题很难直接计算，即使使用流行的数据密集型框架，如MapReduce或Pregel，部署在大型计算机集群上，因为计算复杂度极高。另一方面，许多研究表明，存在多项式时间算法的图有界树宽，这使得它有可能解决这些问题的大型图。然而，这些算法通常难以理解或并行化。在本文中，我们提出了一种新的编程框架，它提供了一个用户友好的编程界面和自动的黑盒并行化。编程接口，这是一个简单而直接的抽象，称为生成测试聚合（简称GTA），是用来描述一组图形问题。我们建议从用户指定的GTA算法中推导出树分解的自底向上动态规划算法，并进一步将自底向上算法转换为并行算法，这些算法在子树列表上以分治的方式运行。此外，平衡树划分策略进行了讨论，以有效的并行计算。我们的最大加权独立集问题的初步实验结果表明，我们的方法的实际可行性。
Many graph optimization problems, such as the Maximum Weighted Independent Set problem, are NP-hard. For large scale graphs that have billions of edges or vertices, these problems are hard to be computed directly even using popular data-intensive frameworks like MapReduce or Pregel that are deployed on large computer-clusters, because of the extremely high computational complexity. On the other hand, many studies have shown the existence of polynomial time algorithms on graphs with bounded treewidth, which makes it possible to solve these problems on large graphs. However, the algorithms are usually difficult to be understood or parallelized. In this paper, we propose a novel programming framework which provides a user-friendly programming interface and automatic in-black-box parallelization. The programming interface, which is a simple and straightforward abstraction called Generate-Test-Aggregate (GTA for short), is used to describe a set of graph problems. We propose to derive bottom-up dynamic programming algorithms on tree decompositions from the user-specified GTA algorithms, and further transform the bottom-up algorithms to parallel ones which run in a divide-and-conquer manner on a list of subtrees. Besides, balanced tree partition strategies are discussed for efficient parallel computing. Our preliminary experimental results on the Maximum Weighted Independent Set problem demonstrate the practical viability of our approaches.