publication . Conference object . Other literature type . Part of book or chapter of book . 2017

Towards Generic Scalable Parallel Combinatorial Search

Archibald, Blair; Maier, Patrick; Stewart, Robert; Trinder, Phil; De Beule, Jan;
Open Access English
  • Published: 23 Jul 2017
Abstract
Combinatorial search problems in mathematics, e.g. in finite geometry, are notoriously hard; a state-of-the-art backtracking search algorithm can easily take months to solve a single problem. There is clearly demand for parallel combinatorial search algorithms scaling to hundreds of cores and beyond. However, backtracking combinatorial searches are challenging to parallelise due to their sensitivity to search order and due to the their irregularly shaped search trees. Moreover, scaling parallel search to hundreds of cores generally requires highly specialist parallel programming expertise.\ud \ud This paper proposes a generic scalable framework for solving hard ...
Subjects
free text keywords: Best-first search, Beam stack search, Task parallelism, Computer science, Beam search, Algorithmic skeleton, Combinatorial search, Backtracking, Parallel computing, Search algorithm, Theoretical computer science
26 references, page 1 of 2

[1] Enrique Alba, Francisco Almeida, Maria J. Blesa, J. Cabeza, Carlos CoŠa, Manuel D´ıaz, Isabel Dorta, Joaquim Gabarro´, Coromoto Leo´n, J. Luna, Luz Marina Moreno, C. Pablos, Jordi Petit, Ange´lica Rojas, and Fatos Xhafa. 2002. MALLBA: A Library of Skeletons for Combinatorial Optimisation. In Euro-Par 2002, Paderborn, Germany (LNCS 2400). Springer, 927-932. DOI:hŠp://dx.doi.org/10.1007/ 3-540-45706-2 132

[2] Blair Archibald, Patrick Maier, Robert Stewart, Phil Trinder, and Jan De Beule. 2017. Towards Generic Scalable Parallel Combinatorial Search [Data Collection]. (2017). hŠp://dx.doi.org/10.5525/gla.researchdata.430

[3] Blair Archibald, Ciaran McCreesh, Patrick Maier, Robert Stewart, and Phil Trinder. 2017. Replicable Parallel Branch and Bound Search. (2017). arXiv:1703.05647

[4] John Bamberg, Anton BeŠen, Philippe Cara, Jan De Beule, Michel Lavrauw, and Max Neunho¨‚er. 2015. FinInG - Finite Incidence Geometry, Version 1.3. hŠp://cage.ugent.be/€ning

[5] Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. 1996. Cilk: An Ecient Multithreaded Runtime System. J. Parallel and Distrib. Comput. 37, 1 (1996), 55-69. DOI: hŠp://dx.doi.org/10.1006/jpdc.1996.0107 [OpenAIRE]

[6] F. Buekenhout (Ed.). 1995. Handbook of Incidence Geometry. North-Holland, Amsterdam.

[7] Murray Cole. 1991. Algorithmic Skeletons: Structured Management of Parallel Computation. MIT Press.

[8] Matjaz Depolli, Janez Konc, Kati Rozman, Roman Trobec, and Dusanka Janezic. 2013. Exact Parallel Maximum Clique Algorithm for General and Protein Graphs. Journal of Chemical Information and Modeling 53, 9 (2013), 2217-2228. DOI: hŠp://dx.doi.org/10.1021/ci4002525 [OpenAIRE]

[9] A. Djerrah, Bertrand Le Cun, Van-Dat Cung, and Catherine Roucairol. 2006. Bob++: Framework for Solving Optimization Problems with Branch-and-Bound methods. In High Performance Distributed Computing, HPDC-15, Paris, France. IEEE, 369-370. DOI:hŠp://dx.doi.org/10.1109/HPDC.2006.1652188

[10] J. Falcou, J. Se´rot, T. Chateau, and J.T. Lapreste´. 2006. ‹a‚: ecient C++ design for parallel skeletons. Parallel Comput. 32, 7-8 (2006), 604 - 615. DOI: hŠp://dx.doi.org/10.1016/j.parco.2006.06.001 [OpenAIRE]

[11] Œierry Gautier, Xavier Besseron, and Laurent Pigeon. 2007. KAAPI: A thread scheduling runtime system for data ƒow computations on cluster of multiprocessors. In Parallel Symbolic Computation, PASCO 2007, London, Ontario, Canada. ACM, 15-23. DOI:hŠp://dx.doi.org/10.1145/1278177.1278182

[12] Yi Guo, Jisheng Zhao, Vincent Cave´, and Vivek Sarkar. 2010. SLAW: A scalable locality-aware adaptive work-stealing scheduler. In 2010 IEEE International Symposium on Parallel Distributed Processing, IPDPS 2010, Atlanta, Georgia, USA. 1-12. DOI:hŠp://dx.doi.org/10.1109/IPDPS.2010.5470425 [OpenAIRE]

[13] David J. Johnson and Michael A. Trick (Eds.). Cliques, Coloring, and Satis€ability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. American Mathematical Society.

[14] Hartmut Kaiser, Œomas Heller, Bryce Adelstein-Lelbach, Adrian Serio, and Dietmar Fey. 2014. HPX: A Task Based Programming Model in a Global Address Space. In Partitioned Global Address Space Programming Models, PGAS 2014, Eugene, Oregon, USA. ACM, Article 6. DOI:hŠp://dx.doi.org/10.1145/2676870. 2676883

[15] Daniel Kunkle. Roomy: A System for Space Limited Computations. In Parallel Symbolic Computation, PASCO 2010, Grenoble, France. ACM, 22-25. DOI:hŠp: //dx.doi.org/10.1145/1837210.1837216

