9862

Parallelization Strategies for Local Search Algorithms on Graphics Processing Units

Audrey Delevacq, Pierre Delisle, Michael Krajecki
CReSTIC, Universite de Reims Champagne-Ardenne, Reims, France
18th International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’12), 2012
@InProceedings{CReSTIC-2360,

   author={Del{‘e}vacq, Audrey and Delisle, Pierre and Krajecki, Micha{"e}l},

   title={Parallelization Strategies for Local Search Algorithms on Graphics Processing Units},

   booktitle={18th International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’12)},

   address={Las Vegas, USA},

   month={jul},

   year={2012}

}

Download Download (PDF)   View View   Source Source   

608

views

The purpose of this paper is to propose effective parallelization strategies for Local Search algorithms on Graphics Processing Units (GPU). We consider the distribution of the 3-opt neighborhood structure embedded in the Iterated Local Search framework. Three resulting approaches are evaluated and compared on both speedup and solution quality on a state-of-the-art Fermi GPU architecture. Solving instances of the Travelling Salesman Problem ranging from 100 to 3038 cities, we report speedups of up to 8.51 with solution quality similar to the best known sequential implementations and of up to 45.40 with a variable increase in tour length. The proposed experimental study highlights the influence of the pivoting rule, neighborhood size and parallelization granularity on the obtained level of performance.
VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

* * *

* * *

Follow us on Twitter

HGPU group

1863 peoples are following HGPU @twitter

Like us on Facebook

HGPU group

407 people like HGPU on Facebook

HGPU group © 2010-2016 hgpu.org

All rights belong to the respective authors

Contact us: