From 13080826e276892556e2782003357544610b4579 Mon Sep 17 00:00:00 2001 From: megacz Date: Sun, 1 Mar 2009 08:17:39 -0800 Subject: [PATCH] first pass at getting mergesort to run on the interpreter --- .../berkeley/fleet/interpreter/Interpreter.java | 31 ++++++------ .../fleet/interpreter/InterpreterDock.java | 51 +++++++++++--------- .../fleet/interpreter/InterpreterShip.java | 8 ++- 3 files changed, 52 insertions(+), 38 deletions(-) diff --git a/src/edu/berkeley/fleet/interpreter/Interpreter.java b/src/edu/berkeley/fleet/interpreter/Interpreter.java index 50bcc20..063e15b 100644 --- a/src/edu/berkeley/fleet/interpreter/Interpreter.java +++ b/src/edu/berkeley/fleet/interpreter/Interpreter.java @@ -72,13 +72,6 @@ public class Interpreter extends FleetTwoFleet { } } - void dispatch(Instruction i) { - Log.dispatch(i); - long il = writeInstruction(i, debugShip.getDock("in")); - Path path = debugShip.getDock("in").getPath(i.dock.getInstructionDestination(), null); - new Packet((InterpreterPath)path, new BitVector(getWordWidth()).set(il), false).send(); - } - private Ship createShip(String shipType, String shipname) { try { if (ships.get(shipname)!=null) return ships.get(shipname); @@ -178,7 +171,6 @@ public class Interpreter extends FleetTwoFleet { public class InterpreterProcess extends FleetProcess implements Runnable { private Instruction[] instructions; - public void flush() { } public synchronized void sendWord(Destination d, BitVector word) { InterpreterPath path = (InterpreterPath)debugShip.getDock("in").getPath(d, new BitVector(1)); ((InterpreterDestination)d). @@ -195,7 +187,12 @@ public class Interpreter extends FleetTwoFleet { sendInstruction(i); } public Fleet getFleet() { return Interpreter.this; } - public void sendInstruction(Instruction i) { dispatch(i); } + public synchronized void sendInstruction(Instruction i) { + Log.dispatch(i); + long il = writeInstruction(i, debugShip.getDock("in")); + Path path = debugShip.getDock("in").getPath(i.dock.getInstructionDestination(), null); + new Packet((InterpreterPath)path, new BitVector(getWordWidth()).set(il), false).send(); + } public Dock getDebugInputDock() { return debugShip.getDock("in"); } public BitVector recvWord() { try { @@ -206,11 +203,7 @@ public class Interpreter extends FleetTwoFleet { public void run() { try { while(!isTerminated()) { - for(InterpreterShip ship : ships.values()) - for(int j=0; j<10; j++) - synchronized(this) { - ship._service(); - } + flush(); } for(InterpreterShip ship : ships.values()) ship.reset(); @@ -221,6 +214,16 @@ public class Interpreter extends FleetTwoFleet { } } + public void flush() { + // FIXME: should this run until we detect some sort of "quiescence"? OTOH that might never happen. + for(InterpreterShip ship : ships.values()) + for(int j=0; j<10; j++) + if (!isTerminated()) + synchronized(this) { + ship._service(); + } + } + public synchronized void step(Dock d) { ((InterpreterDock)d).service(); } diff --git a/src/edu/berkeley/fleet/interpreter/InterpreterDock.java b/src/edu/berkeley/fleet/interpreter/InterpreterDock.java index 52aadba..14fd5b3 100644 --- a/src/edu/berkeley/fleet/interpreter/InterpreterDock.java +++ b/src/edu/berkeley/fleet/interpreter/InterpreterDock.java @@ -23,6 +23,10 @@ class InterpreterDock extends FleetTwoDock { Queue instructions = new LinkedList(); Queue dataPackets = new LinkedList(); + + // HACK + private Queue instructionsBackedUpIntoSwitchFabric = new LinkedList(); + boolean dataReadyForShip = false; boolean readyForDataFromShip = true; long dataFromShip; @@ -41,6 +45,7 @@ class InterpreterDock extends FleetTwoDock { requeueStageHasTailInstruction = false; instructions.clear(); dataPackets.clear(); + instructionsBackedUpIntoSwitchFabric.clear(); dataReadyForShip = false; readyForDataFromShip = true; torpedoWaiting = false; @@ -54,6 +59,8 @@ class InterpreterDock extends FleetTwoDock { public String toString() { return getDock()+":i"; } public void addDataFromFabric(Packet p) { if (p.isToken()) { + if (instructionsBackedUpIntoSwitchFabric.size()!=0) + throw new RuntimeException("torpedo arrived while instructions were backed up into switch fabric"); if (torpedoWaiting) throw new RuntimeException("two torpedoes collided!"); torpedoWaiting = true; return; @@ -62,28 +69,7 @@ class InterpreterDock extends FleetTwoDock { 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); + addInstruction(inst); } }; public InterpreterDestination dataDestination = new InterpreterDestination(this) { @@ -102,6 +88,21 @@ class InterpreterDock extends FleetTwoDock { public int getInstructionFifoSize() { return Integer.MAX_VALUE; } public Interpreter getInterpreter() { return ((InterpreterShip)getShip()).getInterpreter(); } + boolean trace = false; + + private void addInstruction(Instruction inst) { + if (requeueStageInCirculatingState || requeueStageHasTailInstruction) { + // GROSS HACK + instructionsBackedUpIntoSwitchFabric.add(inst); + return; + } + if (inst instanceof Instruction.Tail) { + requeueStageHasTailInstruction = true; + return; + } + instructions.add(inst); + } + protected final void service() { if (dataReadyForShip || flushing) return; @@ -173,6 +174,12 @@ class InterpreterDock extends FleetTwoDock { } else if (instructions.peek() instanceof Instruction.Abort) { requeueStageInCirculatingState = false; + // HACK + while (instructionsBackedUpIntoSwitchFabric.size()!=0) { + Instruction i = instructionsBackedUpIntoSwitchFabric.remove(); + addInstruction(i); + instructionsBackedUpIntoSwitchFabric.clear(); + } break; } else if (instructions.peek() instanceof Instruction.Flush) { diff --git a/src/edu/berkeley/fleet/interpreter/InterpreterShip.java b/src/edu/berkeley/fleet/interpreter/InterpreterShip.java index 7f6397c..033b33b 100644 --- a/src/edu/berkeley/fleet/interpreter/InterpreterShip.java +++ b/src/edu/berkeley/fleet/interpreter/InterpreterShip.java @@ -33,20 +33,24 @@ abstract class InterpreterShip extends FleetTwoShip { // flushing logic (must come between dock servicing and subclass) boolean someflushing = false; boolean allflushing = true; + boolean someempty = false; for(InterpreterDock d : docks.values()) { if (!d.isInputDock()) continue; if (d.flushing) someflushing = true; else allflushing = false; + if (!d.flushing && !d.dataReadyForShip) someempty = true; } if (allflushing) { for(InterpreterDock d : docks.values()) if (d.isInputDock()) d.flushing = false; return; - } else if (someflushing) { + } else if (someflushing && !someempty) { for(InterpreterDock d : docks.values()) - if (d.isInputDock() && !d.flushing && d.dataReadyForShip) + if (d.isInputDock() && !d.flushing && d.dataReadyForShip) { + System.out.println("FLUSH AT " + this); d.dataReadyForShip = false; + } } // now pass control to the subclass -- 1.7.10.4