YewPar: Skeletons for Exact Combinatorial Search

Blair Archibald, Patrick Maier, Robert Stewart, Phil Trinder

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

2 Citations (Scopus)
1 Downloads (Pure)

Abstract

Combinatorial search is central to many applications, yet the huge irregular search trees and the need to respect search heuristics make it hard to parallelise. We aim to improve the reuse of intricate parallel search implementations by providing the first general purpose scalable parallel framework for exact combinatorial search, YewPar. We make the following contributions. (1) We present a novel formal model of parallel backtracking search, covering enumeration, decision, and optimisation search. (2) We introduce Lazy Node Generators as a uniform API for search tree generation. (3) We present the design and implementation of 12 widely applicable algorithmic skeletons for tree search on shared and distributed memory architectures. (4) Uniquely in the field we demonstrate how a wide range of parallel search applications can easily be constructed by composing Lazy Node Generators and the search skeletons. (5) We report a systematic performance analysis of all 12 YewPar skeletons on standard instances of 7 search applications, investigating skeleton overheads and scalability up to 255 workers on 17 distributed locations.
Original languageEnglish
Title of host publicationPPoPP '20: Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
PublisherAssociation for Computing Machinery
Pages292–307
Number of pages16
ISBN (Print)9781450368186
DOIs
Publication statusPublished - 25 Feb 2020
EventPrinciples and Practice of Parallel Programming 2020 - San Diego Mission Bay Resort, San Diego, United States
Duration: 22 Feb 202026 Feb 2020
Conference number: 25
https://ppopp20.sigplan.org/

Conference

ConferencePrinciples and Practice of Parallel Programming 2020
Abbreviated titlePPoPP 2020
CountryUnited States
CitySan Diego
Period22/02/2026/02/20
Internet address

Keywords

  • Algorithmic Skeletons
  • Combinatorial Search
  • Distributed Memory Parallelism
  • HPX

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'YewPar: Skeletons for Exact Combinatorial Search'. Together they form a unique fingerprint.

  • Profiles

    Cite this

    Archibald, B., Maier, P., Stewart, R., & Trinder, P. (2020). YewPar: Skeletons for Exact Combinatorial Search. In PPoPP '20: Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp. 292–307). Association for Computing Machinery. https://doi.org/10.1145/3332466.3374537