Conference Proceeding

Implementing YewPar: a Framework for Parallel Tree Search

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

StatusPublished
FundersEngineering 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 seriesLecture Notes in Computer Science
Number in series11725
Publication date31/12/2019
Publication date online13/08/2019
URLhttp://hdl.handle.net/1893/29999
PublisherSpringer Verlag
Place of publicationCham, Switzerland
ISSN of series0302-9743
ISBN978-3-030-29399-4
eISBN978-3-030-29400-7
ConferenceEuro-Par 2019: 25th International Conference on Parallel and Distributed Computing
Conference locationGöttingen, Germany
Dates

People (1)

Dr Patrick Maier

Dr Patrick Maier

Lecturer, Computing Science