Content deleted Content added
m WP:CHECKWIKI error 61 fixes + general fixes, References after punctuation per WP:REFPUNC and WP:PAIC using AWB (7671) |
m →Parallel Merge: Cite cleanup using AWB (7836) |
||
Line 23:
In [[parallel computing]], [[Array data structure|array]]s of sorted values may be merged efficiently using an [[all nearest smaller values]] computation.<ref>{{citation|first1=Omer|last1=Berkman|first2=Baruch|last2=Schieber|first3=Uzi|last3=Vishkin|author3-link=Uzi Vishkin|title=Optimal double logarithmic parallel algorithms based on finding all nearest smaller values|journal=Journal of Algorithms|volume=14|pages=344–370|year=1993|issue=3|doi=10.1006/jagm.1993.1018}}.</ref>
Parallel merge can also be implemented using a divide-and-conquer algorithm, developed and shown in pseudo-code in.<ref>{{citation|first1=Thomas|last1=Cormen|first2=Charles|last2=Leiserson|first3=Ronald|last3=Rivest|first4=Clifford |last3=Stein|title=Introduction to Algorithms|edition=Third Edition, MIT Press and McGraw-Hill, 2009|page=800}}.</ref> This algorithm performs well when combined with a fast sequential merge as a base case for merging of small arrays. Implementation using Intel's Threading Building Blocks (TBB) and Microsoft's Parallel Pattern Library (PPL) to run on multi-core processors is shown to perform well in practice.<ref>[http://drdobbs.com/high-performance-computing/229204454 V. J. Duvanenko, "Parallel Merge", Dr. Dobb's Journal, February 2011]</ref>
== References ==
| |||