On scalable 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...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , , |
| التنسيق: | article |
| منشور في: |
2015
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/2778 http://dx.doi.org/10.1016/j.jpdc.2015.07.006 http://www.sciencedirect.com/science/article/pii/S0743731515001240 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513459374260224 |
|---|---|
| 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 | 2015-12-07T13:09:47Z 2015-12-07T13:09:47Z 2015 2015-12-07 |
| dc.identifier.none.fl_str_mv | 0743-7315 http://hdl.handle.net/10725/2778 http://dx.doi.org/10.1016/j.jpdc.2015.07.006 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. http://www.sciencedirect.com/science/article/pii/S0743731515001240 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Journal of Parallel and Distributed Computing |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | On scalable 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 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_75aba4b65be41777269e57cdadb45d23 |
| identifier_str_mv | 0743-7315 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. |
| 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/2778 |
| publishDate | 2015 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | On scalable 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 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.PublishedN/A2015-12-07T13:09:47Z2015-12-07T13:09:47Z20152015-12-07Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article0743-7315http://hdl.handle.net/10725/2778http://dx.doi.org/10.1016/j.jpdc.2015.07.006Abu-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.http://www.sciencedirect.com/science/article/pii/S0743731515001240enJournal of Parallel and Distributed Computinginfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/27782018-05-21T09:28:03Z |
| spellingShingle | On scalable parallel recursive backtracking Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | On scalable parallel recursive backtracking |
| title_full | On scalable parallel recursive backtracking |
| title_fullStr | On scalable parallel recursive backtracking |
| title_full_unstemmed | On scalable parallel recursive backtracking |
| title_short | On scalable parallel recursive backtracking |
| title_sort | On scalable parallel recursive backtracking |
| url | http://hdl.handle.net/10725/2778 http://dx.doi.org/10.1016/j.jpdc.2015.07.006 http://www.sciencedirect.com/science/article/pii/S0743731515001240 |