From d3f3eba69681ba0519db4e60fc3d43651eb204ea Mon Sep 17 00:00:00 2001 From: adam Date: Wed, 25 Oct 2006 11:42:18 +0100 Subject: [PATCH] update with ZOMA and new memread/memwrite --- Makefile | 9 ++- fleet.g | 18 +++-- src/edu/berkeley/fleet/BitBucketShip.java | 18 +++++ src/edu/berkeley/fleet/ConditionalFetchShip.java | 25 +++++++ src/edu/berkeley/fleet/CounterShip.java | 26 +++++++ src/edu/berkeley/fleet/DecrementShip.java | 20 +++++ src/edu/berkeley/fleet/Dup.java | 24 ++++++ src/edu/berkeley/fleet/DupShip.java | 24 ++++++ src/edu/berkeley/fleet/FetchShip.java | 5 +- src/edu/berkeley/fleet/FifoShip.java | 30 ++++++++ src/edu/berkeley/fleet/Fleet.java | 7 ++ src/edu/berkeley/fleet/FleetParser.java | 10 +-- src/edu/berkeley/fleet/LessThanZeroShip.java | 22 ++++++ src/edu/berkeley/fleet/MemReadShip.java | 34 +++++++-- src/edu/berkeley/fleet/MemWriteShip.java | 44 +++++++++-- src/edu/berkeley/fleet/MultiplierShip.java | 21 ++++++ src/edu/berkeley/fleet/Program.java | 72 +++++++++--------- src/edu/berkeley/fleet/Ship.java | 25 ++++++- src/edu/berkeley/fleet/SubtracterShip.java | 21 ++++++ src/edu/berkeley/fleet/UnGateShip.java | 22 ++++++ test.fleet | 86 +++++++++------------- 21 files changed, 449 insertions(+), 114 deletions(-) create mode 100644 src/edu/berkeley/fleet/BitBucketShip.java create mode 100644 src/edu/berkeley/fleet/ConditionalFetchShip.java create mode 100644 src/edu/berkeley/fleet/CounterShip.java create mode 100644 src/edu/berkeley/fleet/DecrementShip.java create mode 100644 src/edu/berkeley/fleet/Dup.java create mode 100644 src/edu/berkeley/fleet/DupShip.java create mode 100644 src/edu/berkeley/fleet/FifoShip.java create mode 100644 src/edu/berkeley/fleet/LessThanZeroShip.java create mode 100644 src/edu/berkeley/fleet/MultiplierShip.java create mode 100644 src/edu/berkeley/fleet/SubtracterShip.java create mode 100644 src/edu/berkeley/fleet/UnGateShip.java diff --git a/Makefile b/Makefile index 1d48bad..310f1e8 100644 --- a/Makefile +++ b/Makefile @@ -1,9 +1,12 @@ +go: fleeterpreter.jar + java -Xmx500m -cp lib/edu.berkeley.sbp.jar:fleeterpreter.jar edu.berkeley.fleet.FleetParser + run: fleeterpreter.jar - java -cp lib/edu.berkeley.sbp.jar:fleeterpreter.jar edu.berkeley.fleet.FleetParser < test.fleet + java -Xmx500m -cp lib/edu.berkeley.sbp.jar:fleeterpreter.jar edu.berkeley.fleet.FleetParser < test.fleet applet: fleeterpreter.jar - java -cp lib/edu.berkeley.sbp.jar:fleeterpreter.jar edu.berkeley.fleet.FleetApplet < test.fleet + java -Xmx500m -cp lib/edu.berkeley.sbp.jar:fleeterpreter.jar edu.berkeley.fleet.FleetApplet < test.fleet fleeterpreter.jar: $(shell find src -name \*.java) fleet.g mkdir -p bin @@ -11,5 +14,5 @@ fleeterpreter.jar: $(shell find src -name \*.java) fleet.g cp test.fleet bin javac -cp lib/edu.berkeley.sbp.jar -d bin $(shell find src -name \*.java) cd bin; jar xvf ../lib/edu.berkeley.sbp.jar - echo 'Main-Class: edu.berkeley.fleet.FleetApplet' > bin/manifest + echo 'Main-Class: edu.berkeley.fleet.FleetParser' > bin/manifest cd bin; jar cvmf manifest ../$@ . diff --git a/fleet.g b/fleet.g index 2e2f96d..b5beac2 100644 --- a/fleet.g +++ b/fleet.g @@ -11,8 +11,14 @@ Comment = "//" ~[\n]* "\n" | "/*" ~[\n]* "*/" -w = [\r\n ]* -ws = (w | Comment)* -> ~[\r\n ] +w = [\r\n ] +ws = w ws! + | Comment ws! + | () + +// for some reason this causes major slowness! +//w = [\r\n ]* +//ws = (w | Comment)* -> ~[\r\n ] s = ws! Program ws! Program = Program:: @@ -29,8 +35,10 @@ Statement = Move ((ws ";")?)! // | ^"#define" Port Port /ws Move = Port ^"->" Destination /ws - | Port ^"->*" Destination /ws - | LiteralMove:: int "->" Destination /ws + | Port ^"-(*)->" Destination /ws + | Port ^"-(" int ")->" Destination /ws + | LiteralMove:: int "->" Destination /ws + | LiteralCountMove:: int "-(" int ")->" Destination /ws | CodeBagMove:: CodeBag "->" Port /ws | CodeBagMoveX:: Port "<-" CodeBag /ws | Port ^"<-" Port /ws @@ -45,7 +53,7 @@ CodeBagName = name Port = Port:: shipname "." portname shipname = ShipName:: name portname = PortName:: name -name = ([A-Za-z0-9\[\]]+ &~ ([0-9]! ~[]*)) +name = Name:: [A-Za-z] [A-Za-z0-9\[\]]* index = "[" [0-9]+ "]" | [0-9]+ int = [\-0-9]++ diff --git a/src/edu/berkeley/fleet/BitBucketShip.java b/src/edu/berkeley/fleet/BitBucketShip.java new file mode 100644 index 0000000..bb832a4 --- /dev/null +++ b/src/edu/berkeley/fleet/BitBucketShip.java @@ -0,0 +1,18 @@ +package edu.berkeley.fleet; + +import java.util.*; +import java.io.*; + +public class BitBucketShip extends Ship { + + Inbox in = new Inbox("in"); + + public BitBucketShip(Fleet fleet, String name) { + super(fleet, name); + } + + public void service() { + if (!in.empty()) in.remove(); + } + +} diff --git a/src/edu/berkeley/fleet/ConditionalFetchShip.java b/src/edu/berkeley/fleet/ConditionalFetchShip.java new file mode 100644 index 0000000..1e8603a --- /dev/null +++ b/src/edu/berkeley/fleet/ConditionalFetchShip.java @@ -0,0 +1,25 @@ +package edu.berkeley.fleet; + +import java.util.*; +import java.io.*; + +public class ConditionalFetchShip extends Ship { + + Inbox in = new Inbox("in"); + Inbox use = new Inbox("use"); + Outbox done = new Outbox("done"); + + public ConditionalFetchShip(Fleet fleet, String name) { + super(fleet, name); + } + + public void service() { + while (!in.empty() && !use.empty()) { + boolean use_ = use.remove() != 0; + int cbd = in.remove(); + if (use_) fleet.dispatchCodeBag(cbd); + done.add(0); + } + } + +} diff --git a/src/edu/berkeley/fleet/CounterShip.java b/src/edu/berkeley/fleet/CounterShip.java new file mode 100644 index 0000000..9ef7a09 --- /dev/null +++ b/src/edu/berkeley/fleet/CounterShip.java @@ -0,0 +1,26 @@ +package edu.berkeley.fleet; + +import java.util.*; +import java.io.*; + +public class CounterShip extends Ship { + + Inbox set = new Inbox("set"); + Inbox next = new Inbox("next"); + Outbox val = new Outbox("val"); + + private int count = 0; + + public CounterShip(Fleet fleet, String name) { + super(fleet, name); + } + + public void service() { + if (!set.empty()) count = set.remove(); + if (!next.empty()) { + next.remove(); + val.add(count--); + } + } + +} diff --git a/src/edu/berkeley/fleet/DecrementShip.java b/src/edu/berkeley/fleet/DecrementShip.java new file mode 100644 index 0000000..1f41cfa --- /dev/null +++ b/src/edu/berkeley/fleet/DecrementShip.java @@ -0,0 +1,20 @@ +package edu.berkeley.fleet; + +import java.util.*; +import java.io.*; + +public class DecrementShip extends Ship { + + Inbox in = new Inbox("in"); + Outbox out = new Outbox("out"); + + public DecrementShip(Fleet fleet, String name) { + super(fleet, name); + } + + public void service() { + if (in.empty()) return; + out.add(in.remove()-1); + } + +} diff --git a/src/edu/berkeley/fleet/Dup.java b/src/edu/berkeley/fleet/Dup.java new file mode 100644 index 0000000..72983b1 --- /dev/null +++ b/src/edu/berkeley/fleet/Dup.java @@ -0,0 +1,24 @@ +package edu.berkeley.fleet; + +import java.util.*; +import java.io.*; + +public class Dup extends Ship { + + Inbox in = new Inbox("in"); + Outbox out1 = new Outbox("out1"); + Outbox out2 = new Outbox("out2"); + + public Dup(Fleet fleet, String name) { + super(fleet, name); + } + + public void service() { + while (!in.empty()) { + int data = in.remove(); + out1.add(data); + out2.add(data); + } + } + +} diff --git a/src/edu/berkeley/fleet/DupShip.java b/src/edu/berkeley/fleet/DupShip.java new file mode 100644 index 0000000..fefcf01 --- /dev/null +++ b/src/edu/berkeley/fleet/DupShip.java @@ -0,0 +1,24 @@ +package edu.berkeley.fleet; + +import java.util.*; +import java.io.*; + +public class DupShip extends Ship { + + Inbox in = new Inbox("in"); + Outbox out1 = new Outbox("out1"); + Outbox out2 = new Outbox("out2"); + + public DupShip(Fleet fleet, String name) { + super(fleet, name); + } + + public void service() { + if (!in.empty()) { + int data = in.remove(); + out1.add(data); + out2.add(data); + } + } + +} diff --git a/src/edu/berkeley/fleet/FetchShip.java b/src/edu/berkeley/fleet/FetchShip.java index a326ab1..7a96cc3 100644 --- a/src/edu/berkeley/fleet/FetchShip.java +++ b/src/edu/berkeley/fleet/FetchShip.java @@ -6,14 +6,17 @@ import java.io.*; public class FetchShip extends Ship { Inbox in = new Inbox("in"); + Outbox done = new Outbox("done"); public FetchShip(Fleet fleet, String name) { super(fleet, name); } public void service() { - while (!in.empty()) + while (!in.empty()) { fleet.dispatchCodeBag(in.remove()); + done.add(0); + } } } diff --git a/src/edu/berkeley/fleet/FifoShip.java b/src/edu/berkeley/fleet/FifoShip.java new file mode 100644 index 0000000..52605ba --- /dev/null +++ b/src/edu/berkeley/fleet/FifoShip.java @@ -0,0 +1,30 @@ +package edu.berkeley.fleet; + +import java.util.*; +import java.io.*; + +public class FifoShip extends Ship { + + Inbox in = new Inbox("in"); + Inbox token = new Inbox("token"); + Outbox out = new Outbox("out"); + + private ArrayList fifo = new ArrayList(); + + public FifoShip(Fleet fleet, String name) { + super(fleet, name); + } + + public void service() { + if (!in.empty()) { + fifo.add(in.remove()); + return; + } + if (!token.empty() && fifo.size()>0) { + token.remove(); + out.add(fifo.remove(0)); + return; + } + } + +} diff --git a/src/edu/berkeley/fleet/Fleet.java b/src/edu/berkeley/fleet/Fleet.java index 227db43..e78ac74 100644 --- a/src/edu/berkeley/fleet/Fleet.java +++ b/src/edu/berkeley/fleet/Fleet.java @@ -25,6 +25,13 @@ public class Fleet { ship._service(); } + public void dumpMem() { + for(int i=0; i 0) { + _loaded = true; + return; + } + } + System.out.println("read_mem["+_addr+"]"); + data.add(_addr>=fleet.mem.length ? 0 : fleet.mem[_addr]); + _count--; + _addr += _stride; } } diff --git a/src/edu/berkeley/fleet/MemWriteShip.java b/src/edu/berkeley/fleet/MemWriteShip.java index 7c02b4b..994b16e 100644 --- a/src/edu/berkeley/fleet/MemWriteShip.java +++ b/src/edu/berkeley/fleet/MemWriteShip.java @@ -5,19 +5,49 @@ import java.io.*; public class MemWriteShip extends Ship { - Inbox addr = new Inbox("addr"); - Inbox data = new Inbox("data"); - Outbox done = new Outbox("done"); + boolean _loaded = false; + int _count = 0; + int _stride = 0; + int _addr = 0; + + Inbox addr = new Inbox("addr"); + Inbox data = new Inbox("data"); + Inbox stride = new Inbox("stride"); + Inbox count = new Inbox("count"); + Outbox token = new Outbox("token"); + Outbox done = new Outbox("done"); public MemWriteShip(Fleet fleet, String name) { super(fleet, name); } public void service() { - // note that the memory interface is pipelined (buffered) - if (!addr.empty() && !data.empty()) { - fleet.mem[addr.remove()] = data.remove(); - done.add(0); + if (_loaded) { + if (_count <= 0) { _count = 0; _loaded = false; done.add(0); return; } + if (data.empty()) return; + if (!token.empty()) return; + } else { + if (addr.empty() || stride.empty() || count.empty() || data.empty()) return; + _count = count.remove(); + _addr = addr.remove(); + _stride = stride.remove(); + if (_count > 0) { + _loaded = true; + return; + } + } + int dat = data.remove(); + if (_addr >= fleet.mem.length) { + int[] mem2 = new int[_addr + 100]; + System.arraycopy(fleet.mem, 0, mem2, 0, fleet.mem.length); + fleet.mem = mem2; + } + System.out.println("write_mem["+_addr+"] = " + dat); + fleet.mem[_addr] = dat; + _count--; + _addr += _stride; + if (_loaded) { + token.add(0); } } diff --git a/src/edu/berkeley/fleet/MultiplierShip.java b/src/edu/berkeley/fleet/MultiplierShip.java new file mode 100644 index 0000000..0a978ee --- /dev/null +++ b/src/edu/berkeley/fleet/MultiplierShip.java @@ -0,0 +1,21 @@ +package edu.berkeley.fleet; + +import java.util.*; +import java.io.*; + +public class MultiplierShip extends Ship { + + Inbox in1 = new Inbox("in1"); + Inbox in2 = new Inbox("in2"); + Outbox out = new Outbox("out"); + + public MultiplierShip(Fleet fleet, String name) { + super(fleet, name); + } + + public void service() { + if (!in1.empty() && !in2.empty()) + out.add(in1.remove() * in2.remove()); + } + +} diff --git a/src/edu/berkeley/fleet/Program.java b/src/edu/berkeley/fleet/Program.java index 9515a1a..d67d394 100644 --- a/src/edu/berkeley/fleet/Program.java +++ b/src/edu/berkeley/fleet/Program.java @@ -55,12 +55,18 @@ public class Program { } public static @bind.as("LiteralMove") Statement move(String value, Port[] dest) { - return new LiteralMove(Integer.parseInt(value), dest); + return new Move(Integer.parseInt(value), dest); + } + public static @bind.as("LiteralCountMove") Statement move(String value, String count, + Port[] dest) { + return new Move(Integer.parseInt(value), dest, Integer.parseInt(count)); } - public static @bind.as("->*") Statement smove(Port source, Port[] dest) { - //return new SMove(source, dest); - return null; + public static @bind.as("-(*)->") Statement smove(Port source, Port[] dest) { + return new Move(source, dest, Integer.MAX_VALUE); + } + public static @bind.as("-(") Statement smove(Port source, String count, Port[] dest) { + return new Move(source, dest, Integer.parseInt(count)); } public static @bind.as("<-") Statement gets(Port dest, Port source) { @@ -77,6 +83,7 @@ public class Program { public static @bind.as("ShipName") String shipname(String name, String index) { return index==null?name:name+index; } public static @bind.as("PortName") String portname(String name, String index) { return index==null?name:name+index; } + public static @bind.as("Name") String name(String a, String b) { return a+b; } public static interface Source { } public static interface Destination { } @@ -150,40 +157,39 @@ public class Program { public static class Move implements Statement { Port source; Port[] dest; - public Move(Port source, Port[] dest) { this.source = source; this.dest = dest; } - public void dispatch(Fleet fleet) { - Ship.Outbox ob = fleet.getOutbox(source.ship, source.port); - for(Port d : dest) { - Ship.Inbox ib = fleet.getInbox(d.ship, d.port); - ob.addDestination(ib); - Log.println("instr: " + ob + " -> " + ib); - } - } - public String toString() { - StringBuffer sb = new StringBuffer(); - sb.append(source + " -> "); - sb.append(dest[0]); - for(int i=1; i " + ib); - } + Ship.Outbox ob = source==null ? null : fleet.getOutbox(source.ship, source.port); + int repcount = count; + if (repcount == 0 || repcount == Integer.MAX_VALUE) repcount = 1; + for(int i=0; i " + ib); + } else { + if (count==0) ob.addTokenDestination(ib); + else if (count==Integer.MAX_VALUE) ob.addStandingDestination(ib); + else ob.addDestination(ib); + Log.println("instr: " + ob + " -> " + ib); + } + } } public String toString() { StringBuffer sb = new StringBuffer(); - sb.append(val + " -> "); + sb.append((source==null ? (val+"") : source+"") + " -"+(count<=1?"":("("+count+")"))+"-> "); sb.append(dest[0]); for(int i=1; i " + destination); + continue; + } + if (ob.standingDestination != null) { + int data = ob.data.remove(); + Inbox destination = ob.standingDestination; + destination.add(data); + Log.println("data: " + ob + " *****("+data+")*****> " + destination); + continue; } } service(); @@ -59,11 +68,23 @@ public abstract class Ship { public class Outbox { private String name; + public Inbox standingDestination; public Queue data = new LinkedList(); public Queue destination = new LinkedList(); public void add(int data) { this.data.add(data); } public void flush() { data.clear(); /* FIXME: risky */ } - public void addDestination(Inbox destination) { this.destination.add(destination); } + public void addTokenDestination(Inbox destination) { + standingDestination = null; + this.destination.add(destination); + this.add(0); + } + public void addStandingDestination(Inbox destination) { + standingDestination = destination; + } + public void addDestination(Inbox destination) { + standingDestination = null; + this.destination.add(destination); + } public boolean empty() { return data.isEmpty(); } public String toString() { return Ship.this.name+"."+name; } public Outbox(String name) { diff --git a/src/edu/berkeley/fleet/SubtracterShip.java b/src/edu/berkeley/fleet/SubtracterShip.java new file mode 100644 index 0000000..159b560 --- /dev/null +++ b/src/edu/berkeley/fleet/SubtracterShip.java @@ -0,0 +1,21 @@ +package edu.berkeley.fleet; + +import java.util.*; +import java.io.*; + +public class SubtracterShip extends Ship { + + Inbox in1 = new Inbox("in1"); + Inbox in2 = new Inbox("in2"); + Outbox out = new Outbox("out"); + + public SubtracterShip(Fleet fleet, String name) { + super(fleet, name); + } + + public void service() { + if (!in1.empty() && !in2.empty()) + out.add(in1.remove() - in2.remove()); + } + +} diff --git a/src/edu/berkeley/fleet/UnGateShip.java b/src/edu/berkeley/fleet/UnGateShip.java new file mode 100644 index 0000000..d92258b --- /dev/null +++ b/src/edu/berkeley/fleet/UnGateShip.java @@ -0,0 +1,22 @@ +package edu.berkeley.fleet; + +import java.util.*; +import java.io.*; + +public class UnGateShip extends Ship { + + Inbox in = new Inbox("in"); + Outbox out = new Outbox("out"); + Outbox token = new Outbox("token"); + + public UnGateShip(Fleet fleet, String name) { + super(fleet, name); + } + + public void service() { + if (in.empty()) return; + out.add(in.remove()); + token.add(0); + } + +} diff --git a/test.fleet b/test.fleet index f71d265..c95fdbd 100644 --- a/test.fleet +++ b/test.fleet @@ -1,54 +1,38 @@ -// lines beginning with "#" are directives to the interpreter -// and are not part of the actual FLEET assembly code - -// import the ships in the Java package edu.berkeley.fleet - #import edu.berkeley.fleet +// skeleton solution to problem #1 (fill in the XXX blanks) + +#memory { 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, + 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, + 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, + 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, + 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 + } + +#ship memread : MemReadShip +#ship memwrite : MemWriteShip +#ship bitbucket : BitBucketShip +#ship halt : HaltShip +#ship fetch : FetchShip + +top: { 100 -> memread.count + 0 -(100)-> memread.token + // XXX -> memread.addr + // XXX -> memread.stride + + memread.data -(*)-> memwrite.data + + // XXX -> memwrite.count + // XXX -> memwrite.addr + // XXX -> memwrite.stride + memwrite.token -(99)-> bitbucket.in + memwrite.token -> halt.in +} + +top -> fetch.in -// these SHIPs do not correspond to those in IES31; -// that will be corrected shortly: - -#ship adder : AdderShip -#ship adder2 : AdderShip -#ship memread : MemReadShip -#ship memwrite : MemWriteShip -#ship halt : HaltShip -#ship less : LessThanShip -#ship ifthen : IfThenElseShip -#ship i : RegisterShip -#ship fetch : FetchShip -#ship gate : GateShip -#ship gate2 : GateShip - - -// define the initial contents of memory -#memory { 000, 100, 200, 300, 400, 500 } - -// preload the counter register -4 -> i.write -i.writedone -> gate.release -gate.codebag <- top - -top: { i.read -> less.in1 - 0 -> less.in2 - less.out -> ifthen.if - ifthen.then <- { 0 -> halt.in } - ifthen.else <- continue - } - -continue: { - i.read -> memread.addr - i.read -> memwrite.addr - memread.data -> adder.in1 - 1000 -> adder.in2 - adder.out -> memwrite.data - memwrite.done -> gate.release - gate.codebag <- { - i.read -> adder2.in1 - -1 -> adder2.in2 - adder2.out -> i.write - i.writedone -> gate2.release - gate2.codebag <- top - } - } -- 1.7.10.4