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)
9 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationEuropean Conference on Parallel Processing: Euro-Par 2019
EditorsRamin Yahyapour
Pages184-196
Number of pages13
ISBN (Electronic)978-3-030-29400-7
DOIs
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
https://2019.euro-par.org/

Publication series

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

Conference

Conference25th International Conference on Parallel and Distributed Computing 2019
Abbreviated titleEuro-Par 2019: Parallel Processing
CountryGermany
CityGöttingen
Period26/08/1930/08/19
Internet address

Keywords

  • Exact combinatorial search
  • HPX
  • Parallel search

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this