--- /dev/null
+ship: Alu3
+
+== Ports ===========================================================
+data in: in1
+data in: in2
+data in: in3
+
+data out: out1
+ shortcut to: in1
+data out: out2
+ shortcut to: in2
+data out: outBits
+
+== Constants ========================================================
+== TeX ==============================================================
+
+{\tt Alu3} is a three-input adder which produces a pair of outputs in
+carry-save form. It has no opcode input.
+
+This ship also contains a private ``bit fifo'' similar to the {\tt
+BitFifo} ship, except that only the dequeueing (output) interface is
+exposed to the programmer. Each addition operation performed causes
+the lowest bit of the {\it save} output to be enqueued into the bit
+fifo. This can be used to produce a very efficient multiplier; see
+the test case for this ship for more details.
+
+\subsection*{Semantics}
+
+When a value is present at each of {\tt in1}, {\tt in2} and {\tt in3},
+these three values are consumed. The {\it carry} result of carry-save
+addition is placed in {\tt out1}, and the {\it save} result of
+carry-save addition is placed in {\tt out2}.
+
+\subsection*{To Do}
+
+Is the second output supposed to be shifted?
+
+Provide a way to clear/flush the internal bitfifo.
+
+Do we even need this? Can we do the same thing with {\tt Lut3} and
+{\tt BitFifo} together?
+
+
+== Fleeterpreter ====================================================
+static class BitStorage {
+ long[] bits;
+ int numbits = 0;
+ int start = 0;
+ BitStorage(int size) {
+ bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
+ }
+ int size() {
+ return numbits;
+ }
+ 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;
+ 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);
+ } else {
+ numbits += num;
+ return true;
+ }
+ }
+ long get(int num) {
+ assert size() >= num : "too few bits in storage";
+ int entry = start / 64;
+ int off = start % 64;
+ int max = 64 - off;
+ int n = num > max ? max : num;
+ long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
+ long res = (bits[entry] >>> off) & mask;
+ int oldstart = start;
+ if (n < num) {
+ int n2 = num - 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 res;
+ }
+ int capacity() {
+ 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);
+ Random rand = new Random();
+ Vector ins = new Vector();
+ Vector ret = new Vector();
+ StringBuffer sbi = new StringBuffer();
+ StringBuffer sbr = new StringBuffer();
+ System.out.println("==== Test #2 ====");
+ for (int i = 0; i < iters; i++) {
+ long 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);
+ num = rand.nextInt(Math.min(37, bs.size()));
+ s = bs.size();
+ data = bs.get(num);
+ assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
+ ret.add(new Integer(num));
+ add(sbr, data, num);
+ }
+ //for (int i = 0; i < iters; i++) {
+ while (bs.size() > 0) {
+ int num = Math.min(rand.nextInt(37), bs.size());
+ //int num = Math.min(33, bs.size());
+ int s = bs.size();
+ long data = bs.get(num);
+ assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
+ ret.add(new Integer(num));
+ add(sbr, data, num);
+ }
+ System.out.println("inserted:");
+ System.out.println(sbi);
+ System.out.println("retrieved:");
+ System.out.println(sbr);
+ System.out.println("insertion 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 test1(String[] args) {
+ int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
+ BitStorage bs = new BitStorage(37 * iters);
+ Random rand = new Random();
+ Vector ins = new Vector();
+ Vector ret = new Vector();
+ StringBuffer sbi = new StringBuffer();
+ StringBuffer sbr = new StringBuffer();
+ System.out.println("==== Test #1 ====");
+ System.out.println("inserting...");
+ for (int i = 0; i < iters; i++) {
+ long 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...");
+ //for (int i = 0; i < iters; i++) {
+ while (bs.size() > 0) {
+ int num = Math.min(rand.nextInt(37), bs.size());
+ //int num = Math.min(33, bs.size());
+ int s = bs.size();
+ long data = bs.get(num);
+ assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
+ 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 print(long data, int num) {
+ for (int i = 0; i < num; i++) {
+ System.out.print((data >>> i) & 0x1);
+ }
+ }
+ static void add(StringBuffer sb, long data, int num) {
+ for (int i = 0; i < num; i++) {
+ sb.append((int) ((data >>> i) & 0x1));
+ }
+ }
+ static void check(StringBuffer sb1, StringBuffer sb2) {
+ int len = sb2.length();
+ if (len > sb1.length()) {
+ System.out.println("error: retrieval sequence is longer than insertion sequence");
+ len = sb1.length();
+ }
+ for (int i = 0; i < sb2.length(); i++) {
+ if (sb1.charAt(i) != sb2.charAt(i)) {
+ System.out.println("error: bit at position " + i + " does not match");
+ }
+ }
+ }
+}
+boolean mode = false;
+BitStorage outBits = new BitStorage(74);
+public void service() {
+ if (outBits.size() >= 37) {
+ if (box_outBits.readyForDataFromShip()) {
+ box_outBits.addDataFromShip(outBits.get(37));
+ }
+ } else
+ if (box_in1.dataReadyForShip() &&
+ box_in2.dataReadyForShip() &&
+ box_in3.dataReadyForShip() &&
+ outBits.hasSpace(1) &&
+ box_out1.readyForDataFromShip() &&
+ box_out2.readyForDataFromShip()) {
+ long v1 = box_in1.removeDataForShip();
+ long v2 = box_in2.removeDataForShip();
+ long v3 = box_in3.removeDataForShip();
+ long o1, o2, o3;
+ o1 = ((v1 & v2) | (v2 & v3) | (v1 & v3))/* << 1*/;
+ o2 = (v1 ^ v2 ^ v3) >> 1;
+ outBits.add((v1 ^ v2 ^ v3) & 0x1L, 1);
+ box_out1.addDataFromShip(o1);
+ box_out2.addDataFromShip(o2);
+ }
+}
+
+== FleetSim ==============================================================
+
+== FPGA ==============================================================
+
+ reg [73:0] bitstorage; initial bitstorage = 0;
+ reg [7:0] bitstorage_count; initial bitstorage_count = 0;
+
+ always @(posedge clk) begin
+ if (!rst) begin
+ `reset
+ bitstorage <= 0;
+ bitstorage_count <= 0;
+ end else begin
+ if (out1_r && out1_a) out1_r <= 0;
+ if (out2_r && out2_a) out2_r <= 0;
+ if (outBits_r && outBits_a) outBits_r <= 0;
+ if (!in1_r && in1_a) in1_a <= 0;
+ if (!in2_r && in2_a) in2_a <= 0;
+ if (!in3_r && in3_a) in3_a <= 0;
+ if (!out1_r && !out2_r && !outBits_r && in1_r && in2_r && in3_r) begin
+ out1_d <= { ((in1_d & in2_d)
+ | (in2_d & in3_d)
+ | (in1_d & in3_d)) };
+ out2_d <= { 1'b0, (in1_d[(`DATAWIDTH-1):1] ^
+ in2_d[(`DATAWIDTH-1):1] ^
+ in3_d[(`DATAWIDTH-1):1]) };
+ if (bitstorage_count >= `DATAWIDTH-1) begin
+ outBits_d <= bitstorage[(`DATAWIDTH-1):0];
+ outBits_r <= 1;
+ bitstorage_count <= 0;
+ bitstorage <= bitstorage >> `DATAWIDTH;
+ end
+ bitstorage[bitstorage_count] <= (in1_d[0] ^ in2_d[0] ^ in3_d[0]);
+ bitstorage_count <= bitstorage_count+1;
+ out1_r <= 1;
+ out2_r <= 1;
+ in1_a <= 1;
+ in2_a <= 1;
+ in3_a <= 1;
+ end
+ end
+ end
+
+
+
+== Test ========================================================================
+#skip
+#ship alu3 : Alu3
+#ship lut3 : Lut3
+#ship debug : Debug
+#ship fifo : Fifo
+#ship rotator : Rotator
+
+#expect 0
+#expect 2
+#expect 1
+
+// 0: 100100100111110000000
+// sel 011110100001001000000
+// 1: 111000101000011000011
+// r: 111000100110111000000
+
+alu3.in1: literal 1; deliver; load repeat counter with 36; deliver;
+alu3.in2: literal 0; deliver; literal 1; load repeat counter with 36; deliver;
+alu3.in3: literal 4; deliver; load repeat counter with 36; deliver;
+
+alu3.out1: take; sendto debug.in; [*] take;
+alu3.out2: take; wait; sendto debug.in; [*] take;
+alu3.outBits: take; wait; sendto debug.in;
+
+debug.in:
+ take, deliver;
+ notify alu3.out2;
+ take, deliver;
+ notify alu3.outBits;
+ take, deliver;
+
+
+== Contributors =========================================================
+Amir Kamil <kamil@cs.berkeley.edu>
+Adam Megacz <megacz@cs.berkeley.edu>
projects / fleet.git / blobdiff