Efficient Parallel Algorithm for Optimal DAG Structure Search on Parallel Computer with Torus Network
Efficient Parallel Algorithm for Optimal DAG Structure Search on Parallel Computer with Torus Network
复制标题
环面网络并行计算机上最优DAG结构搜索的高效并行算法
DOI：
10.1007/978-3-319-49583-5_37
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Suda
中科院分区：
文献类型：
--
作者：
H. Honda;Y. Tamada;R. Suda
最优有向无环图搜索问题构成了对具有最小分数的DAG的搜索，其中DAG的分数是根据其结构定义的。这个问题是已知的NP难问题，最先进的算法需要指数时间和空间。因此，使用单个处理器解决大型实例是不可行的。因此，已经开发了一些并行算法来解决更大的实例。最近提出的一种并行算法可以求解33个顶点的实例，这是迄今为止报道的最大求解规模。在本文提出的研究中，我们开发了一种新的并行算法，专门设计用于在具有环面网络的并行计算机上运行。我们的算法很关键地利用了环面网络结构，从而获得了良好的可扩展性。通过计算实验，我们证实了我们提出的方法在多达20,736个核的运行中，与使用1296个核的运行相比，并行化效率达到了0.94。最后，我们成功地计算了一个36个顶点的实例的最优DAG结构，这是文献中报道的最大可解尺寸。
The optimal directed acyclic graph search problem constitutes searching for a DAG with a minimum score, where the score of a DAG is defined on its structure. This problem is known to be NP-hard, and the state-of-the-art algorithm requires exponential time and space. It is thus not feasible to solve large instances using a single processor. Some parallel algorithms have therefore been developed to solve larger instances. A recently proposed parallel algorithm can solve an instance of 33 vertices, and this is the largest solved size reported thus far. In the study presented in this paper, we developed a novel parallel algorithm designed specifically to operate on a parallel computer with a torus network. Our algorithm crucially exploits the torus network structure, thereby obtaining good scalability. Through computational experiments, we confirmed that a run of our proposed method using up to 20,736 cores showed a parallelization efficiency of 0.94 as compared to a 1296-core run. Finally, we successfully computed an optimal DAG structure for an instance of 36 vertices, which is the largest solved size reported in the literature.