Functional and dynamic programming in the design of parallel prefix networks

Mary Sheeran
CSE department, Chalmers university of technology, Goteborg, se-41296, Sweden
Journal of Functional Programming, 21, 59-114, 2011


   title={Functional and dynamic programming in the design of parallel prefix networks},

   author={Sheeran, M.},

   journal={Journal of Functional Programming},





   publisher={Cambridge Univ Press}


Download Download (PDF)   View View   Source Source   



A parallel prefix network of width n takes n inputs, a_1, a_2, … , a_n, and computes each yi = a_1 o a_2 o … o a_i for 1 <= i <= n, for an associative operator o. This is one of the fundamental problems in computer science, because it gives insight into how parallel computation can be used to solve an apparently sequential problem. As parallel programming becomes the dominant programming paradigm, parallel prefix or scan is proving to be a very important building block of parallel algorithms and applications. There are many different parallel prefix networks, with different properties such as number of operators, depth and allowed fanout from the operators. In this paper, ideas from functional programming are combined with search to enable a deep exploration of parallel prefix network design. Networks that improve on the best known previous results are generated. It is argued that precise modelling in a functional programming language, together with simple visualization of the networks, gives a new, more experimental, approach to parallel prefix network design, improving on the manual techniques typically employed in the literature. The programming idiom that marries search with higher order functions may well have wider application than the network generation described here.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: