ships/CarrySaveAdder.ship

   1 ship: CarrySaveAdder
   2
   3 == Ports ===========================================================
   4 in:   in
   5
   6 out:  out
   7
   8
   9 == TeX ==============================================================
  10
  11 The Carry-Save Adder computes the carry-save sum of three input
  12 values, provided sequentially at {\tt in}, and produces.
  13
  14
  15 == Fleeterpreter ====================================================
  16
  17 int state = 0;
  18 long temp;
  19 long out;
  20 public void reset() {
  21   super.reset();
  22   state = 0;
  23   temp = 0;
  24   out = 0;
  25 }
  26 private long maj(long a, long b, long c) {
  27   long ret = 0;
  28   for(int i=0; i<64; i++) {
  29     boolean a_ = (a&(1L<<i))!=0L;
  30     boolean b_ = (b&(1L<<i))!=0L;
  31     boolean c_ = (c&(1L<<i))!=0L;
  32     if ( (a_ && b_) || (b_ && c_) || (a_ && c_) )
  33       ret |= (1L << i);
  34   }
  35   return ret;
  36 }
  37 public void service() {
  38   if (!box_out.readyForDataFromShip()) return;
  39   if (state!=3 && !box_in.dataReadyForShip()) return;
  40   switch(state) {
  41     case 0: out = box_in.removeDataForShip(); break;
  42     case 1: temp = box_in.removeDataForShip(); break;
  43     case 2:
  44       long in = box_in.removeDataForShip();
  45       long mm = maj(temp, out, in);
  46       box_out.addDataFromShip(mm << 1, ((mm >> (getFleet().getWordWidth()-1)) & 1L)!=0);
  47       temp = (temp ^ out) ^ in;
  48       break;
  49     case 3: box_out.addDataFromShip(temp, false); break;
  50   }
  51   state = (state+1) % 4;
  52 }
  53
  54
  55 == FPGA ==============================================================
  56
  57   reg [(`WORDWIDTH-1):0] temp;
  58   reg [(`WORDWIDTH):0]   out_d;
  59   reg [1:0] state;
  60   initial state = 0;
  61   assign out_d_ = out_d;
  62
  63   wire [(`WORDWIDTH-1):0] majority;
  64   wire [(`WORDWIDTH-1):0] xors;
  65   genvar i;
  66   generate
  67     for(i=0; i<`WORDWIDTH; i=i+1) begin : OUT
  68       assign majority[i] = (temp[i] & out_d[i]) | (in_d[i] & out_d[i]) | (temp[i] & in_d[i]);
  69       assign xors[i]     = temp[i] ^ out_d[i] ^ in_d[i];
  70     end
  71   endgenerate
  72
  73   always @(posedge clk) begin
  74     if (!rst) begin
  75       `reset
  76       state <= 0;
  77     end else begin
  78       `flush
  79       `cleanup
  80       if (`out_empty && state==3) begin
  81         out_d <= { 1'b0, temp };
  82         `fill_out
  83         state <= state + 1;
  84       end else if (`in_full && `out_empty) begin
  85         if (state == 0) begin
  86           out_d <= { 1'b0, in_d };
  87         end else if (state == 1) begin
  88           temp <= in_d;
  89         end else if (state == 2) begin
  90           out_d <= { majority[`WORDWIDTH-1:0], 1'b0 };
  91           temp  <= xors;
  92           `fill_out
  93         end
  94         state <= state + 1;
  95         `drain_in
  96       end
  97     end
  98   end
  99
 100 == Test ==============================================================
 101 // expected output
 102 #expect 0x3c4bc6
 103 #expect 0x1796d2
 104 #expect 0x24b4f4
 105 #expect 0x3c4bc6
 106
 107 // ships required in order to run this code
 108 #ship debug        : Debug
 109 #ship csa          : CarrySaveAdder
 110 #ship alu          : Alu
 111 #ship fifo         : Fifo
 112
 113 fifo.in:
 114    set word=1018217;  deliver;
 115    set word=771820;   deliver;
 116    set word=2161521;  deliver;
 117 fifo.out:
 118    collect, send to csa.in; send to alu.in1;
 119    collect, send to csa.in; send to alu.in2;
 120    collect, send to csa.in; send to alu.in2;
 121
 122 alu.in1: set ilc=4; recv, deliver;
 123 alu.in2: set ilc=4; recv, deliver;
 124 alu.inOp:
 125    set word=Alu.inOp[ADD];
 126    set ilc=4; deliver;
 127 alu.out:
 128    collect, send to alu.in1;
 129    collect; send to debug.in;
 130    recv token;
 131    collect; send to debug.in;
 132
 133 csa.in:
 134    set ilc=*;
 135    recv, deliver;
 136
 137 csa.out:
 138    recv token;
 139    collect, send to debug.in;
 140    send to alu.in1;
 141    collect, send to debug.in;
 142    send to alu.in2;
 143
 144 debug.in:
 145    recv, deliver;
 146    send token to csa.out;
 147    set ilc=2;
 148    recv, deliver;
 149    send token to alu.out;
 150    recv, deliver;
 151
 152
 153 == Contributors =========================================================
 154 Adam Megacz <megacz@cs.berkeley.edu>