A Parallel Searching Scheme for Multiprocessor Systems and Its Application to Combinatorial Problems
A Parallel Searching Scheme for Multiprocessor Systems and Its Application to Combinatorial Problems
复制标题
多处理器系统的并行搜索方案及其在组合问题中的应用
DOI：
--
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
T. Fukumura
中科院分区：
文献类型：
--
作者：
M. Imai;Y. Yoshida;T. Fukumura
针对分支定界(B&B)算法，提出了一种基于多处理器系统的并行化计算方案--并行化深度优先算法(PDFA)。从理论上证明了PDFA算法对p个处理单元的空间需求最多是具有深度优先搜索功能的顺序B&B算法的p倍。此外，通过模拟的实验结果可知，在p个处理单元上的PDFA的计算时间可以减少到采用深度优先搜索函数的顺序B&B算法的1/p以下。我们将这种减少效应称为计算时间加速效应。
In this paper, we propose a parallelized computational scheme called Parallelized Depth-First Algorithm (PDFA) for Branch-and-Bound (B&B) method that works on multiprocessor systems. It is shown theoretically that the space requirement of PDFA on p processing units is at most p times as much as that of the sequential B&B algorithm with the depth-first search function. Moreover, from our experimental results through simulation, it is known that the computation time of PDFA on p processing units can be resuced to less than 1/p that of the sequential B&B algorithm with the depth-first search function. We name this reduction effect in the computation time Acceleration Effect.