Conference Proceeding

YewPar: Skeletons for Exact Combinatorial Search

Details

Citation

Archibald B, Maier P, Stewart R & Trinder P (2020) YewPar: Skeletons for Exact Combinatorial Search. In: PPoPP '20: Proceedings of the 25th Symposium on Principles and Practice of Parallel Programming. Principles and Practice of Parallel Programming 2020 (PPoPP 2020), San Diego, 22.02.2020-26.02.2020. New York: ACM, pp. 292-307. https://doi.org/10.1145/3332466.3374537

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.

StatusPublished
FundersEngineering and Physical Sciences Research Council, Engineering and Physical Sciences Research Council, Engineering and Physical Sciences Research Council and Engineering and Physical Sciences Research Council
Publication date31/12/2020
Publication date online22/02/2020
URLhttp://hdl.handle.net/1893/30587
PublisherACM
Place of publicationNew York
ConferencePrinciples and Practice of Parallel Programming 2020 (PPoPP 2020)
Conference locationSan Diego
Dates

People (1)

People

Dr Patrick Maier

Dr Patrick Maier

Lecturer, Computing Science