From 8d4e63a5dc1ac609a1ea3cebde45a058c24336e1 Mon Sep 17 00:00:00 2001 From: adam Date: Wed, 25 Jun 2008 11:17:37 +0100 Subject: [PATCH] re-arrange defunct ships --- ships/BitFifo.ship | 463 -------------------- ships/{ => obsolete}/Alu1.ship | 0 .../obsolete}/ArithmeticShip.java | 0 .../defunct-ships => ships/obsolete}/Counter.java | 0 .../defunct-ships => ships/obsolete}/DeMux.java | 0 {contrib/defunct-ships => ships/obsolete}/Dup.java | 0 .../defunct-ships => ships/obsolete}/Dup3.java | 0 .../obsolete}/DuplicatorShip.java | 0 .../obsolete}/HomeworkCounter.java | 0 .../obsolete}/MemoryReadShip.java | 0 .../obsolete}/MemoryWriteShip.java | 0 .../obsolete}/MultiplierShip.java | 0 {contrib/defunct-ships => ships/obsolete}/Mux.java | 0 .../obsolete}/ScatterShip.java | 0 .../defunct-ships => ships/obsolete}/Sort2.java | 0 ships/{Stack.ship- => obsolete/Stack.ship} | 0 16 files changed, 463 deletions(-) delete mode 100644 ships/BitFifo.ship rename ships/{ => obsolete}/Alu1.ship (100%) rename {contrib/defunct-ships => ships/obsolete}/ArithmeticShip.java (100%) rename {contrib/defunct-ships => ships/obsolete}/Counter.java (100%) rename {contrib/defunct-ships => ships/obsolete}/DeMux.java (100%) rename {contrib/defunct-ships => ships/obsolete}/Dup.java (100%) rename {contrib/defunct-ships => ships/obsolete}/Dup3.java (100%) rename {contrib/defunct-ships => ships/obsolete}/DuplicatorShip.java (100%) rename {contrib/defunct-ships => ships/obsolete}/HomeworkCounter.java (100%) rename {contrib/defunct-ships => ships/obsolete}/MemoryReadShip.java (100%) rename {contrib/defunct-ships => ships/obsolete}/MemoryWriteShip.java (100%) rename {contrib/defunct-ships => ships/obsolete}/MultiplierShip.java (100%) rename {contrib/defunct-ships => ships/obsolete}/Mux.java (100%) rename {contrib/defunct-ships => ships/obsolete}/ScatterShip.java (100%) rename {contrib/defunct-ships => ships/obsolete}/Sort2.java (100%) rename ships/{Stack.ship- => obsolete/Stack.ship} (100%) diff --git a/ships/BitFifo.ship b/ships/BitFifo.ship deleted file mode 100644 index e315122..0000000 --- a/ships/BitFifo.ship +++ /dev/null @@ -1,463 +0,0 @@ -ship: BitFifo - -== Ports =========================================================== -in: in -in: inOp - constant lsbFirst: ....................................1 - constant msbFirst: ....................................0 - constant drop: .............................uuuuuu.. - constant take: .......................uuuuuu........ - -out: out -in: outOp - constant lsbFirst: ....................................1 - constant msbFirst: ....................................0 - constant signExtend: ...................................1. - constant drop: .............................uuuuuu.. - constant take: ......................0uuuuuu........ - constant copy: ......................1uuuuuu........ - - -== TeX ============================================================== - -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. - -\subsection*{Enqueueing} - -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}. - -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. - -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 -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"); - } - } - } -} - -// Run BitStorage tests -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 Queue bits = new LinkedList(); -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_inOp.dataReadyForShip() && box_in.dataReadyForShip()) { - long op = box_inOp.removeDataForShip(); - long data = box_in.removeDataForShip(); - - 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 (!rev) - for(long i=take-1-drop; i>=0; i--) - add( (data & (1L<> 2) & (~(0xffffffffL << 6))); - int take = (int)((op >> 8) & (~(0xffffffffL << 6))); - if (bits.size() >= take+drop) { - // FIXME: copy - for(int i=0; i=0; i--) - if (get()) ret |= 1L< 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 - 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; load repeat counter with 2; deliver; - -bitfifo.inOp: - literal BitFifo.inOp[take=37]; - deliver; - literal BitFifo.inOp[take=37,lsbFirst]; - deliver; - - -== Contributors ========================================================= -Amir Kamil -Adam Megacz diff --git a/ships/Alu1.ship b/ships/obsolete/Alu1.ship similarity index 100% rename from ships/Alu1.ship rename to ships/obsolete/Alu1.ship diff --git a/contrib/defunct-ships/ArithmeticShip.java b/ships/obsolete/ArithmeticShip.java similarity index 100% rename from contrib/defunct-ships/ArithmeticShip.java rename to ships/obsolete/ArithmeticShip.java diff --git a/contrib/defunct-ships/Counter.java b/ships/obsolete/Counter.java similarity index 100% rename from contrib/defunct-ships/Counter.java rename to ships/obsolete/Counter.java diff --git a/contrib/defunct-ships/DeMux.java b/ships/obsolete/DeMux.java similarity index 100% rename from contrib/defunct-ships/DeMux.java rename to ships/obsolete/DeMux.java diff --git a/contrib/defunct-ships/Dup.java b/ships/obsolete/Dup.java similarity index 100% rename from contrib/defunct-ships/Dup.java rename to ships/obsolete/Dup.java diff --git a/contrib/defunct-ships/Dup3.java b/ships/obsolete/Dup3.java similarity index 100% rename from contrib/defunct-ships/Dup3.java rename to ships/obsolete/Dup3.java diff --git a/contrib/defunct-ships/DuplicatorShip.java b/ships/obsolete/DuplicatorShip.java similarity index 100% rename from contrib/defunct-ships/DuplicatorShip.java rename to ships/obsolete/DuplicatorShip.java diff --git a/contrib/defunct-ships/HomeworkCounter.java b/ships/obsolete/HomeworkCounter.java similarity index 100% rename from contrib/defunct-ships/HomeworkCounter.java rename to ships/obsolete/HomeworkCounter.java diff --git a/contrib/defunct-ships/MemoryReadShip.java b/ships/obsolete/MemoryReadShip.java similarity index 100% rename from contrib/defunct-ships/MemoryReadShip.java rename to ships/obsolete/MemoryReadShip.java diff --git a/contrib/defunct-ships/MemoryWriteShip.java b/ships/obsolete/MemoryWriteShip.java similarity index 100% rename from contrib/defunct-ships/MemoryWriteShip.java rename to ships/obsolete/MemoryWriteShip.java diff --git a/contrib/defunct-ships/MultiplierShip.java b/ships/obsolete/MultiplierShip.java similarity index 100% rename from contrib/defunct-ships/MultiplierShip.java rename to ships/obsolete/MultiplierShip.java diff --git a/contrib/defunct-ships/Mux.java b/ships/obsolete/Mux.java similarity index 100% rename from contrib/defunct-ships/Mux.java rename to ships/obsolete/Mux.java diff --git a/contrib/defunct-ships/ScatterShip.java b/ships/obsolete/ScatterShip.java similarity index 100% rename from contrib/defunct-ships/ScatterShip.java rename to ships/obsolete/ScatterShip.java diff --git a/contrib/defunct-ships/Sort2.java b/ships/obsolete/Sort2.java similarity index 100% rename from contrib/defunct-ships/Sort2.java rename to ships/obsolete/Sort2.java diff --git a/ships/Stack.ship- b/ships/obsolete/Stack.ship similarity index 100% rename from ships/Stack.ship- rename to ships/obsolete/Stack.ship -- 1.7.10.4