2 // Author: Thomas Kho <tkho@eecs.berkeley.edu>
4 #import edu.berkeley.fleet.ships
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 }
10 #ship memread : MemoryReadShip // ports: addr, stride, count, data, done
11 #ship memwrite : MemoryWriteShip // ports: addr, stride, count, data, done
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
21 #ship max : ArithmeticShip // ports: A, B, cmd, out
22 #ship min : ArithmeticShip // ports: A, B, cmd, out
24 #ship dup1 : DuplicatorShip // ports: in, out1, out2, out3, out4
25 #ship dup2 : DuplicatorShip // ports: in, out1, out2, out3, out4
27 #ship tokenfifo : TokenFifo // ports: in, out
28 #ship donecodebag : FifoShip // ports: in, out
30 #ship nextcodebag : FifoShip // ports: in, out
31 #ship exitcodebag : FifoShip // ports: in, out
33 // first, load itercnt counter
35 fetch.done -> bitbucket.token
37 move+ack itercnt.load -> fetch.release
38 itercnt.load -[*]-> ()
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
47 FETCH_NEXT -> fetch.codebag
50 nop+ack itercnt.load -> fetch.release
52 FETCH_NEXT: { // itercnt loaded
53 fetch.done -> bitbucket.token
55 LOOP_BODY -> nextcodebag.in
56 tokensource.out -> itercnt.ask
57 tokensource.out -> fetch.release
61 fetch.done -> bitbucket.token
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
70 fetch.done -> bitbucket.token
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
81 fetch.done -> bitbucket.token
86 memread.done -> bitbucket.token
92 memwrite.done -> bitbucket.token
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
109 fetch.done -> bitbucket.token
111 move+ack counter.load -> fetch.release
112 counter.load -[*]-> () // restore standing move
113 19 -> counter.load // load N - 1 into counter
115 { // on counter load, seed pipeline
116 fetch.done -> bitbucket.token
118 tokensource.out -[3]-> counter.ask
121 // send first memread.data to dup2.in
122 memread.data -> dup2.in
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
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
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
145 // pipeline: max.out -> dup2.in
146 triggered move max.out -[*]-> dup2.in
147 accept+ack dup2.in -[*]-> max.out
149 // pipeline: memread.data -> dup1.in
150 triggered move memread.data -[*]-> dup1.in
151 accept+ack dup1.in -[*]-> memread.data
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
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
167 // setup exit condition
168 counter.zero -[2]-> bitbucket.token
169 counter.zero -> fetch.release
171 { // after N-1 writes
172 fetch.done -> bitbucket.token
174 // once we're done with N-1 writes, we can flush the last one
175 // by comparing with MAXINT
177 tokensource.out -> min.out
178 counter.zero -> fetch.release // trigger next codebag
182 fetch.done -> bitbucket.token
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
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
200 // this, paired with MAXINT at port B, will kill standing copy
203 max.out -> bitbucket.data
204 min.out -> bitbucket.data
206 // restore unacked inbox standing moves
207 nop+ack memwrite.data -> tokenfifo.in
208 memwrite.data -[*]-> ()
209 nop+ack dup1.in -> tokenfifo.in
211 nop+ack dup2.in -> tokenfifo.in
213 nop+ack max.A -> tokenfifo.in
215 nop+ack min.A -> tokenfifo.in
217 nop+ack max.B -> tokenfifo.in
219 nop+ack min.B -> tokenfifo.in
221 nop+ack max.cmd -> tokenfifo.in
223 nop+ack min.cmd -> tokenfifo.in
226 tokenfifo.out -[33]-> bitbucket.token
227 tokenfifo.out -> fetch.release
231 fetch.done -> bitbucket.token
233 // standing copy is gone, so get rid of this last cmd
239 // probably lax on the sequencing here
240 max.out -> bitbucket.data
241 min.out -> bitbucket.data
243 // "function calls" return with a continuation
244 tokensource.out -> fetch.release
245 donecodebag.out -> fetch.codebag