From eb4eadf399ffc23b486db93eec2b225840ad0f27 Mon Sep 17 00:00:00 2001 From: megacz Date: Mon, 6 Apr 2009 11:37:01 -0700 Subject: [PATCH] major refactoring of edu.berkeley.fleet.loops, includes renaming Context to CodeBag --- src/edu/berkeley/fleet/loops/CleanupUtils.java | 17 +- src/edu/berkeley/fleet/loops/CodeBag.java | 183 +++++++++++---- src/edu/berkeley/fleet/loops/Context.java | 86 ------- src/edu/berkeley/fleet/loops/LoopFactory.java | 168 +++++++++----- src/edu/berkeley/fleet/loops/MemoryUtils.java | 291 +++++++++++++++++++----- src/edu/berkeley/fleet/loops/Program.java | 155 +++++++++---- src/edu/berkeley/fleet/loops/ShipPool.java | 7 + 7 files changed, 619 insertions(+), 288 deletions(-) delete mode 100644 src/edu/berkeley/fleet/loops/Context.java diff --git a/src/edu/berkeley/fleet/loops/CleanupUtils.java b/src/edu/berkeley/fleet/loops/CleanupUtils.java index dddac8a..770ae38 100644 --- a/src/edu/berkeley/fleet/loops/CleanupUtils.java +++ b/src/edu/berkeley/fleet/loops/CleanupUtils.java @@ -15,15 +15,18 @@ import static edu.berkeley.fleet.api.Predicate.*; public class CleanupUtils { + /** + * Verifies that the switch fabric and all instruction rings are empty. + */ public static void verifyClean(FleetProcess fp) { Ship debug = fp.getFleet().getShip("Debug", 0); Dock debugIn = debug.getDock("in"); - Context ctx; + CodeBag ctx; LoopFactory lf; - ctx = new Context(fp.getFleet()); - lf = new LoopFactory(ctx, debugIn, 1); + ctx = new CodeBag(fp.getFleet()); + lf = ctx.loopFactory(debugIn, 1); lf.literal(12); lf.deliver(); lf.literal(5); @@ -42,11 +45,11 @@ public class CleanupUtils { System.out.print("checking " + dock + " "); k = (k + 23) % 65535; - ctx = new Context(fp.getFleet()); + ctx = new CodeBag(fp.getFleet()); boolean reverse = (k%2)==0; - lf = new LoopFactory(ctx, debugIn, 4); + lf = ctx.loopFactory(debugIn, 4); lf.recvToken(); lf.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO); lf.setPredicate(Predicate.NotFlagA); @@ -56,12 +59,12 @@ public class CleanupUtils { lf.setPredicate(null); lf.deliver(); - lf = new LoopFactory(ctx, dock, 1); + lf = ctx.loopFactory(dock, 1); lf.sendToken(debugIn.getDataDestination(), new BitVector(1).set(reverse ? 1 : 0)); lf.sendToken(debugIn.getDataDestination(), new BitVector(1).set(reverse ? 0 : 1)); lf.sendToken(dock.getDataDestination(), new BitVector(1).set(reverse ? 1 : 0)); lf.sendToken(dock.getDataDestination(), new BitVector(1).set(reverse ? 0 : 1)); - lf = lf.makeNext(2); + lf = lf.makeNext(2, true); // if a torpedo was lying in wait, the problem will be manifest as a "freezup" lf.abortLoopIfTorpedoPresent(); diff --git a/src/edu/berkeley/fleet/loops/CodeBag.java b/src/edu/berkeley/fleet/loops/CodeBag.java index 6478802..d8b078f 100644 --- a/src/edu/berkeley/fleet/loops/CodeBag.java +++ b/src/edu/berkeley/fleet/loops/CodeBag.java @@ -1,53 +1,152 @@ package edu.berkeley.fleet.loops; -import edu.berkeley.fleet.api.*; import java.util.*; import java.net.*; +import edu.berkeley.fleet.two.*; +import edu.berkeley.fleet.api.*; +import edu.berkeley.fleet.api.Instruction.*; +import edu.berkeley.fleet.api.Instruction.Set; +import edu.berkeley.fleet.api.Instruction.Set.*; +import static edu.berkeley.fleet.util.BitManipulations.*; + + +// QUESTION: does each dock mentioned by a context have a linear chain +// of loops, or can it branch? + +// - or should we use "sub-contexts" for that +// - advantage: it lets us convey the fact that a bunch of loops are dispatched together +// - should loops have an "invoke context" opcode? /** - * A CodeBag represents the instructions of a Context along with - * (compile-time) knowledge of where it resides. Consequently, it is - * meaningful to say "give me the sequence of instructions which will - * invoke this CodeBag". + * A CodeBag is a collection of Loops which obey these rules: + * + * - A CodeBag has exclusive control of all docks mentioned by any of its Loops. + * - A CodeBag includes a "starting loop" for every dock it mentions. + * - When a CodeBag is spawned, it starts the "starting loop" on all of its docks. + * - A loop may or may not have a successor. + * - Control may transfer only two ways: + * - If a loop has a successor, control will transfer to the successor when the loop finishes. + * - A loop may explicitly transfer control to another loop via abortAndInvoke(). The + * invoked loop must belong to the same Dock and the same CodeBag. + * - A CodeBag finishes when all of its docks have finished executing a loop with no successor. + * + * Definitions: + * - A Move instruction is a blocking instruction if either its tokenIn or dataIn bits are set. + * - All other instructions are non-blocking. + * - A dock is quiescent if its instruction ring is empty. + * - A dock is pre-quiescent if + * - all instructions which remain in the target dock's instruction + * fifo are nonblocking instructions, + * - either the docks' OLC=0 or all instructions which remain + * in its instruction fifo are one-shot instructions + * - after executing these remaining instructions, the dock's hatch is open + */ + +/* + * SF works works @diff ok for non size ships + * Dispatch Method Crossings @inbox? docks? tail call? limit consumed + * ------------------------------------------------------------------------------------------ + * + * Inline 0 Y N N Small None + * + * Inline literals 1 N Y Y Tiny None + * w/ "dispatch" + * + * Send CBD to 2+ N Y Y None None (mem ship) + * memory ship + * + * Send token to 3+ Y Y Y None One Output Dock + * assistant outbox first + * + * Release from FIFO 2 Y Y Y Med 1x FIFO, but can be shared + * */ + public class CodeBag { - /* - * SF works works @diff ok for non size ships - * Dispatch Method Crossings @inbox? docks? tail call? limit consumed - * ------------------------------------------------------------------------------------------ - * - * Inline 0 Y N N Small None - * - * Inline literals 1 N Y Y Tiny None - * w/ "dispatch" - * - * Send CBD to 2+ N Y Y None None (mem ship) - * memory ship - * - * Send token to 3+ Y Y Y None One Output Dock - * assistant outbox first - * - * Release from FIFO 2 Y Y Y Med 1x FIFO, but can be shared - * - */ - - final Program program; - final Instruction[] instructions; - final long baseAddress; - - /** - * Given a Context, creates a CodeBag which will live in the - * Memory ship memoryShip at the address given by baseAddress. - */ - CodeBag(Program program, Instruction[] instructions, long baseAddress) { - int MAX_BAG_SIZE = (1<<7)-1; - if (instructions.length > MAX_BAG_SIZE) - throw new RuntimeException("warning: code bag size is "+instructions.length+ - ", which exceeds maximum of "+MAX_BAG_SIZE+ - "; breaking into multiple bags"); - this.program = program; - this.instructions = instructions; - this.baseAddress = baseAddress; + public final Fleet fleet; + + private Program program = null; + private BitVector descriptor = null; + public DeferredBitVector getDescriptor() { + return new DeferredBitVector() { + public BitVector getBitVector() { + if (program==null) throw new RuntimeException(); + seal(); + return descriptor; + } }; + } + + LinkedHashMap startupLoopFactories = new LinkedHashMap(); + ArrayList loopFactories = new ArrayList(); + + // FIXME: currently not used + private boolean sealed = false; + public boolean isSealed() { return sealed; } + public void seal() { + if (sealed) return; + for(LoopFactory lf : loopFactories) lf.flush_pending(); + sealed = true; + if (program!=null) descriptor = program.addInstructions(emit()); + } + + public CodeBag(Fleet fleet) { this(fleet, null); } + public CodeBag(Program prog) { this(prog.fleet, prog); } + public CodeBag(Fleet fleet, Program prog) { + this.fleet = fleet; + this.program = prog; + } + + public LoopFactory loopFactory(Dock dock, int count) { return loopFactory(dock, count, count==0); } + public LoopFactory loopFactory(Dock dock, int count, boolean torpedoable) { + LoopFactory ret = startupLoopFactories.get(dock); + if (ret == null) return new LoopFactory(this, dock, count, torpedoable); + while (ret.getNext()!=null) + ret = ret.getNext(); + return ret.makeNext(count, torpedoable); + } + + boolean autoflush = false; + public void setAutoflush(boolean a) { this.autoflush = a; } + public boolean getAutoflush() { return autoflush; } + + public void emit(ArrayList ic) { + seal(); + for(LoopFactory lf : startupLoopFactories.values()) + lf.emit(ic); + } + + private LoopFactory hack = null; + public void sendTorpedo(Dock dock) { + if (hack==null) hack = loopFactory(fleet.getShip("Timer",0).getDock("out"), 1); + hack.sendToken(dock.getInstructionDestination()); + } + public void sendWord(DeferredBitVector bv, Destination dest) { + // problem: this isn't actually atomic -- two uncoordinated + // actors might invoke these commands at the same time + if (hack==null) hack = loopFactory(fleet.getShip("Timer",0).getDock("out"), 1); + hack.literal(bv); + hack.sendWord(dest); + } + + public Instruction[] emit() { + ArrayList ic = new ArrayList(); + emit(ic); + return (Instruction[])ic.toArray(new Instruction[0]); + } + + public void dispatch(FleetProcess fp) { dispatch(fp, false); } + public void dispatch(FleetProcess fp, boolean flushWhenDone) { + ArrayList ai; + emit(ai = new ArrayList()); + for(Instruction ins : ai) + fp.sendInstruction(ins); + if (flushWhenDone) fp.flush(); + } + + public void append(CodeBag ctx) { + if (sealed) throw new RuntimeException("already sealed"); + // how to handle ship pools? + throw new RuntimeException("not implemented"); } } diff --git a/src/edu/berkeley/fleet/loops/Context.java b/src/edu/berkeley/fleet/loops/Context.java deleted file mode 100644 index 0f0f0d0..0000000 --- a/src/edu/berkeley/fleet/loops/Context.java +++ /dev/null @@ -1,86 +0,0 @@ -package edu.berkeley.fleet.loops; -import java.util.*; -import java.net.*; -import edu.berkeley.fleet.two.*; -import edu.berkeley.fleet.api.*; -import edu.berkeley.fleet.api.Instruction.*; -import edu.berkeley.fleet.api.Instruction.Set; -import edu.berkeley.fleet.api.Instruction.Set.*; -import static edu.berkeley.fleet.util.BitManipulations.*; - -// QUESTION: does each dock mentioned by a context have a linear chain -// of loops, or can it branch? - -// - or should we use "sub-contexts" for that -// - advantage: it lets us convey the fact that a bunch of loops are dispatched together -// - should loops have an "invoke context" opcode? - -/** - * A Context is a collection of Loops which obey these rules: - * - * - A Context has exclusive control of all docks mentioned by any of its Loops. - * - A Context includes a "starting loop" for every dock it mentions. - * - When a Context is spawned, it starts the "starting loop" on all of its docks. - * - A loop may or may not have a successor. - * - Control may transfer only two ways: - * - If a loop has a successor, control will transfer to the successor when the loop finishes. - * - A loop may explicitly transfer control to another loop via abortAndInvoke(). The - * invoked loop must belong to the same Dock and the same Context. - * - A Context finishes when all of its docks have finished executing a loop with no successor. - * - * Definitions: - * - A Move instruction is a blocking instruction if either its tokenIn or dataIn bits are set. - * - All other instructions are non-blocking. - * - A dock is quiescent if its instruction ring is empty. - * - A dock is pre-quiescent if - * - all instructions which remain in the target dock's instruction - * fifo are nonblocking instructions, - * - either the docks' OLC=0 or all instructions which remain - * in its instruction fifo are one-shot instructions - * - after executing these remaining instructions, the dock's hatch is open - */ -public class Context { - - public final Fleet fleet; - - HashMap startupLoopFactories = new HashMap(); - HashSet loopFactories = new HashSet(); - - private final ShipPool pool; - - // FIXME: currently not used - private boolean sealed = false; - public boolean isSealed() { return sealed; } - - public Context(Fleet fleet) { this(fleet, new ShipPool(fleet)); } - public Context(Fleet fleet, ShipPool pool) { - this.fleet = fleet; - this.pool = pool; - } - public Ship allocateShip(String type) { return pool.allocateShip(type); } - - boolean autoflush = false; - public void setAutoflush(boolean a) { this.autoflush = a; } - - public void emit(ArrayList ic) { - sealed = true; - for(LoopFactory lf : startupLoopFactories.values()) - lf.emit(ic); - } - - public Instruction[] emit() { - ArrayList ic = new ArrayList(); - emit(ic); - return (Instruction[])ic.toArray(new Instruction[0]); - } - - public void dispatch(FleetProcess fp) { dispatch(fp, false); } - public void dispatch(FleetProcess fp, boolean flushWhenDone) { - ArrayList ai; - emit(ai = new ArrayList()); - for(Instruction ins : ai) - fp.sendInstruction(ins); - if (flushWhenDone) fp.flush(); - } - -} diff --git a/src/edu/berkeley/fleet/loops/LoopFactory.java b/src/edu/berkeley/fleet/loops/LoopFactory.java index 76ffb83..5bdfc2a 100644 --- a/src/edu/berkeley/fleet/loops/LoopFactory.java +++ b/src/edu/berkeley/fleet/loops/LoopFactory.java @@ -38,7 +38,7 @@ public class LoopFactory { public final int count; public final boolean torpedoable; - private final Context ctx; + private final CodeBag ctx; private LoopFactory next = null; private ArrayList instructions = new ArrayList(); @@ -49,19 +49,19 @@ public class LoopFactory { * @arg prev a loop for which this is the successor loop (if any) * @arg count the number of times to execute this loop; 0 means continue until torpedoed */ - public LoopFactory(Context ctx, Dock dock, int count) { + LoopFactory(CodeBag ctx, Dock dock, int count) { this(ctx, dock, count, count==0, dock.toString(), null); } - public LoopFactory(Context ctx, Dock dock, int count, boolean torpedoable) { + LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable) { this(ctx, dock, count, torpedoable, dock.toString(), null); } - public LoopFactory(Context ctx, Dock dock, int count, String friendlyName) { + LoopFactory(CodeBag ctx, Dock dock, int count, String friendlyName) { this(ctx, dock, count, count==0, friendlyName); } - public LoopFactory(Context ctx, Dock dock, int count, boolean torpedoable, String friendlyName) { + LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable, String friendlyName) { this(ctx, dock, count, torpedoable, friendlyName, null); } - private LoopFactory(Context ctx, Dock dock, int count, boolean torpedoable, String friendlyName, LoopFactory prev) { + private LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable, String friendlyName, LoopFactory prev) { this.ctx = ctx; this.dock = dock; this.count = count; @@ -88,6 +88,7 @@ public class LoopFactory { public LoopFactory getNext() { return next; } private void setNext(LoopFactory next) { if (this.next != null) throw new RuntimeException("attempt to setNext() twice"); + if (ctx.isSealed()) throw new RuntimeException("context already sealed"); this.next = next; } @@ -103,16 +104,23 @@ public class LoopFactory { boolean pending_sendToken = false; Path pending_path = null; + private void addInstruction(Instruction inst) { + if (ctx.isSealed()) throw new RuntimeException("context already sealed"); + instructions.add(inst); + } + void flush_pending() { flush_pending(false); } void flush_pending(boolean pending_dataOut) { if (!pending_recvToken && !pending_recvOrCollect && !pending_sendToken && !pending_dataOut) { + /* if (pending_interruptible) - throw new RuntimeException("abortLoopIfTorpedoPresent() must be followed immediately by a Move"); + throw new RuntimeException("abortLoopIfTorpedoPresent() must be followed immediately by a Move (in LoopFactory for dock " + dock + ")"); + */ } else { - instructions.add(new Move(dock, + addInstruction(new Move(dock, predicate, pending_interruptible, pending_path==null ? null : pending_path, @@ -134,7 +142,7 @@ public class LoopFactory { public void interruptibleNop() { flush_pending(); - instructions.add(new Move(dock, + addInstruction(new Move(dock, predicate, true, null, @@ -193,6 +201,10 @@ public class LoopFactory { pending_path = dock.getPath(dest, signal); pending_sendToken = true; } + public void sendToken(Dock dock) { sendToken(dock.getDataDestination()); } + public void sendToken(Dock dock, BitVector signal) { sendToken(dock.getDataDestination(), signal); } + + public void sendTorpedo(Dock dock) { sendToken(dock.getInstructionDestination()); } /** [inboxes only], will fuse with previous instruction if it was a sendToken() */ public void deliver() { @@ -204,7 +216,7 @@ public class LoopFactory { public void flush() { if (!dock.isInputDock()) throw new RuntimeException("flush() may only be used at input docks"); flush_pending(); - instructions.add(new Instruction.Flush(dock, predicate)); + addInstruction(new Instruction.Flush(dock, predicate)); } /** [outboxes only], will fuse with previous instruction if it was a sendToken() */ @@ -215,50 +227,65 @@ public class LoopFactory { pending_path = dock.getPath(dest, signal); flush_pending(true); } + public void sendWord(Dock dock) { sendWord(dock.getDataDestination()); } + public void sendWord(Dock dock, BitVector signal) { sendWord(dock.getDataDestination(), signal); } + public void sendPacket() { sendWord((Destination)null); } public void literal(String constantName) { literal(dock.getConstant(constantName)); } /** sets the data latch to a literal value */ - public void literal(BitVector literal) { - // FIXME: code duplication here - // FEATURE: be more intelligent here to avoid shifts if possible? + public void literal(final DeferredBitVector literal) { + flush_pending(); + if (literal instanceof BitVector) { + BitVector bv = (BitVector)literal; + boolean can_use_set = true; + for(int i=ctx.fleet.getSetWidth(); i 0) { - BitVector temp = new BitVector(dock.getShip().getFleet().getShiftWidth()); - for(int i=counter-1; i>=counter-ctx.fleet.getShiftWidth(); i--) - if (i=counter_f-ctx.fleet.getShiftWidth(); i--) + if (i 0) { - instructions.add(new Shift(dock, predicate, - new BitVector(dock.getShip().getFleet().getWordWidth()) - .set(getField(counter-1, counter-ctx.fleet.getShiftWidth(), literal)))); - counter -= ctx.fleet.getShiftWidth(); - } - } + literal(new BitVector(ctx.fleet.getWordWidth()).set(literal)); + } + + /** sets the data latch to a code bag descriptor */ + public void literal(CodeBag cb) { + literal(cb.getDescriptor()); } /** sets the flags */ public void setFlags(Instruction.Set.FlagFunction newFlagA, Instruction.Set.FlagFunction newFlagB) { flush_pending(); - instructions.add(new Instruction.Set(dock, + addInstruction(new Instruction.Set(dock, predicate, newFlagA, newFlagB)); @@ -267,23 +294,18 @@ public class LoopFactory { /** abort the loop immediately (if predicate is met) and invoke the successor loop */ public void abort() { flush_pending(); - instructions.add(new Instruction.Set(dock, + addInstruction(new Instruction.Set(dock, predicate, SetDest.OuterLoopCounter, 0)); } - public void abortAndInvoke(LoopFactory lf) { - throw new RuntimeException("not implemented"); - } - // Emitting Code ////////////////////////////////////////////////////////////////////////////// void optimize() { flush_pending(); - // FEATURE: find loops of 1 instruction, use ILC // FEATURE: find sequences of >2 adjacent identical instructions, replace with use of ILC - // FEATURE: after optimizing, find single-instruction loops, replace with use of ILC + // (requires Instruction.equals() be implemented) // FEATURE: consider doing loop unrolling if two copies of the loop fit in the instruction buffer... // FEATURE: clever instruction re-oredering? } @@ -309,20 +331,46 @@ public class LoopFactory { // Set the OLC (it might previously have been zero) ic.add(new Set(dock, Predicate.IgnoreFlagD, SetDest.OuterLoopCounter, count==0 ? 1 : count)); - if (count!=1) { + + boolean olc_loop = count!=1; + /* + if (count != 1 && + (count==0 || count <= 63) && + instructions.size()==1 && + (instructions.get(0) instanceof Instruction.Move)) { + olc_loop = false; + if (count==0) + ic.add(new Instruction.Set(dock, Predicate.Default, + SetDest.InnerLoopCounter, SetSource.Infinity)); + else + ic.add(new Instruction.Set(dock, Predicate.Default, + SetDest.InnerLoopCounter, count)); + } + */ + + if (olc_loop) { ic.add(new Instruction.Head(dock)); } - for(Instruction i : instructions) { - if (i instanceof Move && (((Move)i).tokenIn || ((Move)i).dataIn)) - blockingInstructionEncountered = true; - if (blockingInstructionEncountered) - numInstructionsNotIncludingNonblockingPrefix++; - loopSize++; - ic.add(i); + boolean firstTime = true; + while(true) { + for(Instruction i : instructions) { + if (!firstTime && i.predicate==Predicate.FlagD) continue; + if (i instanceof Move && (((Move)i).tokenIn || ((Move)i).dataIn)) + blockingInstructionEncountered = true; + if (blockingInstructionEncountered) + numInstructionsNotIncludingNonblockingPrefix++; + loopSize++; + ic.add(i); + } + if (count!=0) break; + if (instructions.size()+loopSize+3 > capacity) break; + firstTime = false; + break; + //System.out.println("packing the loop!"); } - if (count==1) { + if (!olc_loop) { if (numInstructionsNotIncludingNonblockingPrefix > capacity) throw new RuntimeException("instruction sequence is too long for instruction fifo at " + dock); } else { @@ -333,24 +381,32 @@ public class LoopFactory { loopSize++; } } - if (count!=1) + if (olc_loop) { ic.add(new Instruction.Abort(dock, Predicate.FlagD)); - if (ctx.autoflush && next==null && dock.isInputDock()) + loopSize++; + } + if (ctx.autoflush && next==null && dock.isInputDock()) { ic.add(new Instruction.Flush(dock, Predicate.FlagD)); + loopSize++; + } // FIXME: need to somehow deal with count!=0 loops that are // torpedoable; they need to wait for a torpedo to arrive // after exhausting their count. - if (count!=1) { + if (olc_loop) { ic.add(new Instruction.Tail(dock)); if (loopSize > capacity) - throw new RuntimeException("instruction loop is too long for instruction fifo"); + throw new RuntimeException("instruction loop is too long for instruction fifo at " + dock); } if (next != null) { - if (count != 1) throw new RuntimeException("no support for successor loops when count!=1 yet"); - next.emit(ic, capacity - loopSize); + if (!olc_loop) { + next.emit(ic, capacity - numInstructionsNotIncludingNonblockingPrefix); + } else { + //next.emit(ic, capacity - loopSize); + throw new RuntimeException("no support for successor loops when count!=1 yet"); + } } } diff --git a/src/edu/berkeley/fleet/loops/MemoryUtils.java b/src/edu/berkeley/fleet/loops/MemoryUtils.java index f8c5163..7a92a32 100644 --- a/src/edu/berkeley/fleet/loops/MemoryUtils.java +++ b/src/edu/berkeley/fleet/loops/MemoryUtils.java @@ -15,16 +15,122 @@ import static edu.berkeley.fleet.api.Predicate.*; public class MemoryUtils { - public static void readMem(FleetProcess fp, Ship memory, long offset, BitVector[] vals) throws RuntimeException { - doMem(true, fp, memory, offset, vals); + public static void readMem(FleetProcess fp, + ShipPool pool, + Ship memory, + long offset, + BitVector[] vals) throws RuntimeException { + doMem(true, fp, pool, memory, offset, vals); } - public static void writeMem(FleetProcess fp, Ship memory, long offset, long[] vals) throws RuntimeException { - doMem(false, fp, memory, offset, long2bv(fp.getFleet(), vals)); + + public static void writeMem(FleetProcess fp, + ShipPool pool, + Ship memory, + long offset, + long[] vals) throws RuntimeException { + doMem(false, fp, pool, memory, offset, long2bv(fp.getFleet(), vals)); + } + + public static void writeMem(FleetProcess fp, + ShipPool pool, + Ship memory, + long offset, + BitVector[] vals) throws RuntimeException { + doMem(false, fp, pool, memory, offset, vals); } - public static void writeMem(FleetProcess fp, Ship memory, long offset, BitVector[] vals) throws RuntimeException { - doMem(false, fp, memory, offset, vals); + + /* + public static void clearMem(FleetProcess fp, + Ship memory, + ShipPool pool, + long offset, + long count) throws RuntimeException { + if (fp.getFleet() != memory.getFleet()) + throw new RuntimeException("Fleet mismatch"); + + Ship counter1 = pool.allocateShip("Counter"); + Ship counter2 = pool.allocateShip("Counter"); + //Ship alu = pool.allocateShip("Alu"); + + final Dock debugIn = fp.getDebugInputDock(); + + CodeBag ctx = new CodeBag(fp.getFleet()); + LoopFactory lf; + + lf = ctx.loopFactory(counter1.getDock("inOp"), 1); + lf.literal(counter1.getDock("inOp").getConstant("COUNT")); + lf.deliver(); + + lf = ctx.loopFactory(counter1.getDock("in1"), 1); + lf.literal(count); + lf.deliver(); + + lf = ctx.loopFactory(counter1.getDock("in2"), 1); + lf.literal(1); + lf.deliver(); + + lf = ctx.loopFactory(counter1.getDock("out"), 0); + lf.abortLoopIfTorpedoPresent(); + lf.recvToken(); + lf.collect(); + lf.send(memory.getDock("inAddrWrite").getDataDestination()); + + lf = ctx.loopFactory(memory.getDock("inDataWrite"), 0); + lf.literal(0); + lf.abortLoopIfTorpedoPresent(); + lf.deliver(); + + lf = ctx.loopFactory(memory.getDock("inAddrWrite"), 1); + lf.sendToken(counter1.getDock("out").getDataDestination()); + lf = lf.makeNext(0); + lf.abortLoopIfTorpedoPresent(); + lf.recvWord(); + lf.deliver(); + lf.sendToken(counter1.getDock("out").getDataDestination()); + + lf = ctx.loopFactory(memory.getDock("out"), 0); + lf.recvToken(); + lf.recvWord(); + lf.send(counter2.getDock("in2").getDataDestination()); + + lf = ctx.loopFactory(counter2.getDock("inOp"), 1); + lf.literal(counter2.getDock("inOp").getConstant("DROP_C1_V2")); + lf.deliver(); + lf.literal(counter2.getDock("inOp").getConstant("PASS_C1_V2")); + lf.deliver(); + + lf = ctx.loopFactory(counter2.getDock("in2"), 0); + lf.recvWord(); + lf.deliver(); + + fp.sendToken(counter1.getDock("out").getInstructionDestination()); + fp.sendToken(memory.getDock("inDataWrite").getInstructionDestination()); + fp.sendToken(memory.getDock("inAddrWrite").getInstructionDestination()); + fp.sendToken(memory.getDock("out").getInstructionDestination()); + fp.sendToken(counter2.getDock("in2").getInstructionDestination()); + + lf = ctx.loopFactory(counter2.getDock("in1"), 1); + lf.literal(count-1); + lf.deliver(); + lf.literal(1); + lf.deliver(); + + lf = ctx.loopFactory(counter2.getDock("out"), 1); + lf.collect(); + lf.send(debugIn.getDataDestination()); + + pool.releaseShip(counter1); + pool.releaseShip(counter2); + //pool.releaseShip(alu); } - public static void doMem(final boolean read, final FleetProcess fp, final Ship memory, final long offset, final BitVector[] vals) throws RuntimeException { + */ + + public static void doMem(final boolean read, + final FleetProcess fp, + final ShipPool pool, + final Ship memory, + final long offset, + final BitVector[] vals) throws RuntimeException { if (fp.getFleet() != memory.getFleet()) throw new RuntimeException("Fleet mismatch"); @@ -32,79 +138,127 @@ public class MemoryUtils { final Dock inDataWrite = memory.getDock("inDataWrite"); final Dock inAddrRead = memory.getDock("inAddrRead"); final Dock out = memory.getDock("out"); - final Dock debugIn = fp.getDebugInputDock(); + final Dock debugIn = read ? fp.getDebugInputDock() : null; + if (debugIn!=null) pool.allocateShip(debugIn.getShip()); + + Ship counter = pool.allocateShip("Counter"); + Dock counter_in1 = counter.getDock("in1"); + Dock counter_in2 = counter.getDock("in2"); + Dock counter_inOp = counter.getDock("inOp"); + Dock counter_out = counter.getDock("out"); - final Semaphore sem = new Semaphore(12 /* FIXME */); + Ship alu = pool.allocateShip("Alu"); - Context ctx = new Context(fp.getFleet()); + CodeBag ctx = new CodeBag(fp.getFleet()); LoopFactory lf; if (read) { - lf = new LoopFactory(ctx, inAddrRead, 0); + lf = ctx.loopFactory(inAddrRead, 0); lf.abortLoopIfTorpedoPresent(); + lf.sendToken(counter_out); lf.recvWord(); lf.deliver(); } else { - lf = new LoopFactory(ctx, inAddrWrite, 0); + lf = ctx.loopFactory(inAddrWrite, 0); + lf.sendToken(counter_out); lf.abortLoopIfTorpedoPresent(); lf.recvWord(); lf.deliver(); - lf = new LoopFactory(ctx, inDataWrite, 0); + lf = ctx.loopFactory(inDataWrite, 0); lf.abortLoopIfTorpedoPresent(); lf.recvWord(); lf.deliver(); } - lf = new LoopFactory(ctx, out, 0); + lf = ctx.loopFactory(counter_in1, 1); + lf.literal(vals.length); + lf.deliver(); + + lf = ctx.loopFactory(counter_in2, 1); + lf.literal(1); + lf.deliver(); + + lf = ctx.loopFactory(counter_inOp, 1); + lf.literal("COUNT"); + lf.deliver(); + + lf = ctx.loopFactory(counter_out, 0); + lf.recvToken(); lf.abortLoopIfTorpedoPresent(); lf.collectWord(); - lf.sendWord(debugIn.getDataDestination()); + lf.sendWord(alu.getDock("in1")); + lf.sendToken(alu.getDock("in2")); + lf.sendToken(alu.getDock("inOp")); - lf = new LoopFactory(ctx, debugIn, 0); + lf = ctx.loopFactory(alu.getDock("in1"), 0); lf.abortLoopIfTorpedoPresent(); lf.recvWord(); lf.deliver(); - ArrayList ai = new ArrayList(); - ctx.emit(ai); - for(Instruction ins : ai) - fp.sendInstruction(ins); - - new Thread() { - public void run() { try { - for(int i=0; i=0; i--) { + if (!read) + fp.sendWord(inDataWrite.getDataDestination(), vals[i]); + if (read) { + BitVector outv = fp.recvWord(); + vals[i] = outv; + } + int pct = (int)Math.ceil(100.0*((double)(vals.length-1-i)/((double)(vals.length-1)))); + String status = i + "/" + (vals.length-1) + "= " + pct + "%"; + if (read) System.out.print("\rread from address: " + status + ", got " + vals[i] + " = " + vals[i].toLong()+" "); + else System.out.print("\rwrote to address: " + status +" "); } + fp.flush(); if (read) { fp.sendToken(inAddrRead.getInstructionDestination()); + fp.sendToken(debugIn.getInstructionDestination()); } else { fp.sendToken(inAddrWrite.getInstructionDestination()); fp.sendToken(inDataWrite.getInstructionDestination()); } + fp.sendToken(alu.getDock("in1").getInstructionDestination()); + fp.sendToken(alu.getDock("in2").getInstructionDestination()); + fp.sendToken(alu.getDock("inOp").getInstructionDestination()); + fp.sendToken(alu.getDock("out").getInstructionDestination()); + fp.sendToken(counter_out.getInstructionDestination()); fp.sendToken(out.getInstructionDestination()); - fp.sendToken(debugIn.getInstructionDestination()); System.out.println(); + + pool.releaseShip(alu); + pool.releaseShip(counter); + if (read) pool.releaseShip(debugIn.getShip()); } private static BitVector[] long2bv(Fleet fleet, long[] initialValues) { @@ -115,15 +269,15 @@ public class MemoryUtils { } public static void putMemoryShipInDispatchMode(FleetProcess fp, Ship memoryShip) { - Context ctx = new Context(fp.getFleet()); + CodeBag ctx = new CodeBag(fp.getFleet()); LoopFactory lf; - lf = new LoopFactory(ctx, memoryShip.getDock("out"), 0); + lf = ctx.loopFactory(memoryShip.getDock("out"), 0); lf.abortLoopIfTorpedoPresent(); lf.collectPacket(); - lf.sendWord(null); + lf.sendPacket(); - lf = new LoopFactory(ctx, memoryShip.getDock("inCBD"), 0); + lf = ctx.loopFactory(memoryShip.getDock("inCBD"), 0); lf.abortLoopIfTorpedoPresent(); lf.recvWord(); lf.deliver(); @@ -140,17 +294,38 @@ public class MemoryUtils { Random random = new Random(System.currentTimeMillis()); Fleet fleet = new Fpga(); FleetProcess fp = fleet.run(new Instruction[0]); - Ship memory = fleet.getShip("DDR2",0); + //Ship memory = fleet.getShip("DDR2",0); + Ship memory = fleet.getShip("Dvi",0); //Ship memory = fleet.getShip("Memory",0); - BitVector[] vals = new BitVector[2 * 1024]; - BitVector[] vals2 = new BitVector[2 * 1024]; - for(int i=0; i codeBags = new HashSet(); + private ArrayList codeBags = new ArrayList(); + private ArrayList all_instructions = new ArrayList(); public Program(Ship memoryShip) { this(memoryShip, 0); } public Program(Ship memoryShip, long startAddress) { @@ -23,51 +28,123 @@ public class Program { this.leastUnallocatedAddress = startAddress; } - public void run(FleetProcess fp, CodeBag run) { - System.out.println("invoking..."); - Context ctx = new Context(fleet); + public Destination getCBDDestination() { + return memoryShip.getDock("inCBD").getDataDestination(); + } + + public long run(FleetProcess fp, CodeBag run, ShipPool pool) { + Ship timer = pool.allocateShip("Timer"); + Ship debug = pool.allocateShip("Debug"); + Dock debugIn = debug.getDock("in"); + LoopFactory lf; - fp.sendWord(memoryShip.getDock("inCBD").getDataDestination(), - new BitVector(fleet.getWordWidth()).set( (run.baseAddress<<6) | run.instructions.length )); - System.out.println("invoked."); + + CodeBag start = new CodeBag(fleet, this); + lf = start.loopFactory(timer.getDock("out"), 1); + lf.collectWord(); + lf.sendWord(debugIn.getDataDestination()); + lf = start.loopFactory(debugIn, 1); + lf.recvWord(); + lf.deliver(); + lf.recvWord(); + lf.deliver(); + start.sendWord(run.getDescriptor(), getCBDDestination()); + + CodeBag done = end; + lf = done.loopFactory(timer.getDock("out"), 1); + lf.collectWord(); + lf.sendWord(debugIn.getDataDestination()); + + start.seal(); + done.seal(); + + install(fp, pool); + + MemoryUtils.putMemoryShipInDispatchMode(fp, memoryShip); + fp.sendWord(getCBDDestination(), start.getDescriptor().getBitVector()); + fp.flush(); + long now = System.currentTimeMillis(); + System.out.println("waiting for timestamps to come back..."); + BitVector bv1 = fp.recvWord(); + System.out.println(); + System.out.println("got start time (bv="+bv1+" = "+bv1.toLong()+")"); + BitVector bv2 = fp.recvWord(); + System.out.println("got end time (bv="+bv2+" = "+bv2.toLong()+")"); + long ret = (bv2.toLong()-bv1.toLong()); + long simtime = (System.currentTimeMillis()-now)/1000; + System.out.println("total run time = " + ret + " gate delays, " + (ret/40) + "ns (simulation time="+simtime+"sec)"); + MemoryUtils.removeMemoryShipFromDispatchMode(fp, memoryShip); + + return ret; } - public void install(FleetProcess fp) { - BitVector[] bvs = new BitVector[(int)(leastUnallocatedAddress-startAddress)]; - int j = 0; - for(CodeBag cb : codeBags) - for(int i=0; i MAX_BAG_SIZE) { - System.out.println("warning: code bag size is "+instructions.length+ - ", which exceeds maximum of "+MAX_BAG_SIZE+ - "; breaking into multiple bags"); - ArrayList subBags = new ArrayList(); - for(int block=0; block FUZZ) throw new RuntimeException("FUZZ="+FUZZ+", fuzz.length="+fuzz.length); + Instruction[] self = new Instruction[fuzz.length+MAX_BAG_SIZE-FUZZ]; + System.arraycopy(instructions, 0, self, 0, MAX_BAG_SIZE-FUZZ); + System.arraycopy(fuzz, 0, self, MAX_BAG_SIZE-FUZZ, fuzz.length); + return addInstructions(self); } } \ No newline at end of file diff --git a/src/edu/berkeley/fleet/loops/ShipPool.java b/src/edu/berkeley/fleet/loops/ShipPool.java index e829c7c..23b9a04 100644 --- a/src/edu/berkeley/fleet/loops/ShipPool.java +++ b/src/edu/berkeley/fleet/loops/ShipPool.java @@ -16,6 +16,7 @@ public class ShipPool implements Iterable { private HashSet allocatedShips = new HashSet(); public ShipPool(Fleet fleet) { this(fleet, null); } + public ShipPool(ShipPool ancestor) { this(ancestor.fleet, ancestor); } public ShipPool(Fleet fleet, ShipPool ancestor) { this.fleet = fleet; this.ancestor = ancestor; @@ -54,4 +55,10 @@ public class ShipPool implements Iterable { if (ancestor != null) ancestor.releaseShip(ship); } + public void releaseAll() { + HashSet toRelease = new HashSet(); + toRelease.addAll(allocatedShips); + for (Ship ship : toRelease) + releaseShip(ship); + } } -- 1.7.10.4