From e6db8cb5901129ea6f3f840b769e55292f17fd53 Mon Sep 17 00:00:00 2001 From: adam Date: Wed, 25 Jun 2008 11:18:34 +0100 Subject: [PATCH] update ships for 1.0 overhaul --- ships/Alu2.ship | 15 +-- ships/Alu3.ship | 213 +++++++++++++++++++++++++++++++++++++++++- ships/Fifo.ship | 20 ++++ ships/Lut3.ship | 16 ++-- ships/Memory.ship | 260 ++++++++++------------------------------------------ ships/Rotator.ship | 1 + 6 files changed, 292 insertions(+), 233 deletions(-) diff --git a/ships/Alu2.ship b/ships/Alu2.ship index 1a17432..10b3eeb 100644 --- a/ships/Alu2.ship +++ b/ships/Alu2.ship @@ -40,13 +40,6 @@ flags typically present in a conventional processor ALU are also not yet implemented. == Fleeterpreter ==================================================== -public long resolveLiteral(String literal) { - if (literal.equals("ADD")) return 0; - if (literal.equals("SUB")) return 1; - if (literal.equals("MAX")) return 2; - if (literal.equals("MIN")) return 3; - return super.resolveLiteral(literal); -} public void service() { if (box_in1.dataReadyForShip() && box_in2.dataReadyForShip() && @@ -115,16 +108,16 @@ alu.in1: alu.in2: literal 8; load repeat counter with 4; deliver; -alu.in1: [*] take, deliver; -alu.in2: [*] take, deliver; -alu.out: [*] take, sendto debug.in; - alu.inOp: literal Alu2.inOp[ADD]; deliver; literal Alu2.inOp[SUB]; deliver; literal Alu2.inOp[MIN]; deliver; literal Alu2.inOp[MAX]; deliver; +alu.in1: [*] take, deliver; +alu.in2: [*] take, deliver; +alu.out: [*] take, sendto debug.in; + == Contributors ========================================================= diff --git a/ships/Alu3.ship b/ships/Alu3.ship index be22147..578d155 100644 --- a/ships/Alu3.ship +++ b/ships/Alu3.ship @@ -42,8 +42,217 @@ Do we even need this? Can we do the same thing with {\tt Lut3} and == 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; -BitFifo.BitStorage outBits = new BitFifo.BitStorage(74); +BitStorage outBits = new BitStorage(74); public void service() { if (outBits.size() >= 37) { if (box_outBits.readyForDataFromShip()) { @@ -114,9 +323,9 @@ public void service() { == Test ======================================================================== +#skip #ship alu3 : Alu3 #ship lut3 : Lut3 -#ship bitfifo : BitFifo #ship debug : Debug #ship fifo : Fifo #ship rotator : Rotator diff --git a/ships/Fifo.ship b/ships/Fifo.ship index bcaec4b..dde1bc0 100644 --- a/ships/Fifo.ship +++ b/ships/Fifo.ship @@ -29,6 +29,26 @@ at least 16 words. == FleetSim ============================================================== +== FPGA ============================================================== + + wire in0_a; + wire out0_r; + wire [(`DATAWIDTH-1):0] out0_d; + + fifo8 fifo8(clk, rst, + in_r, in0_a, in_d, + out0_r, out_a, out0_d); + + always @(posedge clk) begin + if (!rst) begin + `reset + end else begin + in_a <= in0_a; + out_r <= out0_r; + out_d <= out0_d; + end + end + == Test ================================================================= // expected output #expect 9 diff --git a/ships/Lut3.ship b/ships/Lut3.ship index 9e408c5..ddbd37a 100644 --- a/ships/Lut3.ship +++ b/ships/Lut3.ship @@ -373,7 +373,7 @@ is considered ``bit zero''). #ship debug : Debug #ship lut : Lut3 -#ship alu : Alu1 +#ship alu : Alu2 lut.in1: literal 85; [*] deliver; lut.in2: literal 51; [*] deliver; @@ -381,8 +381,11 @@ lut.in3: literal 15; [*] deliver; lut.out: [*] take, sendto debug.in; // cycle through truth tables using alu as INC -alu.inOp: +alu.in2: literal 1; + [*] deliver; +alu.inOp: + literal Alu2.inOp[ADD]; load repeat counter with 63; deliver; load repeat counter with 63; @@ -393,16 +396,15 @@ alu.inOp: deliver; load repeat counter with 3; deliver; -alu.in: +alu.in1: literal 0; deliver; [*] take, deliver; alu.out: - clog; load loop counter with 2; - wait, take, sendto lut.inLut; - sendto alu.in; - unclog; + [L] wait, take, sendto lut.inLut; + [L] sendto alu.in1; + tail; // acks from debug ship trigger new truth tables debug.in: diff --git a/ships/Memory.ship b/ships/Memory.ship index 0f2f7c5..ed6d55e 100644 --- a/ships/Memory.ship +++ b/ships/Memory.ship @@ -9,6 +9,7 @@ data in: inStride data in: inCount data out: out +data out: outIhorn == TeX ============================================================== @@ -78,7 +79,7 @@ sequence guarantee problem mentioned in the previous paragraph. == Fleeterpreter ==================================================== private long[] mem = new long[0]; - public long readMem(int addr) { return mem[addr]; } + public long readMem(int addr) { return addr >= mem.length ? 0 : mem[addr]; } public void writeMem(int addr, long val) { if (addr >= mem.length) { long[] newmem = new long[addr * 2 + 1]; @@ -87,10 +88,10 @@ sequence guarantee problem mentioned in the previous paragraph. } mem[addr] = val; } - +/* public void dispatch(int addr, int size) { for(int i=addr; i> 6; long size = val & 0x3f; dispatch((int)addr, (int)size); } +*/ if (count > 0) { if (writing) { if (box_inDataWrite.dataReadyForShip() && box_out.readyForDataFromShip()) { @@ -161,230 +164,61 @@ sequence guarantee problem mentioned in the previous paragraph. == FleetSim ============================================================== == FPGA ============================================================== -`include "macros.v" -`define BRAM_ADDR_WIDTH 14 -`define BRAM_DATA_WIDTH `INSTRUCTION_WIDTH -`define BRAM_NAME some_bram - -/* bram.inc */ -module `BRAM_NAME(clk, rst, we, a, dpra, di, spo, dpo); - input clk; - input rst; - input we; - input [(`BRAM_ADDR_WIDTH-1):0] a; - input [(`BRAM_ADDR_WIDTH-1):0] dpra; - input [(`BRAM_DATA_WIDTH-1):0] di; - output [(`BRAM_DATA_WIDTH-1):0] spo; - output [(`BRAM_DATA_WIDTH-1):0] dpo; - reg [(`BRAM_DATA_WIDTH-1):0] ram [((1<<(`BRAM_ADDR_WIDTH))-1):0]; - reg [(`BRAM_ADDR_WIDTH-1):0] read_a; - reg [(`BRAM_ADDR_WIDTH-1):0] read_dpra; - always @(posedge clk) begin - if (we) - ram[a] <= di; - read_a <= a; - read_dpra <= dpra; - end - assign spo = ram[read_a]; - assign dpo = ram[read_dpra]; -endmodule -/* bram.inc */ - -module memory (clk, rst, - cbd_r, cbd_a_, cbd_d, - in_addr_r, in_addr_a_, in_addr_d, - write_addr_r, write_addr_a_, write_addr_d, - write_data_r, write_data_a_, write_data_d, - stride_r, stride_a_, stride_d, - count_r, count_a_, count_d, - out_r_, out_a, out_d_, - preload_r, preload_a_, preload_d, - ihorn_r_, ihorn_a, ihorn_d_, - dhorn_r_, dhorn_a, dhorn_d_ - ); - - input clk; - input rst; - `input(in_addr_r, in_addr_a, in_addr_a_, [(2+`DATAWIDTH-1):0], in_addr_d) - `input(write_addr_r, write_addr_a, write_addr_a_, [(2+`DATAWIDTH-1):0], write_addr_d) - `input(write_data_r, write_data_a, write_data_a_, [(`DATAWIDTH-1):0], write_data_d) - `input(stride_r, stride_a, stride_a_, [(`DATAWIDTH-1):0], stride_d) - `input(count_r, count_a, count_a_, [(`DATAWIDTH-1):0], count_d) - `output(out_r, out_r_, out_a, [(`DATAWIDTH-1):0], out_d_) - `input(preload_r, preload_a, preload_a_, [(`DATAWIDTH-1):0], preload_d) - `input(cbd_r, cbd_a, cbd_a_, [(`DATAWIDTH-1):0], cbd_d) - `output(ihorn_r, ihorn_r_, ihorn_a, [(`PACKET_WIDTH-1):0], ihorn_d_) - `defreg(ihorn_d_, [(`PACKET_WIDTH-1):0], ihorn_d) - `output(dhorn_r, dhorn_r_, dhorn_a, [(`PACKET_WIDTH-1):0], dhorn_d_) - `defreg(dhorn_d_, [(`PACKET_WIDTH-1):0], dhorn_d) - - reg ihorn_full; - initial ihorn_full = 0; - reg dhorn_full; - initial dhorn_full = 0; - reg command_valid; - initial command_valid = 0; - - reg [(`BRAM_ADDR_WIDTH-1):0] preload_pos; - reg [(`BRAM_ADDR_WIDTH-1):0] preload_size; - initial preload_size = 0; - - reg [(`BRAM_ADDR_WIDTH-1):0] current_instruction_read_from; - reg [(`BRAM_ADDR_WIDTH-1):0] temp_base; - reg [(`CODEBAG_SIZE_BITS-1):0] temp_size; - reg [(`BRAM_ADDR_WIDTH-1):0] cbd_base; - reg [(`CODEBAG_SIZE_BITS-1):0] cbd_size; - reg [(`CODEBAG_SIZE_BITS-1):0] cbd_pos; - reg [(`INSTRUCTION_WIDTH-1):0] command; - reg [(`BRAM_DATA_WIDTH-1):0] ram [((1<<(`BRAM_ADDR_WIDTH))-1):0]; - reg send_done; - reg send_read; - - reg [(`INSTRUCTION_WIDTH-(2+`DESTINATION_ADDRESS_BITS)):0] temp; - reg [(`DATAWIDTH-1):0] data; + reg [(`CODEBAG_SIZE_BITS-1):0] cursor; reg write_flag; - reg [(`BRAM_ADDR_WIDTH-1):0] in_addr; - reg [(`BRAM_DATA_WIDTH-1):0] write_data; - - wire [(`BRAM_DATA_WIDTH-1):0] ramread; - reg command_valid_read; - initial command_valid_read = 0; + wire [(`BRAM_ADDR_WIDTH-1):0] addr1; + wire [(`BRAM_ADDR_WIDTH-1):0] addr2; + wire [(`BRAM_DATA_WIDTH-1):0] val2; + assign addr1 = write_flag ? inAddrWrite_d[(`DATAWIDTH-1):0] : inAddrRead_d[(`DATAWIDTH-1):0]; + assign addr2 = (inCBD_d[(`INSTRUCTION_WIDTH-1):(`CODEBAG_SIZE_BITS)])+cursor; - reg launched; - initial launched = 0; + bram14 mybram(clk, rst, write_flag, addr1, addr2, inDataWrite_d, out_d_, val2); - some_bram mybram(clk, rst, write_flag, in_addr, current_instruction_read_from, write_data, not_connected, ramread); - assign out_d_ = ramread; + always @(posedge clk) begin - always @(posedge clk /*or negedge rst*/) begin + write_flag <= 0; if (!rst) begin - - in_addr_a = 1; - write_addr_a = 1; - write_data_a = 1; - stride_a = 1; - count_a = 1; - preload_a <= 1; - cbd_a <= 1; - - out_r <= 0; - ihorn_r <= 0; - dhorn_r <= 0; - - ihorn_full <= 0; - dhorn_full <= 0; - command_valid <= 0; - - // uncommenting either of these causes headaches - preload_size <= 0; - preload_pos <= 0; - temp_base = 0; - temp_size = 0; - - launched <= 0; - command_valid_read <= 0; - write_flag <= 0; - - dhorn_r <= 0; - ihorn_r <= 0; - out_r <= 0; + `reset + cursor <= 0; end else begin + write_flag <= 0; - write_flag <= 0; - - if (!in_addr_r && in_addr_a) in_addr_a = 0; - if (!write_data_r && write_data_a) write_data_a = 0; - if (!write_addr_r && write_addr_a) write_addr_a = 0; - - if (command_valid_read) begin - command_valid_read <= 0; - command_valid <= 1; - - end else if (send_done) begin - `onwrite(out_r, out_a) - send_done <= 0; - end - - end else if (send_read) begin - `onwrite(out_r, out_a) - send_read <= 0; - end - - end else if (in_addr_r) begin - in_addr_a = 1; - send_read <= 1; - current_instruction_read_from <= in_addr_d[(`DATAWIDTH-1):0]; - - end else if (write_addr_r && write_data_r) begin - write_addr_a = 1; - write_data_a = 1; - send_done <= 1; - write_flag <= 1; - in_addr <= write_addr_d[(`DATAWIDTH-1):0]; - write_data <= write_data_d; - - end else if (ihorn_full && launched) begin - `onwrite(ihorn_r, ihorn_a) - ihorn_full <= 0; - end - - end else if (dhorn_full) begin - `onwrite(dhorn_r, dhorn_a) - dhorn_full <= 0; - end - - end else if (command_valid) begin - command_valid <= 0; - command = ramread; - ihorn_full <= 1; - `packet_data(ihorn_d) <= `instruction_data(command); - `packet_dest(ihorn_d) <= `instruction_dest(command); - - end else if (cbd_pos < cbd_size) begin - current_instruction_read_from <= cbd_base+cbd_pos; - command_valid_read <= 1; - cbd_pos <= cbd_pos + 1; + if (!inAddrRead_r && inAddrRead_a) inAddrRead_a <= 0; + if (!inDataWrite_r && inDataWrite_a) inDataWrite_a <= 0; + if (!inAddrWrite_r && inAddrWrite_a) inAddrWrite_a <= 0; - end else begin - `onread(cbd_r, cbd_a) - cbd_pos <= 0; - cbd_size <= cbd_d[(`CODEBAG_SIZE_BITS-1):0]; - cbd_base <= cbd_d[(`INSTRUCTION_WIDTH-1):(`CODEBAG_SIZE_BITS)]; - - end else begin - `onread(preload_r, preload_a) - if (preload_size == 0) begin - preload_size <= preload_d; - preload_pos <= 0; - end else if (!launched) begin - write_flag <= 1; - write_data <= preload_d; - in_addr <= preload_pos; - if (preload_pos == 0) begin - temp_base = preload_d[(`INSTRUCTION_WIDTH-(3+`DESTINATION_ADDRESS_BITS)):(`CODEBAG_SIZE_BITS)]; - temp_size = preload_d[(`CODEBAG_SIZE_BITS-1):0]; - end - if ((preload_pos+1) == preload_size) begin - cbd_pos <= 0; - cbd_base <= temp_base; - cbd_size <= temp_size; - launched <= 1; - end - preload_pos <= preload_pos + 1; - end + if ( out_r && !out_a) begin + end else if ( out_r && out_a) begin out_r <= 0; + end else if (!out_r && !out_a && inAddrRead_r && !inAddrRead_a) begin + inAddrRead_a <= 1; + out_r <= 1; + + end else if (!out_r && !out_a && inAddrWrite_r && inDataWrite_r) begin + // timing note: it's okay to set the *_a flags here because *_d will still + // be valid on the *next* cycle, which is all we care about + inAddrWrite_a <= 1; + inDataWrite_a <= 1; + out_r <= 1; + write_flag <= 1; + + end else if ( outIhorn_r && outIhorn_a) begin outIhorn_r <= 0; + end else if (!inCBD_r && inCBD_a) begin inCBD_a <= 0; + end else if ( inCBD_r && !inCBD_a && !outIhorn_r && !outIhorn_a) begin + if (cursor < inCBD_d[(`CODEBAG_SIZE_BITS-1):0]) begin + outIhorn_d <= val2; + outIhorn_r <= 1; + cursor <= cursor + 1; + end else begin + inCBD_a <= 1; + cursor <= 0; end end - - end - end end -endmodule - - + diff --git a/ships/Rotator.ship b/ships/Rotator.ship index c9b5790..4ceec61 100644 --- a/ships/Rotator.ship +++ b/ships/Rotator.ship @@ -54,6 +54,7 @@ public void service() { == Test ============================================================== + // expected output #expect 2 #expect 44627559471 -- 1.7.10.4