   1 :program BatcherBitonicSort;
                                           0 :PROGRAM 8196 8265 37 507
   2 :{
   3 :COMPLEJIDAD:
   4 :Procesadores: O(n)
   5 :HISTORIA: bug corregido. 16.10.93:
   6 :
   7 :	    i := center+name-left+1;
   8 :	    xi := x[i];
   9 :}
  10 :const
  11 :  maxElements = 8191; (* debera ser de la forma 2^n - 1 *)
  12 :  logmaxElements = 13;
  13 :{
  14 :
  15 :N  - 2^N
  16 :7  - 128
  17 :8  - 256
  18 :9  - 512
  19 :10 - 1024
  20 :11 - 2048
  21 :12 - 4096
  22 :13 - 8192
  23 :}
  24 :
  25 :type   vector = array [0..maxElements] of integer;
  26 :
  27 :var
  28 :  x : shared vector;
  29 :  n : integer; (* dimension *)
  30 :  logn : integer;
  31 :  timer,t : integer;
  32 :
  33 :  procedure readVector;
                                           5 :PROCEDURE 1 8 0 5
  34 :  var i : integer;
  35 :  begin
  36 :    writeln('Bitonic Sort');
                                          10 :CONSTANT 1869900098
                                          12 :CONSTANT 543385966
                                          14 :CONSTANT 1953656659
                                          16 :WRITESTR 3 12
                                          19 :CONSTANT 2573
                                          21 :WRITESTR 1 2
  37 :    write('n = (power of two and 0 < n <=',maxElements+1,') : ');
                                          24 :CONSTANT 540876910
                                          26 :CONSTANT 2003791912
                                          28 :CONSTANT 1864397413
                                          30 :CONSTANT 2004099174
                                          32 :CONSTANT 1851859055
                                          34 :CONSTANT 540024932
                                          36 :CONSTANT 544088124
                                          38 :CONSTANT 544095548
                                          40 :WRITESTR 8 30
                                          43 :CONSTANT 8191
                                          45 :CONSTANT 1
                                          47 :ADD
                                          48 :WRITEINT
                                          49 :CONSTANT 540680233
                                          51 :WRITESTR 1 4
  38 :    readln(n);
                                          54 :GLOBALVAR 8195
                                          56 :PRIVATEREADINT
  39 :    write('log n (base is 2) = ');
                                          57 :CONSTANT 543649644
                                          59 :CONSTANT 1646796910
                                          61 :CONSTANT 543519585
                                          63 :CONSTANT 840987497
                                          65 :CONSTANT 540876841
                                          67 :WRITESTR 5 20
  40 :    readln(logn);
                                          70 :GLOBALVAR 8196
                                          72 :PRIVATEREADINT
  41 :    for 0 to n-1 do
                                          73 :CONSTANT 0
                                          75 :GLOBALVALUE 8195
                                          77 :CONSTANT 1
                                          79 :SUBTRACT
  42 :      begin
                                          80 :INITFOR 14
  43 :	{ write('x[',counter,'] = '); }
  44 :	read(x[counter]);
                                          82 :GLOBALVAR 3
                                          84 :PUSHCOUNTER
                                          85 :INDEX 0 8191 1 44
                                          90 :READINT
  45 :      end;
                                          91 :LOOP -9 1
  46 :  end;
                                          94 :ENDPROC 0
  47 :
  48 :  procedure generateVector;
                                          96 :PROCEDURE 1 4 0 5
  49 :  var
  50 :    i : integer;
  51 :  begin
  52 :    n := maxElements+1;
                                         101 :GLOBALVAR 8195
                                         103 :CONSTANT 8191
                                         105 :CONSTANT 1
                                         107 :ADD
                                         108 :PRIVATESIMPLEASSIGN
  53 :    logn := logMaxElements;
                                         109 :GLOBALVAR 8196
                                         111 :CONSTANT 13
                                         113 :PRIVATESIMPLEASSIGN
  54 :    randomize;
                                         114 :RANDOMIZE
  55 :    for 0 to maxElements do
                                         115 :CONSTANT 0
                                         117 :CONSTANT 8191
  56 :      begin
                                         119 :INITFOR 18
  57 :	x[counter] := random(1000);
                                         121 :GLOBALVAR 3
                                         123 :PUSHCOUNTER
                                         124 :INDEX 0 8191 1 57
                                         129 :CONSTANT 1000
                                         131 :RANDOM 1
                                         133 :SIMPLEASSIGN
  58 :	{
  59 :	if (counter mod 10) = 0 then
  60 :	write(x[counter],' ');
  61 :	}
  62 :      end;
                                         134 :LOOP -13 1
  63 :  end;
                                         137 :ENDPROC 0
  64 :
  65 :  procedure writeVector;
                                         139 :PROCEDURE 1 4 0 5
  66 :  var i : integer;
  67 :  begin
  68 :    for 0 to n-1 do
                                         144 :CONSTANT 0
                                         146 :GLOBALVALUE 8195
                                         148 :CONSTANT 1
                                         150 :SUBTRACT
  69 :      begin
                                         151 :INITFOR 37
  70 :	writeln('x[',counter,'] = ',x[counter],' ');
                                         153 :CONSTANT 23416
                                         155 :WRITESTR 1 2
                                         158 :PUSHCOUNTER
                                         159 :WRITEINT
                                         160 :CONSTANT 540876893
                                         162 :WRITESTR 1 4
                                         165 :GLOBALVAR 3
                                         167 :PUSHCOUNTER
                                         168 :INDEX 0 8191 1 70
                                         173 :SIMPLEVALUE
                                         174 :WRITEINT
                                         175 :CONSTANT 32
                                         177 :WRITESTR 1 1
                                         180 :CONSTANT 2573
                                         182 :WRITESTR 1 2
  71 :      end;
                                         185 :LOOP -32 1
  72 :  end;
                                         188 :ENDPROC 0
  73 :
  74 :
  75 :  shared procedure (*task*) bSort(left,right : shared integer;direction : shared boolean);
                                         190 :PROCEDURE 0 1 2 5
  76 :  (* ordena la secuencia bitonica x en orden ascendente si *)
  77 :  (* direction es TRUE y en orden descendente si es FALSE  *)
  78 :  begin
  79 :    if right > left then
                                         195 :LOCALVALUE -2
                                         197 :LOCALVALUE -3
                                         199 :GREATERINT
  80 :      var center : shared integer;
                                         200 :PUSHPATTERN
                                         201 :COPYTOPS
                                         202 :GOIFZERO 186
  81 :      begin
                                         204 :NEWBLOCK 1
  82 :        center := (left + right) div 2;
                                         206 :LOCALVAR 3
                                         208 :GLOBALVALUE -3
                                         210 :GLOBALVALUE -2
                                         212 :ADD
                                         213 :CONSTANT 2
                                         215 :DIVIDE
                                         216 :SIMPLEASSIGN
  83 :        parallel left..center do
                                         217 :GLOBALVALUE -3
                                         219 :LOCALVALUE 3
                                         221 :NESTEDPATTERN 121 1
  84 :          var i, temp1, temp2, xname, xi : integer;
  85 :          begin
                                         224 :NEWBLOCK 5
  86 :            xname := x[name] ;
                                         226 :LOCALVAR 6
                                         228 :GLOBALVARTHREE 3
                                         230 :PUSHNAME 86
                                         232 :INDEX 0 8191 1 86
                                         237 :SIMPLEVALUE
                                         238 :PRIVATESIMPLEASSIGN
  87 :            i := center+name-left+1;
                                         239 :LOCALVAR 3
                                         241 :GLOBALVALUE 3
                                         243 :PUSHNAME 87
                                         245 :ADD
                                         246 :GLOBALVALUETWO -3
                                         248 :SUBTRACT
                                         249 :CONSTANT 1
                                         251 :ADD
                                         252 :PRIVATESIMPLEASSIGN
  88 :            xi := x[i];
                                         253 :LOCALVAR 7
                                         255 :GLOBALVARTHREE 3
                                         257 :LOCALVALUE 3
                                         259 :INDEX 0 8191 1 88
                                         264 :SIMPLEVALUE
                                         265 :PRIVATESIMPLEASSIGN
  89 :            temp1 := xname min xi;
                                         266 :LOCALVAR 4
                                         268 :LOCALVALUE 6
                                         270 :LOCALVALUE 7
                                         272 :MIN
                                         273 :PRIVATESIMPLEASSIGN
  90 :            temp2 := xname max xi;
                                         274 :LOCALVAR 5
                                         276 :LOCALVALUE 6
                                         278 :LOCALVALUE 7
                                         280 :MAX
                                         281 :PRIVATESIMPLEASSIGN
  91 :            if direction then
                                         282 :GLOBALVALUETWO -1
  92 :              begin
                                         284 :PUSHPATTERN
                                         285 :COPYTOPS
                                         286 :GOIFZERO 26
  93 :                x[name] := temp1;
                                         288 :GLOBALVARTHREE 3
                                         290 :PUSHNAME 93
                                         292 :INDEX 0 8191 1 93
                                         297 :LOCALVALUE 4
                                         299 :SIMPLEASSIGN
  94 :                x[i] := temp2;
                                         300 :GLOBALVARTHREE 3
                                         302 :LOCALVALUE 3
                                         304 :INDEX 0 8191 1 94
                                         309 :LOCALVALUE 5
                                         311 :SIMPLEASSIGN
  95 :              end
  96 :            else
                                         312 :COMPLEMENT
                                         313 :GOIFZERO 26
  97 :           begin
  98 :             x[name] := temp2;
                                         315 :GLOBALVARTHREE 3
                                         317 :PUSHNAME 98
                                         319 :INDEX 0 8191 1 98
                                         324 :LOCALVALUE 5
                                         326 :SIMPLEASSIGN
  99 :             x[i] := temp1;
                                         327 :GLOBALVARTHREE 3
                                         329 :LOCALVALUE 3
                                         331 :INDEX 0 8191 1 99
                                         336 :LOCALVALUE 4
                                         338 :SIMPLEASSIGN
 100 :           end;
                                         339 :POPPATTERN
 101 :        end;
                                         340 :ENDBLOCK
                                         341 :ENDNESTEDPATTERN
 102 :        parallel do
 103 :          bSort(left,center,direction) || bSort(center+1,right,direction);
                                         342 :CONSTANT 0
                                         344 :CONSTANT 1
                                         346 :NESTEDPATTERN 41 1
                                         349 :PUSHPATTERN
                                         350 :SINGLECONTROL 0
                                         352 :GLOBALVALUE -3
                                         354 :SHARED 1
                                         356 :LOCALVALUE 3
                                         358 :SHARED 1
                                         360 :GLOBALVALUE -1
                                         362 :SHARED 1
                                         364 :POPPATTERN
                                         365 :PUSHPATTERN
                                         366 :SINGLECONTROL 1
                                         368 :LOCALVALUE 3
                                         370 :CONSTANT 1
                                         372 :ADD
                                         373 :SHARED 1
                                         375 :GLOBALVALUE -2
                                         377 :SHARED 1
                                         379 :GLOBALVALUE -1
                                         381 :SHARED 1
                                         383 :POPPATTERN
                                         384 :GLOBALCALLTWO -194
                                         386 :ENDNESTEDPATTERN
 104 :      end
 105 :  end (* bSort *);
                                         387 :ENDBLOCK
                                         388 :POPPATTERN
                                         389 :ENDPROC 3
 106 :
 107 :
 108 :  procedure bitonicSort;
                                         391 :PROCEDURE 3 5 0 5
 109 :  var
 110 :    length : shared integer;
 111 :    i, numOfIntervals : integer;
 112 :  begin
 113 :    for 1 to logn do
                                         396 :CONSTANT 1
                                         398 :GLOBALVALUE 8196
 114 :      begin
                                         400 :INITFOR 105
 115 :        length := &counter;
                                         402 :LOCALVAR 3
                                         404 :CONSTANT 1
                                         406 :PUSHCOUNTER
                                         407 :SHLINT
                                         408 :SIMPLEASSIGN
 116 :        writeln('length= ', length);
                                         409 :CONSTANT 1735288172
                                         411 :CONSTANT 540895348
                                         413 :WRITESTR 2 8
                                         416 :LOCALVALUE 3
                                         418 :WRITEINT
                                         419 :CONSTANT 2573
                                         421 :WRITESTR 1 2
 117 :        numOfIntervals := n div length;
                                         424 :LOCALVAR 5
                                         426 :GLOBALVALUE 8195
                                         428 :LOCALVALUE 3
                                         430 :DIVIDE
                                         431 :PRIVATESIMPLEASSIGN
 118 :        writeln('intervals= ', numOfIntervals);
                                         432 :CONSTANT 1702129257
                                         434 :CONSTANT 1818326642
                                         436 :CONSTANT 1814052211
                                         438 :WRITESTR 3 11
                                         441 :LOCALVALUE 5
                                         443 :WRITEINT
                                         444 :CONSTANT 2573
                                         446 :WRITESTR 1 2
 119 :        parallel 0..numOfIntervals-1 do
                                         449 :CONSTANT 0
                                         451 :LOCALVALUE 5
                                         453 :CONSTANT 1
                                         455 :SUBTRACT
                                         456 :PATTERN 46 1
 120 :          var first, last : integer;
 121 :          begin
                                         459 :NEWBLOCK 2
 122 :            first := name*length;
                                         461 :LOCALVAR 3
                                         463 :PUSHNAME 122
                                         465 :GLOBALVALUE 3
                                         467 :MULTIPLY
                                         468 :PRIVATESIMPLEASSIGN
 123 :            last := first+length-1;
                                         469 :LOCALVAR 4
                                         471 :LOCALVALUE 3
                                         473 :GLOBALVALUE 3
                                         475 :ADD
                                         476 :CONSTANT 1
                                         478 :SUBTRACT
                                         479 :PRIVATESIMPLEASSIGN
 124 :            bSort(first,last,(name mod 2 = 0));
                                         480 :LOCALVALUE 3
                                         482 :SHARED 1
                                         484 :LOCALVALUE 4
                                         486 :SHARED 1
                                         488 :PUSHNAME 124
                                         490 :CONSTANT 2
                                         492 :MODULO
                                         493 :CONSTANT 0
                                         495 :EQUALINT
                                         496 :SHARED 1
                                         498 :GLOBALCALLTWO -308
 125 :         end;
                                         500 :ENDBLOCK
                                         501 :ENDPATTERN
 126 :      end;
                                         502 :LOOP -100 1
 127 :  end;
                                         505 :ENDPROC 0
 128 :
 129 :begin
 130 :  writeln('Maximo N§ de elementos: ', maxElements);
                                         507 :CONSTANT 1769496909
                                         509 :CONSTANT 1310748525
                                         511 :CONSTANT 1701060775
                                         513 :CONSTANT 1701602592
                                         515 :CONSTANT 1953391981
                                         517 :CONSTANT 540701551
                                         519 :WRITESTR 6 24
                                         522 :CONSTANT 8191
                                         524 :WRITEINT
                                         525 :CONSTANT 2573
                                         527 :WRITESTR 1 2
 131 :
 132 :  readVector;
                                         530 :LOCALCALL -525
 133 :  { generateVector; }
 134 :
 135 :  writeln;
                                         532 :CONSTANT 2573
                                         534 :WRITESTR 1 2
 136 :  writeln('Vector generado.');
                                         537 :CONSTANT 1952671062
                                         539 :CONSTANT 1730179695
                                         541 :CONSTANT 1919250021
                                         543 :CONSTANT 779052129
                                         545 :WRITESTR 4 16
                                         548 :CONSTANT 2573
                                         550 :WRITESTR 1 2
 137 :
 138 :
 139 :  writeln('Comienza la ordenaci¢n.');
                                         553 :CONSTANT 1768779587
                                         555 :CONSTANT 1635413605
                                         557 :CONSTANT 543255584
                                         559 :CONSTANT 1701081711
                                         561 :CONSTANT 1768120686
                                         563 :CONSTANT 1764650658
                                         565 :WRITESTR 6 23
                                         568 :CONSTANT 2573
                                         570 :WRITESTR 1 2
 140 :  settime(t);
                                         573 :LOCALVAR 8198
                                         575 :PRIVATESETTIME
 141 :  bitonicSort;
                                         576 :LOCALCALL -185
 142 :  gettime(timer,t);
                                         578 :LOCALVAR 8197
                                         580 :LOCALVALUE 8198
                                         582 :PRIVATEGETTIME
 143 :  writeln('Ordenaci¢n FINALIZADA.');
                                         583 :CONSTANT 1701081679
                                         585 :CONSTANT 1768120686
                                         587 :CONSTANT 1176530594
                                         589 :CONSTANT 1279348297
                                         591 :CONSTANT 1145133641
                                         593 :CONSTANT 1145122369
                                         595 :WRITESTR 6 22
                                         598 :CONSTANT 2573
                                         600 :WRITESTR 1 2
 144 :
 145 :  {writeVector;}
 146 :end.
 147 :
                                         603 :ENDPROG
