Implementing YewPar: A Framework for Parallel Tree Search

Blair Archibald, Patrick Maier, Robert James Stewart, Phil Trinder

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)
37 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationEuropean Conference on Parallel Processing: Euro-Par 2019
EditorsRamin Yahyapour
Number of pages13
ISBN (Electronic)978-3-030-29400-7
Publication statusE-pub ahead of print - 13 Aug 2019
Event25th International Conference on Parallel and Distributed Computing 2019 - Göttingen, Germany
Duration: 26 Aug 201930 Aug 2019

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference25th International Conference on Parallel and Distributed Computing 2019
Abbreviated titleEuro-Par 2019: Parallel Processing
Internet address


  • Exact combinatorial search
  • HPX
  • Parallel search

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Implementing YewPar: A Framework for Parallel Tree Search'. Together they form a unique fingerprint.

Cite this