ships/Alu.ship

   1 ship: Alu
   2
   3 == Ports ===========================================================
   4 data  in:   in1
   5 data  in:   in2
   6 data  in:   inOp
   7   constant IN1: 0
   8   constant IN2: 1
   9   constant ADD: 2
  10   constant SUB: 3
  11   constant MAX: 4
  12   constant MIN: 5
  13   constant CMP: 6
  14   constant DROP1: 7
  15   constant DROP2: 8
  16   constant MAXMERGE: 9
  17   constant AND: 10
  18   constant OR: 11
  19   constant XOR: 12
  20
  21 data  out:  out
  22
  23
  24 == TeX ==============================================================
  25
  26 {\tt Alu} is a ``two-input'' arithmetic logic unit.  It includes
  27 logic for performing arithmetic operations on a pair of arguments.
  28 Currently this includes
  29 addition ({\sc add}),
  30 subtraction ({\sc sub}),
  31 maximum ({\sc max}), and
  32 minimum ({\sc min}).
  33
  34 \subsection*{Semantics}
  35
  36 When a value is present at each of {\tt in1}, {\tt in2} and {\tt
  37 inOp}, these three values are consumed.  Based on the value consumed
  38 at {\tt inOp}, the requested operation is performed on the values
  39 consumed from {\tt in1} and {\tt in2}.  The result of this operation
  40 is then made available at {\tt out}.
  41
  42 \subsection*{C-Flag}
  43
  44 \begin{verbatim}
  45 IN1      - undefined; drain in1 only
  46 IN2      - undefined; drain in2 only
  47 ADD      - carry-out
  48 SUB      - undefined
  49 MAX      - if in1>in2 cflag=0 and drain in1, else cflag=1 and drain in2
  50 MIN      - if in1>in2 cflag=1 and drain in2, else cflag=0 and drain in1
  51 CMP      - if in1==in2 cflag=1, else cflag=0
  52 DROP1    - consume in1, produce no output
  53 DROP2    - consume in2, produce no output
  54 MAXMERGE - if (in1<0 && in2<0) consume both, emit either, cflag=undef else act as MAX
  55 \end{verbatim}
  56
  57 \subsection*{To Do}
  58
  59 The {\it link bit} and other features of \cite{ies31} are not yet
  60 implemented.
  61
  62 The carry-in, carry-out, zero-test, negative-test, and overflow-test
  63 flags typically present in a conventional processor ALU are also not
  64 yet implemented.
  65
  66 == Fleeterpreter ====================================================
  67 public void service() {
  68   if (box_inOp.dataReadyForShip() &&
  69       box_in1.dataReadyForShip() &&
  70       box_in2.dataReadyForShip() &&
  71       box_out.readyForDataFromShip()) {
  72       long a;
  73       long b;
  74       long op     = box_inOp.removeDataForShip();
  75       switch((int)op) {
  76           case 0:
  77               a = box_in1.removeDataForShip();
  78               box_out.addDataFromShip(a); // IN1
  79               break;
  80           case 1:
  81               b = box_in2.removeDataForShip();
  82               box_out.addDataFromShip(b); // IN2
  83               break;
  84           case 2:
  85               a = box_in1.removeDataForShip();
  86               b = box_in2.removeDataForShip();
  87               box_out.addDataFromShip(a+b); // ADD
  88               break;
  89           case 3:
  90               a = box_in1.removeDataForShip();
  91               b = box_in2.removeDataForShip();
  92               box_out.addDataFromShip(a-b); // SUB
  93               break;
  94
  95           case 9: // MAXMERGE
  96               if (box_in1.peekDataForShip()<0 && box_in2.peekDataForShip()<0) {
  97                 a = box_in1.removeDataForShip();
  98                 b = box_in2.removeDataForShip();
  99                 box_out.addDataFromShip(a, false);
 100                 break;
 101               }
 102               // fall through to MAX
 103           case 4:
 104               a = box_in1.peekDataForShip();
 105               b = box_in2.peekDataForShip();
 106               box_out.addDataFromShip(Math.max(a,b), !(a>b)); // MAX
 107               if (a>b) box_in1.removeDataForShip(); else box_in2.removeDataForShip();
 108               break;
 109
 110           case 5:
 111               a = box_in1.peekDataForShip();
 112               b = box_in2.peekDataForShip();
 113               box_out.addDataFromShip(Math.min(a,b), a>b); // MIN
 114               if (a<b) box_in1.removeDataForShip(); else box_in2.removeDataForShip();
 115               break;
 116           case 6:
 117               a = box_in1.removeDataForShip();
 118               b = box_in2.removeDataForShip();
 119               box_out.addDataFromShip(0, a==b); // CMP
 120               break;
 121 /*
 122           case 7:
 123               box_in1.removeDataForShip();      // DROP1
 124               break;
 125           case 8:
 126               box_in2.removeDataForShip();      // DROP2
 127               break;
 128 */
 129           case 10:
 130               a = box_in1.removeDataForShip();
 131               b = box_in2.removeDataForShip();
 132               box_out.addDataFromShip(a & b); // CMP
 133               break;
 134           case 11:
 135               a = box_in1.removeDataForShip();
 136               b = box_in2.removeDataForShip();
 137               box_out.addDataFromShip(a | b); // CMP
 138               break;
 139           case 12:
 140               a = box_in1.removeDataForShip();
 141               b = box_in2.removeDataForShip();
 142               box_out.addDataFromShip(a ^ b); // CMP
 143               break;
 144           default:
 145               throw new RuntimeException("invalid opcode: " + op);
 146       }
 147   }
 148 }
 149
 150 == FleetSim ==============================================================
 151
 152 == FPGA ==============================================================
 153
 154   wire [`WORDWIDTH:0]     sum;
 155   wire                    cin;
 156   wire [(`WORDWIDTH-1):0] in2_inverted;
 157
 158   wire [(`WORDWIDTH-1):0] res;
 159   wire                    isplus;
 160   wire                    eq;
 161   wire                    cout;
 162
 163   wire [4:0]              inOp_d_trunc;
 164   assign                  inOp_d_trunc = inOp_d[4:0];
 165
 166   assign isplus        = inOp_d_trunc[4:0]==2;
 167   assign cin           = isplus ? 0 : 1;
 168   assign in2_inverted  = isplus ? in2_d : ~in2_d;
 169   assign sum           = {in1_d,cin} + {in2_inverted,cin};
 170   assign res           = sum[`WORDWIDTH:1];
 171   assign greater       = !res[`WORDWIDTH-1];
 172   assign both_negative = in1_d[`WORDWIDTH-1] && in2_d[`WORDWIDTH-1];
 173   assign eq            = in1_d == in2_d;
 174   assign cout          = sum[`WORDWIDTH];
 175
 176   reg out_draining;
 177
 178   assign out_d_[`WORDWIDTH] =
 179           (inOp_d_trunc==0) ? 1'b0 :
 180           (inOp_d_trunc==1) ? 1'b0 :
 181           (inOp_d_trunc==2) ? cout :
 182           (inOp_d_trunc==3) ? cout :
 183           (inOp_d_trunc==4) ? ~greater :
 184           (inOp_d_trunc==5) ?  greater :
 185           (inOp_d_trunc==6) ?  eq :
 186           (inOp_d_trunc==9) ? ~greater :
 187           0;
 188
 189   assign out_d_[(`WORDWIDTH-1):0] =
 190           (inOp_d_trunc==0) ? (in1_d)  :
 191           (inOp_d_trunc==1) ? (in2_d)  :
 192           (inOp_d_trunc==2) ? (res)  :
 193           (inOp_d_trunc==3) ? (res)  :
 194           (inOp_d_trunc==4) ? (greater ? in1_d : in2_d)  :
 195           (inOp_d_trunc==5) ? (greater ? in2_d : in1_d)  :
 196           (inOp_d_trunc==6) ? {{ (`WORDWIDTH-1) {1'b0 }}, eq  } :
 197           (inOp_d_trunc==9) ? (both_negative ? in1_d : (greater ? in1_d : in2_d)) :
 198           (inOp_d_trunc==10) ? (in1_d & in2_d) :
 199           (inOp_d_trunc==11) ? (in1_d | in2_d) :
 200           (inOp_d_trunc==12) ? (in1_d ^ in2_d) :
 201           0;
 202
 203   wire firing_condition;
 204   assign firing_condition =
 205           (inOp_d_trunc==0) ? `in1_full  :
 206           (inOp_d_trunc==1) ? `in2_full  :
 207           (inOp_d_trunc==7) ? `in1_full  :
 208           (inOp_d_trunc==8) ? `in2_full  :
 209           ((`in1_full) && (`in2_full));
 210
 211   always @(posedge clk) begin
 212     if (rst) begin
 213       `reset
 214       out_draining <= 0;
 215     end else begin
 216       `cleanup
 217       if (out_draining && `out_empty) begin
 218         `drain_inOp
 219         out_draining <= 0;
 220         if      (inOp_d_trunc==0) `drain_in1
 221         else if (inOp_d_trunc==1) `drain_in2
 222         else if (inOp_d_trunc==7) `drain_in1
 223         else if (inOp_d_trunc==8) `drain_in2
 224         else if (inOp_d_trunc==9 &&  both_negative) begin `drain_in1 `drain_in2 end
 225         else if (inOp_d_trunc==4 &&  greater) `drain_in1
 226         else if (inOp_d_trunc==5 &&  greater) `drain_in2
 227         else if (inOp_d_trunc==9 &&  greater) `drain_in1
 228         else if (inOp_d_trunc==4 && !greater) `drain_in2
 229         else if (inOp_d_trunc==5 && !greater) `drain_in1
 230         else if (inOp_d_trunc==9 && !greater) `drain_in2
 231         else begin
 232           `drain_in1
 233           `drain_in2
 234         end
 235       end
 236       if (!out_draining && `out_empty && firing_condition && `inOp_full) begin
 237         if (inOp_d_trunc!=7 && inOp_d_trunc!=8) `fill_out
 238         out_draining <= 1;
 239       end
 240     end
 241   end
 242
 243 == Test ==============================================================================
 244
 245 // FIXME: need test for ADD carry-out c-flag
 246
 247 #ship debug : Debug
 248 #ship alu   : Alu
 249
 250 #expect 17
 251 #expect 1
 252 #expect 9
 253 #expect 8
 254 #expect 8
 255 #expect 1
 256 #expect 9
 257 #expect 0
 258 #expect 0
 259 #expect 1
 260
 261 debug.in:   set ilc=*;  recv, deliver;
 262 alu.in1:
 263   set word= 9;
 264   set ilc=5;
 265   deliver;
 266   set word= 9;
 267   deliver;
 268
 269 alu.in2:
 270   set word= 8;
 271   set ilc=5;
 272   deliver;
 273   set word= 9;
 274   deliver;
 275
 276 alu.out:
 277   set ilc=4;
 278   collect, send to debug.in;
 279 alu.inOp:
 280  set word= Alu.inOp[ADD]; deliver;
 281  set word= Alu.inOp[SUB]; deliver;
 282  set word= Alu.inOp[IN1]; deliver;
 283  set word= Alu.inOp[IN2]; deliver;
 284  set word= Alu.inOp[MIN]; deliver;
 285  set word= Alu.inOp[MAX]; deliver;
 286  set word= Alu.inOp[CMP]; deliver;
 287  set word= Alu.inOp[CMP]; deliver;
 288
 289 alu.out:
 290   collect, send to debug.in;        // MIN
 291   set flags a=c, b=b;
 292   [a]  set word= 1;
 293   [!a] set word= 0;
 294   send to debug.in;
 295
 296   collect, send to debug.in;        // MAX
 297   set flags a=c, b=b;
 298   [a]  set word= 1;
 299   [!a] set word= 0;
 300   send to debug.in;
 301
 302   collect;        // CMP
 303   set flags a=c, b=b;
 304   [a]  set word= 1;
 305   [!a] set word= 0;
 306   send to debug.in;
 307
 308   collect;        // CMP
 309   set flags a=c, b=b;
 310   [a]  set word= 1;
 311   [!a] set word= 0;
 312   send to debug.in;
 313
 314 == Contributors =========================================================
 315 Adam Megacz <megacz@cs.berkeley.edu>