首页> 美国政府科技报告 >Tight Upper Bound for the Speed-Up of Parallel Best-First Branch-and-Bound Algorithms

【24h】

Tight Upper Bound for the Speed-Up of Parallel Best-First Branch-and-Bound Algorithms

机译：用于加速并行最佳分支定界算法的紧上界

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

Most previous studies of the speedup of parallel branch-and-bound algorithms are based on the amount of work done in the parallel case and in the sequential case. Any evaluation of a parallel algorithm should include both the execution time and the synchronization delay. In this paper, a finite population queueing model is used to capture the synchronization delay in parallel branch-and-bound algorithms and to quantitatively predict the behavior of their speedup. A program to solve the Traveling Salesman Problem was written on a BBN Butterfly multiprocessor to empirically demonstrate the credibility of this theoretical analysis. Finally, we note that similar analyses can be applied to evaluate parallel AI systems in which processes communicate through a shared global database.

著录项

作者
Huang, S. R.; Davis, L. S.;
展开▼
作者单位

展开▼
年度 1987
页码 p.1-26
总页数 26
原文格式 PDF
正文语种 eng
中图分类工业技术;
关键词
Parallel processing; Algorithms; Queueling theory; Parallel orientation; Sequences; Delay;

机译：并行处理;算法; Queueling理论;并行定向;序列;延迟;

相似文献

外文文献
中文文献
专利

1. A parallel branch-and-bound algorithm to compute a tighter tardiness bound for preemptive global EDF [J] . Leoncini Mauro, Montangero Manuela, Valente Paolo Real-time systems . 2019,第2期

机译：一种并行分支定界算法，可为抢先全局EDF计算更严格的延迟
2. An improved best-first branch-and-bound algorithm for constrained two-dimensional guillotine cutting problems [J] . K. Yoon S. Ahn, M. Kang International Journal of Production Research . 2013,第5a6期

机译：约束二维断头台切割问题的改进的最佳第一分支定界算法
3. An improved best-first branch-and-bound algorithm for unconstrained two-dimensional cutting problems [J] . M. Kang, K. Yoon International Journal of Production Research . 2011,第15a17期

机译：改进的最优优先分支定界算法求解无约束二维切割问题
4. A branch-and-bound algorithm with cyclic best-first search for the permutation flow shop scheduling problem [C] . Marcus Ritt IEEE International Conference on Automation Science and Engineering . 2016

机译：具有循环最佳优先搜索的置换流水车间调度问题的分支定界算法
5. A fast parallel algorithm to numerically compute the Markov renewal kernel via tight lower and upper bounds. [D] . Elkins, Debra Ann. 2000

机译：一种快速的并行算法，用于通过严格的上下限来数值计算马尔可夫更新内核。
6. Monitoring ratio of carbon to nitrogen (C/N) in wheat and barley leaves by using spectral slope features with branch-and-bound algorithm [O] . Xingang Xu, Guijun Yang, Xiaodong Yang, -1

机译：利用分枝定界算法利用光谱斜率特征监测小麦和大麦叶片碳氮比（C / N）
7. Constrained Two-Dimensional Cutting Stock Problems -- A Best-First Branch-and-Bound Algorithm [O] . Van-Dat Cung, Mhand Hifi, Bertrand Le Cun 1997

机译：受约束的二维切割物料问题-最佳优先分支定界算法
8. Anomalies in Parallel Branch-and-Bound Algorithms [R] . Lai, T. H., Sahni, S. 1982

机译：并行分支定界算法的异常

Tight Upper Bound for the Speed-Up of Parallel Best-First Branch-and-Bound Algorithms

摘要

著录项

相似文献

相关主题

期刊订阅