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);
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);
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();
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<Dock,LoopFactory> startupLoopFactories = new LinkedHashMap<Dock,LoopFactory>();
+ ArrayList<LoopFactory> loopFactories = new ArrayList<LoopFactory>();
+
+ // 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<Instruction> 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<Instruction> ic = new ArrayList<Instruction>();
+ 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<Instruction> ai;
+ emit(ai = new ArrayList<Instruction>());
+ 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");
}
}
+++ /dev/null
-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<Dock,LoopFactory> startupLoopFactories = new HashMap<Dock,LoopFactory>();
- HashSet<LoopFactory> loopFactories = new HashSet<LoopFactory>();
-
- 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<Instruction> ic) {
- sealed = true;
- for(LoopFactory lf : startupLoopFactories.values())
- lf.emit(ic);
- }
-
- public Instruction[] emit() {
- ArrayList<Instruction> ic = new ArrayList<Instruction>();
- 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<Instruction> ai;
- emit(ai = new ArrayList<Instruction>());
- for(Instruction ins : ai)
- fp.sendInstruction(ins);
- if (flushWhenDone) fp.flush();
- }
-
-}
public final int count;
public final boolean torpedoable;
- private final Context ctx;
+ private final CodeBag ctx;
private LoopFactory next = null;
private ArrayList<Instruction> instructions = new ArrayList<Instruction>();
* @arg prev a loop for which this is the successor loop (if any)
* @arg count the number of times to execute this loop; <tt>0</tt> 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;
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;
}
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,
public void interruptibleNop() {
flush_pending();
- instructions.add(new Move(dock,
+ addInstruction(new Move(dock,
predicate,
true,
null,
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() {
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() */
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<bv.length(); i++)
+ if (bv.get(i)!=bv.get(ctx.fleet.getSetWidth()-1)) {
+ can_use_set = false;
+ break;
+ }
+ if (can_use_set) {
+ addInstruction(new Instruction.Set(dock, predicate, SetDest.DataLatch, bv.toLong()));
+ return;
+ }
+ }
+
int counter = 0;
while(counter < dock.getShip().getFleet().getWordWidth()) counter += ctx.fleet.getShiftWidth();
while(counter > 0) {
- BitVector temp = new BitVector(dock.getShip().getFleet().getShiftWidth());
- for(int i=counter-1; i>=counter-ctx.fleet.getShiftWidth(); i--)
- if (i<literal.length())
- temp.set(i-(counter-ctx.fleet.getShiftWidth()), literal.get(i));
- instructions.add(new Shift(dock, predicate, temp));
+ final int counter_f = counter;
+ DeferredBitVector temp = new DeferredBitVector() {
+ public BitVector getBitVector() {
+ BitVector bv = literal.getBitVector();
+ BitVector ret = new BitVector(dock.getShip().getFleet().getShiftWidth());
+ for(int i=counter_f-1; i>=counter_f-ctx.fleet.getShiftWidth(); i--)
+ if (i<bv.length())
+ ret.set(i-(counter_f-ctx.fleet.getShiftWidth()), bv.get(i));
+ return ret;
+ }
+ };
+ Shift shift = new Shift(dock, predicate, temp);
+ addInstruction(shift);
counter -= ctx.fleet.getShiftWidth();
}
}
/** sets the data latch to a literal value */
public void literal(long literal) {
- flush_pending();
- if (((FleetTwoFleet)ctx.fleet).isSmallEnoughToFit(literal)) {
- instructions.add(new Instruction.Set(dock, predicate, SetDest.DataLatch, literal));
- } else {
- int counter = 0;
- int extra = 0;
- while(counter < dock.getShip().getFleet().getWordWidth()) { extra++; counter += ctx.fleet.getShiftWidth(); }
- warn("literal " + literal + " requires " + extra + " instructions");
- while(counter > 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));
/** 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?
}
// 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 {
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");
+ }
}
}
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");
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<Instruction> ai = new ArrayList<Instruction>();
- ctx.emit(ai);
- for(Instruction ins : ai)
- fp.sendInstruction(ins);
-
- new Thread() {
- public void run() { try {
- for(int i=0; i<vals.length; i++) {
- if (!sem.tryAcquire()) {
- fp.flush();
- sem.acquire();
- }
- if (read) {
- fp.sendWord(inAddrRead.getDataDestination(), new BitVector(fp.getFleet().getWordWidth()).set(i+offset));
- } else {
- fp.sendWord(inAddrWrite.getDataDestination(), new BitVector(fp.getFleet().getWordWidth()).set(i+offset));
- fp.sendWord(inDataWrite.getDataDestination(), vals[i]);
- }
- }
- fp.flush();
- } catch (Exception e) { throw new RuntimeException(e); }
- }
- }.start();
+ lf = ctx.loopFactory(alu.getDock("in2"), 0);
+ lf.abortLoopIfTorpedoPresent();
+ lf.recvToken();
+ lf.literal(offset);
+ lf.deliver();
- for(int i=0; i<vals.length; i++) {
- BitVector outv = fp.recvWord();
- if (read) vals[i] = outv;
- if (read) System.out.print("\rread from address: " + i + ", got " + vals[i] + " = " + vals[i].toLong()+" ");
- else System.out.print("\rwrote to address: " + i+" ");
- sem.release();
+ lf = ctx.loopFactory(alu.getDock("inOp"), 0);
+ lf.abortLoopIfTorpedoPresent();
+ lf.recvToken();
+ lf.literal("ADD");
+ lf.deliver();
+
+ lf = ctx.loopFactory(alu.getDock("out"), 0);
+ lf.abortLoopIfTorpedoPresent();
+ lf.collectWord();
+ lf.sendWord(read ? inAddrRead : inAddrWrite);
+
+ lf = ctx.loopFactory(out, 0);
+ if (read) lf.recvToken();
+ lf.abortLoopIfTorpedoPresent();
+ lf.collectWord();
+ if (read) lf.sendWord(debugIn.getDataDestination());
+
+ if (read) {
+ lf = ctx.loopFactory(debugIn, 0);
+ lf.sendToken(out);
+ lf.abortLoopIfTorpedoPresent();
+ lf.recvWord();
+ lf.deliver();
+ }
+
+ ctx.dispatch(fp);
+
+ for(int i=vals.length-1; 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) {
}
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();
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<vals.length; i++)
+
+ //int size = (548 * 478) / 2;
+ int size = 2048;
+
+ BitVector[] vals = new BitVector[size];
+ BitVector[] vals2 = new BitVector[size];
+
+ for(int i=0; i<vals.length; i++) {
vals[i] = new BitVector(fleet.getWordWidth()).set(random.nextLong());
- writeMem(fp, memory, 0, vals);
- readMem(fp, memory, 0, vals2);
+ for(int j=36; j<vals[i].length(); j++)
+ vals[i].set(j, false);
+ vals[i].set(1, false);
+ }
+
+ BitVector bv = new BitVector(fleet.getWordWidth());
+ /*
+ for(int i=0; i<bv.length(); i++) bv.set(i, true);
+ for(int i=0; i<vals.length; i++)
+ vals[i] = bv;
+ */
+ ShipPool pool = new ShipPool(fleet);
+ writeMem(fp, pool, memory, 0, vals);
+ readMem(fp, pool, memory, 0, vals2);
+ int fails = 0;
for(int i=0; i<vals.length; i++)
- if (!vals[i].equals(vals2[i]))
+ if (!vals[i].equals(vals2[i])) {
System.out.println("disagreement! on index " + i + "\n "+vals[i]+"\n "+vals2[i]);
- System.out.println("done!");
+ fails++;
+ }
+ System.out.println("done! ("+fails+" failures)");
}
}
import edu.berkeley.fleet.api.*;
import java.util.*;
import java.net.*;
+import java.io.*;
/**
* A program is a collection of CodeBags resident in a particular Memory.
*/
public class Program {
- private Ship memoryShip;
- private Fleet fleet;
+ public final Fleet fleet;
+ public final Ship memoryShip;
+
+ private CodeBag end = null;
+
private long leastUnallocatedAddress;
private long startAddress;
- private HashSet<CodeBag> codeBags = new HashSet<CodeBag>();
+ private ArrayList<CodeBag> codeBags = new ArrayList<CodeBag>();
+ private ArrayList<Instruction> all_instructions = new ArrayList<Instruction>();
public Program(Ship memoryShip) { this(memoryShip, 0); }
public Program(Ship memoryShip, long startAddress) {
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<cb.instructions.length; i++)
- bvs[j++] = fleet.encodeInstruction(cb.instructions[i], memoryShip.getDock("out"));
- System.out.println("writing... ("+bvs.length+" words)");
- MemoryUtils.writeMem(fp, memoryShip, startAddress, bvs);
- System.out.println("written.");
+ public void dump(String file) {
+ try {
+ FileOutputStream fos = new FileOutputStream(file);
+ PrintWriter pw = new PrintWriter(new OutputStreamWriter(fos));
+ for(int i=0; i<codeBags.size(); i++)
+ for(Instruction in : codeBags.get(i).emit())
+ pw.println(in);
+ pw.flush();
+ pw.close();
+ } catch (Exception e) { throw new RuntimeException(e); }
}
- public CodeBag makeCodeBag(Context ctx) {
- return makeCodeBag(ctx.emit());
+ public CodeBag getEndProgramCodeBag() {
+ if (end != null) return end;
+ end = new CodeBag(fleet, this);
+ return end;
}
- public CodeBag makeCodeBag(Instruction[] instructions) {
- int MAX_BAG_SIZE = (1<<7)-1;
- if (instructions.length > 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<CodeBag> subBags = new ArrayList<CodeBag>();
- for(int block=0; block<instructions.length; block+=MAX_BAG_SIZE) {
- Instruction[] inst = new Instruction[Math.min(instructions.length-block, MAX_BAG_SIZE)];
- System.arraycopy(instructions, block, inst, 0, inst.length);
- subBags.add(makeCodeBag(inst));
- }
- throw new RuntimeException("FIXME: not done");
-
- } else {
- CodeBag codeBag = new CodeBag(this, instructions, leastUnallocatedAddress);
- System.out.println("instructions.length="+instructions.length);
+ /** the provided pool should be a sibling of the one which holds this Program's instructions */
+ public void install(FleetProcess fp, ShipPool pool) {
+ for(int i=0; i<codeBags.size(); i++)
+ codeBags.get(i).emit();
+ BitVector[] bvs = new BitVector[(int)(leastUnallocatedAddress-startAddress)];
+ for(int i=0; i<bvs.length; i++) {
+ bvs[i] = fleet.encodeInstruction(all_instructions.get(i), memoryShip.getDock("out"));
+ }
+ MemoryUtils.writeMem(fp, pool, memoryShip, startAddress, bvs);
+ }
+
+ BitVector addInstructions(Instruction[] instructions) {
+
+ // CodeBags are "daisy chained" to eliminate any possibility
+ // of cloggage at the inCBD port as a result of more CBD's
+ // being dispatched than the maximum number that fit in the
+ // data fifo at that dock.
+
+ int MAX_BAG_SIZE = (1<<6)-1;
+
+ // FUZZ is an estimate of the number of instructions required
+ // to dispatch a code bag descriptor
+ int FUZZ = 4;
+
+ if (instructions.length <= MAX_BAG_SIZE) {
+ BitVector descriptor = new BitVector(fleet.getWordWidth());
+ descriptor.set( (leastUnallocatedAddress<<6) | instructions.length );
leastUnallocatedAddress += instructions.length;
- codeBags.add(codeBag);
- return codeBag;
+ for(Instruction i : instructions)
+ all_instructions.add(i);
+ return descriptor;
}
+
+ System.out.println("warning: code bag size is "+instructions.length+
+ ", which exceeds maximum of "+MAX_BAG_SIZE+
+ "; breaking into multiple bags");
+
+ Instruction[] rest = new Instruction[instructions.length - (MAX_BAG_SIZE-FUZZ)];
+ System.arraycopy(instructions, MAX_BAG_SIZE-FUZZ, rest, 0, rest.length);
+
+ DeferredBitVector restbag = addInstructions(rest);
+ CodeBag ctx = new CodeBag(fleet);
+ ctx.sendWord(restbag, getCBDDestination());
+ Instruction[] fuzz = ctx.emit();
+ if (fuzz.length > 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
private HashSet<Ship> allocatedShips = new HashSet<Ship>();
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;
if (ancestor != null) ancestor.releaseShip(ship);
}
+ public void releaseAll() {
+ HashSet<Ship> toRelease = new HashSet<Ship>();
+ toRelease.addAll(allocatedShips);
+ for (Ship ship : toRelease)
+ releaseShip(ship);
+ }
}
projects / fleet.git / commitdiff