2012 · 50 citations · 17 references
ComputingComputer ScienceHigh-performance ComputingAlgorithmsParallel AlgorithmsParallel ComputingBranch And BoundGraphics Processing Unit ArchitectureGraphics Processing Unit ComputingGraphics Processing UnitsHardware AccelerationParallel Computing SystemsGpu AcceleratorsGpu ArchitectureGpu Parallel AlgorithmsKnapsack ProblemsParallel Branch And BoundScientific Computing On GpusSynchronizationSynchronization Mechanisms
In this paper, we propose an efficient implementation of the branch and bound method for knapsack problems on a CPU-GPU system via CUDA. Branch and bound computations can be carried out either on the CPU or on a GPU according to the size of the branch and bound list. A better management of GPUs memories, less GPU-CPU communications and better synchronization between GPU threads are proposed in this new implementation in order to increase efficiency. Indeed, a series of computational results is displayed and analyzed showing a substantial speedup on a Tesla C2050 GPU.
17