src/edu/berkeley/fleet/dataflow/DataFlowGraph.java

   1 package edu.berkeley.fleet.dataflow;
   2 import edu.berkeley.fleet.loops.*;
   3 import java.util.concurrent.Semaphore;
   4 import java.util.*;
   5 import java.net.*;
   6 import edu.berkeley.fleet.two.*;
   7 import edu.berkeley.fleet.api.*;
   8 import edu.berkeley.fleet.fpga.*;
   9 import edu.berkeley.fleet.api.Instruction.*;
  10 import edu.berkeley.fleet.api.Instruction.Set;
  11 import edu.berkeley.fleet.api.Instruction.Set.*;
  12 import static edu.berkeley.fleet.api.Predicate.*;
  13 import static edu.berkeley.fleet.util.BitManipulations.*;
  14
  15 // does peer.recvWord() have to honor the currently-set predicate?
  16
  17 // public class ReplaceNode extends Node { }
  18 // public class CountMergeNode extends Node { }
  19 // public class SortMergeNode extends Node { }
  20 // public class FanOutNode extends Node { }
  21 // public class MemoryNode extends Node { }
  22 // public class DoneNode extends Node { }
  23
  24 public class DataFlowGraph {
  25
  26     public final Fleet    fleet;
  27     public final ShipPool pool;
  28
  29     public DataFlowGraph(Fleet fleet) {
  30         this(fleet, new ShipPool(fleet));
  31     }
  32     public DataFlowGraph(Fleet fleet, ShipPool pool) {
  33         this.fleet = fleet;
  34         this.pool  = pool;
  35     }
  36
  37     public static int reset_count = 0;
  38     public static HashSet<Dock> torpedoes = new HashSet<Dock>();
  39
  40     private HashSet<Node> nodes = new HashSet<Node>();
  41
  42     public void build(Context ctx) {
  43         for(Node mod : nodes)
  44             mod.build(ctx);
  45     }
  46     public void reset(Context ctx, int phase, Destination ackDestination) {
  47         reset_count = 0;
  48         torpedoes.clear();
  49         for(Node mod : nodes)
  50             mod.reset(ctx, phase, ackDestination);
  51     }
  52
  53     public static class Node {
  54
  55         void doReset(Context ctx, int phase, Dock dock, Port peer, Destination ackDestination, boolean peerUsed) {
  56             if (dock.getShip().getType().equals("Debug")) return;
  57
  58             switch(phase) {
  59
  60                 // Phase 0: torpedo every output dock, put it in
  61                 // collecting mode.  Cannot combine with phase 1,
  62                 // because until output docks are in vacuum mode we
  63                 // cannot be sure that the tokens to the input docks
  64                 // will eventually succeed.  This may cause the
  65                 // instructions sent after the tokens to back up into
  66                 // the switch fabric.
  67                 case 0: {
  68                     if (!dock.isInputDock()) {
  69                         torpedoes.add(dock);
  70                         LoopFactory lf = new LoopFactory(ctx, dock, 1);
  71                         lf.sendToken(ackDestination);
  72                         lf = lf.makeNext(0);
  73                         lf.abortLoopIfTorpedoPresent();
  74                         lf.collectWord();
  75                         reset_count++;
  76                     }
  77                     break;
  78                 }
  79
  80                 // Phase 1: torpedo every input dock, put it in loopback mode
  81                 case 1: {
  82                     if (dock.isInputDock()) {
  83                         torpedoes.add(dock);
  84                         LoopFactory lf = new LoopFactory(ctx, dock, 1);
  85                         lf.sendToken(ackDestination);
  86
  87                         // FIXME: this won't work right for ports that
  88                         // get "shared" by two senders (for example,
  89                         // inAddrRead1/2)
  90
  91                         if (peerUsed && peer!=null) {
  92                             lf = lf.makeNext(0);
  93                             lf.abortLoopIfTorpedoPresent();
  94                             ((OutPort)peer).recvWord(lf);
  95                             ((OutPort)peer).sendToken(lf);
  96                         }
  97                         reset_count++;
  98                     }
  99                     break;
 100                 }
 101
 102                 // Phase 2: torpedo every output dock, have it absorb tokens
 103                 case 2: {
 104                     if (!dock.isInputDock()) {
 105                         torpedoes.add(dock);
 106                         LoopFactory lf = new LoopFactory(ctx, dock, 1);
 107                         if (peer != null)
 108                             for(int i=0; i<((InPort)peer).getTokensToAbsorb(); i++)
 109                                 lf.recvToken();
 110                         lf.sendToken(ackDestination);
 111                         reset_count++;
 112                     }
 113                     break;
 114                 }
 115
 116                 // Phase 3: torpedo every input dock, and we're done
 117                 case 3: {
 118                     if (dock.isInputDock()) {
 119                         if (peerUsed && peer!=null) {
 120                             torpedoes.add(dock);
 121                         }
 122                         LoopFactory lf = new LoopFactory(ctx, dock, 1);
 123                         lf.sendToken(ackDestination);
 124                         reset_count++;
 125                     }
 126                     break;
 127                 }
 128
 129
 130             }
 131         }
 132
 133         public final DataFlowGraph dfg;
 134         public Node(DataFlowGraph dfg) {
 135             this.dfg = dfg;
 136             dfg.nodes.add(this);
 137         }
 138
 139         private HashMap<String,Port> ports = new HashMap<String,Port>();
 140
 141         public InPort  getInPort(String name)  { return (InPort)ports.get(name); }
 142         public OutPort getOutPort(String name) { return (OutPort)ports.get(name); }
 143
 144         public void build(Context ctx) { for(Port p : ports.values()) p.build(ctx); }
 145         public void reset(Context ctx, int phase, Destination ackDestination) {
 146             for(Port p : ports.values()) p.reset(ctx, phase, ackDestination);
 147         }
 148
 149         public abstract class Port {
 150             public final String name;
 151             public Port(String name) {
 152                 this.name = name;
 153                 if (Node.this.ports.get(name)!=null) throw new RuntimeException();
 154                 Node.this.ports.put(name,this);
 155             }
 156             public abstract void build(Context ctx);
 157             public abstract void reset(Context ctx, int phase, Destination ackDestination);
 158         }
 159
 160         public abstract class InPort extends Port {
 161             OutPort peer;
 162             public InPort(String name) { super(name); }
 163             public void connect(OutPort peer) {
 164                 this.setPeer(peer);
 165                 peer.setPeer(this);
 166             }
 167             public void setPeer(OutPort peer) {
 168                 if (this.peer!=null) throw new RuntimeException("cannot call setPeer() twice");
 169                 this.peer = peer;
 170             }
 171
 172             /** this port's peer (an OutPort) invokes this to have "recvToken" or equivalent inserted */
 173             public abstract void recvToken(LoopFactory loopfactory_at_output_dock);
 174             /** this port's peer (an OutPort) invokes this to have "sendWord" or equivalent inserted */
 175             public abstract void sendWord(LoopFactory loopfactory_at_output_dock);
 176
 177             public int getTokensToAbsorb() { return 0; }
 178         }
 179
 180         public abstract class OutPort extends Port {
 181             InPort peer;
 182             public OutPort(String name) { super(name); }
 183             public void connect(InPort peer) {
 184                 this.setPeer(peer);
 185                 peer.setPeer(this);
 186             }
 187             public void setPeer(InPort peer) {
 188                 if (this.peer!=null) throw new RuntimeException("cannot call setPeer() twice");
 189                 this.peer = peer;
 190             }
 191
 192             /** this port's peer (an InPort) invokes this to have "sendToken" or equivalent inserted */
 193             public abstract void sendToken(LoopFactory loopfactory_at_input_dock);
 194             /** this port's peer (an InPort) invokes this to have "recvWord" or equivalent inserted */
 195             public abstract void recvWord(LoopFactory loopfactory_at_input_dock);
 196         }
 197
 198         public final class DockInPort extends InPort {
 199             final Dock dock;
 200             int count;
 201             BitVector[] pattern;
 202             public DockInPort(String name, Dock dock) { this(name, dock, 0); }
 203             public DockInPort(String name, Dock dock, int count) { this(name, dock, count, new BitVector[] { null }); }
 204             public DockInPort(String name, Dock dock, int count, BitVector[] pattern) {
 205                 super(name);
 206                 this.dock = dock;
 207                 this.count = count;
 208                 this.pattern = pattern;
 209             }
 210             public void recvToken(LoopFactory lf) { lf.recvToken(); }
 211             public void sendWord(LoopFactory lf) { lf.sendWord(dock.getDataDestination()); }
 212             public void build(Context ctx) { build(ctx, new LoopFactory(ctx, dock, 1)); }
 213             // number-in-flight is considered a property of the input dock in a pair
 214             public int getInflight() { return 4; }
 215             //public int getInflight() { return 1; }
 216             public int getTokensToAbsorb() { return getInflight(); }
 217             private boolean peerUsed() {
 218                 if (peer==null) return false;
 219                 for(int i=0; i<pattern.length; i++) if (pattern[i]==null) return true;
 220                 return false;
 221             }
 222             public void reset(Context ctx, int phase, Destination ackDestination) {
 223                 doReset(ctx, phase, dock, peer, ackDestination, peerUsed());
 224             }
 225             protected void build(Context ctx, LoopFactory lf) {
 226                 int inflight = (count != 0 && count < getInflight()) ? count : getInflight();
 227
 228                 if (peer!=null)
 229                     for(int i=0; i<inflight; i++) peer.sendToken(lf);
 230
 231                 lf = lf.makeNext(count, true);
 232                 for(int i=0; i<pattern.length; i++) {
 233                     if (pattern[i]==null) {
 234                         if (peer!=null) {
 235                             lf.abortLoopIfTorpedoPresent();
 236                             peer.recvWord(lf);
 237                             peer.sendToken(lf);
 238                             lf.deliver();
 239                         } else {
 240                             lf.interruptibleNop();
 241                         }
 242                     } else {
 243                         lf.literal(pattern[i]);
 244                         lf.abortLoopIfTorpedoPresent();
 245                         lf.deliver();
 246                     }
 247                 }
 248
 249                 if (count!=0) {
 250                     // "torpedoable nop" to keep the dock in a receptive state
 251                     lf.abortLoopIfTorpedoPresent();
 252                     lf.recvToken();
 253                 }
 254             }
 255             public BitVector getConstant(String constantName) {
 256                 return dock.getConstant(constantName);
 257             }
 258         }
 259
 260         public /*final*/ class DockOutPort extends OutPort {
 261             public final Dock dock;
 262             public final int count;
 263             public DockOutPort(String name, Dock dock) { this(name, dock, 0); }
 264             public DockOutPort(String name, Dock dock, int count) { super(name); this.dock = dock; this.count = count; }
 265             public void sendToken(LoopFactory lf) { lf.sendToken(dock.getDataDestination()); }
 266             public void recvWord(LoopFactory lf) { lf.recvWord(); }
 267             public void build(Context ctx) { build(ctx, new LoopFactory(ctx, dock, 1)); }
 268             protected void build(Context ctx, LoopFactory lf) {
 269                 if (peer==null) return;
 270                 lf = lf.makeNext(count);
 271                 lf.abortLoopIfTorpedoPresent();
 272                 peer.recvToken(lf);
 273                 lf.collectWord();
 274                 peer.sendWord(lf);
 275             }
 276             public void reset(Context ctx, int phase, Destination ackDestination) {
 277                 doReset(ctx, phase, dock, peer, ackDestination, true);
 278             }
 279         }
 280     }
 281
 282     private BitVector bv(long l) { return new BitVector(fleet.getWordWidth()).set(l); }
 283     private BitVector[] bv(long[] l) {
 284         BitVector[] ret = new BitVector[l.length];
 285         for(int i=0; i<ret.length; i++) ret[i] = bv(l[i]);
 286         return ret;
 287     }
 288
 289     /**
 290      *  Deliver the constant at out forever.  Flow control in<->out is
 291      *  maintained, but out is not flow-controlled, so be sure
 292      *  that every datum sent there is consumed synchronously wiht
 293      *  data items sent to out.
 294      */
 295     public static class ForeverNode extends Node {
 296         private BitVector bv;
 297         public final OutPort out = new OutPort("out") {
 298                 public void sendToken(LoopFactory lf) { }
 299                 public void recvWord(LoopFactory lf) { }
 300                 public void build(Context ctx) { }
 301                 public void reset(Context ctx, int phase, Destination ackDestination) { }
 302                 public void setPeer(InPort peer) {
 303                     this.peer = peer;
 304                     DockInPort pip = ((DockInPort)peer);
 305                     for(int i=0; i<pip.pattern.length; i++) {
 306                         if (pip.pattern[i]==null)
 307                             pip.pattern[i] = bv;
 308                     }
 309                 }
 310             };
 311         public ForeverNode(DataFlowGraph dfg, long l) { this(dfg, new BitVector(dfg.fleet.getWordWidth()).set(l)); }
 312         public ForeverNode(DataFlowGraph dfg, final BitVector bv) { super(dfg); this.bv = bv; }
 313     }
 314
 315     public static class OnceNode extends Node {
 316         private BitVector bv;
 317         public final OutPort out = new OutPort("out") {
 318                 public void sendToken(LoopFactory lf) { }
 319                 public void recvWord(LoopFactory lf) { }
 320                 public void build(Context ctx) { }
 321                 public void reset(Context ctx, int phase, Destination ackDestination) { }
 322                 public void setPeer(InPort peer) {
 323                     this.peer = peer;
 324                     DockInPort pip = ((DockInPort)peer);
 325                     BitVector[] pip_pattern = pip.pattern;
 326                     BitVector[] temp = new BitVector[pip_pattern.length * 2];
 327                     int j = 0;
 328                     int i = 0;
 329                     boolean done = false;
 330                     // FIXME: if peer.count is already 1, this gets simpler and different
 331                     for(i=0; i<temp.length; i++) {
 332                         if (pip_pattern[j] != null) {
 333                             temp[i] = pip_pattern[j];
 334                         } else {
 335                             if (done) break;
 336                             done = true;
 337                             temp[i] = bv;
 338                         }
 339                         j++;
 340                         if (j >= pip_pattern.length) j = 0;
 341                     }
 342                     pip.pattern = new BitVector[i];
 343                     System.arraycopy(temp, 0, pip.pattern, 0, i);
 344                     pip.count = 1;
 345                 }
 346             };
 347         public OnceNode(DataFlowGraph dfg, long l) { this(dfg, new BitVector(dfg.fleet.getWordWidth()).set(l)); }
 348         public OnceNode(DataFlowGraph dfg, final BitVector bv) { super(dfg); this.bv = bv; }
 349     }
 350
 351     public static class DebugNode extends Node {
 352         public final Ship ship = dfg.pool.allocateShip("Debug");
 353         public final InPort in = new DockInPort("in", ship.getDock("in"));
 354         // NOTE: shutdown needs to treat this specially
 355         public DebugNode(DataFlowGraph dfg) { super(dfg); }
 356     }
 357
 358     public static class UnPunctuatorNode extends Node {
 359         private final Ship    ship  = dfg.pool.allocateShip("Counter");
 360         public  final OutPort out   = new DockOutPort("out", ship.getDock("out"));
 361         public  final InPort  val   = new DockInPort("in1",  ship.getDock("in1"));
 362         public  final InPort  count = new DockInPort("in2",  ship.getDock("in2"), 0, new BitVector[] { null, dfg.bv(1) });
 363         public  final InPort  op    = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] {
 364                 ship.getDock("inOp").getConstant("PASS_C2_V1"),
 365                 ship.getDock("inOp").getConstant("DROP_C2_V1") } );
 366         public UnPunctuatorNode(DataFlowGraph dfg) { super(dfg); }
 367     }
 368
 369     public static class PunctuatorNode extends Node {
 370         private final long    punc;
 371         private final Ship    ship  = dfg.pool.allocateShip("Counter");
 372         public  final OutPort out   = new DockOutPort("out", ship.getDock("out"));
 373         public  final InPort  val   = new DockInPort("in1",  ship.getDock("in1"));
 374         public  final InPort  op    = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] {
 375                 ship.getDock("inOp").getConstant("PASS_C2_V1"),
 376                 ship.getDock("inOp").getConstant("PASS_C2_V2") } );
 377         public  final InPort  count;
 378         public PunctuatorNode(DataFlowGraph dfg, long punc) {
 379             super(dfg);
 380             this.punc = punc;
 381             this.count = new DockInPort("in2",  ship.getDock("in2"), 0, new BitVector[] { null, dfg.bv(1), dfg.bv(punc) });
 382         }
 383     }
 384
 385     public static class AluNode extends Node {
 386         public final Ship    ship = dfg.pool.allocateShip("Alu");
 387         public final InPort  in1 = new DockInPort("in1",  ship.getDock("in1"));
 388         public final InPort  in2 = new DockInPort("in2",  ship.getDock("in2"));
 389         public final InPort  inOp = new DockInPort("inOp", ship.getDock("inOp"));
 390         public final OutPort out  = new DockOutPort("out", ship.getDock("out"));
 391         public AluNode(DataFlowGraph dfg) { super(dfg); }
 392     }
 393
 394     public static class DownCounterNode extends Node {
 395         public final Ship    ship  = dfg.pool.allocateShip("Counter");
 396         public final InPort  start = new DockInPort("in1",  ship.getDock("in1"));
 397         public final InPort  incr  = new DockInPort("in2",  ship.getDock("in2"));
 398         public final InPort  inOp  = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] {
 399                 ship.getDock("inOp").getConstant("COUNT") });
 400         public final OutPort out   = new DockOutPort("out", ship.getDock("out"));
 401         public DownCounterNode(DataFlowGraph dfg) { super(dfg); }
 402     }
 403
 404     public static class RepeatNode extends Node {
 405         public final Ship    ship   = dfg.pool.allocateShip("Counter");
 406         public final InPort  count  = new DockInPort("in1",  ship.getDock("in1"));
 407         public final InPort  val    = new DockInPort("in2",  ship.getDock("in2"));
 408         public final InPort  inOP   = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] {
 409                 ship.getDock("inOp").getConstant("REPEAT_C1_V2") });
 410         public final OutPort out    = new DockOutPort("out", ship.getDock("out"));
 411         public RepeatNode(DataFlowGraph dfg) { super(dfg); }
 412     }
 413
 414     public static class SortedMergeNode extends Node {
 415         public final Ship    ship = dfg.pool.allocateShip("Alu");
 416         public final InPort  in1  = new DockInPort("in1",  ship.getDock("in1"));
 417         public final InPort  in2  = new DockInPort("in2",  ship.getDock("in2"));
 418         public final InPort  inOp = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] {
 419                 ship.getDock("inOp").getConstant("MAXMERGE") });
 420         public final OutPort out  = new DockOutPort("out", ship.getDock("out"));
 421         public SortedMergeNode(DataFlowGraph dfg) { super(dfg); }
 422     }
 423
 424     public static class MemoryNode extends Node {
 425         public final Ship    ship;
 426         public final InPort  inCBD;
 427         public final InPort  inAddrRead1;
 428         public final InPort  inAddrRead2;
 429         public final InPort  inAddrWrite;
 430         public final InPort  inDataWrite;
 431         public final OutPort outRead1;
 432         public final OutPort outRead2;
 433         public final OutPort outWrite;
 434         public MemoryNode(DataFlowGraph dfg, Ship memoryShip) {
 435             super(dfg);
 436             this.ship = memoryShip;
 437             this.inCBD        = ship.getType().equals("Memory") ? new DockInPort("inCBD", ship.getDock("inCBD")) : null;
 438             this.inAddrWrite  = new DockInPort("inAddrWrite", ship.getDock("inAddrWrite"));
 439             this.inDataWrite  = new DockInPort("inDataWrite", ship.getDock("inDataWrite"));
 440             this.inAddrRead1  = new InPort("inAddrRead1") {
 441                     public void recvToken(LoopFactory lf) { lf.recvToken(); }
 442                     public void sendWord(LoopFactory lf) { lf.sendWord(ship.getDock("inAddrRead").getDataDestination(), new BitVector(1).set(0)); }
 443                     public void build(Context ctx) { }
 444                     public int getTokensToAbsorb() { return outRead1.peer.getTokensToAbsorb(); }
 445                     public void reset(Context ctx, int phase, Destination ackDestination) {
 446                         doReset(ctx, phase, ship.getDock("inAddrRead"), null, ackDestination, false);
 447                     }
 448                 };
 449             this.inAddrRead2  = new InPort("inAddrRead2") {
 450                     public void recvToken(LoopFactory lf) { lf.recvToken(); }
 451                     public void sendWord(LoopFactory lf) { lf.sendWord(ship.getDock("inAddrRead").getDataDestination(), new BitVector(1).set(1)); }
 452                     public void build(Context ctx) { }
 453                     public int getTokensToAbsorb() { return outRead2.peer.getTokensToAbsorb(); }
 454                     public void reset(Context ctx, int phase, Destination ackDestination) { }
 455                 };
 456             this.outRead1 = new OutPort("outRead1") {
 457                     public void sendToken(LoopFactory lf) { inAddrRead1.peer.sendToken(lf); }
 458                     public void recvWord(LoopFactory lf) { lf.recvWord(); }
 459                     public void build(Context ctx) { }
 460                     public void reset(Context ctx, int phase, Destination ackDestination) { }
 461                 };
 462             this.outRead2 = new OutPort("outRead2") {
 463                     public void sendToken(LoopFactory lf) { inAddrRead2.peer.sendToken(lf); }
 464                     public void recvWord(LoopFactory lf) { lf.recvWord(); }
 465                     public void build(Context ctx) { }
 466                     public void reset(Context ctx, int phase, Destination ackDestination) { }
 467                 };
 468             this.outWrite = new DockOutPort("out", ship.getDock("out")) {
 469                     protected void build(Context ctx, LoopFactory lf) {
 470                         lf = lf.makeNext(0);
 471                         lf.abortLoopIfTorpedoPresent();
 472                         lf.collectWord();
 473
 474                         lf.setFlags(FlagFunction.ZERO, FlagFunction.ZERO.add(FlagC));
 475                         if (this.peer != null) {
 476                             lf.setPredicate(Predicate.FlagB);
 477                             lf.literal(77);
 478                             lf.abortLoopIfTorpedoPresent();
 479                             this.peer.recvToken(lf);
 480                             this.peer.sendWord(lf);
 481                         }
 482
 483                         lf.setPredicate(Predicate.NotFlagB);
 484                         lf.abortLoopIfTorpedoPresent();
 485                         lf.recvToken();
 486                         lf.setFlags(FlagFunction.ZERO.add(NotFlagC).add(FlagB), FlagFunction.ZERO.add(FlagC).add(FlagB));
 487                         if (outRead1.peer != null) {
 488                             lf.setPredicate(Predicate.NotFlagB);
 489                             outRead1.peer.sendWord(lf);
 490                         }
 491                         if (outRead2.peer != null) {
 492                             lf.setPredicate(Predicate.NotFlagA);
 493                             outRead2.peer.sendWord(lf);
 494                         }
 495                         lf.setPredicate(null);
 496                     }
 497                 };
 498         }
 499         public void build(Context ctx) {
 500             super.build(ctx);
 501             LoopFactory lf;
 502
 503             lf = new LoopFactory(ctx, ship.getDock("inAddrRead"), 0);
 504             lf.abortLoopIfTorpedoPresent();
 505             lf.recvWord();
 506             lf.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO);
 507             lf.setPredicate(Predicate.NotFlagA);
 508             lf.sendToken(ship.getDock("out").getDataDestination(), new BitVector(1).set(0));
 509             lf.setPredicate(Predicate.FlagA);
 510             lf.sendToken(ship.getDock("out").getDataDestination(), new BitVector(1).set(1));
 511             lf.setPredicate(null);
 512             lf.deliver();
 513         }
 514     }
 515
 516     public static void main(String[] s) throws Exception {
 517         Fleet fleet = new Fpga();
 518         //Fleet fleet = new Interpreter(false);
 519
 520         Random random = new Random(System.currentTimeMillis());
 521         long[] vals = new long[256];
 522         for(int i=0; i<vals.length; i++) {
 523             vals[i] = Math.abs(random.nextInt());
 524         }
 525
 526         Ship mem1 = fleet.getShip("Memory", 0);
 527         Ship mem2 = fleet.getShip("Memory", 1);
 528         //Ship mem2 = fleet.getShip("DDR2", 0);
 529
 530         FleetProcess fp;
 531         int stride = 1;
 532         fp = null;
 533
 534         fp = fleet.run(new Instruction[0]);
 535         MemoryUtils.writeMem(fp, mem1, 0, vals);
 536         int vals_length = vals.length;
 537
 538         // Disable readback/writeback inside the loop
 539         vals = null;
 540
 541         while(stride < vals_length) {
 542
 543             // reset the FleetProcess
 544             //fp.terminate(); fp = null;
 545
 546             System.out.println("stride " + stride);
 547
 548             // if we reset the FleetProcess, restart it
 549             if (fp==null) fp = fleet.run(new Instruction[0]);
 550
 551             // do the mergeSort
 552             vals = mergeSort(fp, fleet, vals, vals_length, stride, mem1, mem2);
 553
 554             // verify the cleanup
 555             //CleanupUtils.verifyClean(fp);
 556
 557             Ship mem = mem1; mem1=mem2; mem2=mem;
 558
 559             stride = stride * 2;
 560             System.out.println();
 561         }
 562
 563         BitVector[] bvs = new BitVector[vals_length];
 564         MemoryUtils.readMem(fp, mem1, 0, bvs);
 565         System.out.println("results:");
 566         for(int i=0; i<vals_length; i++)
 567             System.out.println(bvs[i].toLong());
 568     }
 569
 570
 571     public static long[] mergeSort(FleetProcess fp, Fleet fleet,
 572                                    long[] vals, int vals_length, int stride_length,
 573                                    Ship memoryShip1, Ship memoryShip2) throws Exception {
 574
 575         if (vals != null) {
 576             BitVector[] mem = new BitVector[vals_length];
 577             for(int i=0; i<mem.length; i++) mem[i] = new BitVector(fleet.getWordWidth()).set(vals[i]);
 578             MemoryUtils.writeMem(fp, memoryShip1, 0, mem);
 579         }
 580
 581         //////////////////////////////////////////////////////////////////////////////
 582
 583         DataFlowGraph proc = new DataFlowGraph(fleet);
 584         DebugNode dm = new DebugNode(proc);
 585
 586         int end_of_data = vals_length;
 587         int num_strides = end_of_data / (stride_length * 2);
 588
 589         MemoryNode mm  = new MemoryNode(proc, memoryShip1);
 590         SortedMergeNode sm = new SortedMergeNode(proc);
 591
 592         // So far: we have four spare Counter ships; one can be used for resetting
 593         for(int i=0; i<2; i++) {
 594
 595             DownCounterNode c0 = new DownCounterNode(proc);
 596             DownCounterNode c1 = new DownCounterNode(proc);
 597
 598             c0.start.connect(new ForeverNode(proc, stride_length).out);
 599             c0.incr.connect(new ForeverNode(proc, 1).out);
 600
 601             c1.start.connect(new OnceNode(proc, end_of_data + i*stride_length).out);
 602             c1.incr.connect(new OnceNode(proc, stride_length*2).out);
 603
 604             RepeatNode r1 = new RepeatNode(proc);
 605             r1.val.connect(c1.out);
 606             r1.count.connect(new ForeverNode(proc, stride_length).out);
 607
 608             AluNode alu = new AluNode(proc);
 609             alu.in1.connect(r1.out);
 610             alu.in2.connect(c0.out);
 611             alu.inOp.connect(new ForeverNode(proc, ((Node.DockInPort)alu.inOp).getConstant("ADD")).out);
 612             alu.out.connect(i==0 ? mm.inAddrRead1 : mm.inAddrRead2);
 613
 614             PunctuatorNode punc = new PunctuatorNode(proc, -1);
 615             punc.count.connect(new ForeverNode(proc, stride_length).out);
 616             punc.val.connect(i==0 ? mm.outRead1 : mm.outRead2);
 617             punc.out.connect(i==0 ? sm.in1 : sm.in2);
 618         }
 619
 620         UnPunctuatorNode unpunc = new UnPunctuatorNode(proc);
 621         unpunc.val.connect(sm.out);
 622         unpunc.count.connect(new ForeverNode(proc, 2*stride_length).out);
 623
 624         DownCounterNode cw = new DownCounterNode(proc);
 625         cw.start.connect(new OnceNode(proc, end_of_data).out);
 626         cw.incr.connect(new OnceNode(proc, 1).out);
 627
 628         MemoryNode mm2 = new MemoryNode(proc, memoryShip2);
 629         mm2.inAddrWrite.connect(cw.out);
 630         mm2.inDataWrite.connect(unpunc.out);
 631         mm2.outWrite.connect(dm.in);
 632
 633         //////////////////////////////////////////////////////////////////////////////
 634
 635         Context ctx = new Context(fp.getFleet());
 636         ctx.setAutoflush(true);
 637
 638         ArrayList<Instruction> ai = new ArrayList<Instruction>();
 639         proc.build(ctx);
 640         ctx.emit(ai);
 641         for(Instruction ins : ai) {
 642             //System.out.println(ins);
 643             fp.sendInstruction(ins);
 644         }
 645         fp.flush();
 646
 647         for(int i=0; i<vals_length; i++) {
 648             System.out.print("\rreading back... " + i+"/"+vals_length+"  ");
 649             BitVector rec = fp.recvWord();
 650             System.out.print(" (prev result: " + rec + " = " + rec.toLong() + ")");
 651         }
 652         System.out.println("\rdone.                                                                    ");
 653
 654         //if (true) return ret;
 655
 656         Context ctx2 = new Context(fp.getFleet());
 657         Dock debugIn = fleet.getShip("Debug",0).getDock("in");
 658         Dock fred = debugIn;
 659         fp.sendToken(debugIn.getInstructionDestination());
 660         fp.flush();
 661
 662         LoopFactory lf = new LoopFactory(ctx2, debugIn, 0);
 663         lf.literal(0);
 664         lf.abortLoopIfTorpedoPresent();
 665         lf.recvToken();
 666         lf.deliver();
 667
 668         ctx2.dispatch(fp);
 669         fp.flush();
 670
 671         int count = 0;
 672
 673         Ship counter = proc.pool.allocateShip("Counter");
 674
 675         for(int phase=0; phase<=3; phase++) {
 676             System.out.println("== phase "+phase+" ==================================================================");
 677             ctx2 = new Context(fp.getFleet());
 678
 679             Destination ackDestination = counter.getDock("in2").getDataDestination();
 680             proc.reset(ctx2, phase, ackDestination);
 681
 682             Context ctx3 = new Context(fp.getFleet());
 683             lf = new LoopFactory(ctx3, counter.getDock("inOp"), 1);
 684             lf.literal("DROP_C1_V2");
 685             lf.deliver();
 686             lf.literal(5);
 687             lf.deliver();
 688             lf = new LoopFactory(ctx3, counter.getDock("in1"), 1);
 689             lf.literal(reset_count-1);
 690             lf.deliver();
 691             lf.literal(1);
 692             lf.deliver();
 693             lf = new LoopFactory(ctx3, counter.getDock("in2"), 0);
 694             lf.abortLoopIfTorpedoPresent();
 695             lf.recvWord();
 696             lf.deliver();
 697             lf = new LoopFactory(ctx3, counter.getDock("out"), 1);
 698             lf.collectWord();
 699             lf.sendToken(counter.getDock("in2").getInstructionDestination());  // HACK: we don't check to make sure this hits
 700             lf.sendToken(debugIn.getDataDestination());
 701             ctx3.dispatch(fp);  // HACK: we don't check to make sure that this is "firmly in place"
 702
 703             for(Dock dock : torpedoes) fp.sendToken(dock.getInstructionDestination());
 704             ctx2.dispatch(fp);
 705             fp.flush();
 706             System.out.println("flushed");
 707
 708             fp.recvWord();
 709             System.out.println("phase done");
 710
 711             System.out.println();
 712         }
 713
 714         fp.sendToken(debugIn.getInstructionDestination());
 715         fp.flush();
 716
 717         //System.out.println("verifying cleanup:");
 718         //CleanupUtils.verifyClean(fp);
 719
 720         System.out.println("reading back:");
 721         long[] ret = null;
 722         if (vals != null) {
 723             ret = new long[vals_length];
 724             BitVector[] mem = new BitVector[vals_length];
 725             MemoryUtils.readMem(fp, memoryShip2, 0, mem);
 726             for(int i=0; i<ret.length; i++) ret[i] = mem[i].toLong();
 727         }
 728         return ret;
 729     }
 730
 731     private BitVector[] longsToBitVectors(long[] initialValues) {
 732         BitVector[] bv = new BitVector[initialValues.length];
 733         for(int i=0; i<initialValues.length; i++)
 734             bv[i] = new BitVector(fleet.getWordWidth()).set(initialValues[i]);
 735         return bv;
 736     }
 737 }
 738
 739