×

Functional and dynamic programming in the design of parallel prefix networks. (English) Zbl 1220.68046

Summary: A parallel prefix network of width \(n\) takes \(n\) inputs, \(a_{1}, a_{2},\ldots, a_{n}\), and computes each \(y_{i} = a_{1} \circ a_{2} \circ \cdots \circ a_{i}\) for \(1 \leqslant i \leqslant 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 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.

MSC:

68N18 Functional programming and lambda calculus
68M10 Network design and communication in computer systems
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)

Software:

SPIRAL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Singh, FPGAs for Custom Computing Machines (FCCM) pp 145– (2000)
[2] DOI: 10.1109/TEC.1960.5219822
[3] DOI: 10.1007/3-540-44798-9_28
[4] DOI: 10.1109/12.156534
[5] DOI: 10.1007/978-3-540-30494-4_2
[6] Blelloch, Prefix Sums and Their Applications (1990)
[7] DOI: 10.1007/978-3-540-39724-3_4
[8] DOI: 10.1145/289423.289440 · Zbl 06763136
[9] Püschel, Proceedings of IEEE, Special Issue on Program Generation, Optimization and Adaptation 93 pp 232– (2005)
[10] DOI: 10.1109/MEMCOD.2010.5558637
[11] DOI: 10.1147/rd.312.0235 · Zbl 0653.68016
[12] DOI: 10.1109/MSE.2005.55
[13] DOI: 10.1145/1721654.1721675 · Zbl 05748176
[14] DOI: 10.1109/ARITH.1995.465378
[15] Liu, ASP-DAC’07: Proceedings of the 2007 Asia and South Pacific Design Automation Conference pp 609– (2007)
[16] DOI: 10.1016/j.jpdc.2005.05.017 · Zbl 1103.68976
[17] DOI: 10.1016/S0020-0190(99)00058-7 · Zbl 1002.68067
[18] DOI: 10.1023/A:1022084814175 · Zbl 1039.68096
[19] DOI: 10.1145/1455229.1455244 · Zbl 05517257
[20] Lakshmivarahan, Proceedings of International Conference on Parallel Processing pp 58– (1987)
[21] DOI: 10.1145/322217.322232 · Zbl 0445.68066
[22] DOI: 10.1109/TC.1973.5009159 · Zbl 0262.68015
[23] Knowles, Proceedings of International. Symposium on Computer Arithmetic pp 277– (1999)
[24] Jones, Formal Methods for VLSI Design pp 13– (1990)
[25] DOI: 10.1007/978-3-540-27764-4_11
[26] Han, Proceedings of International Symposium on Computer Arithmetic pp 49– (1987)
[27] DOI: 10.1007/978-3-642-16478-1_2 · Zbl 05809302
[28] DOI: 10.1145/1142155.1142162 · Zbl 05456872
[29] Giegerich, Informatik bewegt: Informatik 2002–32. Jahrestagung der Gesellschaft für Informatik e.v. (gi) pp 3– (2002)
[30] Wadler, Proceedings of the Marktoberdorf Summer School on Program Design Calculi (1992)
[31] Franchetti, Proceedings of IFIP Working Conference on Domain Specific Languages (DSL WC) pp 385– (2009)
[32] DOI: 10.1145/800061.808738
[33] Voigtländer, Proceedings of the 35th Symposium on Principles of Programming Languages pp 29– (2008)
[34] Cormen, Introduction to Algorithms (2001)
[35] Svensson, Proceedings of the Seventh International Workshop on Practical Aspects of High-level Parallel Programming, ICCS pp 2059– (2010)
[36] Snir, J. Algebra 7 pp 185– (1986)
[37] Singh, Designing Correct Circuits pp 119– (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.