This paper explores parallel nondeterministic programming as an extension to the C programming language; it provides constructs for specifying code containing ambiguous choice as introduced by McCarthy. A translator to plain C code was implemented as an extension to the ableC language specification. Translation involves a transformation to continuation passing style, providing lazy choice by storing continuation closures in a separate task buffer. This exploration considers various search evaluation approaches and their impact on correctness and performance. Multiple search drivers were implemented, including single-Threaded depth-first search, a combined breadth-And depth-first approach, as well as two approaches to parallelism. Several benchmark applications were created using the extension, including n-Queens, SAT, and triangle peg solitaire. The simplest parallel search driver, using independent threads, showed the best performance in most cases, providing a significant speedup over the sequential versions. Adding task sharing between threads showed similar or slightly improved performance.
|Original language||English (US)|
|Title of host publication||GPCE 2019 - Proceedings of the 18th ACM SIGPLAN International Conference on Generative Programming|
|Subtitle of host publication||Concepts and Experiences, co-located with SPLASH 2019|
|Editors||Ina Schaefer, Christoph Reichenbach, Tijs van der Storm|
|Publisher||Association for Computing Machinery, Inc|
|Number of pages||7|
|State||Published - Oct 21 2019|
|Event||18th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences, GPCE 2019, co-located with ACM SIGPLAN Conference on Systems, Programming, Languages, and Applications: Software for Humanity, SPLASH 2019 - Athens, Greece|
Duration: Oct 21 2019 → Oct 22 2019
|Name||GPCE 2019 - Proceedings of the 18th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences, co-located with SPLASH 2019|
|Conference||18th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences, GPCE 2019, co-located with ACM SIGPLAN Conference on Systems, Programming, Languages, and Applications: Software for Humanity, SPLASH 2019|
|Period||10/21/19 → 10/22/19|
Bibliographical noteFunding Information:
This material is partially based upon work supported by the National Science Foundation (NSF) under Grant Nos. 1628929. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the NSF.
Copyright © 2019 by the Association for Computing Machinery, Inc. (ACM).
- Extensible languages
- Nondeterministic programming
- Parallel programming