contrib/bubblesort.fleet

   1 // bubblesort.fleet
   2 // Author: Thomas Kho <tkho@eecs.berkeley.edu>
   3
   4 #import edu.berkeley.fleet.ships
   5
   6 // 20 elements in memory
   7 #memory { 1, 2, 6, 1, 3, 9, 4, 4, 7, 1,
   8           9, 4, 7, 6, 1, 2, 3, 0, 9, 3 }
   9
  10 #ship memread      : MemoryReadShip   // ports: addr, stride, count, data, done
  11 #ship memwrite     : MemoryWriteShip  // ports: addr, stride, count, data, done
  12
  13 #ship halt         : HaltShip         // ports: in
  14 #ship fetch        : FetchShip        // ports: codebag, release, revoke, done
  15 #ship tokensource  : TokenSourceShip  // ports: out
  16 #ship bitbucket    : BitBucketShip    // ports: token, data
  17 #ship debug        : DebugShip        // ports: token, data
  18 #ship counter      : HomeworkCounter  // ports: load, zero, positive, ask
  19 #ship itercnt      : HomeworkCounter  // ports: load, zero, positive, ask
  20
  21 #ship max          : ArithmeticShip   // ports: A, B, cmd, out
  22 #ship min          : ArithmeticShip   // ports: A, B, cmd, out
  23
  24 #ship dup1         : DuplicatorShip   // ports: in, out1, out2, out3, out4
  25 #ship dup2         : DuplicatorShip   // ports: in, out1, out2, out3, out4
  26
  27 #ship tokenfifo    : TokenFifo        // ports: in, out
  28 #ship donecodebag  : FifoShip         // ports: in, out
  29
  30 #ship nextcodebag  : FifoShip         // ports: in, out
  31 #ship exitcodebag  : FifoShip         // ports: in, out
  32
  33 // first, load itercnt counter
  34 {
  35   fetch.done -> bitbucket.token
  36
  37   move+ack itercnt.load -> fetch.release
  38   itercnt.load -[*]-> ()
  39
  40   itercnt.positive -[*]-> nextcodebag.out
  41   itercnt.zero -> exitcodebag.out
  42   // use tokens from itercnt to trigger delivery of the correct codebag
  43   triggered move nextcodebag.out -[*]-> fetch.codebag
  44   triggered move exitcodebag.out -[*]-> fetch.codebag
  45   CLEANUP -> exitcodebag.in
  46
  47   FETCH_NEXT -> fetch.codebag
  48   19 -> itercnt.load
  49 } -> fetch.codebag
  50 nop+ack itercnt.load -> fetch.release
  51
  52 FETCH_NEXT: { // itercnt loaded
  53   fetch.done -> bitbucket.token
  54
  55   LOOP_BODY -> nextcodebag.in
  56   tokensource.out -> itercnt.ask
  57   tokensource.out -> fetch.release
  58 }
  59
  60 LOOP_BODY: {
  61   fetch.done -> bitbucket.token
  62
  63   // donecodebag.in is called after one iteration of sort
  64   FETCH_NEXT -> donecodebag.in
  65   tokensource.out -> fetch.release
  66   SORT_ONCE -> fetch.codebag
  67 }
  68
  69 CLEANUP: {
  70   fetch.done -> bitbucket.token
  71
  72   nop+ack exitcodebag.out -> tokenfifo.in
  73   nop+ack nextcodebag.out -> tokenfifo.in
  74   nop+ack itercnt.positive -> tokenfifo.in
  75   nextcodebag.out -> bitbucket.data
  76   tokenfifo.out -[2]-> bitbucket.token
  77   tokenfifo.out -> halt.in
  78 }
  79
  80 SORT_ONCE: {
  81   fetch.done -> bitbucket.token
  82
  83   0 -> memread.addr
  84   1 -> memread.stride
  85   20 -> memread.count
  86   memread.done -> bitbucket.token
  87
  88   // in-place sorting
  89   0 -> memwrite.addr
  90   1 -> memwrite.stride
  91   20 -> memwrite.count
  92   memwrite.done -> bitbucket.token
  93
  94   // clear standing moves at inboxes that will ack
  95   nop+ack dup1.in -> tokenfifo.in
  96   nop+ack dup2.in -> tokenfifo.in
  97   nop+ack max.A -> tokenfifo.in
  98   nop+ack max.B -> tokenfifo.in
  99   nop+ack max.cmd -> tokenfifo.in
 100   nop+ack min.A -> tokenfifo.in
 101   nop+ack min.B -> tokenfifo.in
 102   nop+ack min.cmd -> tokenfifo.in
 103   nop+ack memwrite.data -> tokenfifo.in
 104   nop+ack counter.load -> tokenfifo.in
 105   tokenfifo.out -[9]-> bitbucket.token
 106   tokenfifo.out -> fetch.release
 107
 108   {
 109     fetch.done -> bitbucket.token
 110
 111     move+ack counter.load -> fetch.release
 112     counter.load -[*]-> () // restore standing move
 113     19 -> counter.load // load N - 1 into counter
 114
 115     { // on counter load, seed pipeline
 116       fetch.done -> bitbucket.token
 117
 118       tokensource.out -[3]-> counter.ask
 119     } -> fetch.codebag
 120
 121     // send first memread.data to dup2.in
 122     memread.data -> dup2.in
 123
 124     // counting pipeline: min.out -> memwrite.data
 125     triggered move min.out -[*]-> memwrite.data
 126     accept+ack memwrite.data -[*]-> counter.ask
 127     counter.positive -[*]-> min.out
 128
 129     // standing commands on min, max ships
 130     copy min.cmd -[*]-> ()
 131     "MIN ZERO ZERO" -> min.cmd
 132     copy max.cmd -[*]-> ()
 133     "MAX ZERO ZERO" -> max.cmd
 134
 135     // pipelines: dup1 -> max, dup2 -> max, dup1 -> min, dup2 -> min
 136     triggered move dup1.out1 -[*]-> max.A
 137     accept+ack max.A -[*]-> dup1.out1
 138     triggered move dup2.out1 -[*]-> max.B
 139     accept+ack max.B -[*]-> dup2.out1
 140     triggered move dup1.out2 -[*]-> min.A
 141     accept+ack min.A -[*]-> dup1.out2
 142     triggered move dup2.out2 -[*]-> min.B
 143     accept+ack min.B -[*]-> dup2.out2
 144
 145     // pipeline: max.out -> dup2.in
 146     triggered move max.out -[*]-> dup2.in
 147     accept+ack dup2.in -[*]-> max.out
 148
 149     // pipeline: memread.data -> dup1.in
 150     triggered move memread.data -[*]-> dup1.in
 151     accept+ack dup1.in -[*]-> memread.data
 152
 153     // seed the above 6 pipelines
 154     tokensource.out -[3]-> dup1.out1
 155     tokensource.out -[3]-> dup1.out2
 156     tokensource.out -[3]-> dup2.out1
 157     tokensource.out -[3]-> dup2.out2
 158     tokensource.out -[3]-> memread.data
 159     tokensource.out -[2]-> max.out // also seeded with first data
 160
 161     // ignore dup[12].out[03]
 162     dup1.out3 -[*]-> bitbucket.data
 163     dup1.out0 -[*]-> bitbucket.data
 164     dup2.out3 -[*]-> bitbucket.data
 165     dup2.out0 -[*]-> bitbucket.data
 166
 167     // setup exit condition
 168     counter.zero -[2]-> bitbucket.token
 169     counter.zero -> fetch.release
 170
 171     { // after N-1 writes
 172       fetch.done -> bitbucket.token
 173
 174       // once we're done with N-1 writes, we can flush the last one
 175       // by comparing with MAXINT
 176       999 -> dup1.in
 177       tokensource.out -> min.out
 178       counter.zero -> fetch.release // trigger next codebag
 179     } -> fetch.codebag
 180
 181     { // cleanup codebag
 182       fetch.done -> bitbucket.token
 183
 184       // clear outbox standing moves
 185       nop+ack dup1.out0 -> tokenfifo.in
 186       nop+ack dup1.out3 -> tokenfifo.in
 187       nop+ack dup2.out0 -> tokenfifo.in
 188       nop+ack dup2.out3 -> tokenfifo.in
 189       nop+ack counter.positive -> tokenfifo.in
 190       nop+ack min.out -> tokenfifo.in
 191
 192       // get rid of tokens
 193       triggered nop+ack memread.data -[4]-> tokenfifo.in // 3 + flush
 194       triggered nop+ack max.out -[3]-> tokenfifo.in
 195       triggered nop+ack dup1.out1 -[3]-> tokenfifo.in
 196       triggered nop+ack dup1.out2 -[3]-> tokenfifo.in
 197       triggered nop+ack dup2.out1 -[3]-> tokenfifo.in
 198       triggered nop+ack dup2.out2 -[3]-> tokenfifo.in
 199
 200       // this, paired with MAXINT at port B, will kill standing copy
 201       0 -> max.A
 202       0 -> min.A
 203       max.out -> bitbucket.data
 204       min.out -> bitbucket.data
 205
 206       // restore unacked inbox standing moves
 207       nop+ack memwrite.data -> tokenfifo.in
 208       memwrite.data -[*]-> ()
 209       nop+ack dup1.in -> tokenfifo.in
 210       dup1.in -[*]-> ()
 211       nop+ack dup2.in -> tokenfifo.in
 212       dup2.in -[*]-> ()
 213       nop+ack max.A -> tokenfifo.in
 214       max.A -[*]-> ()
 215       nop+ack min.A -> tokenfifo.in
 216       min.A -[*]-> ()
 217       nop+ack max.B -> tokenfifo.in
 218       max.B -[*]-> ()
 219       nop+ack min.B -> tokenfifo.in
 220       min.B -[*]-> ()
 221       nop+ack max.cmd -> tokenfifo.in
 222       max.cmd -[*]-> ()
 223       nop+ack min.cmd -> tokenfifo.in
 224       min.cmd -[*]-> ()
 225
 226       tokenfifo.out -[33]-> bitbucket.token
 227       tokenfifo.out -> fetch.release
 228     } -> fetch.codebag
 229
 230     {
 231       fetch.done -> bitbucket.token
 232
 233       // standing copy is gone, so get rid of this last cmd
 234       0 -> max.A
 235       0 -> min.A
 236       0 -> max.B
 237       0 -> min.B
 238
 239       // probably lax on the sequencing here
 240       max.out -> bitbucket.data
 241       min.out -> bitbucket.data
 242
 243       // "function calls" return with a continuation
 244       tokensource.out -> fetch.release
 245       donecodebag.out -> fetch.codebag
 246     } -> fetch.codebag
 247   } -> fetch.codebag
 248 }
 249