Title :
Parallel Branch and Bound on a CPU-GPU System
Author :
Boukedjar, Abdelamine ; Lalami, Mohamed Esseghir ; El-Baz, Didier
Author_Institution :
LAAS, Toulouse, France
Abstract :
Hybrid implementation via CUDA of a branch and bound method for knapsack problems is proposed. Branch and bound computations can be carried out either on the CPU or on the GPU according to the size of the branch and bound list, i.e. the number of nodes. Tests are carried out on a Tesla C2050 GPU. A first series of computational results showing a substantial speedup is displayed and analyzed.
Keywords :
graphics processing units; knapsack problems; parallel architectures; tree searching; CPU-GPU system; CUDA; knapsack problems; parallel branch and bound; Computer architecture; Graphics processing unit; Instruction sets; Kernel; Optimization; Parallel algorithms; Upper bound; CUDA; branch and bound; combinatorial optimization; computing; hybrid computing; knapsack problems;
Conference_Titel :
Parallel, Distributed and Network-Based Processing (PDP), 2012 20th Euromicro International Conference on
Conference_Location :
Garching
Print_ISBN :
978-1-4673-0226-5
DOI :
10.1109/PDP.2012.23
