contrib/sort.fleet

   1 // A bubble sort implementation.
   2 // This only works for 6 input elements. To change the number of input
   3 // elements, modify the counts in the lines marked below.
   4 // Author: Amir Kamil <kamil@cs.berkeley.edu>
   5 // Date:   7/16/07
   6
   7 #import edu.berkeley.fleet.ships
   8 #ship alu          : Alu2b
   9 #ship blu          : Alu2b
  10 #ship debug        : Debug
  11 #ship fifo1        : Fifo
  12 #ship fifo2        : Fifo
  13 #ship fifo3        : Fifo
  14 #ship mem          : Memory
  15
  16 #expect 1
  17 #expect 2
  18 #expect 3
  19 #expect 9
  20 #expect 8
  21 #expect 11
  22
  23 // for debugging; the solution should work with any set of numbers
  24
  25 9:          sendto fifo1.in;
  26 1:          sendto fifo1.in;
  27 3:          sendto fifo1.in;
  28 11:         sendto fifo1.in;
  29 2:          sendto fifo1.in;
  30 8:          sendto fifo1.in;
  31
  32 // basic setup
  33
  34 fifo1.in:   [*] take, deliver;
  35 fifo2.in:   [*] take, deliver;
  36 debug.in:   [*] take, deliver;
  37 alu.in1:    [*] take, deliver;
  38 alu.in2:    [*] take, deliver;
  39 blu.in1:    [*] take, deliver;
  40 blu.in2:    [*] take, deliver;
  41 fifo3.out:  [*] wait, take, sendto mem.inCBD;
  42 mem.inCBD:  [*] take, deliver;
  43
  44 // one loop iteration
  45 // this code needs flow control
  46
  47 ITER: {
  48   fifo1.out:  take, sendto alu.in1.max;
  49               sendto blu.in1.min;
  50               [*] nop;
  51               (*) take, sendto alu.in2;
  52               (*) sendto blu.in2;
  53               kill*;
  54   alu.out:    [*] nop;
  55               (*) take, sendto alu.in1.max;
  56               (*) sendto blu.in1.min;
  57               kill;
  58   blu.out:    [5] take, sendto fifo2.in; // count = num - 1
  59               notify fifo3.out;
  60 }
  61
  62 // iteration cleanup
  63
  64 END: {
  65   0:          sendto alu.in2; // flush
  66   0:          sendto blu.in2; // flush
  67   fifo1.out:  kill;
  68               kill;
  69   alu.out:    kill;
  70               kill;
  71               sendto fifo2.in;
  72               dismiss;
  73   blu.out:    dismiss;
  74   fifo2.out:  [6] take, sendto fifo1.in; // count = num
  75               notify fifo3.out;
  76 }
  77
  78 // overall control
  79
  80 SENDDONE:   sendto fifo3.in;
  81 ITER:       sendto fifo2.in;
  82 END:        sendto fifo2.in;
  83 fifo2.out:  wait;
  84             [*] nop;
  85             (6) take, sendto fifo3.in;   // count = num
  86             (6) sendto fifo2.in;         // count = num
  87             (6) take, sendto fifo3.in;   // count = num
  88             (6) sendto fifo2.in;         // count = num
  89             kill*;
  90 fifo3.in:   take, deliver, notify fifo2.out;
  91             [12] take, deliver;          // count = 2 * num
  92             notify fifo3.out;
  93
  94 // send done cbd into fifo3
  95
  96 SENDDONE: {
  97   DONE:       sendto fifo3.in;
  98   fifo2.out:  [2] dismiss;
  99               notify fifo3.out;
 100   fifo3.in:   take, deliver;
 101 }
 102
 103 // done cbd
 104
 105 DONE: {
 106   fifo1.out:  [6] take, sendto debug.in; // count = num
 107 }