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 or negedge rst) begin
  58     if (!rst) depth <= 0;
  59     else begin
  60     skip = 0;
  61     if (depth > 0) begin
  62       `onwrite(pop_r, pop_a)
  63         if (depth > 1) begin
  64           pop_d <= mem[depth-2];
  65         end
  66         depth <= depth - 1;
  67         skip = 1;
  68       end
  69     end
  70     if (!skip && depth < 32) begin
  71       `onread(push_r, push_a)
  72         pop_d      <= push_d;
  73         mem[depth] <= push_d;
  74         depth      <= depth + 1;
  75       end
  76     end
  77     end
  78   end
  79
  80
  81 == Test ====================================================
  82 #skip
  83 #ship stack : Stack
  84 #ship stack : Debug
  85
  86 #expect 4
  87 #expect 3
  88 #expect 2
  89 #expect 1
  90 #expect 0
  91
  92 debug.in:  [*] take, deliver;
  93
  94 stack.pop: wait; [*] take, sendto debug.in;
  95
  96 stack.push:
  97   literal 0; deliver;
  98   literal 1; deliver;
  99   literal 2; deliver;
 100   literal 3; deliver;
 101   literal 4; deliver;
 102   notify stack.pop;
 103
 104
 105
 106
 107 == Contributors =========================================================
 108 Adam Megacz <megacz@cs.berkeley.edu>