Mercurial > cgi-bin > hgwebdir.cgi > POP > oldRepo

annotate 3__Intelligence_gathering/Bitonic_Sort.mht @ 2:5c0400b5ae59

find changesets by author, revision, files, or words in the commit message
Unknown changes.. committing to get them captured
author Sean Halle <seanhalle@yahoo.com>
date Fri, 13 Sep 2013 11:04:58 -0700
parents
children
rev   line source
Me@0 1 From: <Saved by Microsoft Internet Explorer 5>
Me@0 2 Subject: Bitonic Sort
Me@0 3 Date: Mon, 4 Jun 2007 10:57:06 -0700
Me@0 4 MIME-Version: 1.0
Me@0 5 Content-Type: text/html;
Me@0 6 charset="Windows-1252"
Me@0 7 Content-Transfer-Encoding: quoted-printable
Me@0 8 Content-Location: http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm
Me@0 9 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2962
Me@0 10
Me@0 11 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
Me@0 12 <HTML><HEAD><TITLE>Bitonic Sort</TITLE>
Me@0 13 <META http-equiv=3DContent-Type content=3D"text/html; =
Me@0 14 charset=3Dwindows-1252">
Me@0 15 <META content=3D"MSHTML 6.00.2900.2963" name=3DGENERATOR></HEAD>
Me@0 16 <BODY text=3D#000000 vLink=3D#6699cc aLink=3D#ff3300 link=3D#3333cc =
Me@0 17 bgColor=3D#ffcc99>
Me@0 18 <H1 align=3Dcenter>Bitonic Sort</H1>
Me@0 19 <P align=3Dcenter>Abstract</P>
Me@0 20 <BLOCKQUOTE>
Me@0 21 <BLOCKQUOTE>
Me@0 22 <BLOCKQUOTE>
Me@0 23 <BLOCKQUOTE>
Me@0 24 <P align=3Dleft>Continuing a tutorial on sorting algorithms, =
Me@0 25 this page=20
Me@0 26 animates bitonic =
Me@0 27 sort.</P></BLOCKQUOTE></BLOCKQUOTE></BLOCKQUOTE></BLOCKQUOTE>
Me@0 28 <P align=3Dcenter>Author<BR>Thomas W. Christopher<BR></P>
Me@0 29 <P>Bitonic sort is a sorting algorithm designed specially for parallel=20
Me@0 30 machines.</P>
Me@0 31 <P>A sorted sequence is a monotonically non-decreasing (or =
Me@0 32 non-increasing)=20
Me@0 33 sequence. A bitonic sequence is composed of two subsequences, one =
Me@0 34 monotonically=20
Me@0 35 non-decreasing and the other monotonically non-increasing. A "V" and an =
Me@0 36 A-frame=20
Me@0 37 are examples of bitonic sequences.</P>
Me@0 38 <P>I get tired of saying "non-decreasing" and "non-increasing." They are =
Me@0 39 clunky=20
Me@0 40 and throw an extra negative into sentences. I will use "ascending" to =
Me@0 41 mean=20
Me@0 42 "non-decreasing" and "descending" to mean "non-increasing."</P>
Me@0 43 <P>Moreover, any rotation of a bitonic sequence is a bitonic sequence, =
Me@0 44 or if you=20
Me@0 45 prefer, one of the subsequences can wrap around the end of the bitonic=20
Me@0 46 sequence.</P>
Me@0 47 <P>Of course, a sorted sequence is itself a bitonic sequence: one of the =
Me@0 48
Me@0 49 subsequences is empty.</P>
Me@0 50 <P>Now we come to a strange property of bitoinic sequences, the property =
Me@0 51 that is=20
Me@0 52 uses in bitonic sort: </P>
Me@0 53 <BLOCKQUOTE>
Me@0 54 <P>Suppose you have a bitonic sequence of length 2n, that is, elements =
Me@0 55 in=20
Me@0 56 positions [0,2n). You can easily divide it into two halves, [0,n) and =
Me@0 57 [n,2n),=20
Me@0 58 such that
Me@0 59 <UL>
Me@0 60 <LI>each half is a bitonic sequence, and=20
Me@0 61 <LI>every element in half [0,n) is less than or equal to each =
Me@0 62 element in=20
Me@0 63 [n,2n). (Or greater than or equal to, of course.) =
Me@0 64 </LI></UL></BLOCKQUOTE>
Me@0 65 <P>What is this easy method? Simply compare elements in the =
Me@0 66 corresponding=20
Me@0 67 positions in the two halves and exchange them if they are out of =
Me@0 68 order.</P>
Me@0 69 <BLOCKQUOTE>
Me@0 70 <P>&nbsp;&nbsp;&nbsp; for (i=3D0;i&lt;n;i++)=20
Me@0 71 {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if =
Me@0 72 (get(i)&gt;get(i+n))=20
Me@0 73 exchange(i,i+n);<BR>&nbsp;&nbsp;&nbsp; }</P></BLOCKQUOTE>
Me@0 74 <P>This is sometimes called a bitonic merge.</P>
Me@0 75 <P>Why does it work? I'm not sure I could do a concise and clear enough =
Me@0 76 proof to=20
Me@0 77 fit in with these pages. Let's just leave it without a proof, but =
Me@0 78 true.</P>
Me@0 79 <P>So here's how we do a bitonic sort:=20
Me@0 80 <UL>
Me@0 81 <LI>We sort only sequences a power of two in length, so we can always =
Me@0 82 divide a=20
Me@0 83 subsequence of mnore than one element into two halves.=20
Me@0 84 <LI>We sort the lower half into ascending (=3Dnon-decreasing, =
Me@0 85 remember) order=20
Me@0 86 and the upper half into descending order. This gives us a bitonic =
Me@0 87 sequence.=20
Me@0 88 <LI>We perform a bitonic merge on the sequence, which gives us a =
Me@0 89 bitonic=20
Me@0 90 sequence in each half and all the larger elements in the upper half.=20
Me@0 91 <LI>We recursively bitonically merge each half until all the elements =
Me@0 92 are=20
Me@0 93 sorted. </LI></UL>
Me@0 94 <P><APPLET height=3D200 archive=3Dsorts3.jar width=3D400 align=3Dleft=20
Me@0 95 code=3Dcom.toolsofcomputing.SortApplets.BitonicSort.class>
Me@0 96 Bitonic Sort</APPLET> <B>Bitonic Sort</B> This first version actually =
Me@0 97 uses=20
Me@0 98 recursion. It uses methods sortup, sortdown, mergeup, and mergedown, to =
Me@0 99 sort=20
Me@0 100 into ascending order or descending order and to recursively merge into =
Me@0 101 ascending=20
Me@0 102 or descending order.</P>
Me@0 103 <P>Method <EM>void sortup(int m, int n)</EM> will sort the n elements in =
Me@0 104 the=20
Me@0 105 range [m,m+n) into ascending order. It uses method <EM>void mergeup(int =
Me@0 106 m, int=20
Me@0 107 n)</EM> to merge the n elements in the subsequence [m,m+n) into =
Me@0 108 ascending order.=20
Me@0 109 Similarly for <EM>void sortdown(int m, int n)</EM> and <EM>void =
Me@0 110 mergedown(int m,=20
Me@0 111 int n)</EM>.</P>
Me@0 112 <P>The overall sort is performed by a call:</P>
Me@0 113 <BLOCKQUOTE>
Me@0 114 <P>&nbsp;&nbsp;&nbsp; sortup(0,N);</P></BLOCKQUOTE>
Me@0 115 <P>Both sortup and sortdown recursively sort each half to produce an =
Me@0 116 A-frame=20
Me@0 117 shape and then recursively merge that into an ascending or descending=20
Me@0 118 sequence.</P>
Me@0 119 <BLOCKQUOTE>
Me@0 120 <P>void sortup(int m, int n) {//from m to m+n<BR>&nbsp;&nbsp;&nbsp; if =
Me@0 121 (n=3D=3D1)=20
Me@0 122 return;<BR>&nbsp;&nbsp;&nbsp; sortup(m,n/2);<BR>&nbsp;&nbsp;&nbsp;=20
Me@0 123 sortdown(m+n/2,n/2);<BR>&nbsp;&nbsp;&nbsp; =
Me@0 124 mergeup(m,n/2);<BR>}<BR>void=20
Me@0 125 sortdown(int m, int n) {//from m to m+n<BR>&nbsp;&nbsp;&nbsp; if =
Me@0 126 (n=3D=3D1)=20
Me@0 127 return;<BR>&nbsp;&nbsp;&nbsp; sortup(m,n/2);<BR>&nbsp;&nbsp;&nbsp;=20
Me@0 128 sortdown(m+n/2,n/2);<BR>&nbsp;&nbsp;&nbsp;=20
Me@0 129 mergedown(m,n/2);<BR>}</P></BLOCKQUOTE>
Me@0 130 <P>Methods mergeup and mergedown are fairly straightfoward. They compare =
Me@0 131
Me@0 132 elements in the two halves, exchange them if they are out of order, and=20
Me@0 133 recursively merge the two halves. Call mergeup( m,&nbsp; n) sorts into =
Me@0 134 ascending=20
Me@0 135 order the 2*n elements in the range [m,2n).</P>
Me@0 136 <BLOCKQUOTE>
Me@0 137 <P>void mergeup(int m, int n) {<BR>&nbsp;&nbsp;&nbsp; if (n=3D=3D0)=20
Me@0 138 return;<BR>&nbsp;&nbsp;&nbsp; int i;<BR>&nbsp;&nbsp;&nbsp; for=20
Me@0 139 (i=3D0;i&lt;n;i++) {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if=20
Me@0 140 (get(m+i)&gt;get(m+i+n)) exchange(m+i,m+i+n);<BR>&nbsp;&nbsp;&nbsp;=20
Me@0 141 }<BR>&nbsp;&nbsp;&nbsp; mergeup(m,n/2);<BR>&nbsp;&nbsp;&nbsp;=20
Me@0 142 mergeup(m+n,n/2);<BR>}<BR>void mergedown(int m, int n) =
Me@0 143 {<BR>&nbsp;&nbsp;&nbsp;=20
Me@0 144 if (n=3D=3D0) return;<BR>&nbsp;&nbsp;&nbsp; int =
Me@0 145 i;<BR>&nbsp;&nbsp;&nbsp; for=20
Me@0 146 (i=3D0;i&lt;n;i++) {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if=20
Me@0 147 (get(m+i)&lt;get(m+i+n)) exchange(m+i,m+i+n);<BR>&nbsp;&nbsp;&nbsp;=20
Me@0 148 }<BR>&nbsp;&nbsp;&nbsp; mergedown(m,n/2);<BR>&nbsp;&nbsp;&nbsp;=20
Me@0 149 mergedown(m+n,n/2);<BR>}</P></BLOCKQUOTE>
Me@0 150 <P>&nbsp;</P>
Me@0 151 <P><APPLET height=3D200 archive=3Dsorts3.jar width=3D400 align=3Dleft=20
Me@0 152 code=3Dcom.toolsofcomputing.SortApplets.BitonicSort2.class>
Me@0 153 Bitonic Sort2</APPLET> <B>Bitonic Sort2</B> Bitonic sort is perfect for=20
Me@0 154 parallelization. The recursive calls of merge can be done in parallel. =
Me@0 155 The loops=20
Me@0 156 in the merges, comparing and conditionally exchanging elements (m+i) and =
Me@0 157 (m+i+n)=20
Me@0 158 can also be run in parallel.</P>
Me@0 159 <P>However, getting it to run efficiently in parallel requires turning =
Me@0 160 the=20
Me@0 161 algorithm upside down. The algorithm is expressed in terms of recursive =
Me@0 162 calls.=20
Me@0 163 What we need is an algorithm in terms of each individual element.</P>
Me@0 164 <P>Let's examine what the elements are doing. We will use an =
Me@0 165 eight-element array=20
Me@0 166 and identify the elements by their positions in binary.</P>
Me@0 167 <BLOCKQUOTE>
Me@0 168 <DIV align=3Dleft>
Me@0 169 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
Me@0 170 border=3D1>
Me@0 171 <TBODY>
Me@0 172 <TR>
Me@0 173 <TD>index</TD>
Me@0 174 <TD align=3Dmiddle>0</TD>
Me@0 175 <TD align=3Dmiddle>1</TD>
Me@0 176 <TD align=3Dmiddle>2</TD>
Me@0 177 <TD align=3Dmiddle>3</TD>
Me@0 178 <TD align=3Dmiddle>4</TD>
Me@0 179 <TD align=3Dmiddle>5</TD>
Me@0 180 <TD align=3Dmiddle>6</TD>
Me@0 181 <TD align=3Dmiddle>7</TD></TR>
Me@0 182 <TR>
Me@0 183 <TD>in binary</TD>
Me@0 184 <TD align=3Dmiddle>0000</TD>
Me@0 185 <TD align=3Dmiddle>0001</TD>
Me@0 186 <TD align=3Dmiddle>0010</TD>
Me@0 187 <TD align=3Dmiddle>0011</TD>
Me@0 188 <TD align=3Dmiddle>0100</TD>
Me@0 189 <TD align=3Dmiddle>0101</TD>
Me@0 190 <TD align=3Dmiddle>0110</TD>
Me@0 191 <TD =
Me@0 192 align=3Dmiddle>0111</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE>
Me@0 193 <P>The bits in the addresses are numbered from 0 on the right: the =
Me@0 194 rightmost bit=20
Me@0 195 is bit 0, the bit to its left is bit 1, etc. Bit j contributes =
Me@0 196 2<SUP>j</SUP> to=20
Me@0 197 the value of the binary number.</P>
Me@0 198 <P>Here is the sequence of operations that can be performed in parallel: =
Me@0 199
Me@0 200 <OL>
Me@0 201 <LI>All elements are sorted single element subsequences.=20
Me@0 202 <LI>Pairs of elements are sorted into ascending or descending =
Me@0 203 subsequences:
Me@0 204 <DIV align=3Dleft>
Me@0 205 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
Me@0 206 border=3D1>
Me@0 207 <TBODY>
Me@0 208 <TR>
Me@0 209 <TD>[0000,0001]</TD>
Me@0 210 <TD>ascending</TD></TR>
Me@0 211 <TR>
Me@0 212 <TD>[0010,0011]</TD>
Me@0 213 <TD>descending</TD></TR>
Me@0 214 <TR>
Me@0 215 <TD>[0100,0101]</TD>
Me@0 216 <TD>ascending</TD></TR>
Me@0 217 <TR>
Me@0 218 <TD>[0110,0111]</TD>
Me@0 219 <TD>descending</TD></TR></TBODY></TABLE></DIV></LI></OL>
Me@0 220 <BLOCKQUOTE>
Me@0 221 <UL>
Me@0 222 <LI>Pairs of elements whose numbers differ in bit 0, the lowest bit, =
Me@0 223 are=20
Me@0 224 compared and conditionally exchanged.=20
Me@0 225 <LI>Pairs of numbers whose bit 1 is zero are sorted in ascending =
Me@0 226 order.=20
Me@0 227 Those whose bit 1 is one are sorted into descending order.=20
Me@0 228 </LI></UL></BLOCKQUOTE>
Me@0 229 <OL start=3D3>
Me@0 230 <LI>These pairs are compared and conditionally exchanged: </LI></OL>
Me@0 231 <BLOCKQUOTE>
Me@0 232 <P>First, corresponding to the top level merge call:</P></BLOCKQUOTE>
Me@0 233 <BLOCKQUOTE>
Me@0 234 <DIV align=3Dleft>
Me@0 235 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
Me@0 236 border=3D1>
Me@0 237 <TBODY>
Me@0 238 <TR>
Me@0 239 <TD>0000&lt;-&gt;0010</TD>
Me@0 240 <TD>ascending</TD></TR>
Me@0 241 <TR>
Me@0 242 <TD>0001&lt;-&gt;0011</TD>
Me@0 243 <TD>ascending</TD></TR>
Me@0 244 <TR>
Me@0 245 <TD>0100&lt;-&gt;0110</TD>
Me@0 246 <TD>descending</TD></TR>
Me@0 247 <TR>
Me@0 248 <TD>0101&lt;-&gt;0111</TD>
Me@0 249 <TD>descending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE>
Me@0 250 <BLOCKQUOTE>
Me@0 251 <P>Second, corresponding to the recursive merge =
Me@0 252 calls:</P></BLOCKQUOTE>
Me@0 253 <BLOCKQUOTE>
Me@0 254 <DIV align=3Dleft>
Me@0 255 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
Me@0 256 border=3D1>
Me@0 257 <TBODY>
Me@0 258 <TR>
Me@0 259 <TD>0000&lt;-&gt;0001</TD>
Me@0 260 <TD>ascending</TD></TR>
Me@0 261 <TR>
Me@0 262 <TD>0010&lt;-&gt;0011</TD>
Me@0 263 <TD>ascending</TD></TR>
Me@0 264 <TR>
Me@0 265 <TD>0100&lt;-&gt;0101</TD>
Me@0 266 <TD>descending</TD></TR>
Me@0 267 <TR>
Me@0 268 <TD>0110&lt;-&gt;0111</TD>
Me@0 269 <TD>descending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE>
Me@0 270 <BLOCKQUOTE>
Me@0 271 <P>In both cases, bit 2 determines whether the elements are sorted =
Me@0 272 ascending=20
Me@0 273 (bit 2 equals 0) or descending (=3D1).</P>
Me@0 274 <P>In the first level recursive call of mergeup or mergedown, the =
Me@0 275 elements=20
Me@0 276 compared have positions that differ in bit 1. In the second level =
Me@0 277 calls, the=20
Me@0 278 elements compared differ in bit 0.</P></BLOCKQUOTE>
Me@0 279 <OL start=3D4>
Me@0 280 <LI>The final series of merges that puts the array in order =
Me@0 281 corresponds to=20
Me@0 282 three levels of calls to mergeup.=20
Me@0 283 <P>First level call of mergeup:</P>
Me@0 284 <DIV align=3Dleft>
Me@0 285 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
Me@0 286 border=3D1>
Me@0 287 <TBODY>
Me@0 288 <TR>
Me@0 289 <TD>0000&lt;-&gt;0100</TD>
Me@0 290 <TD>ascending</TD></TR>
Me@0 291 <TR>
Me@0 292 <TD>0001&lt;-&gt;0101</TD>
Me@0 293 <TD>ascending</TD></TR>
Me@0 294 <TR>
Me@0 295 <TD>0010&lt;-&gt;0110</TD>
Me@0 296 <TD>ascending</TD></TR>
Me@0 297 <TR>
Me@0 298 <TD>0011&lt;-&gt;0111</TD>
Me@0 299 <TD>ascending</TD></TR></TBODY></TABLE></DIV></LI></OL>
Me@0 300 <BLOCKQUOTE>
Me@0 301 <P>Two second level recursive calls of mergeup:</P></BLOCKQUOTE>
Me@0 302 <BLOCKQUOTE>
Me@0 303 <DIV align=3Dleft>
Me@0 304 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
Me@0 305 border=3D1>
Me@0 306 <TBODY>
Me@0 307 <TR>
Me@0 308 <TD>0000&lt;-&gt;0010</TD>
Me@0 309 <TD>ascending</TD></TR>
Me@0 310 <TR>
Me@0 311 <TD>0001&lt;-&gt;0011</TD>
Me@0 312 <TD>ascending</TD></TR>
Me@0 313 <TR>
Me@0 314 <TD>0100&lt;-&gt;0110</TD>
Me@0 315 <TD>ascending</TD></TR>
Me@0 316 <TR>
Me@0 317 <TD>0101&lt;-&gt;0111</TD>
Me@0 318 <TD>ascending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE>
Me@0 319 <BLOCKQUOTE>
Me@0 320 <P>Four third level recursive calls of mergeup:</P></BLOCKQUOTE>
Me@0 321 <BLOCKQUOTE>
Me@0 322 <DIV align=3Dleft>
Me@0 323 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
Me@0 324 border=3D1>
Me@0 325 <TBODY>
Me@0 326 <TR>
Me@0 327 <TD>0000&lt;-&gt;0001</TD>
Me@0 328 <TD>ascending</TD></TR>
Me@0 329 <TR>
Me@0 330 <TD>0010&lt;-&gt;0011</TD>
Me@0 331 <TD>ascending</TD></TR>
Me@0 332 <TR>
Me@0 333 <TD>0100&lt;-&gt;0101</TD>
Me@0 334 <TD>ascending</TD></TR>
Me@0 335 <TR>
Me@0 336 <TD>0110&lt;-&gt;0111</TD>
Me@0 337 <TD>ascending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE>
Me@0 338 <BLOCKQUOTE>
Me@0 339 <P>In all cases, bit 3 determines that the elements are sorted =
Me@0 340 ascending (bit=20
Me@0 341 3 equals 0).</P>
Me@0 342 <P>In the first level recursive call of mergeup or mergedown, the =
Me@0 343 elements=20
Me@0 344 compared have positions that differ in bit 2. In the second level =
Me@0 345 calls, the=20
Me@0 346 elements compared differ in bit 1. In the third level calls, the =
Me@0 347 elements=20
Me@0 348 compared differ in bit 0.</P>
Me@0 349 <P>So here's the code:</P>
Me@0 350 <BLOCKQUOTE><PRE> <FONT face=3DCourier> </FONT>int i,j,k;
Me@0 351 for (k=3D2;k&lt;=3DN;k=3D2*k) {
Me@0 352 for (j=3Dk&gt;&gt;1;j&gt;0;j=3Dj&gt;&gt;1) {
Me@0 353 for (i=3D0;i&lt;N;i++) {
Me@0 354 int ixj=3Di^j;
Me@0 355 if ((ixj)&gt;i) {
Me@0 356 if ((i&amp;k)=3D=3D0 &amp;&amp; get(i)&gt;get(ixj)) =
Me@0 357 exchange(i,ixj);
Me@0 358 if ((i&amp;k)!=3D0 &amp;&amp; get(i)&lt;get(ixj)) =
Me@0 359 exchange(i,ixj);
Me@0 360 }
Me@0 361 }
Me@0 362 }
Me@0 363 }</PRE></BLOCKQUOTE>
Me@0 364 <P>In this code, k selects the bit position that determines whether =
Me@0 365 the pairs=20
Me@0 366 of elements are to be exchanged into ascending or descending order. =
Me@0 367 Variable j=20
Me@0 368 corresponds to the distance apart the elements are that are to be =
Me@0 369 compared and=20
Me@0 370 conditionally exchanged. &nbsp; Variable i goes through all the =
Me@0 371 elements; ixj=20
Me@0 372 is the element that is the pair of element i (the exclusive-or of i =
Me@0 373 and j, the=20
Me@0 374 element whose position differs only in bit position (log<SUB>2</SUB> =
Me@0 375 j)). We=20
Me@0 376 only compare elements i and ixj if i&lt;ixj. This avoids comparing =
Me@0 377 them=20
Me@0 378 twice.</P></BLOCKQUOTE>
Me@0 379 <P><APPLET height=3D200 archive=3Dsorts3.jar width=3D400 align=3Dleft=20
Me@0 380 code=3Dcom.toolsofcomputing.SortApplets.BitonicSort3.class>
Me@0 381 Bitonic Sort3</APPLET> <B>Bitonic Sort3</B><STRONG>.</STRONG> The third =
Me@0 382 version=20
Me@0 383 of bitonic sort is the same as the second except that the array is shown =
Me@0 384 after=20
Me@0 385 each iteration of the <EM>for i</EM> loop. This gives the appearance of =
Me@0 386 a=20
Me@0 387 parallel algorithm.</P>
Me@0 388 <P>In this version, the delay between each showing of the array is set =
Me@0 389 to five=20
Me@0 390 times the delay following exchanges of single elements in the other =
Me@0 391 versions.=20
Me@0 392 There are two reasons: first, it simulates the longer time required to =
Me@0 393 exchange=20
Me@0 394 elements between nodes of a distributed memory parallel computer, and =
Me@0 395 second, it=20
Me@0 396 slows down the simulation enough that you will be able to make sense of =
Me@0 397 it. </P>
Me@0 398 <P>&nbsp;</P>
Me@0 399 <P>&nbsp;</P>
Me@0 400 <P><STRONG>Parallel bitonic sort.&nbsp; </STRONG>Here is a version of =
Me@0 401 bitonic=20
Me@0 402 sort that uses the Tools of Computing thread package. A version of the =
Me@0 403 first=20
Me@0 404 bitonic sort algorithm builds a task graph to do the sorting. The tasks =
Me@0 405 are=20
Me@0 406 placed in a RunQueue when they become runnable. Tasks become runnable =
Me@0 407 when all=20
Me@0 408 tasks in a predecessor set have terminated. There are a limited number =
Me@0 409 of=20
Me@0 410 Threads (4) running tasks from the queue. When tasks complete, they =
Me@0 411 signal a=20
Me@0 412 TerminationGroup. When all tasks in a TerminationGroup have signaled =
Me@0 413 their=20
Me@0 414 completion, the tasks waiting for the termination of that group are made =
Me@0 415
Me@0 416 runnable.</P>
Me@0 417 <P><APPLET height=3D200 archive=3Dsorts3.jar width=3D768=20
Me@0 418 code=3Dcom.toolsofcomputing.SortApplets.ParBitonicSort.class>
Me@0 419 ParBitonicSort </APPLET> </P>
Me@0 420 <P><A=20
Me@0 421 href=3D"http://www.tools-of-computing.com/tc/CS/Sorts/SortAlgorithms.htm"=
Me@0 422 >Back to=20
Me@0 423 beginning of the tutorial</A></P></BODY></HTML>