25,161
edits
Changes
no edit summary
'''[[Main Page|Home]] * [[Programming]] * [[Algorithms]] * Parallel Prefix Algorithms'''
[[FILE:parallelprefixsum.png|border|right|thumb|link=http://www.toves.org/books/distalg/|Parallel Prefix Sum <ref>[http://ozark.hendrix.edu/~burch/ [Mathematician#CBurch|Carl Burch]] ('''2009'''). ''[http://www.toves.org/books/distalg/ Introduction to parallel & distributed algorithms]''. On-line Book</ref> ]]
'''Parallel prefix algorithms''' compute all [https://en.wikipedia.org/wiki/Prefix_sum prefixes] of a input sequence in [https://en.wikipedia.org/wiki/Time_complexity#Logarithmic_time logarithmic time], and are topic of various [[SIMD and SWAR Techniques|SIMD and SWAR techniques]] applied to [[Bitboards|bitboards]] <ref>[[#Seealso|See also]]</ref> . This page provides some basics on simple parallel prefix problems, like parity words and [https://en.wikipedia.org/wiki/Gray_code Gray code] with some interesting properties, followed by some theoretical background on more complex parallel prefix problems, like [[Kogge-Stone Algorithm|Kogge-Stone]] by [[Steffan Westcott]], and a comparison of three similar Kogge-Stone routines for different purpose.
* [[Clyde Kruskal]], [[Mathematician#LRudolph|Larry Rudolph]], [[Mathematician#MSnir|Marc Snir]] ('''1985'''). ''[https://www.computer.org/csdl/journal/tc/1985/10/06312202/13rRUy0HYQl The power of parallel prefix]''. [[IEEE#TOC|IEEE Transactions on Computers]], Vol. C-34, No. 10
* [[Peter Sanders]], [http://www.traff-industries.de/ Jesper Larsson Träff] ('''2006'''). ''Parallel Prefix (Scan) Algorithms for MPI''. in EuroPVM/MPI 2006, LNCS, [http://algo2.iti.uni-karlsruhe.de/sanders/papers/scan.pdf pdf]
* [http://ozark.hendrix.edu/~burch/ [Mathematician#CBurch|Carl Burch]] ('''2009'''). ''[http://www.toves.org/books/distalg/ Introduction to parallel & distributed algorithms]''. On-line Book
=Forum Posts=
