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.
// SIMD bytewise add a + b
U64 koggeStoneByteAdd(U64 a, U64 b) {
const U64 aFile = C64(0x0101010101010101);
U64 gen, pro;
gen = a & b;
// SIMD bytewise sub a - b
U64 koggeStoneByteSub(U64 a, U64 b) {
const U64 aFile = C64(0x0101010101010101);
U64 gen, pro;
gen = a & ~b; // based on -b = ~b + 1
<pre>
U64 eastAttacks(U64 occ, U64 rooks) {
const U64 aFile = C64(0x0101010101010101);
U64 gen, pro;
pro = ~occ & ~aFile;
=Publications=
* [http://www.cse.nd.edu/%7Ekogge/ [Mathematician#PMKogge|Peter M. Kogge]], [[Mathematician#HSStone|Harold S. Stone]] ('''19731972'''). ''[https://ntrl.ntis.gov/NTRL/dashboard/searchResults/titleDetail/PB212080.xhtml A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations]''. IEEE Transactions on Computers, 1973, C-22, 783-791Technical Report 25, [http://bwrc.eecs.berkeley.edu/Classes/ee225c/2000%20225c/Papers/KoggeStone.pdf pdf[Stanford University]]* [http://www[Mathematician#PMKogge|Peter M.cs.washington.edu/homes/ladner/ Richard E. LadnerKogge], [http://cs-www.cs.yale.edu/homes/fischer/ Michael J. Fischer] ('''19801973'''). ''Parallel Prefix ComputationSolution of Recurrence Problems''. Ph.D. thesis, [[Stanford University]], advisor [[Mathematician#HSStone|Harold S. Stone]], [httphttps://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=5EBA05F3F708ABC617EE34DD08B65485?doi=10.1.1.10684.62472724&rep=rep1&type=pdf pdf] via * [http[Mathematician#PMKogge|Peter M. Kogge]], [[Mathematician#HSStone|Harold S. Stone]] ('''1973'''). ''[https://citeseerxieeexplore.istieee.psu.eduorg/viewdocdocument/summary?doi=105009159 A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations]''.1[[IEEE#TOC|IEEE Transactions on Computers]], Vol.1C-22, No.106.6247 CiteSeerX]8* [[Clyde KruskalMathematician#RELadner|Richard E. Ladner]], [http[Mathematician#MJFischer|Michael J. Fischer]] ('''1980'''). ''[https://necsidl.acm.eduorg/doi/facultyabs/rudolph10.html 1145/322217.322232?download=true Parallel Prefix Computation]''. [[ACM#Journal|Journal of the ACM]], Vol. 27, No. 4* [[Clyde Kruskal]], [[Mathematician#LRudolph|Larry Rudolph]], [[Mathematician#MSnir|Marc Snir]] ('''1985'''). ''The power of parallel prefix''. [https://enwww.wikipediacomputer.org/wikicsdl/journal/IEEE_Transactions_on_Computers 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=
