1143c5b2864f56ae7ee57401658c2fbf31644f1f
[fleet.git] / ships / Stack.ship
1 ship: Stack
2
3 == Ports ===========================================================
4 data  in:   push
5 data  out:  pop
6
7 == Constants ========================================================
8
9 == TeX ==============================================================
10 A stack ship with capacity for at least 16 elements.
11
12 Push operations are executed as soon as an inbound datum is delivered
13 to the {\tt push} port.  Completion of a push can be confirmed by
14 sending a token from the {\tt push} port after {\tt deliver}ing.
15
16 Pop operations are executed no earlier than the time at which the {\tt
17 pop} port attempts to {\tt take} data from the ship.
18
19 When the stack becomes full, it will simply not process any new {\tt
20 push} operations.  When the stack becomes empty, it will simply not
21 process any new {\tt pop} operations.  Phrased another way, if a {\tt
22 pop} is issued to an empty stack, that operation will wait for a {\tt
23 push} to occur; at some point after that, the {\tt pop} will proceed
24 to pop the pushed value.  There is no ``underflow'' or ``overflow.''
25
26 \subsection*{To Do}
27
28 There is some difficulty here when it comes to arbitration -- does the
29 execution of the instruction after the {\tt deliver} to the {\tt push}
30 port indicate that the value has been safely pushed?  This is much
31 tricker than it seems.
32
33 Perhaps there should be a single port, {\tt operation}, to which
34 either a {\sc PUSH} or {\sc POP} command is sent.  This would simplify
35 the arbitration issues.
36
37 == Fleeterpreter ====================================================
38     private ArrayList<Long> stack = new ArrayList<Long>();
39     public void service() {
40         if (box_push.dataReadyForShip() && stack.size()<32) {
41             stack.add(box_push.removeDataForShip());
42         }
43         if (box_pop.readyForDataFromShip() && stack.size() > 0) {
44             box_pop.addDataFromShip(stack.get(stack.size()-1));
45             stack.remove(stack.size()-1);
46         }
47     }
48
49 == FleetSim ==============================================================
50 == FPGA ==============================================================
51 /* FIXME: inefficient */
52   reg    [(`DATAWIDTH-1):0] mem [4:0];
53   reg    [5:0]              depth;
54   reg    skip;
55   initial depth = 0;
56
57   always @(posedge clk) begin
58     skip = 0;
59     if (depth > 0) begin
60       `onwrite(pop_r, pop_a)
61         if (depth > 1) begin
62           pop_d <= mem[depth-2];
63         end
64         depth <= depth - 1;
65         skip = 1;
66       end
67     end
68     if (!skip && depth < 32) begin
69       `onread(push_r, push_a)
70         pop_d      <= push_d;
71         mem[depth] <= push_d;
72         depth      <= depth + 1;
73       end
74     end
75   end
76
77
78 == Test ====================================================
79 #ship stack : Stack
80 #ship debug : Debug
81
82 #expect 4
83 #expect 3
84 #expect 2
85 #expect 1
86 #expect 0
87
88 debug.in:  [*] take, deliver;
89
90 stack.pop: wait; [*] take, sendto debug.in;
91
92 stack.push:
93   literal 0; deliver;
94   literal 1; deliver;
95   literal 2; deliver;
96   literal 3; deliver;
97   literal 4; deliver;
98   notify stack.pop;
99
100
101
102
103 == Contributors =========================================================
104 Adam Megacz <megacz@cs.berkeley.edu>