An easy-to-use scalable framework for parallel recursive backtracking
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 severa...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | article |
| Published: |
2013
|
| Online Access: | http://hdl.handle.net/10725/7594 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://arxiv.org/abs/1312.7626 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513482423009280 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Daudjee, Khuzaima Mouawad, Amer E. Nishimura, Naomi |
| author2_role | author author author |
| author_facet | Abu-Khzam, Faisal N. Daudjee, Khuzaima Mouawad, Amer E. Nishimura, Naomi |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Daudjee, Khuzaima Mouawad, Amer E. Nishimura, Naomi |
| dc.date.none.fl_str_mv | 2013 2018-04-26T06:36:08Z 2018-04-26T06:36:08Z 2018-04-26 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/7594 Abu-Khzam, F. N., Daudjee, K., Mouawad, A. E., & Nishimura, N. (2013). An easy-to-use scalable framework for parallel recursive backtracking. arXiv preprint arXiv:1312.7626. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://arxiv.org/abs/1312.7626 |
| dc.language.none.fl_str_mv | en |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | An easy-to-use scalable framework for parallel recursive backtracking |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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 framework for transforming almost any recursive backtracking algorithm into a parallel one. Our framework 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 this framework is the use of an indexed search tree approach that is oblivious to the problem being solved. We test our framework with parallel implementations of algorithms for the well-known Vertex Cover and Dominating Set problems. On sufficiently hard instances, experimental results show linear speedups for thousands of cores, reducing running times from days to just a few minutes. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_f189dc51cec5f46ffabdd8e2e3000c36 |
| identifier_str_mv | Abu-Khzam, F. N., Daudjee, K., Mouawad, A. E., & Nishimura, N. (2013). An easy-to-use scalable framework for parallel recursive backtracking. arXiv preprint arXiv:1312.7626. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/7594 |
| publishDate | 2013 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | An easy-to-use scalable framework for parallel recursive backtrackingAbu-Khzam, Faisal N.Daudjee, KhuzaimaMouawad, Amer E.Nishimura, NaomiSupercomputers 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 framework for transforming almost any recursive backtracking algorithm into a parallel one. Our framework 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 this framework is the use of an indexed search tree approach that is oblivious to the problem being solved. We test our framework with parallel implementations of algorithms for the well-known Vertex Cover and Dominating Set problems. On sufficiently hard instances, experimental results show linear speedups for thousands of cores, reducing running times from days to just a few minutes.Pre-printN/A2018-04-26T06:36:08Z2018-04-26T06:36:08Z20132018-04-26Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/articlehttp://hdl.handle.net/10725/7594Abu-Khzam, F. N., Daudjee, K., Mouawad, A. E., & Nishimura, N. (2013). An easy-to-use scalable framework for parallel recursive backtracking. arXiv preprint arXiv:1312.7626.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://arxiv.org/abs/1312.7626eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/75942021-03-19T10:43:13Z |
| spellingShingle | An easy-to-use scalable framework for parallel recursive backtracking Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | An easy-to-use scalable framework for parallel recursive backtracking |
| title_full | An easy-to-use scalable framework for parallel recursive backtracking |
| title_fullStr | An easy-to-use scalable framework for parallel recursive backtracking |
| title_full_unstemmed | An easy-to-use scalable framework for parallel recursive backtracking |
| title_short | An easy-to-use scalable framework for parallel recursive backtracking |
| title_sort | An easy-to-use scalable framework for parallel recursive backtracking |
| url | http://hdl.handle.net/10725/7594 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://arxiv.org/abs/1312.7626 |