26 references, page 1 of 2
Abstract
Combinatorial search problems in mathematics, e.g. in finite geometry, are notoriously hard; a state-of-the-art backtracking search algorithm can easily take months to solve a single problem. There is clearly demand for parallel combinatorial search algorithms scaling to hundreds of cores and beyond. However, backtracking combinatorial searches are challenging to parallelise due to their sensitivity to search order and due to the their irregularly shaped search trees. Moreover, scaling parallel search to hundreds of cores generally requires highly specialist parallel programming expertise.\ud \ud This paper proposes a generic scalable framework for solving hard ...
Subjects
free text keywords: Best-first search, Beam stack search, Task parallelism, Computer science, Beam search, Algorithmic skeleton, Combinatorial search, Backtracking, Parallel computing, Search algorithm, Theoretical computer science
26 references, page 1 of 2

[1] Enrique Alba, Francisco Almeida, Maria J. Blesa, J. Cabeza, Carlos CoŠa, Manuel D´ıaz, Isabel Dorta, Joaquim Gabarro´, Coromoto Leo´n, J. Luna, Luz Marina Moreno, C. Pablos, Jordi Petit, Ange´lica Rojas, and Fatos Xhafa. 2002. MALLBA: A Library of Skeletons for Combinatorial Optimisation. In Euro-Par 2002, Paderborn, Germany (LNCS 2400). Springer, 927-932. DOI:hŠp://dx.doi.org/10.1007/ 3-540-45706-2 132

[2] Blair Archibald, Patrick Maier, Robert Stewart, Phil Trinder, and Jan De Beule. 2017. Towards Generic Scalable Parallel Combinatorial Search [Data Collection]. (2017). hŠp://dx.doi.org/10.5525/gla.researchdata.430

[3] Blair Archibald, Ciaran McCreesh, Patrick Maier, Robert Stewart, and Phil Trinder. 2017. Replicable Parallel Branch and Bound Search. (2017). arXiv:1703.05647

[4] John Bamberg, Anton BeŠen, Philippe Cara, Jan De Beule, Michel Lavrauw, and Max Neunho¨‚er. 2015. FinInG - Finite Incidence Geometry, Version 1.3. hŠp://cage.ugent.be/€ning

[5] Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. 1996. Cilk: An Ecient Multithreaded Runtime System. J. Parallel and Distrib. Comput. 37, 1 (1996), 55-69. DOI: hŠp://dx.doi.org/10.1006/jpdc.1996.0107 [OpenAIRE]

[6] F. Buekenhout (Ed.). 1995. Handbook of Incidence Geometry. North-Holland, Amsterdam.

[7] Murray Cole. 1991. Algorithmic Skeletons: Structured Management of Parallel Computation. MIT Press.

[8] Matjaz Depolli, Janez Konc, Kati Rozman, Roman Trobec, and Dusanka Janezic. 2013. Exact Parallel Maximum Clique Algorithm for General and Protein Graphs. Journal of Chemical Information and Modeling 53, 9 (2013), 2217-2228. DOI: hŠp://dx.doi.org/10.1021/ci4002525 [OpenAIRE]

[9] A. Djerrah, Bertrand Le Cun, Van-Dat Cung, and Catherine Roucairol. 2006. Bob++: Framework for Solving Optimization Problems with Branch-and-Bound methods. In High Performance Distributed Computing, HPDC-15, Paris, France. IEEE, 369-370. DOI:hŠp://dx.doi.org/10.1109/HPDC.2006.1652188

[10] J. Falcou, J. Se´rot, T. Chateau, and J.T. Lapreste´. 2006. ‹a‚: ecient C++ design for parallel skeletons. Parallel Comput. 32, 7-8 (2006), 604 - 615. DOI: hŠp://dx.doi.org/10.1016/j.parco.2006.06.001 [OpenAIRE]

[11] Œierry Gautier, Xavier Besseron, and Laurent Pigeon. 2007. KAAPI: A thread scheduling runtime system for data ƒow computations on cluster of multiprocessors. In Parallel Symbolic Computation, PASCO 2007, London, Ontario, Canada. ACM, 15-23. DOI:hŠp://dx.doi.org/10.1145/1278177.1278182

[12] Yi Guo, Jisheng Zhao, Vincent Cave´, and Vivek Sarkar. 2010. SLAW: A scalable locality-aware adaptive work-stealing scheduler. In 2010 IEEE International Symposium on Parallel Distributed Processing, IPDPS 2010, Atlanta, Georgia, USA. 1-12. DOI:hŠp://dx.doi.org/10.1109/IPDPS.2010.5470425 [OpenAIRE]

[13] David J. Johnson and Michael A. Trick (Eds.). Cliques, Coloring, and Satis€ability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. American Mathematical Society.

[14] Hartmut Kaiser, Œomas Heller, Bryce Adelstein-Lelbach, Adrian Serio, and Dietmar Fey. 2014. HPX: A Task Based Programming Model in a Global Address Space. In Partitioned Global Address Space Programming Models, PGAS 2014, Eugene, Oregon, USA. ACM, Article 6. DOI:hŠp://dx.doi.org/10.1145/2676870. 2676883

[15] Daniel Kunkle. Roomy: A System for Space Limited Computations. In Parallel Symbolic Computation, PASCO 2010, Grenoble, France. ACM, 22-25. DOI:hŠp: //dx.doi.org/10.1145/1837210.1837216

26 references, page 1 of 2
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue