ships/BitFifo.ship

   1 ship: BitFifo
   2
   3 == Ports ===========================================================
   4 in:   in
   5 in:   inOp
   6   constant lsbFirst: ....................................1
   7   constant msbFirst: ....................................0
   8   constant drop:     .............................uuuuuu..
   9   constant take:     .......................uuuuuu........
  10
  11 out:  out
  12 in:   outOp
  13   constant lsbFirst:   ....................................1
  14   constant msbFirst:   ....................................0
  15   constant signExtend: ...................................1.
  16   constant drop:       .............................uuuuuu..
  17   constant take:       ......................0uuuuuu........
  18   constant copy:       ......................1uuuuuu........
  19
  20
  21 == TeX ==============================================================
  22
  23 The BitFifo internally stores some number of bits in a fifo structure.
  24 Its capacity is guaranteed to be at least two full machine words or
  25 more.
  26
  27 \subsection*{Enqueueing}
  28
  29 Bits are enqueued by providing a word at the {\tt in} port and a code
  30 word at the {\tt inOp} port (ports are named this way to take
  31 advantage of the switch fabric opcode mechanism \cite{am25}).  As
  32 shown in the constant diagram, this code word has fields {\tt
  33 lsbFirst}, {\tt msbFirst}, {\tt drop}, and {\tt take}.
  34
  35 When a word is consumed from {\tt in}, it is ``oriented'' in either
  36 Most Significant Bit First ({\tt msbFirst}) or Least Significant Bit
  37 First ({\tt lsbFirst}) depending on whether or not these flags are
  38 set.  Based on this orientation, the first {\tt drop} bits are
  39 discarded.  Then the next {\tt take} bits are enqueued into the fifo.
  40 Any remaining bits are discarded.  Attempting to drop or take beyond
  41 the end of a word produces undefined results.
  42
  43 \subsection*{Dequeueing}
  44
  45 Bits are dequeued by providing a code word at the {\tt outOp} port
  46 (despite its name, this is actually an {\it input port}).  As shown in
  47 the constant diagram, this code word has fields {\tt lsbFirst}, {\tt
  48 msbFirst}, {\tt signExtend}, {\tt drop}, {\tt take}, and {\tt copy}
  49 fields.
  50
  51 Before additional processing, {\tt drop} bits are discarded from the
  52 head of the fifo.  Next, bits are dequeued into an empty word-width
  53 register.  If the {\tt msbFirst} flag is set, bits will be deposited
  54 into this register starting with the most significant bit of the
  55 register and working towards the least significant bit.  If the {\tt
  56 lsbFirst} flag is set, bits will be deposited into this register
  57 starting with the {\it least} significant bit of the register and
  58 working towards the {\it most} significant bit.  The number of bits
  59 dequeued is specified by the {\tt take} field.  If the {\tt copy}
  60 field is specified instead, the bits will be {\it copied} out of the
  61 fifo rather than being removed.
  62
  63 Finally, if the {\tt signExtend} bit is set, all bits in the register
  64 which were not filled by bits dequeued from the fifo will be filled
  65 with a copy of {\it the last bit dequeued from the fifo}.
  66
  67 As a final addendum to the above, whenever a request arrives at {\tt
  68 outOp} which requires more bits than are available in the fifo, the
  69 operation will wait until enough bits are present.
  70
  71 \subsection*{To Do}
  72
  73 The text above regarding sign extending and dequeueing
  74 msbFirst/lsbFirst is wrong.
  75
  76
  77 == Fleeterpreter ====================================================
  78 // Internal storage
  79 static class BitStorage {
  80   long[] bits;
  81   int numbits = 0;
  82   int start = 0;
  83   BitStorage(int size) {
  84     bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
  85   }
  86   int size() {
  87     return numbits;
  88   }
  89   boolean hasSpace(int num) {
  90     return bits.length * 64 - numbits >= num;
  91   }
  92   boolean peekTailBit() {
  93     int entry = (((numbits-1) + start) / 64) % bits.length;
  94     int off = ((numbits-1) + start) % 64;
  95     int maxadd = 64 - off;
  96     long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
  97     return (bits[entry] & ~mask) != 0;
  98   }
  99   boolean add(long data, int num) {
 100     if (!hasSpace(num)) return false;
 101     int entry = ((numbits + start) / 64) % bits.length;
 102     int off = (numbits + start) % 64;
 103     int maxadd = 64 - off;
 104     long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
 105     bits[entry] = (bits[entry] & mask) | (data << off);
 106     if (num > maxadd) {
 107       numbits += maxadd;
 108       return add(data >>> maxadd, num - maxadd);
 109     } else {
 110       numbits += num;
 111       return true;
 112     }
 113   }
 114   long get(int num) {
 115     assert size() >= num : "too few bits in storage";
 116     int entry = start / 64;
 117     int off = start % 64;
 118     int max = 64 - off;
 119     int n = num > max ? max : num;
 120     long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
 121     long res = (bits[entry] >>> off) & mask;
 122     int oldstart = start;
 123     if (n < num) {
 124       int n2 = num - n;
 125       long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
 126       res |= (bits[(entry + 1) % bits.length] & mask2) << n;
 127     }
 128     start = (start + num) % (64 * bits.length);
 129     numbits -= num;
 130     return res;
 131   }
 132   int capacity() {
 133     return 64 * bits.length;
 134   }
 135   // Test code for BitStorage
 136   static void test3(String[] args) {
 137       BitStorage bs = new BitStorage(37);
 138       Random rand = new Random();
 139       Vector ins = new Vector();
 140       Vector ret = new Vector();
 141       StringBuffer sbi = new StringBuffer();
 142       StringBuffer sbr = new StringBuffer();
 143       System.out.println("==== Test #3 ====");
 144       System.out.println("inserting...");
 145       long data = rand.nextLong();
 146       bs.add(data, 0);
 147       ins.add(new Integer(0));
 148       data = rand.nextLong();
 149       int num = rand.nextInt(37);
 150       int s = bs.size();
 151       bs.add(data, num);
 152       assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 153       ins.add(new Integer(num));
 154       add(sbi, data, num);
 155       print(data, num);
 156       System.out.println("\nretrieving...");
 157       num = bs.size();
 158       data = bs.get(num);
 159       ret.add(new Integer(num));
 160       add(sbr, data, num);
 161       print(data, num);
 162       System.out.println("\ninsertion sequence:");
 163       for (int i = 0; i < ins.size(); i++) {
 164           System.out.print(" " + ins.get(i));
 165       }
 166       System.out.println("\nretrieval sequence:");
 167       for (int i = 0; i < ret.size(); i++) {
 168           System.out.print(" " + ret.get(i));
 169       }
 170       System.out.println();
 171       check(sbi, sbr);
 172   }
 173   static void test2(String[] args) {
 174       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 175       BitStorage bs = new BitStorage(37 * iters);
 176       Random rand = new Random();
 177       Vector ins = new Vector();
 178       Vector ret = new Vector();
 179       StringBuffer sbi = new StringBuffer();
 180       StringBuffer sbr = new StringBuffer();
 181       System.out.println("==== Test #2 ====");
 182       for (int i = 0; i < iters; i++) {
 183           long data = rand.nextLong();
 184           int num = rand.nextInt(37);
 185           int s = bs.size();
 186           bs.add(data, num);
 187           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 188           ins.add(new Integer(num));
 189           add(sbi, data, num);
 190           num = rand.nextInt(Math.min(37, bs.size()));
 191           s = bs.size();
 192           data = bs.get(num);
 193           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 194           ret.add(new Integer(num));
 195           add(sbr, data, num);
 196       }
 197       //for (int i = 0; i < iters; i++) {
 198       while (bs.size() > 0) {
 199           int num = Math.min(rand.nextInt(37), bs.size());
 200           //int num = Math.min(33, bs.size());
 201           int s = bs.size();
 202           long data = bs.get(num);
 203           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 204           ret.add(new Integer(num));
 205           add(sbr, data, num);
 206       }
 207       System.out.println("inserted:");
 208       System.out.println(sbi);
 209       System.out.println("retrieved:");
 210       System.out.println(sbr);
 211       System.out.println("insertion sequence:");
 212       for (int i = 0; i < ins.size(); i++) {
 213           System.out.print(" " + ins.get(i));
 214       }
 215       System.out.println("\nretrieval sequence:");
 216       for (int i = 0; i < ret.size(); i++) {
 217           System.out.print(" " + ret.get(i));
 218       }
 219       System.out.println();
 220       check(sbi, sbr);
 221   }
 222   static void test1(String[] args) {
 223       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 224       BitStorage bs = new BitStorage(37 * iters);
 225       Random rand = new Random();
 226       Vector ins = new Vector();
 227       Vector ret = new Vector();
 228       StringBuffer sbi = new StringBuffer();
 229       StringBuffer sbr = new StringBuffer();
 230       System.out.println("==== Test #1 ====");
 231       System.out.println("inserting...");
 232       for (int i = 0; i < iters; i++) {
 233           long data = rand.nextLong();
 234           int num = rand.nextInt(37);
 235           int s = bs.size();
 236           bs.add(data, num);
 237           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 238           ins.add(new Integer(num));
 239           add(sbi, data, num);
 240           print(data, num);
 241       }
 242       System.out.println("\nretrieving...");
 243       //for (int i = 0; i < iters; i++) {
 244       while (bs.size() > 0) {
 245           int num = Math.min(rand.nextInt(37), bs.size());
 246           //int num = Math.min(33, bs.size());
 247           int s = bs.size();
 248           long data = bs.get(num);
 249           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 250           ret.add(new Integer(num));
 251           add(sbr, data, num);
 252           print(data, num);
 253       }
 254       System.out.println("\ninsertion sequence:");
 255       for (int i = 0; i < ins.size(); i++) {
 256           System.out.print(" " + ins.get(i));
 257       }
 258       System.out.println("\nretrieval sequence:");
 259       for (int i = 0; i < ret.size(); i++) {
 260           System.out.print(" " + ret.get(i));
 261       }
 262       System.out.println();
 263       check(sbi, sbr);
 264   }
 265   static void print(long data, int num) {
 266       for (int i = 0; i < num; i++) {
 267           System.out.print((data >>> i) & 0x1);
 268       }
 269   }
 270   static void add(StringBuffer sb, long data, int num) {
 271       for (int i = 0; i < num; i++) {
 272           sb.append((int) ((data >>> i) & 0x1));
 273       }
 274   }
 275   static void check(StringBuffer sb1, StringBuffer sb2) {
 276       int len = sb2.length();
 277       if (len > sb1.length()) {
 278           System.out.println("error: retrieval sequence is longer than insertion sequence");
 279           len = sb1.length();
 280       }
 281       for (int i = 0; i < sb2.length(); i++) {
 282           if (sb1.charAt(i) != sb2.charAt(i)) {
 283               System.out.println("error: bit at position " + i + " does not match");
 284           }
 285       }
 286   }
 287 }
 288
 289 // Run BitStorage tests
 290 public static void main(String[] args) {
 291     BitStorage.test1(args);
 292     BitStorage.test2(args);
 293     BitStorage.test3(args);
 294 }
 295
 296 // Ship implementation
 297 private Packet selector;
 298 private static final int MAXBITS = 128;
 299 private static final int WORDSIZE = 37;
 300 private Queue bits = new LinkedList<Boolean>();
 301 boolean last = false;
 302
 303 // dummy routine used for Alu3 test -- FIXME later but keep this functionality somehow!
 304 private void add(boolean bit) {
 305   bits.add(bit);
 306   last = bit;
 307 }
 308 private boolean get() {
 309   return ((Boolean)bits.remove());
 310 }
 311 boolean haveBoxOutOp;
 312 long  boxOutOp;
 313 public void service() {
 314   if (box_inOp.dataReadyForShip() && box_in.dataReadyForShip()) {
 315     long op    = box_inOp.removeDataForShip();
 316     long data  = box_in.removeDataForShip();
 317
 318     boolean rev = (op & 1) != 0;
 319     int drop    = (int)((op >> 2) & (~(0xffffffffL << 6)));
 320     int take    = (int)((op >> 8) & (~(0xffffffffL << 6)));
 321     if (take==0) { add(last); return; }
 322
 323     if (!rev)
 324       for(long i=take-1-drop; i>=0; i--)
 325         add( (data & (1L<<i)) != 0);
 326     if (rev)
 327       for(long i=WORDSIZE-take+drop; i<WORDSIZE; i++)
 328         add( (data & (1L<<i)) != 0);
 329     return;
 330   }
 331
 332   if (!haveBoxOutOp && box_outOp.dataReadyForShip()) {
 333      boxOutOp = box_outOp.removeDataForShip();
 334      haveBoxOutOp = true;
 335   }
 336
 337   if (haveBoxOutOp && box_out.readyForDataFromShip()) {
 338     long op = boxOutOp;
 339     boolean rev  = (op & 1) != 0;
 340     boolean sign = (op & 2) != 0;
 341     boolean copy = (op & (1<<8)) != 0;
 342     int drop     = (int)((op >> 2) & (~(0xffffffffL << 6)));
 343     int take     = (int)((op >> 8) & (~(0xffffffffL << 6)));
 344     if (bits.size() >= take+drop) {
 345       // FIXME: copy
 346       for(int i=0; i<drop; i++) get();
 347       long ret = 0;
 348       if (!rev) {
 349         for(long i=take-1; i>=0; i--)
 350           if (get()) ret |= 1L<<i;
 351         if (sign && (ret & (1L<<(take-1)))!=0)
 352           ret |= (0xffffffffffffffffL << take);
 353       } else {
 354         for(long i=WORDSIZE-take; i<WORDSIZE; i++)
 355           if (get()) ret |= 1L<<i;
 356         // FIXME: sign-extend!
 357       }
 358       box_out.addDataFromShip(ret);
 359       haveBoxOutOp = false;
 360     }
 361   }
 362 }
 363
 364
 365 == FPGA ==============================================================
 366 `define BITSTORAGE_SIZE 148
 367 `define BITSTORAGE_BITS 16
 368 `define OP_SIGNEXT 1
 369 `define OP_LSBFIRST 0
 370 `define OP_COUNT 13:8
 371 `define OP_DROP  7:2
 372   reg [(`BITSTORAGE_SIZE-1):0] bitstorage;
 373   reg [(`BITSTORAGE_BITS-1):0] bitstorage_count;
 374   reg [(`BITSTORAGE_BITS-1):0] dequeue_remaining;
 375   reg [(`BITSTORAGE_BITS-1):0] enqueue_remaining;
 376   initial dequeue_remaining = 0;
 377   initial enqueue_remaining = 0;
 378   initial bitstorage_count = 0;
 379
 380   always @(posedge clk) begin
 381     if (!rst) begin
 382       bitstorage_count <= 0;
 383       enqueue_remaining <= 0;
 384       dequeue_remaining <= 0;
 385       `reset
 386     end else begin
 387     if (!in_r    && in_a)     in_a    <= 0;
 388     if (!inOp_r  && inOp_a)   inOp_a  <= 0;
 389     if (!outOp_r && outOp_a)  outOp_a <= 0;
 390
 391     if (out_r    && out_a)    out_r   <= 0;
 392
 393     if (dequeue_remaining > 0) begin
 394       if (dequeue_remaining <= outOp_d[`OP_COUNT])
 395       begin
 396         if (outOp_d[`OP_LSBFIRST]) begin
 397           out_d[`DATAWIDTH-1-(dequeue_remaining-1)] <= bitstorage[0];
 398         end else begin
 399           out_d[              dequeue_remaining-1 ] <= bitstorage[0];
 400         end
 401       end
 402       bitstorage[(`BITSTORAGE_SIZE-2):0] <= bitstorage[(`BITSTORAGE_SIZE-1):1];
 403       bitstorage_count  <= bitstorage_count - 1;
 404       if (dequeue_remaining == 1) begin
 405         out_r   <= 1;
 406         outOp_a <= 1;
 407       end
 408       dequeue_remaining <= dequeue_remaining - 1;
 409
 410     end else if (enqueue_remaining > 0) begin
 411       bitstorage[bitstorage_count] <=
 412          inOp_d[`OP_LSBFIRST]
 413          ?  in_d[`DATAWIDTH-1-(inOp_d[`OP_DROP]+enqueue_remaining-1)]
 414          :  in_d[              inOp_d[`OP_DROP]+enqueue_remaining-1 ];
 415       bitstorage_count  <= bitstorage_count + 1;
 416       if (enqueue_remaining == 1) begin
 417         in_a   <= 1;
 418         inOp_a <= 1;
 419       end
 420       enqueue_remaining <= enqueue_remaining - 1;
 421
 422     end else if (in_r && !in_a && inOp_r && !inOp_a && `BITSTORAGE_SIZE > bitstorage_count + inOp_d[`OP_COUNT]) begin
 423       // FIXME: zero count => lockup
 424       enqueue_remaining <= inOp_d[`OP_COUNT];
 425
 426     end else if (!out_r && !out_a && outOp_r && !outOp_a && (bitstorage_count >= (outOp_d[`OP_COUNT]+outOp_d[`OP_DROP]))) begin
 427       dequeue_remaining <= outOp_d[`OP_COUNT] + outOp_d[`OP_DROP];
 428       out_d <= (outOp_d[`OP_SIGNEXT] && bitstorage[outOp_d[`OP_DROP]]) ? 37'b1111111111111111111111111111111111111 : 0;
 429
 430     end
 431     end
 432   end
 433
 434
 435 == Test ==============================================================
 436
 437 // FIXME: this test case is woefully inadequate!!!!!
 438
 439 // expected output
 440 #expect 1
 441 #expect 68719476736
 442 //#expect 12
 443 //#expect 13
 444
 445 // ships required in order to run this code
 446 #ship debug        : Debug
 447 #ship bitfifo      : BitFifo
 448
 449 bitfifo.outOp:      literal BitFifo.outOp[take=37]; [*] deliver;
 450 bitfifo.out:        [*] take, sendto debug.in;
 451 debug.in:           [*] take, deliver;
 452 bitfifo.in:         literal 1; load repeat counter with 2; deliver;
 453
 454 bitfifo.inOp:
 455   literal BitFifo.inOp[take=37];
 456   deliver;
 457   literal BitFifo.inOp[take=37,lsbFirst];
 458   deliver;
 459
 460
 461 == Contributors =========================================================
 462 Amir Kamil <kamil@cs.berkeley.edu>
 463 Adam Megacz <megacz@cs.berkeley.edu>