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.
==Add==
[[FILE:300px-4_bit_Kogge_Stone_Adder_Example_new4 bit Kogge Stone Adder Example new.png|none|border|text-bottomright|link=https://en.wikipedia.org/wiki/Kogge-Stone_adderthumb|4-bit Kogge-Stone adder]]
The software approach of a [https://en.wikipedia.org/wiki/Kogge-Stone_adder Kogge-Stone] [[Combinatorial Logic#Adder|hardware adder]] <ref>[http://www.aoki.ecei.tohoku.ac.jp/arith/mg/algorithm.html#fsa_pfx Hardware algorithms for arithmetic modules] from the ARITH research group, Aoki lab., [https://en.wikipedia.org/wiki/Tohoku_University Tohoku University]</ref> , requires the initial carry bits as generator, thus the [[General Setwise Operations#Intersection|intersection]] of both summands, while the propagator is the modulo 2 sum, the [[General Setwise Operations#ExclusiveOr|exclusive or]] of both summands. To avoid inter byte overflows, the propagator has the least significant bits of each byte cleared. However the final carries need one further masked shift and the modulo two sum with the initial propagator.
<pre>
* [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]], [http://cs.illinois.edu/people/faculty/marc-snir [Mathematician#MSnir|Marc Snir] ] ('''1985'''). ''The power of parallel prefix''. [https://enwww.wikipediacomputer.org/wikicsdl/journal/tc/1985/10/06312202/IEEE_Transactions_on_Computers 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=
* [http://everything2.com/title/parallel+prefix+algorithm parallel prefix algorithm] from [http://everything2.com/ Everything2.com]
* [http://charm.cs.uiuc.edu/tutorial/ParallelPrefix.htm Charm++ Tutorial - Parallel Prefix Program]
* [[Videos#JoeZawinul:Category:Joe Zawinul|Joe Zawinul]], [[Videos#TrilokGurtu:Category:Trilok Gurtu|Trilok Gurtu]] - Orient Express Part1, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=922LumI2ilo|alignment=left|valignment=top}}
'''[[Algorithms|Up one Level]]'''
[[Category:Trilok Gurtu]]
[[Category:Joe Zawinul]]
