Parallel Bi-objective Shortest Paths Using Weight-Balanced B-trees with Bulk Updates
Parallel Bi-objective Shortest Paths Using Weight-Balanced B-trees with Bulk Updates
复制标题
使用带有批量更新的权重平衡 B 树的并行双目标最短路径
DOI：
10.1007/978-3-319-07959-2_10
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Peter Sanders
中科院分区：
文献类型：
--
作者：
Stephan Erb;Moritz Kobitzsch;Peter Sanders
我们提出了一种实用的并行算法，用于寻找存在两个目标函数的最短路径。该算法建立在最近的一个理论结果之上，乍一看似乎不切实际。我们通过仔细地重新设计算法以实现适度的并行性，解决了由于大量前缀和计算而导致的显著常数因子开销的问题。此外，我们还开发了一个并行的权重平衡的b树数据结构，该结构有效地缓存支持批量更新。这个结果可能是独立的，并且缩小了理论结果所需的全面搜索树数据结构与顺序算法的简单优先级队列之间的差距。将我们的实现与高度调优的顺序双目标搜索进行比较，我们在16核上实现了8的加速。
We present a practical parallel algorithm for finding shortest paths in the presence of two objective functions. The algorithm builds on a recent theoretical result that on the first glance looks impractical. We address the problem of significant constant factor overheads due to numerous prefix sum computations by carefully re-engineering the algorithm for moderate parallelism. In addition, we develop a parallel weight-balanced B-tree data structure that cache efficiently supports bulk updates. This result might be of independent interest and closes the gap between the full-blown search tree data structure required by the theoretical result over the simple priority queue for the sequential algorithm. Comparing our implementation against a highly tuned sequential bi-objective search, we achieve speedups of 8 on 16 cores.
登录
查看更多内容
DOI：
10.1145/781027.781063
发表时间：
2003-06
期刊：
--
影响因子：
--
作者：
R. Hankins;J. Patel
通讯作者：
R. Hankins;J. Patel
无线网络中空洞和边界分布式检测的高效算法
DOI：
10.1007/978-3-642-20662-7_33
发表时间：
2011
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
D. Schieferdecker;M. Völker;D. Wagner
通讯作者：
D. Wagner
Euro-Par 2007 研讨会：并行处理、HPPC 2007、UNICORE Summit 2007 和 VHPC 2007，法国雷恩，2007 年 8 月 28 日至 31 日，修订后的精选论文
DOI：
10.1007/978-3-540-78474-6
发表时间：
2008
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
L. Bougé
通讯作者：
L. Bougé
STL 字典批量操作的并行化
DOI：
10.1007/978-3-540-78474-6_8
发表时间：
2007
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
Leonor Frias;J. Singler
通讯作者：
J. Singler
并行标签设置多目标最短路径搜索
DOI：
--
发表时间：
2013
期刊：
2013 IEEE 27th International Symposium on Parallel and Distributed Processing
影响因子：
--
作者：
P. Sanders;L. Mandow
通讯作者：
L. Mandow