Implementing YewPar: A Framework for Parallel Tree Search

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

doi:10.1007/978-3-030-29400-7_14

Implementing YewPar: A Framework for Parallel Tree Search

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Citations (Scopus)

84 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 language	English
Title of host publication	European Conference on Parallel Processing: Euro-Par 2019
Editors	Ramin Yahyapour
Publisher	Springer
Pages	184-196
Number of pages	13
ISBN (Electronic)	9783030294007
ISBN (Print)	9783030293994
DOIs	https://doi.org/10.1007/978-3-030-29400-7_14
Publication status	Published - 13 Aug 2019
Event	25th International Conference on Parallel and Distributed Computing 2019 - Göttingen, Germany Duration: 26 Aug 2019 → 30 Aug 2019 https://2019.euro-par.org/

Publication series

Name	Lecture Notes in Computer Science
Volume	11725
ISSN (Print)	0302-9743

Conference

Conference	25th International Conference on Parallel and Distributed Computing 2019
Abbreviated title	Euro-Par 2019: Parallel Processing
Country/Territory	Germany
City	Göttingen
Period	26/08/19 → 30/08/19
Internet address	https://2019.euro-par.org/

Keywords

Exact combinatorial search
HPX
Parallel search

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-29400-7_14

Download pdf
The final authenticated publication is available online at https://doi.org/10.1007/978-3-030-29400-7_14
Accepted author manuscript, 343 KB

Cite this

@inproceedings{96f04c729105489db9c5064f6e526042,

title = "Implementing YewPar: A Framework for Parallel Tree Search",

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, HPX, Parallel search",

author = "Blair Archibald and Patrick Maier and Stewart, \{Robert James\} and Phil Trinder",

year = "2019",

month = aug,

day = "13",

doi = "10.1007/978-3-030-29400-7\_14",

language = "English",

isbn = "9783030293994",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "184--196",

editor = "Ramin Yahyapour",

booktitle = "European Conference on Parallel Processing: Euro-Par 2019",

note = "25th International Conference on Parallel and Distributed Computing 2019, Euro-Par 2019: Parallel Processing ; Conference date: 26-08-2019 Through 30-08-2019",

url = "https://2019.euro-par.org/",

}

Archibald, B, Maier, P, Stewart, RJ & Trinder, P 2019, Implementing YewPar: A Framework for Parallel Tree Search. in R Yahyapour (ed.), European Conference on Parallel Processing: Euro-Par 2019. Lecture Notes in Computer Science, vol. 11725, Springer, pp. 184-196, 25th International Conference on Parallel and Distributed Computing 2019, Göttingen, Germany, 26/08/19. https://doi.org/10.1007/978-3-030-29400-7_14

Implementing YewPar: A Framework for Parallel Tree Search. / Archibald, Blair; Maier, Patrick; Stewart, Robert James et al.
European Conference on Parallel Processing: Euro-Par 2019. ed. / Ramin Yahyapour. Springer, 2019. p. 184-196 (Lecture Notes in Computer Science; Vol. 11725).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Implementing YewPar: A Framework for Parallel Tree Search

AU - Archibald, Blair

AU - Maier, Patrick

AU - Stewart, Robert James

AU - Trinder, Phil

PY - 2019/8/13

Y1 - 2019/8/13

N2 - 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.

AB - 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.

KW - Exact combinatorial search

KW - HPX

KW - Parallel search

UR - https://www.scopus.com/pages/publications/85075844025

U2 - 10.1007/978-3-030-29400-7_14

DO - 10.1007/978-3-030-29400-7_14

M3 - Conference contribution

SN - 9783030293994

T3 - Lecture Notes in Computer Science

SP - 184

EP - 196

BT - European Conference on Parallel Processing: Euro-Par 2019

A2 - Yahyapour, Ramin

PB - Springer

T2 - 25th International Conference on Parallel and Distributed Computing 2019

Y2 - 26 August 2019 through 30 August 2019

ER -

Implementing YewPar: A Framework for Parallel Tree Search

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this