10564

A GPU Implementation of Parallel Constraint-based Local Search

Alejandro Arbelaez, Philippe Codognet
JFLI, University of Tokyo
Techniques foR Implementing Constraint programming Systems (TRICS), 2013
@article{arbelaez2013gpu,

   title={A GPU Implementation of Parallel Constraint-based Local Search},

   author={Arbelaez, Alejandro and Codognet, Philippe},

   year={2013}

}

Download Download (PDF)   View View   Source Source   

618

views

In this paper we study the performance of constraint-based local search solvers on a GPU. The massively parallel architecture of the GPU makes it possible to explore parallelism at two different levels inside the local search algorithm. First, by executing multiple copies of the algorithm in a multi-walk manner and, second, by evaluating large neighborhoods in parallel in a single-walk manner. Experiments on three well-known problem benchmarks indicate that the current GPU implementation is up to 17 times faster than a well-tuned sequential algorithm implemented on a desktop computer.
VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

* * *

* * *

Follow us on Twitter

HGPU group

1895 peoples are following HGPU @twitter

Like us on Facebook

HGPU group

421 people like HGPU on Facebook

HGPU group © 2010-2016 hgpu.org

All rights belong to the respective authors

Contact us: