Heterogeneous cluster computing for many-task exact optimization - Application to permutation problems. (Optimisation massivement multi-tâche sur grappes de calcul hétérogènes - Application aux problèmes de permutation)
Heterogeneous cluster computing for many-task exact optimization - Application to permutation problems. (Optimisation massivement multi-tâche sur grappes de calcul hétérogènes - Application aux problèmes de permutation)
复制标题
DOI：
--
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
Jan Gmys
中科院分区：
文献类型：
--
作者：
Jan Gmys
分支定界（B&B）是一种常用的树搜索方法，用于求解组合优化问题。然而，在实践中，只有很小的问题实例可以在顺序计算机上解决，因为B&B生成的通常会生成大量的子问题。为了解决大型COP问题，我们重新审视了在大型异构集群之上，集成多核CPU、众核处理器和GPU的大规模并行B&B的设计和实现。为了有效地存储和管理的子问题的原始数据结构（IVM）专用于排列问题。由于B&B树的高度不规则和不可预测的形状，并行探索进程之间的动态负载平衡是本文要解决的主要问题之一。基于对搜索空间的区间压缩编码，提出了多核和GPU的工作窃取策略，以及分布式内存多CPU/多GPU系统的负载均衡分层方法.三个置换问题，流水车间调度问题（FSP），二次分配问题（QAP）和n皇后难题问题被用作测试用例。在9个小时内，估计顺序执行时间为22年的FSP实例的分辨率证明了所提出的算法在由36个GPU组成的集群上的可扩展性。
Branch-and-Bound (B&B) is a frequently used tree-search exploratory method for the exact resolution of combinatorial optimization problems (COPs). However, in practice, only small problem instances can be solved on a sequential computer, as B&B generates often generates a huge amount of subproblems to be evaluated. In order to solve large COPs, we revisit the design and implementation of massively parallel B&B on top of large heterogeneous clusters, integrating multi-core CPUs, many-core processors and GPUs. For the efficient storage and management of subproblems an original data structure (IVM) dedicated to permutation problems is used. Because of the highly irregular and unpredictable shape of the B&B tree, dynamic load balancing between parallel exploration processes is one of the main issues addressed in this thesis. Based on a compact encoding of the search space in the form of intervals, work stealing strategies for multi-core and GPU are proposed, as well as hierarchical approaches for load balancing in distributed memory multi-CPU/multi-GPU systems. Three permutation problems, the Flowshop Scheduling Problem (FSP), the Quadratic Assignment Problem (QAP) and the n-Queens puzzle problem are used as test-cases. The resolution, in 9 hours, of a FSP instance with an estimated sequential execution time of 22 years demonstrates the scalability of the proposed algorithms on a cluster composed of 36 GPUs.