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     wrote = 0;
  90     if (bitstorage_count >= `DATAWIDTH) begin
  91       outBits_d  = bitstorage[(`DATAWIDTH-1):0];
  92       `onwrite(outBits_r, outBits_a)
  93         bitstorage_count <= 0;
  94         bitstorage        = bitstorage >> `DATAWIDTH;
  95       end
  96     end else if (have_out1) begin
  97       `onwrite(out1_r, out1_a) have_out1 <= 0; end
  98     end else if (have_out2) begin
  99       `onwrite(out2_r, out2_a) have_out2 <= 0; end
 100     end else if (!have_in1) begin
 101       `onread(in1_r, in1_a) have_in1 <= 1; keep_in1 <= in1_d; end
 102     end else if (!have_in2) begin
 103       `onread(in2_r, in2_a) have_in2 <= 1; keep_in2 <= in2_d; end
 104     end else if (!have_in3) begin
 105       `onread(in3_r, in3_a) have_in3 <= 1; keep_in3 <= in3_d; end
 106     end else begin
 107           out1_d           <= { ((keep_in1 & keep_in2) | (keep_in2 & keep_in3) | (keep_in1 & keep_in3)) };
 108           out2_d                       <= { 1'b0, (keep_in1[(`DATAWIDTH-1):1] ^
 109                                                    keep_in2[(`DATAWIDTH-1):1] ^
 110                                                    keep_in3[(`DATAWIDTH-1):1]) };
 111         bitstorage[bitstorage_count]  = (keep_in1[0] ^ keep_in2[0] ^ keep_in3[0]);
 112         bitstorage_count             <= bitstorage_count+1;
 113         have_out1 <= 1;
 114         have_out2 <= 1;
 115         have_in1  <= 0;
 116         have_in2  <= 0;
 117         have_in3  <= 0;
 118     end
 119
 120   end
 121
 122
 123
 124 == Test ========================================================================
 125 #skip
 126 #ship alu3    : Alu3
 127 #ship lut3    : Lut3
 128 #ship bitfifo : BitFifo
 129 #ship debug   : Debug
 130 #ship fifo    : Fifo
 131
 132 #expect -66848683
 133 #expect 18682
 134
 135 // 0:  100100100111110000000
 136 // sel 011110100001001000000
 137 // 1:  111000101000011000011
 138 // r:  111000100110111000000
 139
 140 bitfifo.in:
 141   deliver;      // deliver a junk word
 142   literal 10000;
 143   [37] deliver; // deliver it 37 times (once per bit)
 144   literal 0;
 145   [38] deliver; // deliver it 37 times
 146
 147 // insert bits in lsb order
 148 bitfifo.inOp:
 149   literal BitFifo.inOp[lsbFirst,take=37];
 150   [*] deliver;
 151
 152 // toss out 37 bits, take one, repeat.  sign extend the result
 153 bitfifo.outOp:
 154   literal BitFifo.outOp[drop=37,take=1,signExtend];
 155   [*] deliver;
 156
 157 bitfifo.out:        [*] wait, take, sendto lut3.in2;
 158 lut3.in2:           [4] notify bitfifo.out;
 159                     [74] take, deliver, notify bitfifo.out;
 160
 161 // mux on second input
 162 lut3.inLut:         literal 226;
 163                     [74] deliver;
 164
 165 lut3.in1:           literal 18683;
 166                     [37] deliver;
 167                     literal 0;
 168                     [37] deliver;
 169
 170 lut3.in3:           literal 12000;
 171                     [37] deliver;
 172                     literal 0;
 173                     [37] deliver;
 174
 175 lut3.out:           [*] wait, take, sendto alu3.in2;
 176
 177 alu3.in1:      literal 0; deliver; [*] take, deliver;
 178 alu3.in2:      [1] notify lut3.out; [*] take, deliver, notify lut3.out;
 179 alu3.in3:      literal 0; deliver; [*] take, deliver;
 180 alu3.out1:     [74] take, sendto alu3.in1;
 181 alu3.out2:     [74] take, sendto alu3.in3;
 182 alu3.outBits:  [*] take, sendto debug.in;
 183
 184
 185 debug.in:      [*] take, deliver;
 186
 187
 188 == Contributors =========================================================
 189 Amir Kamil <kamil@cs.berkeley.edu>
 190 Adam Megacz <megacz@cs.berkeley.edu>