misc/obsolete-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 static class BitStorage {
  46   long[] bits;
  47   int numbits = 0;
  48   int start = 0;
  49   BitStorage(int size) {
  50     bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
  51   }
  52   int size() {
  53     return numbits;
  54   }
  55   boolean hasSpace(int num) {
  56     return bits.length * 64 - numbits >= num;
  57   }
  58   boolean peekTailBit() {
  59     int entry = (((numbits-1) + start) / 64) % bits.length;
  60     int off = ((numbits-1) + start) % 64;
  61     int maxadd = 64 - off;
  62     long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
  63     return (bits[entry] & ~mask) != 0;
  64   }
  65   boolean add(long data, int num) {
  66     if (!hasSpace(num)) return false;
  67     int entry = ((numbits + start) / 64) % bits.length;
  68     int off = (numbits + start) % 64;
  69     int maxadd = 64 - off;
  70     long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
  71     bits[entry] = (bits[entry] & mask) | (data << off);
  72     if (num > maxadd) {
  73       numbits += maxadd;
  74       return add(data >>> maxadd, num - maxadd);
  75     } else {
  76       numbits += num;
  77       return true;
  78     }
  79   }
  80   long get(int num) {
  81     assert size() >= num : "too few bits in storage";
  82     int entry = start / 64;
  83     int off = start % 64;
  84     int max = 64 - off;
  85     int n = num > max ? max : num;
  86     long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
  87     long res = (bits[entry] >>> off) & mask;
  88     int oldstart = start;
  89     if (n < num) {
  90       int n2 = num - n;
  91       long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
  92       res |= (bits[(entry + 1) % bits.length] & mask2) << n;
  93     }
  94     start = (start + num) % (64 * bits.length);
  95     numbits -= num;
  96     return res;
  97   }
  98   int capacity() {
  99     return 64 * bits.length;
 100   }
 101   // Test code for BitStorage
 102   static void test3(String[] args) {
 103       BitStorage bs = new BitStorage(37);
 104       Random rand = new Random();
 105       Vector ins = new Vector();
 106       Vector ret = new Vector();
 107       StringBuffer sbi = new StringBuffer();
 108       StringBuffer sbr = new StringBuffer();
 109       System.out.println("==== Test #3 ====");
 110       System.out.println("inserting...");
 111       long data = rand.nextLong();
 112       bs.add(data, 0);
 113       ins.add(new Integer(0));
 114       data = rand.nextLong();
 115       int num = rand.nextInt(37);
 116       int s = bs.size();
 117       bs.add(data, num);
 118       assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 119       ins.add(new Integer(num));
 120       add(sbi, data, num);
 121       print(data, num);
 122       System.out.println("\nretrieving...");
 123       num = bs.size();
 124       data = bs.get(num);
 125       ret.add(new Integer(num));
 126       add(sbr, data, num);
 127       print(data, num);
 128       System.out.println("\ninsertion sequence:");
 129       for (int i = 0; i < ins.size(); i++) {
 130           System.out.print(" " + ins.get(i));
 131       }
 132       System.out.println("\nretrieval sequence:");
 133       for (int i = 0; i < ret.size(); i++) {
 134           System.out.print(" " + ret.get(i));
 135       }
 136       System.out.println();
 137       check(sbi, sbr);
 138   }
 139   static void test2(String[] args) {
 140       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 141       BitStorage bs = new BitStorage(37 * iters);
 142       Random rand = new Random();
 143       Vector ins = new Vector();
 144       Vector ret = new Vector();
 145       StringBuffer sbi = new StringBuffer();
 146       StringBuffer sbr = new StringBuffer();
 147       System.out.println("==== Test #2 ====");
 148       for (int i = 0; i < iters; i++) {
 149           long data = rand.nextLong();
 150           int num = rand.nextInt(37);
 151           int s = bs.size();
 152           bs.add(data, num);
 153           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 154           ins.add(new Integer(num));
 155           add(sbi, data, num);
 156           num = rand.nextInt(Math.min(37, bs.size()));
 157           s = bs.size();
 158           data = bs.get(num);
 159           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 160           ret.add(new Integer(num));
 161           add(sbr, data, num);
 162       }
 163       //for (int i = 0; i < iters; i++) {
 164       while (bs.size() > 0) {
 165           int num = Math.min(rand.nextInt(37), bs.size());
 166           //int num = Math.min(33, bs.size());
 167           int s = bs.size();
 168           long data = bs.get(num);
 169           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 170           ret.add(new Integer(num));
 171           add(sbr, data, num);
 172       }
 173       System.out.println("inserted:");
 174       System.out.println(sbi);
 175       System.out.println("retrieved:");
 176       System.out.println(sbr);
 177       System.out.println("insertion sequence:");
 178       for (int i = 0; i < ins.size(); i++) {
 179           System.out.print(" " + ins.get(i));
 180       }
 181       System.out.println("\nretrieval sequence:");
 182       for (int i = 0; i < ret.size(); i++) {
 183           System.out.print(" " + ret.get(i));
 184       }
 185       System.out.println();
 186       check(sbi, sbr);
 187   }
 188   static void test1(String[] args) {
 189       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 190       BitStorage bs = new BitStorage(37 * iters);
 191       Random rand = new Random();
 192       Vector ins = new Vector();
 193       Vector ret = new Vector();
 194       StringBuffer sbi = new StringBuffer();
 195       StringBuffer sbr = new StringBuffer();
 196       System.out.println("==== Test #1 ====");
 197       System.out.println("inserting...");
 198       for (int i = 0; i < iters; i++) {
 199           long data = rand.nextLong();
 200           int num = rand.nextInt(37);
 201           int s = bs.size();
 202           bs.add(data, num);
 203           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 204           ins.add(new Integer(num));
 205           add(sbi, data, num);
 206           print(data, num);
 207       }
 208       System.out.println("\nretrieving...");
 209       //for (int i = 0; i < iters; i++) {
 210       while (bs.size() > 0) {
 211           int num = Math.min(rand.nextInt(37), bs.size());
 212           //int num = Math.min(33, bs.size());
 213           int s = bs.size();
 214           long data = bs.get(num);
 215           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 216           ret.add(new Integer(num));
 217           add(sbr, data, num);
 218           print(data, num);
 219       }
 220       System.out.println("\ninsertion sequence:");
 221       for (int i = 0; i < ins.size(); i++) {
 222           System.out.print(" " + ins.get(i));
 223       }
 224       System.out.println("\nretrieval sequence:");
 225       for (int i = 0; i < ret.size(); i++) {
 226           System.out.print(" " + ret.get(i));
 227       }
 228       System.out.println();
 229       check(sbi, sbr);
 230   }
 231   static void print(long data, int num) {
 232       for (int i = 0; i < num; i++) {
 233           System.out.print((data >>> i) & 0x1);
 234       }
 235   }
 236   static void add(StringBuffer sb, long data, int num) {
 237       for (int i = 0; i < num; i++) {
 238           sb.append((int) ((data >>> i) & 0x1));
 239       }
 240   }
 241   static void check(StringBuffer sb1, StringBuffer sb2) {
 242       int len = sb2.length();
 243       if (len > sb1.length()) {
 244           System.out.println("error: retrieval sequence is longer than insertion sequence");
 245           len = sb1.length();
 246       }
 247       for (int i = 0; i < sb2.length(); i++) {
 248           if (sb1.charAt(i) != sb2.charAt(i)) {
 249               System.out.println("error: bit at position " + i + " does not match");
 250           }
 251       }
 252   }
 253 }
 254 boolean mode = false;
 255 BitStorage outBits = new BitStorage(74);
 256 public void service() {
 257   if (outBits.size() >= 37) {
 258     if (box_outBits.readyForDataFromShip()) {
 259         box_outBits.addDataFromShip(outBits.get(37));
 260     }
 261   } else
 262   if (box_in1.dataReadyForShip() &&
 263       box_in2.dataReadyForShip() &&
 264       box_in3.dataReadyForShip() &&
 265       outBits.hasSpace(1) &&
 266       box_out1.readyForDataFromShip() &&
 267       box_out2.readyForDataFromShip()) {
 268       long v1 = box_in1.removeDataForShip();
 269       long v2 = box_in2.removeDataForShip();
 270       long v3 = box_in3.removeDataForShip();
 271       long o1, o2, o3;
 272       o1 = ((v1 & v2) | (v2 & v3) | (v1 & v3))/* << 1*/;
 273       o2 = (v1 ^ v2 ^ v3) >> 1;
 274       outBits.add((v1 ^ v2 ^ v3) & 0x1L, 1);
 275       box_out1.addDataFromShip(o1);
 276       box_out2.addDataFromShip(o2);
 277   }
 278 }
 279
 280 == FleetSim ==============================================================
 281
 282 == FPGA ==============================================================
 283
 284   reg [73:0] bitstorage;               initial bitstorage = 0;
 285   reg [7:0] bitstorage_count;          initial bitstorage_count = 0;
 286
 287   always @(posedge clk) begin
 288     if (!rst) begin
 289       `reset
 290       bitstorage       <= 0;
 291       bitstorage_count <= 0;
 292     end else begin
 293       if (out1_r    && out1_a)    out1_r    <= 0;
 294       if (out2_r    && out2_a)    out2_r    <= 0;
 295       if (outBits_r && outBits_a) outBits_r <= 0;
 296       if (!in1_r    && in1_a)     in1_a     <= 0;
 297       if (!in2_r    && in2_a)     in2_a     <= 0;
 298       if (!in3_r    && in3_a)     in3_a     <= 0;
 299       if (!out1_r && !out2_r && !outBits_r && in1_r && in2_r && in3_r) begin
 300           out1_d  <= { ((in1_d & in2_d)
 301                       | (in2_d & in3_d)
 302                       | (in1_d & in3_d)) };
 303           out2_d  <= { 1'b0, (in1_d[(`DATAWIDTH-1):1] ^
 304                               in2_d[(`DATAWIDTH-1):1] ^
 305                               in3_d[(`DATAWIDTH-1):1]) };
 306         if (bitstorage_count >= `DATAWIDTH-1) begin
 307           outBits_d <= bitstorage[(`DATAWIDTH-1):0];
 308           outBits_r <= 1;
 309           bitstorage_count <= 0;
 310           bitstorage       <= bitstorage >> `DATAWIDTH;
 311         end
 312         bitstorage[bitstorage_count] <= (in1_d[0] ^ in2_d[0] ^ in3_d[0]);
 313         bitstorage_count             <= bitstorage_count+1;
 314         out1_r <= 1;
 315         out2_r <= 1;
 316         in1_a  <= 1;
 317         in2_a  <= 1;
 318         in3_a  <= 1;
 319       end
 320     end
 321   end
 322
 323
 324
 325 == Test ========================================================================
 326 #skip
 327 #ship alu3    : Alu3
 328 #ship lut3    : Lut3
 329 #ship debug   : Debug
 330 #ship fifo    : Fifo
 331 #ship rotator : Rotator
 332
 333 #expect 0
 334 #expect 2
 335 #expect 1
 336
 337 // 0:  100100100111110000000
 338 // sel 011110100001001000000
 339 // 1:  111000101000011000011
 340 // r:  111000100110111000000
 341
 342 alu3.in1:      literal 1; deliver;            load repeat counter with 36; deliver;
 343 alu3.in2:      literal 0; deliver; literal 1; load repeat counter with 36; deliver;
 344 alu3.in3:      literal 4; deliver;            load repeat counter with 36; deliver;
 345
 346 alu3.out1:    take;       sendto debug.in; [*] take;
 347 alu3.out2:    take; wait; sendto debug.in; [*] take;
 348 alu3.outBits: take; wait; sendto debug.in;
 349
 350 debug.in:
 351   take, deliver;
 352   notify alu3.out2;
 353   take, deliver;
 354   notify alu3.outBits;
 355   take, deliver;
 356
 357
 358 == Contributors =========================================================
 359 Amir Kamil <kamil@cs.berkeley.edu>
 360 Adam Megacz <megacz@cs.berkeley.edu>