多维二分查找与分割算法并行化技术研究

摘要

很多实际问题都可归结为需求空间探索问题，多维二分查找与分割算法利用需求空间的单调性可以快速确定问题的需求空间，然而该算法计算量和存储量很大，难以在单机环境下在额定的时间内完成仿真实验。本文针对串行多维二分查找与分割算法运行时间长的问题，挖掘其内在的并行性，提出了并行多维二分查找与分割算法，根据算法过程对加速比进行了推导，并在PC集群环境下进行了实现和测试，理论和实验结果表明并行算法具有可观的加速比和并行效率，如3个计算节点时可达2.338的加速比，加速比随计算节点数目呈线性增长，而并行效率维持在0.7左右。