first pass at getting mergesort to run on the interpreter

diff --git a/src/edu/berkeley/fleet/interpreter/Interpreter.java b/src/edu/berkeley/fleet/interpreter/Interpreter.java
index 50bcc20..063e15b 100644 (file)
--- 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 (file)
--- 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<Instruction> instructions = new LinkedList<Instruction>();
     Queue<Packet> dataPackets = new LinkedList<Packet>();
+
+    // HACK
+    private Queue<Instruction> instructionsBackedUpIntoSwitchFabric = new LinkedList<Instruction>();
+
     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 (file)
--- 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