On scalable parallel recursive backtracking

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Daudjee, Khuzaima
dc.contributor.author Mouawad, Amer E.
dc.contributor.author Nishimura, Naomi
dc.date.accessioned 2015-12-07T13:09:47Z
dc.date.available 2015-12-07T13:09:47Z
dc.date.copyright 2015
dc.date.issued 2015-12-07
dc.identifier.issn 0743-7315 en_US
dc.identifier.uri http://hdl.handle.net/10725/2778
dc.description.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. en_US
dc.language.iso en en_US
dc.title On scalable parallel recursive backtracking en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.woa N/A en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Journal of Parallel and Distributed Computing en_US
dc.journal.volume 84 en_US
dc.article.pages 65-75 en_US
dc.keywords Parallel algorithms en_US
dc.keywords Recursive backtracking en_US
dc.keywords Load balancing en_US
dc.keywords Vertex cover en_US
dc.keywords Dominating set en_US
dc.identifier.doi http://dx.doi.org/10.1016/j.jpdc.2015.07.006 en_US
dc.identifier.ctation Abu-Khzam, F. N., Daudjee, K., Mouawad, A. E., & Nishimura, N. (2015). On scalable parallel recursive backtracking. Journal of Parallel and Distributed Computing, 84, 65-75. en_US
dc.author.email faisal.abukhzam@lau.edu.lb
dc.identifier.url http://www.sciencedirect.com/science/article/pii/S0743731515001240
dc.orcid.id https://orcid.org/0000-0001-5221-8421

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account