Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

On scalable parallel recursive backtracking

Abu-Khzam, Faisal N., Daudjee, Khuzaima, Mouawad, Amer E. and Nishimura, Naomi (2015). On scalable parallel recursive backtracking. Journal of Parallel and Distributed Computing,84(October):65-75.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

IRMA ID 83393865xPUB228
Title On scalable parallel recursive backtracking
Author Abu-Khzam, Faisal N.
Daudjee, Khuzaima
Mouawad, Amer E.
Nishimura, Naomi
Journal Name Journal of Parallel and Distributed Computing
Publication Date 2015
Volume Number 84
Issue Number October
ISSN 0743-7315   (check CDU catalogue open catalogue search in new window)
Scopus ID 2-s2.0-84938702239
Start Page 65
End Page 75
Total Pages 11
Place of Publication United States
Publisher Academic Press
Field of Research ENGINEERING
TECHNOLOGY
HERDC Category C1 - Journal Article (DIISR)
Abstract Supercomputers are equipped with an increasingly large number of cores to use computational power as a way of solving problems that are otherwise intractable. Unfortunately, getting serial algorithms to run in parallel to take advantage of these computational resources remains a challenge for several application domains. Many parallel algorithms can scale to only hundreds of cores. The limiting factors of such algorithms are usually communication overhead and poor load balancing. Solving NP-hard graph problems to optimality using exact algorithms is an example of an area in which there has so far been limited success in obtaining large scale parallelism. Many of these algorithms use recursive backtracking as their core solution paradigm. In this paper, we propose a lightweight, easy-to-use, scalable approach for transforming almost any recursive backtracking algorithm into a parallel one. Our approach incurs minimal communication overhead and guarantees a load-balancing strategy that is implicit, i.e., does not require any problem-specific knowledge. The key idea behind our approach is the use of efficient traversal operations on an indexed search tree that is oblivious to the problem being solved. We test our approach with parallel implementations of algorithms for the well-known Vertex Cover and Dominating Set problems. On sufficiently hard instances, experimental results show nearly linear speedups for thousands of cores, reducing running times from days to just a few minutes.
Keywords Parallel algorithms
Recursive backtracking
Load balancing
Vertex cover
Dominating set
DOI http://dx.doi.org/10.1016/j.jpdc.2015.07.006   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 176 Abstract Views  -  Detailed Statistics
Created: Tue, 26 Jul 2016, 12:40:40 CST