ship: BitFifo
== Ports ===========================================================
-data in: in
+in: in
+in: inOp
+ constant lsbFirst: ....................................1
+ constant msbFirst: ....................................0
+ constant drop: .............................uuuuuu..
+ constant take: .......................uuuuuu........
-data in: cmd.drop
-data in: cmd.dropInv
-data in: cmd.takeFillZeros
-data in: cmd.takeInvFillZeros
-data in: cmd.takeFillOnes
-data in: cmd.takeInvFillOnes
-data in: cmd.takeSignExtend
-data in: cmd.takeInvSignExtend
+out: out
+in: outOp
+ constant lsbFirst: ....................................1
+ constant msbFirst: ....................................0
+ constant signExtend: ...................................1.
+ constant drop: .............................uuuuuu..
+ constant take: ......................0uuuuuu........
+ constant copy: ......................1uuuuuu........
-data out: out
+
+== TeX ==============================================================
-== Constants ========================================================
+The BitFifo internally stores some number of bits in a fifo structure.
+Its capacity is guaranteed to be at least two full machine words or
+more.
-== TeX ==============================================================
+\subsection*{Enqueueing}
-\begin{verbatim}
-+-------------+ +---------------+ +------------+
-| inEnqueue |-->| |-->| outDequeue |
-+-------------+ | | +------------+
- | BitFifo |
-+-------------+ | | +-------------+
-| inEnqueueOp |-->| |<--| inDequeueOp |
-+-------------+ +---------------+ +-------------+
-\end{verbatim}
-
-\section*{inEnqueueOp}
-\setlength{\bitwidth}{6mm}
-{\tt\footnotesize
-\begin{bytefield}{14}
- \bitheader[b]{0,5,6,11,12,13}\\
- \bitbox{1}{Rev}
- \bitbox{1}{Inv}
- \bitbox{6}{Count}
- \bitbox{6}{Offset}
-\end{bytefield}
-}
+Bits are enqueued by providing a word at the {\tt in} port and a code
+word at the {\tt inOp} port (ports are named this way to take
+advantage of the switch fabric opcode mechanism \cite{am25}). As
+shown in the constant diagram, this code word has fields {\tt
+lsbFirst}, {\tt msbFirst}, {\tt drop}, and {\tt take}.
-\begin{itemize}
- \item [\tt Rev] ({\bf Reverse Before Enqueue})
- \item [\tt Inv] ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
- \item [\tt Count] ({\bf Count of Bits To Enqueue})
- \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
-\end{itemize}
-
-By default, bits are enqueued {\it most significant bit first} (bits
-in Sun byte order). If {\tt Rev=1}, the bits are reversed before
-performing the directions below.
-
-If {\tt Inv=1}, then the {\tt Count} field is treated as if its value
-was actually {\tt 37-Offset-Count} for all directions below.
-
-
-
-\pagebreak
-
-\section*{inDequeueOp}
-\setlength{\bitwidth}{6mm}
-{\tt\scriptsize
-\begin{bytefield}{23}
- \bitheader[b]{0,5,6,11-21,22}\\
- \bitbox{2}{Until}
- \bitbox{1}{Sort}
- \bitbox{1}{Get}
- \bitbox{1}{Rev}
- \bitbox{1}{Inv}
- \bitbox{1}{Rst}
- \bitbox{2}{Left\\ Fill}
- \bitbox{2}{Right\\ Fill}
- \bitbox{6}{Count}
- \bitbox{6}{Offset}
-\end{bytefield}
-}
+When a word is consumed from {\tt in}, it is ``oriented'' in either
+Most Significant Bit First ({\tt msbFirst}) or Least Significant Bit
+First ({\tt lsbFirst}) depending on whether or not these flags are
+set. Based on this orientation, the first {\tt drop} bits are
+discarded. Then the next {\tt take} bits are enqueued into the fifo.
+Any remaining bits are discarded. Attempting to drop or take beyond
+the end of a word produces undefined results.
+
+\subsection*{Dequeueing}
+
+Bits are dequeued by providing a code word at the {\tt outOp} port
+(despite its name, this is actually an {\it input port}). As shown in
+the constant diagram, this code word has fields {\tt lsbFirst}, {\tt
+msbFirst}, {\tt signExtend}, {\tt drop}, {\tt take}, and {\tt copy}
+fields.
+
+Before additional processing, {\tt drop} bits are discarded from the
+head of the fifo. Next, bits are dequeued into an empty word-width
+register. If the {\tt msbFirst} flag is set, bits will be deposited
+into this register starting with the most significant bit of the
+register and working towards the least significant bit. If the {\tt
+lsbFirst} flag is set, bits will be deposited into this register
+starting with the {\it least} significant bit of the register and
+working towards the {\it most} significant bit. The number of bits
+dequeued is specified by the {\tt take} field. If the {\tt copy}
+field is specified instead, the bits will be {\it copied} out of the
+fifo rather than being removed.
-\begin{itemize}
- \item [\tt Until] ({\bf Shift until you see a (0, 1)})
- \item [\tt Sort] ({\bf Sort the Bits})
- \item [\tt Get] ({\bf Get the value of the counter})
- \item [\tt Rev] ({\bf Reverse Before Enqueue})
- \item [\tt Inv] ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
- \item [\tt Rst] ({\bf Reset Counter Before Operation})
- \item [\tt Left Fill] ({\bf Left Fill (0, 1, sign)})
- \item [\tt Right Fill] ({\bf Right Fill (0, 1, sign)})
- \item [\tt Count] ({\bf Count of Bits To Enqueue})
- \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
-\end{itemize}
+Finally, if the {\tt signExtend} bit is set, all bits in the register
+which were not filled by bits dequeued from the fifo will be filled
+with a copy of {\it the last bit dequeued from the fifo}.
+
+As a final addendum to the above, whenever a request arrives at {\tt
+outOp} which requires more bits than are available in the fifo, the
+operation will wait until enough bits are present.
+
+\subsection*{To Do}
+
+The text above regarding sign extending and dequeueing
+msbFirst/lsbFirst is wrong.
== Fleeterpreter ====================================================
// Internal storage
-private static class BitStorage {
+static class BitStorage {
long[] bits;
int numbits = 0;
int start = 0;
boolean hasSpace(int num) {
return bits.length * 64 - numbits >= num;
}
+ boolean peekTailBit() {
+ int entry = (((numbits-1) + start) / 64) % bits.length;
+ int off = ((numbits-1) + start) % 64;
+ int maxadd = 64 - off;
+ long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
+ return (bits[entry] & ~mask) != 0;
+ }
boolean add(long data, int num) {
if (!hasSpace(num)) return false;
int entry = ((numbits + start) / 64) % bits.length;
int off = (numbits + start) % 64;
int maxadd = 64 - off;
- bits[entry] = (bits[entry] & (-1L >>> maxadd)) | (data << off);
+ long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
+ bits[entry] = (bits[entry] & mask) | (data << off);
if (num > maxadd) {
numbits += maxadd;
return add(data >>> maxadd, num - maxadd);
int off = start % 64;
int max = 64 - off;
int n = num > max ? max : num;
- long res = (bits[entry] >>> off) & (-1L >>> (64 - n));
+ long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
+ long res = (bits[entry] >>> off) & mask;
int oldstart = start;
if (n < num) {
int n2 = num - n;
- res |= (bits[(entry + 1) % bits.length] & (-1L >>> (64 - n2))) << n;
+ long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
+ res |= (bits[(entry + 1) % bits.length] & mask2) << n;
}
start = (start + num) % (64 * bits.length);
numbits -= num;
return 64 * bits.length;
}
// Test code for BitStorage
+ static void test3(String[] args) {
+ BitStorage bs = new BitStorage(37);
+ Random rand = new Random();
+ Vector ins = new Vector();
+ Vector ret = new Vector();
+ StringBuffer sbi = new StringBuffer();
+ StringBuffer sbr = new StringBuffer();
+ System.out.println("==== Test #3 ====");
+ System.out.println("inserting...");
+ long data = rand.nextLong();
+ bs.add(data, 0);
+ ins.add(new Integer(0));
+ data = rand.nextLong();
+ int num = rand.nextInt(37);
+ int s = bs.size();
+ bs.add(data, num);
+ assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
+ ins.add(new Integer(num));
+ add(sbi, data, num);
+ print(data, num);
+ System.out.println("\nretrieving...");
+ num = bs.size();
+ data = bs.get(num);
+ ret.add(new Integer(num));
+ add(sbr, data, num);
+ print(data, num);
+ System.out.println("\ninsertion sequence:");
+ for (int i = 0; i < ins.size(); i++) {
+ System.out.print(" " + ins.get(i));
+ }
+ System.out.println("\nretrieval sequence:");
+ for (int i = 0; i < ret.size(); i++) {
+ System.out.print(" " + ret.get(i));
+ }
+ System.out.println();
+ check(sbi, sbr);
+ }
static void test2(String[] args) {
int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
BitStorage bs = new BitStorage(37 * iters);
public static void main(String[] args) {
BitStorage.test1(args);
BitStorage.test2(args);
+ BitStorage.test3(args);
}
// Ship implementation
private Packet selector;
private static final int MAXBITS = 128;
private static final int WORDSIZE = 37;
-private BitStorage bits = new BitStorage(MAXBITS);
+private Queue bits = new LinkedList<Boolean>();
+boolean last = false;
+// dummy routine used for Alu3 test -- FIXME later but keep this functionality somehow!
+private void add(boolean bit) {
+ bits.add(bit);
+ last = bit;
+}
+private boolean get() {
+ return ((Boolean)bits.remove());
+}
+boolean haveBoxOutOp;
+long boxOutOp;
public void service() {
- if (!box_out.readyForDataFromShip() && !box_in.dataReadyForShip()) return;
- if (box_in.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
- long data = box_in.removeDataForShip();
- bits.add(data, WORDSIZE);
- }
- if (selector == null && !box_cmd.dataReadyForShip()) return;
- if (selector == null) selector = box_cmd.removePacketForShip();
+ if (box_inOp.dataReadyForShip() && box_in.dataReadyForShip()) {
+ long op = box_inOp.removeDataForShip();
+ long data = box_in.removeDataForShip();
- String port = selector.destination.getDestinationName();
- long val = selector.value; // check if <= 37?
+ boolean rev = (op & 1) != 0;
+ int drop = (int)((op >> 2) & (~(0xffffffffL << 6)));
+ int take = (int)((op >> 8) & (~(0xffffffffL << 6)));
+ if (take==0) { add(last); return; }
- if (port.startsWith("takeInv") || port.startsWith("dropInv")) {
- val = 37 - val;
- }
- if (val < bits.size()) {
+ if (!rev)
+ for(long i=take-1-drop; i>=0; i--)
+ add( (data & (1L<<i)) != 0);
+ if (rev)
+ for(long i=WORDSIZE-take+drop; i<WORDSIZE; i++)
+ add( (data & (1L<<i)) != 0);
return;
}
- if (port.startsWith("take")) {
- if (!box_out.readyForDataFromShip()) return;
- long data = bits.get((int) val);
- if (port.endsWith("FillOnes")) {
- data |= (-1L << val);
- } else if (port.endsWith("SignExtend")) {
- data = (data << (64 - val)) >> (64 - val);
+ if (!haveBoxOutOp && box_outOp.dataReadyForShip()) {
+ boxOutOp = box_outOp.removeDataForShip();
+ haveBoxOutOp = true;
+ }
+
+ if (haveBoxOutOp && box_out.readyForDataFromShip()) {
+ long op = boxOutOp;
+ boolean rev = (op & 1) != 0;
+ boolean sign = (op & 2) != 0;
+ boolean copy = (op & (1<<8)) != 0;
+ int drop = (int)((op >> 2) & (~(0xffffffffL << 6)));
+ int take = (int)((op >> 8) & (~(0xffffffffL << 6)));
+ if (bits.size() >= take+drop) {
+ // FIXME: copy
+ for(int i=0; i<drop; i++) get();
+ long ret = 0;
+ if (!rev) {
+ for(long i=take-1; i>=0; i--)
+ if (get()) ret |= 1L<<i;
+ if (sign && (ret & (1L<<(take-1)))!=0)
+ ret |= (0xffffffffffffffffL << take);
+ } else {
+ for(long i=WORDSIZE-take; i<WORDSIZE; i++)
+ if (get()) ret |= 1L<<i;
+ // FIXME: sign-extend!
+ }
+ box_out.addDataFromShip(ret);
+ haveBoxOutOp = false;
}
- box_out.addDataFromShip(data);
- selector = null;
- return;
- } else {
- bits.get((int) val);
- selector = null;
- return;
}
}
-== FleetSim ==============================================================
== FPGA ==============================================================
+`define BITSTORAGE_SIZE 148
+`define BITSTORAGE_BITS 16
+`define OP_SIGNEXT 1
+`define OP_LSBFIRST 0
+`define OP_COUNT 13:8
+`define OP_DROP 7:2
+ reg [(`BITSTORAGE_SIZE-1):0] bitstorage;
+ reg [(`BITSTORAGE_BITS-1):0] bitstorage_count;
+ reg [(`BITSTORAGE_BITS-1):0] dequeue_remaining;
+ reg [(`BITSTORAGE_BITS-1):0] enqueue_remaining;
+ initial dequeue_remaining = 0;
+ initial enqueue_remaining = 0;
+ initial bitstorage_count = 0;
+
+ always @(posedge clk) begin
+ if (!in_r && in_a) in_a <= 0;
+ if (!inOp_r && inOp_a) inOp_a <= 0;
+ if (!outOp_r && outOp_a) outOp_a <= 0;
+
+ if (out_r && out_a) out_r <= 0;
+
+ if (dequeue_remaining > 0) begin
+ if (dequeue_remaining <= outOp_d[`OP_COUNT])
+ begin
+ if (outOp_d[`OP_LSBFIRST]) begin
+ out_d[`DATAWIDTH-1-(dequeue_remaining-1)] <= bitstorage[0];
+ end else begin
+ out_d[ dequeue_remaining-1 ] <= bitstorage[0];
+ end
+ end
+ bitstorage[(`BITSTORAGE_SIZE-2):0] <= bitstorage[(`BITSTORAGE_SIZE-1):1];
+ bitstorage_count <= bitstorage_count - 1;
+ if (dequeue_remaining == 1) begin
+ out_r <= 1;
+ outOp_a <= 1;
+ end
+ dequeue_remaining <= dequeue_remaining - 1;
+
+ end else if (enqueue_remaining > 0) begin
+ bitstorage[bitstorage_count] <=
+ inOp_d[`OP_LSBFIRST]
+ ? in_d[`DATAWIDTH-1-(inOp_d[`OP_DROP]+enqueue_remaining-1)]
+ : in_d[ inOp_d[`OP_DROP]+enqueue_remaining-1 ];
+ bitstorage_count <= bitstorage_count + 1;
+ if (enqueue_remaining == 1) begin
+ in_a <= 1;
+ inOp_a <= 1;
+ end
+ enqueue_remaining <= enqueue_remaining - 1;
+
+ end else if (in_r && !in_a && inOp_r && !inOp_a && `BITSTORAGE_SIZE > bitstorage_count + inOp_d[`OP_COUNT]) begin
+ // FIXME: zero count => lockup
+ enqueue_remaining <= inOp_d[`OP_COUNT];
+
+ end else if (!out_r && !out_a && outOp_r && !outOp_a && (bitstorage_count >= (outOp_d[`OP_COUNT]+outOp_d[`OP_DROP]))) begin
+ dequeue_remaining <= outOp_d[`OP_COUNT] + outOp_d[`OP_DROP];
+ out_d <= (outOp_d[`OP_SIGNEXT] && bitstorage[outOp_d[`OP_DROP]]) ? 37'b1111111111111111111111111111111111111 : 0;
+
+ end
+ end
+
+
+== Test ==============================================================
+
+// FIXME: this test case is woefully inadequate!!!!!
+
+// expected output
+#expect 1
+#expect 68719476736
+//#expect 12
+//#expect 13
+
+// ships required in order to run this code
+#ship debug : Debug
+#ship bitfifo : BitFifo
+
+bitfifo.outOp: literal BitFifo.outOp[take=37]; [*] deliver;
+bitfifo.out: [*] take, sendto debug.in;
+debug.in: [*] take, deliver;
+bitfifo.in: literal 1; [2] deliver;
+
+bitfifo.inOp:
+ literal BitFifo.inOp[take=37];
+ deliver;
+ literal BitFifo.inOp[take=37,lsbFirst];
+ deliver;
+
== Contributors =========================================================
Amir Kamil <kamil@cs.berkeley.edu>
+Adam Megacz <megacz@cs.berkeley.edu>