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)
13 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