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.
* [http://www.cse.nd.edu/%7Ekogge/ Peter M. Kogge], [[Mathematician#HSStone|Harold S. Stone]] ('''1973'''). ''A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations''. IEEE Transactions on Computers, 1973, C-22, 783-791, [http://bwrc.eecs.berkeley.edu/Classes/ee225c/2000%20225c/Papers/KoggeStone.pdf pdf]
* [http://www.cs.washington.edu/homes/ladner/ Richard E. Ladner], [http://cs-www.cs.yale.edu/homes/fischer/ Michael J. Fischer] ('''1980'''). ''Parallel Prefix Computation''. [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=5EBA05F3F708ABC617EE34DD08B65485?doi=10.1.1.106.6247&rep=rep1&type=pdf pdf] via [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.6247 CiteSeerX]
* [[Clyde Kruskal]], [http://necsi.edu/faculty/rudolph.html [Mathematician#LRudolph|Larry Rudolph]], [[Mathematician#MSnir|Marc Snir]] ('''1985'''). ''The power of parallel prefix''. [https://enwww.wikipediacomputer.org/wikicsdl/IEEE_Transactions_on_Computers 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=
* [https://www.stmintz.com/ccc/index.php?id=252289 flood fill attack bitboards] by [[Steffan Westcott]] from [[Computer Chess Forums|CCC]], September 15, 2002
* [http://www.talkchess.com/forum/viewtopic.php?start=0&t=25979&start=10 Re: Hyperbola Quiesscene: hardly any improvement] by [[Karlo Balla|Karlo Bala Jr.]], [[CCC]], January 14, 2009 » [[Hyperbola Quintessence]]
=External Links=
