CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Functional and dynamic programming in the design of parallel prefix networks

Mary Sheeran (Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers))
Göteborg : Chalmers University of Technology, 2009. - 37 s.
[Rapport]

A parallel prefix network computes each $x_0 \circ x_1 \circ \ldots x_k$ for $0 \le k < n$, for an associative operator $\circ$. 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 a great 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 Haskell, 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.



Denna post skapades 2009-12-10. Senast ändrad 2013-08-14.
CPL Pubid: 103228

 

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers) (2008-2010)

Ämnesområden

Datavetenskap (datalogi)

Chalmers infrastruktur

Ingår i serie

Technical report - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University 2009:12