From 91886d89be53ba69e40bb82203f15bbf0f5fa625 Mon Sep 17 00:00:00 2001
From: tkho <tkho@eecs.berkeley.edu>
Date: Mon, 18 Dec 2006 11:05:32 +0100
Subject: [PATCH] added bubblesort.fleet in contrib

---
 contrib/bubblesort.fleet |  249 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 249 insertions(+)
 create mode 100644 contrib/bubblesort.fleet

diff --git a/contrib/bubblesort.fleet b/contrib/bubblesort.fleet
new file mode 100644
index 0000000..4dc8913
--- /dev/null
+++ b/contrib/bubblesort.fleet
@@ -0,0 +1,249 @@
+// bubblesort.fleet
+// Author: Thomas Kho <tkho@eecs.berkeley.edu>
+
+#import edu.berkeley.fleet.ships
+
+// 20 elements in memory
+#memory { 1, 2, 6, 1, 3, 9, 4, 4, 7, 1,
+          9, 4, 7, 6, 1, 2, 3, 0, 9, 3 }
+
+#ship memread      : MemoryReadShip   // ports: addr, stride, count, data, done
+#ship memwrite     : MemoryWriteShip  // ports: addr, stride, count, data, done
+
+#ship halt         : HaltShip         // ports: in
+#ship fetch        : FetchShip        // ports: codebag, release, revoke, done
+#ship tokensource  : TokenSourceShip  // ports: out
+#ship bitbucket    : BitBucketShip    // ports: token, data
+#ship debug        : DebugShip        // ports: token, data
+#ship counter      : HomeworkCounter  // ports: load, zero, positive, ask
+#ship itercnt      : HomeworkCounter  // ports: load, zero, positive, ask
+
+#ship max          : ArithmeticShip   // ports: A, B, cmd, out
+#ship min          : ArithmeticShip   // ports: A, B, cmd, out
+
+#ship dup1         : DuplicatorShip   // ports: in, out1, out2, out3, out4
+#ship dup2         : DuplicatorShip   // ports: in, out1, out2, out3, out4
+
+#ship tokenfifo    : TokenFifo        // ports: in, out
+#ship donecodebag  : FifoShip         // ports: in, out
+
+#ship nextcodebag  : FifoShip         // ports: in, out
+#ship exitcodebag  : FifoShip         // ports: in, out
+
+// first, load itercnt counter
+{
+  fetch.done -> bitbucket.token
+
+  move+ack itercnt.load -> fetch.release
+  itercnt.load -[*]-> ()
+
+  itercnt.positive -[*]-> nextcodebag.out
+  itercnt.zero -> exitcodebag.out
+  // use tokens from itercnt to trigger delivery of the correct codebag
+  triggered move nextcodebag.out -[*]-> fetch.codebag
+  triggered move exitcodebag.out -[*]-> fetch.codebag
+  CLEANUP -> exitcodebag.in
+
+  FETCH_NEXT -> fetch.codebag
+  19 -> itercnt.load
+} -> fetch.codebag
+nop+ack itercnt.load -> fetch.release
+
+FETCH_NEXT: { // itercnt loaded
+  fetch.done -> bitbucket.token
+
+  LOOP_BODY -> nextcodebag.in
+  tokensource.out -> itercnt.ask
+  tokensource.out -> fetch.release
+}
+
+LOOP_BODY: {
+  fetch.done -> bitbucket.token
+
+  // donecodebag.in is called after one iteration of sort
+  FETCH_NEXT -> donecodebag.in
+  tokensource.out -> fetch.release
+  SORT_ONCE -> fetch.codebag
+}
+
+CLEANUP: {
+  fetch.done -> bitbucket.token
+
+  nop+ack exitcodebag.out -> tokenfifo.in
+  nop+ack nextcodebag.out -> tokenfifo.in
+  nop+ack itercnt.positive -> tokenfifo.in
+  nextcodebag.out -> bitbucket.data
+  tokenfifo.out -[2]-> bitbucket.token
+  tokenfifo.out -> halt.in
+}
+
+SORT_ONCE: {
+  fetch.done -> bitbucket.token
+
+  0 -> memread.addr
+  1 -> memread.stride
+  20 -> memread.count
+  memread.done -> bitbucket.token
+
+  // in-place sorting
+  0 -> memwrite.addr
+  1 -> memwrite.stride
+  20 -> memwrite.count
+  memwrite.done -> bitbucket.token
+
+  // clear standing moves at inboxes that will ack
+  nop+ack dup1.in -> tokenfifo.in
+  nop+ack dup2.in -> tokenfifo.in
+  nop+ack max.A -> tokenfifo.in
+  nop+ack max.B -> tokenfifo.in
+  nop+ack max.cmd -> tokenfifo.in
+  nop+ack min.A -> tokenfifo.in
+  nop+ack min.B -> tokenfifo.in
+  nop+ack min.cmd -> tokenfifo.in
+  nop+ack memwrite.data -> tokenfifo.in
+  nop+ack counter.load -> tokenfifo.in
+  tokenfifo.out -[9]-> bitbucket.token
+  tokenfifo.out -> fetch.release
+
+  {
+    fetch.done -> bitbucket.token
+
+    move+ack counter.load -> fetch.release
+    counter.load -[*]-> () // restore standing move
+    19 -> counter.load // load N - 1 into counter
+
+    { // on counter load, seed pipeline
+      fetch.done -> bitbucket.token
+
+      tokensource.out -[3]-> counter.ask
+    } -> fetch.codebag
+
+    // send first memread.data to dup2.in
+    memread.data -> dup2.in
+
+    // counting pipeline: min.out -> memwrite.data
+    triggered move min.out -[*]-> memwrite.data
+    accept+ack memwrite.data -[*]-> counter.ask
+    counter.positive -[*]-> min.out
+
+    // standing commands on min, max ships
+    copy min.cmd -[*]-> ()
+    "MIN ZERO ZERO" -> min.cmd
+    copy max.cmd -[*]-> ()
+    "MAX ZERO ZERO" -> max.cmd
+
+    // pipelines: dup1 -> max, dup2 -> max, dup1 -> min, dup2 -> min
+    triggered move dup1.out1 -[*]-> max.A
+    accept+ack max.A -[*]-> dup1.out1
+    triggered move dup2.out1 -[*]-> max.B
+    accept+ack max.B -[*]-> dup2.out1
+    triggered move dup1.out2 -[*]-> min.A
+    accept+ack min.A -[*]-> dup1.out2
+    triggered move dup2.out2 -[*]-> min.B
+    accept+ack min.B -[*]-> dup2.out2
+
+    // pipeline: max.out -> dup2.in
+    triggered move max.out -[*]-> dup2.in
+    accept+ack dup2.in -[*]-> max.out
+
+    // pipeline: memread.data -> dup1.in
+    triggered move memread.data -[*]-> dup1.in
+    accept+ack dup1.in -[*]-> memread.data
+
+    // seed the above 6 pipelines
+    tokensource.out -[3]-> dup1.out1
+    tokensource.out -[3]-> dup1.out2
+    tokensource.out -[3]-> dup2.out1
+    tokensource.out -[3]-> dup2.out2
+    tokensource.out -[3]-> memread.data
+    tokensource.out -[2]-> max.out // also seeded with first data
+
+    // ignore dup[12].out[03]
+    dup1.out3 -[*]-> bitbucket.data
+    dup1.out0 -[*]-> bitbucket.data
+    dup2.out3 -[*]-> bitbucket.data
+    dup2.out0 -[*]-> bitbucket.data
+
+    // setup exit condition
+    counter.zero -[2]-> bitbucket.token
+    counter.zero -> fetch.release
+
+    { // after N-1 writes
+      fetch.done -> bitbucket.token
+
+      // once we're done with N-1 writes, we can flush the last one
+      // by comparing with MAXINT
+      999 -> dup1.in
+      tokensource.out -> min.out
+      counter.zero -> fetch.release // trigger next codebag
+    } -> fetch.codebag
+
+    { // cleanup codebag
+      fetch.done -> bitbucket.token
+
+      // clear outbox standing moves
+      nop+ack dup1.out0 -> tokenfifo.in
+      nop+ack dup1.out3 -> tokenfifo.in
+      nop+ack dup2.out0 -> tokenfifo.in
+      nop+ack dup2.out3 -> tokenfifo.in
+      nop+ack counter.positive -> tokenfifo.in
+      nop+ack min.out -> tokenfifo.in
+
+      // get rid of tokens
+      triggered nop+ack memread.data -[4]-> tokenfifo.in // 3 + flush
+      triggered nop+ack max.out -[3]-> tokenfifo.in
+      triggered nop+ack dup1.out1 -[3]-> tokenfifo.in
+      triggered nop+ack dup1.out2 -[3]-> tokenfifo.in
+      triggered nop+ack dup2.out1 -[3]-> tokenfifo.in
+      triggered nop+ack dup2.out2 -[3]-> tokenfifo.in
+
+      // this, paired with MAXINT at port B, will kill standing copy
+      0 -> max.A
+      0 -> min.A
+      max.out -> bitbucket.data
+      min.out -> bitbucket.data
+
+      // restore unacked inbox standing moves
+      nop+ack memwrite.data -> tokenfifo.in
+      memwrite.data -[*]-> ()
+      nop+ack dup1.in -> tokenfifo.in
+      dup1.in -[*]-> ()
+      nop+ack dup2.in -> tokenfifo.in
+      dup2.in -[*]-> ()
+      nop+ack max.A -> tokenfifo.in
+      max.A -[*]-> ()
+      nop+ack min.A -> tokenfifo.in
+      min.A -[*]-> ()
+      nop+ack max.B -> tokenfifo.in
+      max.B -[*]-> ()
+      nop+ack min.B -> tokenfifo.in
+      min.B -[*]-> ()
+      nop+ack max.cmd -> tokenfifo.in
+      max.cmd -[*]-> ()
+      nop+ack min.cmd -> tokenfifo.in
+      min.cmd -[*]-> ()
+
+      tokenfifo.out -[33]-> bitbucket.token
+      tokenfifo.out -> fetch.release
+    } -> fetch.codebag
+
+    {
+      fetch.done -> bitbucket.token
+
+      // standing copy is gone, so get rid of this last cmd
+      0 -> max.A
+      0 -> min.A
+      0 -> max.B
+      0 -> min.B
+
+      // probably lax on the sequencing here
+      max.out -> bitbucket.data
+      min.out -> bitbucket.data
+
+      // "function calls" return with a continuation
+      tokensource.out -> fetch.release
+      donecodebag.out -> fetch.codebag
+    } -> fetch.codebag
+  } -> fetch.codebag
+}
+
-- 
1.7.10.4