A GPU-Based Backtracking Algorithm for Permutation Combinatorial Problems

被引：5

作者：

Pessoa, Tiago Carneiro ^{[1
]}

Gmys, Jan ^{[2
,3
]}

Melab, Nouredine ^{[3
]}

de Carvalho Junior, Francisco Heron ^{[1
]}

Tuyttens, Daniel ^{[2
]}

机构：

[1] Univ Fed Ceara, ParGO Res Grp Parallelism Optimizat & Graphs, Ciencia Computacao, Fortaleza, Ceara, Brazil

[2] Univ Mons, Math & Operat Res Dept MARO, Mons, Belgium

[3] Univ Lille 1, CNRS, CRIStAL, INRIA Lille Nord Europe, Cite Sci, F-59655 Villeneuve Dascq, France

来源：

ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, ICA3PP 2016 | 2016年 / 10048卷

关键词：

GPU computing; Backtracking; Depth-first search; Load balancing; Work stealing; SEARCH;

D O I：

10.1007/978-3-319-49583-5_24

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This work presents a GPU-based backtracking algorithm for permutation combinatorial problems based on the Integer-Vector-Matrix (IVM) data structure. IVM is a data structure dedicated to permutation combinatorial optimization problems. In this algorithm, the load balancing is performed without intervention of the CPU, inside a work stealing phase invoked after each node expansion phase. The proposed work stealing approach uses a virtual n-dimensional hypercube topology and a triggering mechanism to reduce the overhead incurred by dynamic load balancing. We have implemented this new algorithm for solving instances of the Asymmetric Travelling Salesman Problem by implicit enumeration, a scenario where the cost of node evaluation is low, compared to the overall search procedure. Experimental results show that the dynamically load balanced IVM-algorithm reaches speed-ups up to 17x over a serial implementation using a bitset-data structure and up to 2x over its GPU counterpart.

引用

页码：310 / 324

页数：15

共 18 条

[1]

Burtscher M., 2012, 2012 IEEE International Symposium on Workload Characterization (IISWC 2012), P141, DOI 10.1109/IISWC.2012.6402918

[2]

Carneiro T., 2011, 2011 Proceedings of 23rd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD 2011), P41, DOI 10.1109/SBAC-PAD.2011.20

[3]

Carneiro T, 2012, NVIDIAS GCDF GPU COM

[4]

Cirasella J., 2001, The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests, volume 2153 of Lecture Notes in Computer Science, V2153, P32, DOI DOI 10.1007/3-540-44808-X

[5]

Cook W., 2012, In pursuit of the traveling salesman: mathematics at the limits of computation

[6] Regularity versus Load-Balancing on GPU for treefix computations [J].

Defour, David ;

Marin, Manuel .

2013 INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE, 2013, 18 :309-318

[7]

Feinbube Frank, 2010, Proceedings of the Ninth International Symposium on Parallel and Distributed Computing (ISPDC 2010), P63, DOI 10.1109/ISPDC.2010.22

[8]

Gmys J., 2016, PARALLEL COMPUT

[9]

Jenkins J, 2011, LECT NOTES COMPUT SC, V6853, P425, DOI 10.1007/978-3-642-23397-5_42

[10] RANDOMIZED PARALLEL ALGORITHMS FOR BACKTRACK SEARCH AND BRANCH-AND-BOUND COMPUTATION [J].

KARP, RM ;

ZHANG, YJ .

JOURNAL OF THE ACM, 1993, 40 (03) :765-789

← 1 2 →