Implementing declarative parallel bottom-avoiding choice

• A. Rauber Du Bois Heriot-Watt University
• R. Pointon Heriot-Watt University
• H. -W. Loidl Heriot-Watt University
• P. Trinder Heriot-Watt University

Resumo

Non-deterministic choice supports efficient parallel speculation, but unrestricted non-determinism destroys the referential transparency of purely-declarative languages by removing unfoldability and it bears the danger of wasting resources on unnecessary computations. While numerous choice mechanisms have been proposed that preserve unfoldability, and some concurrent implementations exist, we believe that no compiled parallel implementation has previously been constructed This paper presents the design, semantics, implementation and use of a family of bottom-avoiding choice operators for Glasgow parallel Haskell. The subtle semantic properties of our choice operations are described, including a careful classification using an existing framework, together with a discussion of operational semantics issues and the pragmatics of distributed memory implementation. The expressiveness of our choice operators is demonstrated by constructing a branch and bound search, a merge and a speculative conditional. Their effectiveness is demonstrated by comparing the parallel performance of the speculative search with naive and 'perfect' implementations. Their efficiency is assessed by measuring runtime overhead and heap consumption.

Palavras-chave: Yarn, Neodymium, Concurrent computing, Runtime, Control systems, Proposals, Computer architecture, High performance computing, Data structures, Skeleton