Conference Proceeding
Details
Citation
Archibald B, Maier P, Stewart R & Trinder P (2019) Implementing YewPar: a Framework for Parallel Tree Search. In: Yahyapour R (ed.) Euro-Par 2019: Parallel Processing. Lecture Notes in Computer Science, 11725. Euro-Par 2019: 25th International Conference on Parallel and Distributed Computing, Göttingen, Germany, 26.08.2019-30.08.2019. Cham, Switzerland: Springer Verlag, pp. 184-196. https://doi.org/10.1007/978-3-030-29400-7_14
Abstract
Combinatorial search is central to many applications yet hard to parallelise. We argue for improving the reuse of parallel searches, and present the design and implementation of a new parallel search framework. YewPar generalises search by abstracting search tree generation, and by providing algorithmic skeletons that support three search types, together with a set of search coordination strategies. The evaluation shows that the cost of YewPar generality is low (6.1%); global knowledge is inexpensively shared between workers; irregular tasks are effectively distributed; and YewPar delivers good runtimes, speedups and efficiency with up to 255 workers on 17 localities.
Keywords
exact combinatorial search; parallel search; HPX
| Status | Published |
|---|---|
| Funders | Engineering and Physical Sciences Research Council, Engineering and Physical Sciences Research Council, Engineering and Physical Sciences Research Council and Engineering and Physical Sciences Research Council |
| Title of series | Lecture Notes in Computer Science |
| Number in series | 11725 |
| Publication date | 31/12/2019 |
| Publication date online | 13/08/2019 |
| URL | http://hdl.handle.net/1893/29999 |
| Publisher | Springer Verlag |
| Place of publication | Cham, Switzerland |
| ISSN of series | 0302-9743 |
| ISBN | 978-3-030-29399-4 |
| eISBN | 978-3-030-29400-7 |
| Conference | Euro-Par 2019: 25th International Conference on Parallel and Distributed Computing |
| Conference location | Göttingen, Germany |
| Dates | – |
People (1)
People
Lecturer, Computing Science