In this paper we describe a generic scheme for the parallel exploration of directed acyclic graphs starting from one or more `roots' of the graph. Our scheme is designed for graphs with the following properties, (i) discovering neighbors at any node requires a non-trivial amount of computation, it is not a simple lookup; (ii) once a node is processed, all its neighbors are discovered; (iii) each node can be discovered through multiple paths, but should only be processed once. Several computational problems can be reduced to traversing such graphs, where the goal is to explore the graph and build a traversal roadmap. As a proof of concept for the effectiveness of our scheme at achieving speedup due to parallelism, we implement the scheme for the parallel exploration of assembly landscape using the EASAL methodology.
翻译:在本文中,我们描述了一个从图中一个或多个“基层”开始的平行探索定向圆形图的通用计划。我们的计划是为具有以下属性的图表设计的,(一) 在任何节点发现邻居需要非三重量的计算,这不是简单的查看;(二) 一旦处理一个节点,就发现其所有邻居;(三) 每个节点都可以通过多条路径发现,但只能处理一次。几个计算问题可以简化到绘制这些图表,目的是探索图表,并绘制一个跨行路径图。作为我们计划因平行主义而实现加速效率的概念的证明,我们用EASAL方法实施平行探索组装场的计划。