package edu.berkeley.fleet.interpreter;
import java.util.*;
-import edu.berkeley.sbp.util.ANSI;
import edu.berkeley.fleet.two.*;
import edu.berkeley.fleet.api.*;
-import edu.berkeley.fleet.api.Instruction;
-import static edu.berkeley.fleet.api.Predicate.*;
/** anything that has a source (instruction horn) address on the switch fabric */
class InterpreterDock extends FleetTwoDock {
// Dock State //////////////////////////////////////////////////////////////////////////////
- public boolean flag_a = false;
- public boolean flag_b = false;
- public boolean flag_c = false;
- public int ilc = 1;
- public int olc = 1;
- public BitVector dataLatch = new BitVector(getShip().getFleet().getWordWidth());
- public InterpreterPath pathLatch = null;
- public InterpreterPath tapl = null;
- public boolean hatchIsOpen = true;
+ boolean flag_a = false;
+ boolean flag_b = false;
+ boolean flag_c = false;
+ boolean flag_d = false;
+ int ilc = 1;
+ int olc = 1;
+ final BitVector dataLatch = new BitVector(getShip().getFleet().getWordWidth());
+ InterpreterPath pathLatch = null;
+ boolean requeueStageInCirculatingState = false;
+ boolean requeueStageHasTailInstruction = false;
+ boolean torpedoWaiting = false;
+ boolean flushing = false;
- Instruction executing = null;
Queue<Instruction> instructions = new LinkedList<Instruction>();
- Queue<Instruction> epilogue = new LinkedList<Instruction>();
Queue<Packet> dataPackets = new LinkedList<Packet>();
boolean dataReadyForShip = false;
boolean readyForDataFromShip = true;
long dataFromShip;
- boolean torpedoWaiting = false;
+ boolean flagCFromShip;
protected void reset() {
ilc = 1;
flag_a = false;
flag_b = false;
flag_c = false;
- dataLatch = new BitVector(getShip().getFleet().getWordWidth());
+ flag_d = false;
+ dataLatch.set(0);
pathLatch = null;
- hatchIsOpen = true;
- executing = null;
+ requeueStageInCirculatingState = false;
+ requeueStageHasTailInstruction = false;
instructions.clear();
- epilogue.clear();
+ dataPackets.clear();
dataReadyForShip = false;
readyForDataFromShip = true;
- tapl = null;
torpedoWaiting = false;
+ flushing = false;
}
// Destinations //////////////////////////////////////////////////////////////////////////////
if (p.isToken()) {
if (torpedoWaiting) throw new RuntimeException("two torpedoes collided!");
torpedoWaiting = true;
- } else {
- BitVector bv = p.getValue();
- long val = 0;
- for(int i=0; i<bv.length(); i++)
- if (bv.get(i))
- val |= (1L << i);
- epilogue.add(getInterpreter().readInstruction(val, InterpreterDock.this));
+ return;
}
+
+ Instruction inst =
+ getInterpreter().decodeInstruction(p.getValue(),
+ InterpreterDock.this /* this is wrong, but harmless */);
+
+ // FIXME: this is a bit too conservative. In theory,
+ // it's okay to dispatch new instructions to the dock
+ // as long as we know that it will reach the updating
+ // state without any further input from the outside
+ // world -- ie that the instructions which remain to
+ // be executed before the requeue stage transitions to
+ // the updating state are all "non-blocking" (no moves
+ // with Ti=1 or Di=1)
+ if (requeueStageInCirculatingState || requeueStageHasTailInstruction)
+ throw new RuntimeException("An instruction arrived while the requeue stage was circulating -- "+
+ "this means that instructions have backed up into "+
+ "the switch fabric, which nearly always risks deadlock! "+
+ "Fix your program!"+
+ "\n dock: " + InterpreterDock.this +
+ "\n instruction: " + inst
+ );
+ if (inst instanceof Instruction.Tail) {
+ requeueStageHasTailInstruction = true;
+ return;
+ }
+ instructions.add(inst);
}
};
public InterpreterDestination dataDestination = new InterpreterDestination(this) {
public int getInstructionFifoSize() { return Integer.MAX_VALUE; }
public Interpreter getInterpreter() { return ((InterpreterShip)getShip()).getInterpreter(); }
- // interface to subclass ///////////////////////////////////////////////////////////////////////
-
- /** this will be invoked periodically; should return true to "consume" an instruction, false to leave it executing */
-
- public boolean dataReadyForShip() { return dataReadyForShip; }
- public final boolean readyForDataFromShip() { return readyForDataFromShip; }
-
- public long removeDataForShip() {
- long val = peekDataForShip();
- dataReadyForShip = false;
- return val;
- }
- public long peekDataForShip() {
- if (!dataReadyForShip) throw new RuntimeException();
- BitVector bv = dataLatch;
- long val = 0;
- for(int i=0; i<bv.length(); i++)
- if (bv.get(i))
- val |= (1L << i);
- return val;
- }
- public void addDataFromShip(long data) {
- if (!readyForDataFromShip()) throw new RuntimeException();
- readyForDataFromShip = false;
- dataFromShip = data;
- }
-
protected final void service() {
- if (hatchIsOpen && epilogue.size() > 0) {
- Instruction inst = epilogue.remove();
- if (inst instanceof Instruction.Head) {
- // FIXME
- return;
- }
- if (inst instanceof Instruction.Tail)
- hatchIsOpen = false;
- else
- instructions.add(inst);
- }
-
- if (dataReadyForShip) return;
-
- if (executing==null && instructions.size() > 0) {
- executing = instructions.remove();
- return;
- }
-
- if (executing==null) return;
-
- if (executing.looping && hatchIsOpen && olc>0) return;
+ if (dataReadyForShip || flushing) return;
+ if (instructions.size()==0) return;
- boolean enabled = true;
- switch(executing.predicate) {
- case IgnoreFlagD: enabled = true; break;
- case Default: enabled = olc>0; break;
- case FlagA: enabled = flag_a; break;
- case FlagB: enabled = flag_b; break;
- case FlagC: enabled = flag_c; break;
- case NotFlagA: enabled = !flag_a; break;
- case NotFlagB: enabled = !flag_b; break;
- case NotFlagC: enabled = !flag_c; break;
- default: throw new RuntimeException();
- }
- if (!enabled) {
- if (executing.looping && olc>0)
- instructions.add(executing);
- executing = null;
+ if (instructions.peek() instanceof Instruction.Head) {
+ if (requeueStageInCirculatingState) { instructions.remove(); return; }
+ if (!requeueStageHasTailInstruction) return;
+ requeueStageHasTailInstruction = false;
+ requeueStageInCirculatingState = true;
+ instructions.remove();
return;
}
- if (executing instanceof Instruction.Move) {
- Instruction.Move move = (Instruction.Move)executing;
+ // in the while..false idiom block below, use "break" to
+ // consume the instruction at instructions.peek(), or "return"
+ // to leave it and retry on the next call.
+ do {
+ if (!instructions.peek().predicate.evaluate(flag_a, flag_b, flag_c, flag_d))
+ break;
- if (move.interruptible && torpedoWaiting) {
- torpedoWaiting = false;
- executing = null;
- ilc = 1;
- olc = 0;
- if (tapl != null)
- new Packet(tapl, new BitVector(getInterpreter().getWordWidth()), true).send();
- hatchIsOpen = true;
- return;
- }
+ if (instructions.peek() instanceof Instruction.Move) {
+ Instruction.Move move = (Instruction.Move)instructions.peek();
- if (move.dataIn && !isInputDock() && readyForDataFromShip) return;
- if (move.dataIn && isInputDock() && dataPackets.size()==0) return;
- if (move.tokenIn && dataPackets.size()==0) return;
- }
+ if (ilc==0) { ilc = 1; break; }
- if (executing.looping && olc>0)
- instructions.add(executing);
+ if (move.interruptible && torpedoWaiting) {
+ torpedoWaiting = false;
+ ilc = 1;
+ flag_d = true;
+ break;
+ }
- if (executing instanceof Instruction.Shift) {
- /*
- Instruction.Shift shift = (Instruction.Shift)executing;
- for(int i=dataLatch.length()-1; i>=getShip().getFleet().getShiftWidth(); i--)
- dataLatch.set(i, dataLatch.get(i-getShip().getFleet().getShiftWidth()));
- for(int i=getShip().getFleet().getShiftWidth()-1; i>=0; i--)
- dataLatch.set(i, shift.immediate.get(i));
- executing = null;
- return;
- */
- throw new RuntimeException("FIXME");
- }
+ if (move.dataIn && !isInputDock() && readyForDataFromShip) return;
+ if (move.dataIn && isInputDock() && dataPackets.size()==0) return;
+ if (move.tokenIn && dataPackets.size()==0) return;
- if (executing instanceof Instruction.Set) {
- Instruction.Set set = (Instruction.Set)executing;
- switch(set.dest) {
- case DataLatch:
- dataLatch = new BitVector(getInterpreter().getWordWidth()).setAndSignExtend(set.immediate);
- break;
- case InnerLoopCounter:
- switch(set.source) {
- case Infinity:
- ilc = -1;
- break;
- case DataLatch:
- ilc = 0;
- for(int i=0; i<((FleetTwoFleet)getShip().getFleet()).SET_ILC_FROM_IMMEDIATE.valmaskwidth-1; i++)
- if (dataLatch.get(i))
- ilc |= (1 << i);
- break;
- case Immediate:
- ilc = (int)set.immediate;
- break;
- default:
- throw new RuntimeException("FIXME!");
+ if (move.tokenIn) {
+ Packet p = dataPackets.remove();
+ flag_c = p.getSignal().get(0);
+ }
+ if (move.dataIn) {
+ BitVector bv = null;
+ if (isInputDock()) {
+ Packet p = dataPackets.remove();
+ bv = new BitVector(p.getValue());
+ flag_c = p.getSignal().get(0);
+ } else {
+ bv = new BitVector(getInterpreter().getWordWidth()).set(dataFromShip);
+ readyForDataFromShip = true;
+ flag_c = flagCFromShip;
}
- break;
- case OuterLoopCounter:
- switch(set.source) {
- case Decrement:
- olc = Math.max(0,olc-1);
- if (olc==0) hatchIsOpen = true;
- break;
- case DataLatch:
- olc = 0;
- for(int i=0; i<((FleetTwoFleet)getShip().getFleet()).SET_OLC_FROM_IMMEDIATE.valmaskwidth-1; i++)
- if (dataLatch.get(i))
- olc |= (1 << i);
- if (olc==0) hatchIsOpen = true;
- break;
- case Immediate:
- olc = (int)set.immediate;
- if (olc==0) hatchIsOpen = true;
- break;
- default:
- throw new RuntimeException("FIXME!");
+ if (move.latchData) dataLatch.set(bv);
+ if (move.latchPath) {
+ BitVector bvp = ((FleetTwoFleet)getShip().getFleet()).DISPATCH_PATH.getvalAsBitVector(bv);
+ pathLatch = (InterpreterPath)getInterpreter().getPathByAddr(this, bvp);
}
- break;
+ }
+
+ if (move.path != null) pathLatch = (InterpreterPath)move.path;
+
+ if (move.dataOut && isInputDock()) dataReadyForShip = true;
+ if (move.dataOut && !isInputDock()) new Packet(pathLatch, new BitVector(dataLatch), false).send();
+ if (move.tokenOut) new Packet(pathLatch, new BitVector(getInterpreter().getWordWidth()), true).send();
+
+ if (ilc==1) break;
+ if (ilc!=-1) ilc--;
+ return;
- case Flags: {
- boolean new_flag_a = false;
- boolean new_flag_b = false;
- for(Predicate p : set.newFlagA)
- switch(p) {
- case FlagA: new_flag_a |= flag_a; break;
- case FlagB: new_flag_a |= flag_b; break;
- case FlagC: new_flag_a |= flag_c; break;
- case NotFlagA: new_flag_a |= !flag_a; break;
- case NotFlagB: new_flag_a |= !flag_b; break;
- case NotFlagC: new_flag_a |= !flag_c; break;
+ } else if (instructions.peek() instanceof Instruction.Abort) {
+ requeueStageInCirculatingState = false;
+ break;
+
+ } else if (instructions.peek() instanceof Instruction.Flush) {
+ flushing = true;
+ break;
+
+ } else if (instructions.peek() instanceof Instruction.Shift) {
+ Instruction.Shift shift = (Instruction.Shift)instructions.peek();
+ for(int i=dataLatch.length()-1; i>=getShip().getFleet().getShiftWidth(); i--)
+ dataLatch.set(i, dataLatch.get(i-getShip().getFleet().getShiftWidth()));
+ for(int i=getShip().getFleet().getShiftWidth()-1; i>=0; i--)
+ dataLatch.set(i, shift.immediate.get(i));
+ break;
+
+ } else if (instructions.peek() instanceof Instruction.Set) {
+ Instruction.Set set = (Instruction.Set)instructions.peek();
+ switch(set.dest) {
+ case DataLatch: dataLatch.setAndSignExtend(set.immediate);
+ break;
+ case InnerLoopCounter:
+ switch(set.source) {
+ case Infinity: ilc = -1; break;
+ case Immediate: ilc = (int)set.immediate; break;
+ case DataLatch:
+ ilc = 0;
+ for(int i=0; i<((FleetTwoFleet)getShip().getFleet()).SET_ILC_FROM_IMMEDIATE.valmaskwidth-1; i++)
+ if (dataLatch.get(i))
+ ilc |= (1 << i);
+ break;
+ default: throw new RuntimeException("impossible");
}
- for(Predicate p : set.newFlagB)
- switch(p) {
- case FlagA: new_flag_b |= flag_a; break;
- case FlagB: new_flag_b |= flag_b; break;
- case FlagC: new_flag_b |= flag_c; break;
- case NotFlagA: new_flag_b |= !flag_a; break;
- case NotFlagB: new_flag_b |= !flag_b; break;
- case NotFlagC: new_flag_b |= !flag_c; break;
+ break;
+ case OuterLoopCounter:
+ switch(set.source) {
+ case Decrement: olc = Math.max(0,olc-1); break;
+ case Immediate: olc = (int)set.immediate; break;
+ case DataLatch:
+ olc = 0;
+ for(int i=0; i<((FleetTwoFleet)getShip().getFleet()).SET_OLC_FROM_IMMEDIATE.valmaskwidth-1; i++)
+ if (dataLatch.get(i))
+ olc |= (1 << i);
+ break;
+ default: throw new RuntimeException("impossible");
}
- flag_a = new_flag_a;
- flag_b = new_flag_b;
- break;
+ flag_d = olc==0;
+ break;
+
+ case Flags: {
+ boolean new_flag_a = set.newFlagA.evaluate(flag_a, flag_b, flag_c, flag_d);
+ boolean new_flag_b = set.newFlagB.evaluate(flag_a, flag_b, flag_c, flag_d);
+ flag_a = new_flag_a;
+ flag_b = new_flag_b;
+ break;
+ }
+ default: throw new RuntimeException("FIXME!");
}
- default:
- throw new RuntimeException("FIXME!");
- }
- executing = null;
- return;
- }
-
- Instruction.Move move = (Instruction.Move)executing;
-
- // if ILC==0, don't even bother
- if (ilc==0) { ilc = 1; executing = null; return; }
-
- if (ilc==-1) { }
- else if (ilc==1) executing = null;
- else ilc--;
-
- Packet p = null;
- if (move.tokenIn) {
- p = dataPackets.remove();
- if (p.getSignal() != null) flag_c = p.getSignal().get(0);
- }
- if (move.dataIn) {
- BitVector bv = null;
- if (isInputDock()) {
- p = dataPackets.remove();
- bv = new BitVector(p.getValue());
- if (p.getSignal() != null) flag_c = p.getSignal().get(0);
} else {
- bv = new BitVector(getInterpreter().getWordWidth()).set(dataFromShip);
- readyForDataFromShip = true;
+ throw new RuntimeException("unimplemented instruction: " + instructions.peek());
}
- if (move.latchData) dataLatch = bv;
- if (move.latchPath)
- pathLatch = (InterpreterPath)getInterpreter().getPathByAddr(this, ((FleetTwoFleet)getShip().getFleet()).DISPATCH_PATH.getvalAsBitVector(bv.toLong()));
- // FIXME: c-flag at output docks
- }
+ } while(false);
- if (move.path != null) pathLatch = (InterpreterPath)move.path;
+ if (requeueStageInCirculatingState)
+ instructions.add(instructions.peek());
+ instructions.remove();
+ return;
+ }
- if (move.dataOut && isInputDock()) dataReadyForShip = true;
- if (move.dataOut && !isInputDock())
- new Packet(pathLatch, new BitVector(dataLatch), true).send();
- if (move.tokenOut)
- new Packet(pathLatch, new BitVector(getInterpreter().getWordWidth()), true).send();
+ // Interface for use by Subclasses ///////////////////////////////////////////////////////////////////////
- return;
+ // all the methods below convert 64-bit longs to/from
+ // getWordWidth()-bit BitVectors by truncation and sign-extension.
+
+ protected boolean dataReadyForShip() { return dataReadyForShip; }
+ protected final boolean readyForDataFromShip() { return readyForDataFromShip; }
+ protected long removeDataForShip() {
+ long val = peekDataForShip();
+ dataReadyForShip = false;
+ return val;
+ }
+ protected long peekDataForShip() {
+ if (!dataReadyForShip)
+ throw new RuntimeException("peekDataForShip() invoked when dataReadyForShip()==false");
+ BitVector bv = dataLatch;
+ long val = 0;
+ for(int i=0; i<bv.length(); i++)
+ if (bv.get(i))
+ val |= (1L << i);
+ return val;
+ }
+ protected void addDataFromShip(long data) { addDataFromShip(data, false); }
+ protected void addDataFromShip(long data, boolean pending_flag_c) {
+ if (!readyForDataFromShip())
+ throw new RuntimeException("addDataFromShip() invoked when readyForDataFromShip()");
+ readyForDataFromShip = false;
+ dataFromShip = data;
+ flagCFromShip = pending_flag_c;
}
}
projects / fleet.git / commitdiff