{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:44:38Z","timestamp":1740123878137,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T00:00:00Z","timestamp":1670371200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T00:00:00Z","timestamp":1670371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N007565","EP\/P006434"],"award-info":[{"award-number":["EP\/N007565","EP\/P006434"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Exact combinatorial search is essential to a wide range of important applications, and there are many large problems that need to be solved quickly. Searches are extremely challenging to parallelise due to a combination of factors, e.g. searches are non-deterministic, dynamic pruning changes the workload, and search tasks have very different runtimes. YewPar is a C++\/HPX framework that generalises parallel search by providing a range of sophisticated search skeletons.This paper demonstrates <jats:italic>generic<\/jats:italic> high performance combinatorial search, i.e. that a variety of exact combinatorial searches can be easily parallelised for HPC using YewPar. We present a new mechanism for profiling key aspects of YewPar parallel combinatorial search, and demonstrate its value. We exhibit, for the first time, generic exact combinatorial searches at HPC scale. We baseline YewPar against state-of-the-art sequential C++ and C++\/OpenMP implementations. We demonstrate that deploying YewPar on an HPC system can dramatically reduce the runtime of large problems, e.g.\u00a0from days to just 100s. The maximum relative speedups we achieve for an enumeration search are near-linear up to 195(6825) compute-nodes(workers), super-linear for an optimisation search on up to 128(4480) (pruning reduces the workload), and sub-linear for decision searches on up to 64(2240) compute-nodes(workers).<\/jats:p>","DOI":"10.1007\/s10766-022-00744-3","type":"journal-article","created":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T17:04:53Z","timestamp":1670432693000},"page":"83-106","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generic Exact Combinatorial Search at HPC Scale"],"prefix":"10.1007","volume":"51","author":[{"given":"Ruairidh","family":"MacGregor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Blair","family":"Archibald","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phil","family":"Trinder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,7]]},"reference":[{"key":"744_CR1","doi-asserted-by":"crossref","unstructured":"Alba, E., et\u00a0al.: MALLBA: a library of skeletons for combinatorial optimisation. In: Euro-Par, Paderborn, Germany, August, 2002, Proceedings (2002)","DOI":"10.1007\/3-540-45706-2_132"},{"key":"744_CR2","unstructured":"Archibald, B.: Skeletons for Exact Combinatorial Search at Scale. Ph.D. thesis, University of Glasgow (2018) http:\/\/theses.gla.ac.uk\/id\/eprint\/31000"},{"key":"744_CR3","volume-title":"Implementing YewPar: A Framework for Parallel Tree Search","author":"B Archibald","year":"2019","unstructured":"Archibald, B., Maier, P., Stewart, R., Trinder, P.: Implementing YewPar: A Framework for Parallel Tree Search. Euro-Par, Gottingen (2019)"},{"key":"744_CR4","doi-asserted-by":"crossref","unstructured":"Archibald, B., et\u00a0al.: Sequential and parallel solution-biased search for subgraph algorithms. In: CPAIOR 16th Thessaloniki, Greece, June 2019 (2019)","DOI":"10.1007\/978-3-030-19212-9_2"},{"key":"744_CR5","doi-asserted-by":"crossref","unstructured":"Archibald, B., et\u00a0al.: YewPar: skeletons for exact combinatorial search. In: PPoPP\u201920:, San Diego, California, USA, February, 2020. ACM (2020)","DOI":"10.1145\/3332466.3374537"},{"key":"744_CR6","volume-title":"Maximality Properties in Numerical Semigroups and Applications to One-Dimensional Analytically Irreducible Local Domains","author":"V Barucci","year":"1997","unstructured":"Barucci, V., et al.: Maximality Properties in Numerical Semigroups and Applications to One-Dimensional Analytically Irreducible Local Domains, vol. 598. American Mathematical Society, Providence (1997)"},{"issue":"301","key":"744_CR7","doi-asserted-by":"publisher","first-page":"2553","DOI":"10.1090\/mcom\/3075","volume":"85","author":"J Fromentin","year":"2016","unstructured":"Fromentin, J., Hivert, F.: Exploring the tree of numerical semigroups. Am. Math. Comput. 85(301), 2553\u20132568 (2016)","journal-title":"Am. Math. Comput."},{"key":"744_CR8","unstructured":"Galea, F., Le\u00a0Cun, B.: Bob++: a framework for exact combinatorial optimization methods on parallel machines. In: International Conference High Performance Computing and Simulation (HPCS) (2007)"},{"issue":"8","key":"744_CR9","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/3107239","volume":"60","author":"MJH Heule","year":"2017","unstructured":"Heule, M.J.H., Kullmann, O.: The science of brute force. Commun. ACM 60(8), 70\u201379 (2017)","journal-title":"Commun. ACM"},{"key":"744_CR10","doi-asserted-by":"crossref","unstructured":"Johnson, D.J., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October, 1993. American Mathematical Society (1996)","DOI":"10.1090\/dimacs\/026"},{"key":"744_CR11","doi-asserted-by":"crossref","unstructured":"Kaiser, H., et\u00a0al.: HPX: A Task Based Programming Model in a Global Address Space. In: ICPGASPM 2014, Eugene, OR, USA, Oct. 2014 (2014)","DOI":"10.1145\/2676870.2676883"},{"key":"744_CR12","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-030-49432-2_3","volume-title":"Cloud Computing and Services Science\u20139th International Conference, CLOSER 2019, Heraklion, Crete, Greece, May 2\u20134, 2019, Revised Selected Papers. Communications in Computer and Information Science","author":"S Kehrer","year":"2019","unstructured":"Kehrer, S., Blochinger, W.: Development and operation of elastic parallel tree search applications using TASKWORK. In: Ferguson, D., Mu\u00f1oz, V.M., Pahl, C., Helfert, M. (eds.) Cloud Computing and Services Science\u20139th International Conference, CLOSER 2019, Heraklion, Crete, Greece, May 2\u20134, 2019, Revised Selected Papers. Communications in Computer and Information Science, vol. 1218, pp. 42\u201365. Springer, Berlin (2019). https:\/\/doi.org\/10.1007\/978-3-030-49432-2_3"},{"key":"744_CR13","first-page":"38","volume":"29","author":"A Klein","year":"2011","unstructured":"Klein, A., Storme, L.: Applications of finite geometry in coding theory and cryptography. Inf. Secur. Cod. Theory Rel. Comb. 29, 38\u201358 (2011)","journal-title":"Inf. Secur. Cod. Theory Rel. Comb."},{"key":"744_CR14","doi-asserted-by":"publisher","unstructured":"Knizikevi\u010dius, I., Trinder, P., Archibald, B., Yan, J.: Parallel flowshop in YewPar (2022). https:\/\/doi.org\/10.48550\/ARXIV.2207.06902","DOI":"10.48550\/ARXIV.2207.06902"},{"key":"744_CR15","unstructured":"Knizikevi\u010dius, I., Trinder, P., Archibald, B., Yan, J.: Parallel Flowshop in YewPar. arXiv preprint arXiv:2207.06902 (2022)"},{"key":"744_CR16","doi-asserted-by":"publisher","unstructured":"MacGregor, R.: Generic High Performance Exact Combinatorial Search [Data Repository]. https:\/\/doi.org\/10.5281\/zenodo.4270336","DOI":"10.5281\/zenodo.4270336"},{"key":"744_CR17","unstructured":"Maher, S.J., Ralphs, T.K., Shinano, Y.: Assessing the effectiveness of (parallel) branch-and-bound algorithms. arXiv preprint arXiv:2104.10025 (2021)"},{"key":"744_CR18","unstructured":"McCreesh, C.: Solving hard subgraph problems in parallel. Ph.D. thesis, University of Glasgow (2017)"},{"key":"744_CR19","unstructured":"McCreesh, C.: Sequential MCsa1 Maximum Clique Implementation (2018). https:\/\/github.com\/ciaranm\/sicsa-multicore-challenge-iii\/c++\/"},{"issue":"4","key":"744_CR20","doi-asserted-by":"publisher","first-page":"618","DOI":"10.3390\/a6040618","volume":"6","author":"C McCreesh","year":"2013","unstructured":"McCreesh, C., Prosser, P.: Multi-threading a state-of-the-art maximum clique algorithm. Algorithms 6(4), 618\u2013635 (2013)","journal-title":"Algorithms"},{"key":"744_CR21","doi-asserted-by":"publisher","DOI":"10.1145\/2742359","author":"C McCreesh","year":"2015","unstructured":"McCreesh, C., Prosser, P.: The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound. TOPC (2015). https:\/\/doi.org\/10.1145\/2742359","journal-title":"TOPC"},{"key":"744_CR22","doi-asserted-by":"publisher","unstructured":"McCreesh, C., Prosser, P., Trimble, J.: The glasgow subgraph solver: Using constraint programming to tackle hard subgraph isomorphism problem variants. In: Gadducci, F., Kehrer, T. (eds.) Graph Transformation\u201413th International Conference, ICGT 2020, Held as Part of STAF 2020, Bergen, Norway, June 25\u201326, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12150, pp. 316\u2013324. Springer, Berlin (2020). https:\/\/doi.org\/10.1007\/978-3-030-51372-6_19","DOI":"10.1007\/978-3-030-51372-6_19"},{"key":"744_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-015-0356-7","author":"T Menouer","year":"2016","unstructured":"Menouer, T., et al.: Mixing static and dynamic partitioning to parallelize a constraint programming solver. Int. J. Parallel Program. (2016). https:\/\/doi.org\/10.1007\/s10766-015-0356-7","journal-title":"Int. J. Parallel Program."},{"key":"744_CR24","doi-asserted-by":"crossref","unstructured":"Olivier, S., Huan, J., Liu, J., Prins, J., Dinan, J., Sadayappan, P., Tseng, C.W.: UTS: an unbalanced tree search benchmark. In: International Workshop on Languages and Compilers for Parallel Computing, pp. 235\u2013250. Springer, Berlin","DOI":"10.1007\/978-3-540-72521-3_18"},{"key":"744_CR25","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1613\/jair.5456","volume":"59","author":"L Otten","year":"2017","unstructured":"Otten, L., Dechter, R.: AND\/OR branch-and-bound on a computational grid. J. Artif. Intell. Res. 59, 351\u2013435 (2017)","journal-title":"J. Artif. Intell. Res."},{"key":"744_CR26","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01098364","volume":"4","author":"P Pardalos","year":"1994","unstructured":"Pardalos, P., Xue, J.: The maximum clique problem. J. Global Optim. 4, 301\u2013328 (1994)","journal-title":"J. Global Optim."},{"key":"744_CR27","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jpdc.2014.09.007","volume":"76","author":"A Pietracaprina","year":"2015","unstructured":"Pietracaprina, A., et al.: Space-efficient parallel algorithms for combinatorial search problems. J. Parallel Distrib. Comput. 76, 58\u201365 (2015)","journal-title":"J. Parallel Distrib. Comput."},{"key":"744_CR28","unstructured":"Poldner, M., Kuchen, H.: Algorithmic skeletons for branch & bound. In: ICSOFT, Set\u00fabal, Portugal, Sept. 2006 (2006)"},{"key":"744_CR29","doi-asserted-by":"publisher","DOI":"10.3390\/a5040545","author":"P Prosser","year":"2012","unstructured":"Prosser, P.: Exact algorithms for maximum clique: a computational study. Algorithms (2012). https:\/\/doi.org\/10.3390\/a5040545","journal-title":"Algorithms"},{"key":"744_CR30","doi-asserted-by":"publisher","unstructured":"R\u00e9gin, J., Rezgui, M., Malapert, A.: Embarrassingly parallel search. In: Schulte, C. (ed.) Principles and Practice of Constraint Programming\u201419th International Conference, CP 2013, Uppsala, Sweden, Sept 16\u201320, vol. 8124, pp. 596\u2013610. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-3-642-40627-0_45","DOI":"10.1007\/978-3-642-40627-0_45"},{"key":"744_CR31","unstructured":"The GAP Group: GAP - Groups, Algorithms, and Programming, Version 4.8.7 (2017), https:\/\/www.gap-system.org\/Releases\/4.8.7.html"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-022-00744-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-022-00744-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-022-00744-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T19:40:45Z","timestamp":1674848445000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-022-00744-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,7]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["744"],"URL":"https:\/\/doi.org\/10.1007\/s10766-022-00744-3","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"type":"print","value":"0885-7458"},{"type":"electronic","value":"1573-7640"}],"subject":[],"published":{"date-parts":[[2022,12,7]]},"assertion":[{"value":"9 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interests"}}]}}