ships/Alu3.ship

   1 ship: Alu3
   2
   3 == Ports ===========================================================
   4 data  in:   in1
   5 data  in:   in2
   6 data  in:   in3
   7
   8 data  out:  out1
   9   shortcut to: in1
  10 data  out:  out2
  11   shortcut to: in2
  12 data  out:  outBits
  13
  14 == Constants ========================================================
  15 == TeX ==============================================================
  16
  17 {\tt Alu3} is a three-input adder which produces a pair of outputs in
  18 carry-save form.  It has no opcode input.
  19
  20 This ship also contains a private ``bit fifo'' similar to the {\tt
  21 BitFifo} ship, except that only the dequeueing (output) interface is
  22 exposed to the programmer.  Each addition operation performed causes
  23 the lowest bit of the {\it save} output to be enqueued into the bit
  24 fifo.  This can be used to produce a very efficient multiplier; see
  25 the test case for this ship for more details.
  26
  27 \subsection*{Semantics}
  28
  29 When a value is present at each of {\tt in1}, {\tt in2} and {\tt in3},
  30 these three values are consumed.  The {\it carry} result of carry-save
  31 addition is placed in {\tt out1}, and the {\it save} result of
  32 carry-save addition is placed in {\tt out2}.
  33
  34 \subsection*{To Do}
  35
  36 Is the second output supposed to be shifted?
  37
  38 Provide a way to clear/flush the internal bitfifo.
  39
  40 Do we even need this?  Can we do the same thing with {\tt Lut3} and
  41 {\tt BitFifo} together?
  42
  43
  44 == Fleeterpreter ====================================================
  45 boolean mode = false;
  46 BitFifo.BitStorage outBits = new BitFifo.BitStorage(74);
  47 public void service() {
  48   if (outBits.size() >= 37) {
  49     if (box_outBits.readyForDataFromShip()) {
  50         box_outBits.addDataFromShip(outBits.get(37));
  51     }
  52   } else
  53   if (box_in1.dataReadyForShip() &&
  54       box_in2.dataReadyForShip() &&
  55       box_in3.dataReadyForShip() &&
  56       outBits.hasSpace(1) &&
  57       box_out1.readyForDataFromShip() &&
  58       box_out2.readyForDataFromShip()) {
  59       long v1 = box_in1.removeDataForShip();
  60       long v2 = box_in2.removeDataForShip();
  61       long v3 = box_in3.removeDataForShip();
  62       long o1, o2, o3;
  63       o1 = ((v1 & v2) | (v2 & v3) | (v1 & v3))/* << 1*/;
  64       o2 = (v1 ^ v2 ^ v3) >> 1;
  65       outBits.add((v1 ^ v2 ^ v3) & 0x1L, 1);
  66       box_out1.addDataFromShip(o1);
  67       box_out2.addDataFromShip(o2);
  68   }
  69 }
  70
  71 == FleetSim ==============================================================
  72
  73 == FPGA ==============================================================
  74
  75   reg                    mode;         initial mode = 0;
  76   reg                    have_in1;     initial have_in1 = 0;
  77   reg                    have_in2;     initial have_in2 = 0;
  78   reg                    have_in3;     initial have_in3 = 0;
  79   reg [(`DATAWIDTH-1):0] keep_in1;     initial keep_in1 = 0;
  80   reg [(`DATAWIDTH-1):0] keep_in2;     initial keep_in2 = 0;
  81   reg [(`DATAWIDTH-1):0] keep_in3;     initial keep_in3 = 0;
  82   reg                    have_out1;    initial have_out1 = 0;
  83   reg                    have_out2;    initial have_out2 = 0;
  84   reg [73:0] bitstorage; initial bitstorage = 0;
  85   reg [7:0] bitstorage_count;          initial bitstorage_count = 0;
  86   reg wrote;                           initial wrote = 0;
  87
  88   always @(posedge clk) begin
  89     if (!rst) begin
  90       `reset
  91       mode = 0;
  92       have_in1 <= 0;
  93       have_in2 <= 0;
  94       have_in3 <= 0;
  95       keep_in1 <= 0;
  96       keep_in2 <= 0;
  97       keep_in3 <= 0;
  98       have_out1 <= 0;
  99       have_out2 <= 0;
 100       bitstorage = 0;
 101       bitstorage_count <= 0;
 102       wrote = 0;
 103     end else begin
 104     wrote = 0;
 105     if (bitstorage_count >= `DATAWIDTH) begin
 106       outBits_d  = bitstorage[(`DATAWIDTH-1):0];
 107       `onwrite(outBits_r, outBits_a)
 108         bitstorage_count <= 0;
 109         bitstorage        = bitstorage >> `DATAWIDTH;
 110       end
 111     end else if (have_out1) begin
 112       `onwrite(out1_r, out1_a) have_out1 <= 0; end
 113     end else if (have_out2) begin
 114       `onwrite(out2_r, out2_a) have_out2 <= 0; end
 115     end else if (!have_in1) begin
 116       `onread(in1_r, in1_a) have_in1 <= 1; keep_in1 <= in1_d; end
 117     end else if (!have_in2) begin
 118       `onread(in2_r, in2_a) have_in2 <= 1; keep_in2 <= in2_d; end
 119     end else if (!have_in3) begin
 120       `onread(in3_r, in3_a) have_in3 <= 1; keep_in3 <= in3_d; end
 121     end else begin
 122           out1_d           <= { ((keep_in1 & keep_in2) | (keep_in2 & keep_in3) | (keep_in1 & keep_in3)) };
 123           out2_d                       <= { 1'b0, (keep_in1[(`DATAWIDTH-1):1] ^
 124                                                    keep_in2[(`DATAWIDTH-1):1] ^
 125                                                    keep_in3[(`DATAWIDTH-1):1]) };
 126         bitstorage[bitstorage_count]  = (keep_in1[0] ^ keep_in2[0] ^ keep_in3[0]);
 127         bitstorage_count             <= bitstorage_count+1;
 128         have_out1 <= 1;
 129         have_out2 <= 1;
 130         have_in1  <= 0;
 131         have_in2  <= 0;
 132         have_in3  <= 0;
 133     end
 134     end
 135
 136   end
 137
 138
 139
 140 == Test ========================================================================
 141 #ship alu3    : Alu3
 142 #ship lut3    : Lut3
 143 #ship bitfifo : BitFifo
 144 #ship debug   : Debug
 145 #ship fifo    : Fifo
 146
 147 #expect -66848683
 148 #expect 18682
 149
 150 // 0:  100100100111110000000
 151 // sel 011110100001001000000
 152 // 1:  111000101000011000011
 153 // r:  111000100110111000000
 154
 155 bitfifo.in:
 156   literal 10000;
 157   deliver;      // deliver a junk word
 158   load repeat counter with 37; deliver; // deliver it 37 times (once per bit)
 159   literal 0;
 160   load repeat counter with 38; deliver; // deliver it 37 times
 161
 162 // insert bits in lsb order
 163 bitfifo.inOp:
 164   literal BitFifo.inOp[lsbFirst,take=37];
 165   [*] deliver;
 166
 167 // toss out 37 bits, take one, repeat.  sign extend the result
 168 bitfifo.outOp:
 169   literal BitFifo.outOp[drop=37,take=1,signExtend];
 170   [*] deliver;
 171
 172 bitfifo.out:        [*] wait, take, sendto lut3.in2;
 173 lut3.in2:           load repeat counter with 4; notify bitfifo.out;
 174                     load repeat counter with 63;
 175                     take, deliver, notify bitfifo.out;
 176                     load repeat counter with 11;
 177                     take, deliver, notify bitfifo.out;
 178
 179 // mux on second input
 180 lut3.inLut:         literal 226;
 181                     [*] deliver;
 182
 183 lut3.in1:           literal 18683;
 184                     load repeat counter with 37; deliver;
 185                     literal 0;
 186                     load repeat counter with 37; deliver;
 187
 188 lut3.in3:           literal 12000;
 189                     load repeat counter with 37; deliver;
 190                     literal 0;
 191                     load repeat counter with 37; deliver;
 192
 193 lut3.out:           [*] wait, take, sendto alu3.in2;
 194
 195 alu3.in1:      literal 0; deliver; [*] take, deliver;
 196 alu3.in2:      notify lut3.out; [*] take, deliver, notify lut3.out;
 197 alu3.in3:      literal 0; deliver; [*] take, deliver;
 198 alu3.outBits:  [*] take, sendto debug.in;
 199
 200 alu3.out1:     [*] take, sendto alu3.in1;
 201 alu3.out2:     [*] take, sendto alu3.in3;
 202
 203 debug.in:      [*] take, deliver;
 204
 205
 206 == Contributors =========================================================
 207 Amir Kamil <kamil@cs.berkeley.edu>
 208 Adam Megacz <megacz@cs.berkeley.edu>