首页> 外文期刊>Concurrency and computation: practice and experience >Work stealing with private integer–vector–matrix data structure for multi-core branch-and-bound algorithms
【24h】

Work stealing with private integer–vector–matrix data structure for multi-core branch-and-bound algorithms

机译:使用私有整数-矢量矩阵数据结构进行窃取,以实现多核分支定界算法

获取原文
获取原文并翻译 | 示例

摘要

In this paper, the focus is put on multi-core branch-and-bound algorithms for solving large-scale permutation-based optimization problems. We investigate five work stealing (WS) strategies with a new data structure called integer–vector–matrix (IVM). In these strategies, each thread has a private IVM allowing the local management of a set of subproblems enumerated using a factorial system. The WS strategies differ in the way the victim thread is selected and the granularity of stolen work units (intervals of factoradics). To assess the efficiency of the private IVM-based WS approach, the five WS strategies have been extensively experimented on the flowshop scheduling permutation problem and compared with their conventional linked-list-based counterparts. The obtained results demonstrate that the IVM-based WS outperforms the linked-list-based one in terms of CPU time, memory usage and number of performed WS operations. Copyright © 2016 John Wiley & Sons, Ltd.
机译:在本文中,重点放在解决大规模基于排列的优化问题的多核分支定界算法上。我们使用一种称为整数矢量矩阵(IVM)的新数据结构研究了五种工作窃取(WS)策略。在这些策略中,每个线程都有一个专用的IVM,允许对使用子系统枚举的一组子问题进行本地管理。 WS策略在选择受害者线程的方式和被盗工作单元的粒度(因数间隔)方面有所不同。为了评估基于私有IVM的WS方法的效率,已经对Flowshop调度排列问题进行了广泛的5种WS策略实验,并将其与基于常规链表的对应策略进行了比较。获得的结果表明,基于IVM的WS在CPU时间,内存使用率和执行的WS操作数量方面胜过基于链表的WS。版权所有©2016 John Wiley&Sons,Ltd.

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号