src/edu/berkeley/fleet/ir/Process.java

   1 package edu.berkeley.fleet.ir;
   2 import java.util.concurrent.Semaphore;
   3 import java.util.*;
   4 import java.net.*;
   5 import edu.berkeley.fleet.two.*;
   6 import edu.berkeley.fleet.api.*;
   7 import edu.berkeley.fleet.fpga.*;
   8 import edu.berkeley.fleet.api.Instruction.*;
   9 import edu.berkeley.fleet.api.Instruction.Set;
  10 import edu.berkeley.fleet.api.Instruction.Set.*;
  11 import static edu.berkeley.fleet.api.Predicate.*;
  12 import static edu.berkeley.fleet.util.BitManipulations.*;
  13
  14
  15 /*
  16   - refactor the cleanup into the subclasses of Port (phase1, phase2, etc)
  17 */
  18
  19 // does peer.recvWord() have to honor the currently-set predicate?
  20
  21 // public class ReplaceModule extends Module { }
  22 // public class CountMergeModule extends Module { }
  23 // public class SortMergeModule extends Module { }
  24 // public class FanOutModule extends Module { }
  25 // public class MemoryModule extends Module { }
  26 // public class DoneModule extends Module { }
  27
  28 public class Process {
  29
  30
  31     public static int reset_count = 0;
  32     public static HashSet<Dock> torpedoes = new HashSet<Dock>();
  33
  34     public final Fleet    fleet;
  35     public final ShipPool pool;
  36
  37     public Process(Fleet fleet) {
  38         this.fleet = fleet;
  39         this.pool  = new ShipPool(fleet);
  40     }
  41
  42     private HashSet<Module> modules = new HashSet<Module>();
  43
  44     public void build(Context ctx) {
  45         for(Module mod : modules)
  46             mod.build(ctx);
  47     }
  48     public void reset(Context ctx, int phase, Destination ackDestination) {
  49         reset_count = 0;
  50         torpedoes.clear();
  51         for(Module mod : modules)
  52             mod.reset(ctx, phase, ackDestination);
  53     }
  54
  55     public class Module {
  56
  57         void doReset(Context ctx, int phase, Dock dock, Port peer, Destination ackDestination, boolean peerUsed) {
  58             if (dock.getShip().getType().equals("Debug")) return;
  59
  60             switch(phase) {
  61
  62                 // Phase 0: torpedo every output dock, put it in
  63                 // collecting mode.  Cannot combine with phase 1,
  64                 // because until output docks are in vacuum mode we
  65                 // cannot be sure that the tokens to the input docks
  66                 // will eventually succeed.  This may cause the
  67                 // instructions sent after the tokens to back up into
  68                 // the switch fabric.
  69                 case 0: {
  70                     if (!dock.isInputDock()) {
  71                         torpedoes.add(dock);
  72                         Context.LoopFactory lf = ctx.new LoopFactory(dock, 1);
  73                         lf.sendToken(ackDestination);
  74                         lf = lf.makeNext(0);
  75                         lf.abortLoopIfTorpedoPresent();
  76                         lf.collectWord();
  77                         reset_count++;
  78                     }
  79                     break;
  80                 }
  81
  82                 // Phase 1: torpedo every input dock, put it in loopback mode
  83                 case 1: {
  84                     if (dock.isInputDock()) {
  85                         torpedoes.add(dock);
  86                         Context.LoopFactory lf = ctx.new LoopFactory(dock, 1);
  87                         lf.sendToken(ackDestination);
  88
  89                         // FIXME: this won't work right for ports that
  90                         // get "shared" by two senders (for example,
  91                         // inAddrRead1/2)
  92
  93                         if (peerUsed && peer!=null) {
  94                             lf = lf.makeNext(0);
  95                             lf.abortLoopIfTorpedoPresent();
  96                             ((OutPort)peer).recvWord(lf);
  97                             ((OutPort)peer).sendToken(lf);
  98                         }
  99                         reset_count++;
 100                     }
 101                     break;
 102                 }
 103
 104                 // Phase 2: torpedo every output dock, have it absorb tokens
 105                 case 2: {
 106                     if (!dock.isInputDock()) {
 107                         torpedoes.add(dock);
 108                         Context.LoopFactory lf = ctx.new LoopFactory(dock, 1);
 109                         if (peer != null)
 110                             for(int i=0; i<((InPort)peer).getTokensToAbsorb(); i++)
 111                                 lf.recvToken();
 112                         lf.sendToken(ackDestination);
 113                         reset_count++;
 114                     }
 115                     break;
 116                 }
 117
 118                 // Phase 3: torpedo every input dock, and we're done
 119                 case 3: {
 120                     if (dock.isInputDock()) {
 121                         if (peerUsed && peer!=null) {
 122                             torpedoes.add(dock);
 123                         }
 124                         Context.LoopFactory lf = ctx.new LoopFactory(dock, 1);
 125                         lf.sendToken(ackDestination);
 126                         reset_count++;
 127                     }
 128                     break;
 129                 }
 130
 131
 132             }
 133         }
 134
 135         public Module() {
 136             Process.this.modules.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 (Module.this.ports.get(name)!=null) throw new RuntimeException();
 154                 Module.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(Context.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(Context.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(Context.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(Context.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(Context.LoopFactory lf) { lf.recvToken(); }
 211             public void sendWord(Context.LoopFactory lf) { lf.sendWord(dock.getDataDestination()); }
 212             public void build(Context ctx) { build(ctx, ctx.new LoopFactory(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, Context.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);
 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         }
 256
 257         public /*final*/ class DockOutPort extends OutPort {
 258             public final Dock dock;
 259             public final int count;
 260             public DockOutPort(String name, Dock dock) { this(name, dock, 0); }
 261             public DockOutPort(String name, Dock dock, int count) { super(name); this.dock = dock; this.count = count; }
 262             public void sendToken(Context.LoopFactory lf) { lf.sendToken(dock.getDataDestination()); }
 263             public void recvWord(Context.LoopFactory lf) { lf.recvWord(); }
 264             public void build(Context ctx) { build(ctx, ctx.new LoopFactory(dock, 1)); }
 265             protected void build(Context ctx, Context.LoopFactory lf) {
 266                 if (peer==null) return;
 267                 lf = lf.makeNext(count);
 268                 lf.abortLoopIfTorpedoPresent();
 269                 peer.recvToken(lf);
 270                 lf.collectWord();
 271                 peer.sendWord(lf);
 272             }
 273             public void reset(Context ctx, int phase, Destination ackDestination) {
 274                 doReset(ctx, phase, dock, peer, ackDestination, true);
 275             }
 276         }
 277     }
 278
 279     private static BitVector bv(long l) { return new BitVector(/*FIXME fleet.getWordWidth()*/37).set(l); }
 280     private static BitVector[] bv(long[] l) {
 281         BitVector[] ret = new BitVector[l.length];
 282         for(int i=0; i<ret.length; i++) ret[i] = bv(l[i]);
 283         return ret;
 284     }
 285
 286     /**
 287      *  Deliver the constant at out forever.  Flow control in<->out is
 288      *  maintained, but out is not flow-controlled, so be sure
 289      *  that every datum sent there is consumed synchronously wiht
 290      *  data items sent to out.
 291      */
 292     public class ForeverModule extends Module {
 293         private BitVector bv;
 294         public final OutPort out = new OutPort("out") {
 295                 public void sendToken(Context.LoopFactory lf) { }
 296                 public void recvWord(Context.LoopFactory lf) { }
 297                 public void build(Context ctx) { }
 298                 public void reset(Context ctx, int phase, Destination ackDestination) { }
 299                 public void setPeer(InPort peer) {
 300                     this.peer = peer;
 301                     DockInPort pip = ((DockInPort)peer);
 302                     for(int i=0; i<pip.pattern.length; i++) {
 303                         if (pip.pattern[i]==null)
 304                             pip.pattern[i] = bv;
 305                     }
 306                 }
 307             };
 308         public ForeverModule(long l) { this(new BitVector(fleet.getWordWidth()).set(l)); }
 309         public ForeverModule(final BitVector bv) { this.bv = bv; }
 310     }
 311
 312     public class OnceModule extends Module {
 313         private BitVector bv;
 314         public final OutPort out = new OutPort("out") {
 315                 public void sendToken(Context.LoopFactory lf) { }
 316                 public void recvWord(Context.LoopFactory lf) { }
 317                 public void build(Context ctx) { }
 318                 public void reset(Context ctx, int phase, Destination ackDestination) { }
 319                 public void setPeer(InPort peer) {
 320                     this.peer = peer;
 321                     DockInPort pip = ((DockInPort)peer);
 322                     BitVector[] pip_pattern = pip.pattern;
 323                     BitVector[] temp = new BitVector[pip_pattern.length * 2];
 324                     int j = 0;
 325                     int i = 0;
 326                     boolean done = false;
 327                     // FIXME: if peer.count is already 1, this gets simpler and different
 328                     for(i=0; i<temp.length; i++) {
 329                         if (pip_pattern[j] != null) {
 330                             temp[i] = pip_pattern[j];
 331                         } else {
 332                             if (done) break;
 333                             done = true;
 334                             temp[i] = bv;
 335                         }
 336                         j++;
 337                         if (j >= pip_pattern.length) j = 0;
 338                     }
 339                     pip.pattern = new BitVector[i];
 340                     System.arraycopy(temp, 0, pip.pattern, 0, i);
 341                     pip.count = 1;
 342                 }
 343             };
 344         public OnceModule(long l) { this(new BitVector(fleet.getWordWidth()).set(l)); }
 345         public OnceModule(final BitVector bv) { this.bv = bv; }
 346     }
 347
 348     public class DebugModule extends Module {
 349         public final Ship ship = pool.allocateShip("Debug");
 350         public final InPort in = new DockInPort("in", ship.getDock("in"));
 351         // NOTE: shutdown needs to treat this specially
 352         public DebugModule() { }
 353     }
 354
 355     public class UnPunctuatorModule extends Module {
 356         private final Ship    ship  = pool.allocateShip("Counter");
 357         public  final OutPort out   = new DockOutPort("out", ship.getDock("out"));
 358         public  final InPort  val   = new DockInPort("in1",  ship.getDock("in1"));
 359         public  final InPort  count = new DockInPort("in2",  ship.getDock("in2"), 0, new BitVector[] { null, bv(1) });
 360         public  final InPort  op    = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(6 /*PASS_C2_V1*/), bv(10 /*DROP_C2_V1*/) } );
 361         public UnPunctuatorModule() { }
 362     }
 363
 364     public class PunctuatorModule extends Module {
 365         private final long    punc;
 366         private final Ship    ship  = pool.allocateShip("Counter");
 367         public  final OutPort out   = new DockOutPort("out", ship.getDock("out"));
 368         public  final InPort  val   = new DockInPort("in1",  ship.getDock("in1"));
 369         public  final InPort  op    = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(6 /*PASS_C2_V1*/), bv(7 /*PASS_C2_V2*/) } );
 370         public  final InPort  count;
 371         public PunctuatorModule(long punc) {
 372             this.punc = punc;
 373             this.count = new DockInPort("in2",  ship.getDock("in2"), 0, new BitVector[] { null, bv(1), bv(punc) });
 374         }
 375     }
 376
 377     public class AluModule extends Module {
 378         public final Ship    ship = pool.allocateShip("Alu");
 379         public final InPort  in1 = new DockInPort("in1",  ship.getDock("in1"));
 380         public final InPort  in2 = new DockInPort("in2",  ship.getDock("in2"));
 381         public final InPort  inOp = new DockInPort("inOp", ship.getDock("inOp"));
 382         public final OutPort out  = new DockOutPort("out", ship.getDock("out"));
 383         public AluModule() { }
 384     }
 385
 386     public class DownCounterModule extends Module {
 387         public final Ship    ship  = pool.allocateShip("Counter");
 388         public final InPort  start = new DockInPort("in1",  ship.getDock("in1"));
 389         public final InPort  incr  = new DockInPort("in2",  ship.getDock("in2"));
 390         public final InPort  inOp  = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(12 /*COUNTDOWN*/) });
 391         public final OutPort out   = new DockOutPort("out", ship.getDock("out"));
 392         public DownCounterModule() { }
 393     }
 394
 395     public class RepeatModule extends Module {
 396         public final Ship    ship   = pool.allocateShip("Counter");
 397         public final InPort  count  = new DockInPort("in1",  ship.getDock("in1"));
 398         public final InPort  val    = new DockInPort("in2",  ship.getDock("in2"));
 399         public final InPort  inOP   = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(1 /*REPEAT_C1_V2*/) });
 400         public final OutPort out    = new DockOutPort("out", ship.getDock("out"));
 401         public RepeatModule() { }
 402     }
 403
 404     public class SortedMergeModule extends Module {
 405         public final Ship    ship = pool.allocateShip("Alu");
 406         public final InPort  in1  = new DockInPort("in1",  ship.getDock("in1"));
 407         public final InPort  in2  = new DockInPort("in2",  ship.getDock("in2"));
 408         public final InPort  inOp = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(9 /*MAXMERGE*/) });
 409         public final OutPort out  = new DockOutPort("out", ship.getDock("out"));
 410         public SortedMergeModule() { }
 411     }
 412
 413     public class MemoryModule extends Module {
 414         public final Ship    ship;
 415         public final InPort  inCBD;
 416         public final InPort  inAddrRead1;
 417         public final InPort  inAddrRead2;
 418         public final InPort  inAddrWrite;
 419         public final InPort  inDataWrite;
 420         public final OutPort outRead1;
 421         public final OutPort outRead2;
 422         public final OutPort outWrite;
 423         public MemoryModule(Ship memoryShip) {
 424             this.ship = memoryShip;
 425             this.inCBD        = ship.getType().equals("Memory") ? new DockInPort("inCBD", ship.getDock("inCBD")) : null;
 426             this.inAddrWrite  = new DockInPort("inAddrWrite", ship.getDock("inAddrWrite"));
 427             this.inDataWrite  = new DockInPort("inDataWrite", ship.getDock("inDataWrite"));
 428             this.inAddrRead1  = new InPort("inAddrRead1") {
 429                     public void recvToken(Context.LoopFactory lf) { lf.recvToken(); }
 430                     public void sendWord(Context.LoopFactory lf) { lf.sendWord(ship.getDock("inAddrRead").getDataDestination(), new BitVector(1).set(0)); }
 431                     public void build(Context ctx) { }
 432                     public int getTokensToAbsorb() { return outRead1.peer.getTokensToAbsorb(); }
 433                     public void reset(Context ctx, int phase, Destination ackDestination) {
 434                         doReset(ctx, phase, ship.getDock("inAddrRead"), null, ackDestination, false);
 435                     }
 436                 };
 437             this.inAddrRead2  = new InPort("inAddrRead2") {
 438                     public void recvToken(Context.LoopFactory lf) { lf.recvToken(); }
 439                     public void sendWord(Context.LoopFactory lf) { lf.sendWord(ship.getDock("inAddrRead").getDataDestination(), new BitVector(1).set(1)); }
 440                     public void build(Context ctx) { }
 441                     public int getTokensToAbsorb() { return outRead2.peer.getTokensToAbsorb(); }
 442                     public void reset(Context ctx, int phase, Destination ackDestination) { }
 443                 };
 444             this.outRead1 = new OutPort("outRead1") {
 445                     public void sendToken(Context.LoopFactory lf) { inAddrRead1.peer.sendToken(lf); }
 446                     public void recvWord(Context.LoopFactory lf) { lf.recvWord(); }
 447                     public void build(Context ctx) { }
 448                     public void reset(Context ctx, int phase, Destination ackDestination) { }
 449                 };
 450             this.outRead2 = new OutPort("outRead2") {
 451                     public void sendToken(Context.LoopFactory lf) { inAddrRead2.peer.sendToken(lf); }
 452                     public void recvWord(Context.LoopFactory lf) { lf.recvWord(); }
 453                     public void build(Context ctx) { }
 454                     public void reset(Context ctx, int phase, Destination ackDestination) { }
 455                 };
 456             this.outWrite = new DockOutPort("out", ship.getDock("out")) {
 457                     protected void build(Context ctx, Context.LoopFactory lf) {
 458                         lf = lf.makeNext(0);
 459                         lf.abortLoopIfTorpedoPresent();
 460                         lf.collectWord();
 461
 462                         lf.setFlags(FlagFunction.ZERO, FlagFunction.ZERO.add(FlagC));
 463                         if (this.peer != null) {
 464                             lf.setPredicate(Predicate.FlagB);
 465                             lf.literal(77);
 466                             lf.abortLoopIfTorpedoPresent();
 467                             this.peer.recvToken(lf);
 468                             this.peer.sendWord(lf);
 469                         }
 470
 471                         lf.setPredicate(Predicate.NotFlagB);
 472                         lf.abortLoopIfTorpedoPresent();
 473                         lf.recvToken();
 474                         lf.setFlags(FlagFunction.ZERO.add(NotFlagC).add(FlagB), FlagFunction.ZERO.add(FlagC).add(FlagB));
 475                         if (outRead1.peer != null) {
 476                             lf.setPredicate(Predicate.NotFlagB);
 477                             outRead1.peer.sendWord(lf);
 478                         }
 479                         if (outRead2.peer != null) {
 480                             lf.setPredicate(Predicate.NotFlagA);
 481                             outRead2.peer.sendWord(lf);
 482                         }
 483                         lf.setPredicate(null);
 484                     }
 485                 };
 486         }
 487         public void build(Context ctx) {
 488             super.build(ctx);
 489             Context.LoopFactory lf;
 490
 491             lf = ctx.new LoopFactory(ship.getDock("inAddrRead"), 0);
 492             lf.abortLoopIfTorpedoPresent();
 493             lf.recvWord();
 494             lf.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO);
 495             lf.setPredicate(Predicate.NotFlagA);
 496             lf.sendToken(ship.getDock("out").getDataDestination(), new BitVector(1).set(0));
 497             lf.setPredicate(Predicate.FlagA);
 498             lf.sendToken(ship.getDock("out").getDataDestination(), new BitVector(1).set(1));
 499             lf.setPredicate(null);
 500             lf.deliver();
 501         }
 502     }
 503
 504     public static void main(String[] s) throws Exception {
 505         Fleet fleet = new Fpga();
 506         //Fleet fleet = new Interpreter(false);
 507
 508         Random random = new Random(System.currentTimeMillis());
 509         long[] vals = new long[256];
 510         for(int i=0; i<vals.length; i++) {
 511             vals[i] = Math.abs(random.nextInt());
 512         }
 513
 514         Ship mem1 = fleet.getShip("Memory", 0);
 515         Ship mem2 = fleet.getShip("Memory", 1);
 516         //Ship mem2 = fleet.getShip("DDR2", 0);
 517
 518         FleetProcess fp;
 519         int stride = 1;
 520         fp = null;
 521
 522         fp = fleet.run(new Instruction[0]);
 523         Gadgets.writeMem(fp, mem1, 0, bv(vals));
 524         int vals_length = vals.length;
 525
 526         // Disable readback/writeback inside the loop
 527         vals = null;
 528
 529         while(stride < vals_length) {
 530
 531             // reset the FleetProcess
 532             //fp.terminate(); fp = null;
 533
 534             System.out.println("stride " + stride);
 535
 536             // if we reset the FleetProcess, restart it
 537             if (fp==null) fp = fleet.run(new Instruction[0]);
 538
 539             // do the mergeSort
 540             vals = mergeSort(fp, fleet, vals, vals_length, stride, mem1, mem2);
 541
 542             // verify the cleanup
 543             //verifyClean(fp);
 544
 545             Ship mem = mem1; mem1=mem2; mem2=mem;
 546
 547             stride = stride * 2;
 548             System.out.println();
 549         }
 550
 551         BitVector[] bvs = new BitVector[vals_length];
 552         Gadgets.readMem(fp, mem1, 0, bvs);
 553         System.out.println("results:");
 554         for(int i=0; i<vals_length; i++)
 555             System.out.println(bvs[i].toLong());
 556     }
 557
 558     // FIXME: check for "lingering" torpedoes?
 559     public static void verifyClean(FleetProcess fp) {
 560         Ship debug   = fp.getFleet().getShip("Debug", 0);
 561         Dock debugIn = debug.getDock("in");
 562
 563         Context ctx;
 564         Context.LoopFactory lf;
 565
 566         ctx = new Context(fp.getFleet());
 567         lf = ctx.new LoopFactory(debugIn, 1);
 568         lf.literal(12);
 569         lf.deliver();
 570         lf.literal(5);
 571         lf.deliver();
 572         Gadgets.dispatch(fp, ctx);
 573         fp.flush();
 574
 575         System.out.println("checking debug.in");
 576         if (fp.recvWord().toLong() != 12) throw new RuntimeException("debug dock not properly initialized");
 577         if (fp.recvWord().toLong() != 5)  throw new RuntimeException("debug dock not properly initialized");
 578
 579         long k = 0;
 580         for(Ship ship : fp.getFleet())
 581             if (!"Debug".equals(ship.getType()))
 582                 for (Dock dock : ship) {
 583                     System.out.print("checking " + dock + "                     ");
 584
 585                     k = (k + 23) % 65535;
 586                     ctx = new Context(fp.getFleet());
 587
 588                     boolean reverse = (k%2)==0;
 589
 590                     lf = ctx.new LoopFactory(debugIn, 4);
 591                     lf.recvToken();
 592                     lf.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO);
 593                     lf.setPredicate(Predicate.NotFlagA);
 594                     lf.literal(k);
 595                     lf.setPredicate(Predicate.FlagA);
 596                     lf.literal(k+1);
 597                     lf.setPredicate(null);
 598                     lf.deliver();
 599
 600                     lf = ctx.new LoopFactory(dock, 1);
 601                     lf.sendToken(debugIn.getDataDestination(), new BitVector(1).set(reverse ? 1 : 0));
 602                     lf.sendToken(debugIn.getDataDestination(), new BitVector(1).set(reverse ? 0 : 1));
 603                     lf.sendToken(dock.getDataDestination(), new BitVector(1).set(reverse ? 1 : 0));
 604                     lf.sendToken(dock.getDataDestination(), new BitVector(1).set(reverse ? 0 : 1));
 605                     lf = lf.makeNext(2);
 606
 607                     // if a torpedo was lying in wait, the problem will be manifest as a "freezup"
 608                     lf.abortLoopIfTorpedoPresent();
 609
 610                     lf.recvToken();
 611                     lf.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO);
 612                     lf.setPredicate(Predicate.NotFlagA);
 613                     lf.sendToken(debugIn.getDataDestination(), new BitVector(1).set(0));
 614                     lf.setPredicate(Predicate.FlagA);
 615                     lf.sendToken(debugIn.getDataDestination(), new BitVector(1).set(1));
 616                     lf.setPredicate(null);
 617
 618                     Gadgets.dispatch(fp, ctx);
 619                     fp.flush();
 620
 621                     long kk;
 622                     for(int i=0; i<4; i++) {
 623                         kk = fp.recvWord().toLong();
 624                         System.out.print("\rchecking " + dock + " (got "+(i+1)+")");
 625                         if (kk != ((reverse ^ (i%2!=0)) ? k+1 : k)) {
 626                             System.out.println();
 627                             throw new RuntimeException(dock+" not properly initialized ("+(i+1)+")");
 628                         }
 629                     }
 630                     System.out.println();
 631                 }
 632     }
 633
 634     public static long[] mergeSort(FleetProcess fp, Fleet fleet,
 635                                    long[] vals, int vals_length, int stride_length,
 636                                    Ship memoryShip1, Ship memoryShip2) throws Exception {
 637
 638         if (vals != null) {
 639             BitVector[] mem = new BitVector[vals_length];
 640             for(int i=0; i<mem.length; i++) mem[i] = new BitVector(fleet.getWordWidth()).set(vals[i]);
 641             Gadgets.writeMem(fp, memoryShip1, 0, mem);
 642         }
 643
 644         //////////////////////////////////////////////////////////////////////////////
 645
 646         Process proc = new Process(fleet);
 647         DebugModule dm = proc.new DebugModule();
 648
 649         int end_of_data = vals_length;
 650         int num_strides = end_of_data / (stride_length * 2);
 651
 652         MemoryModule mm  = proc.new MemoryModule(memoryShip1);
 653         SortedMergeModule sm = proc.new SortedMergeModule();
 654
 655         // So far: we have four spare Counter ships; one can be used for resetting
 656         for(int i=0; i<2; i++) {
 657
 658             DownCounterModule c0 = proc.new DownCounterModule();
 659             DownCounterModule c1 = proc.new DownCounterModule();
 660
 661             c0.start.connect(proc.new ForeverModule(stride_length).out);
 662             c0.incr.connect(proc.new ForeverModule(1).out);
 663
 664             c1.start.connect(proc.new OnceModule(end_of_data + i*stride_length).out);
 665             c1.incr.connect(proc.new OnceModule(stride_length*2).out);
 666
 667             RepeatModule r1 = proc.new RepeatModule();
 668             r1.val.connect(c1.out);
 669             r1.count.connect(proc.new ForeverModule(stride_length).out);
 670
 671             AluModule alu = proc.new AluModule();
 672             alu.in1.connect(r1.out);
 673             alu.in2.connect(c0.out);
 674             alu.inOp.connect(proc.new ForeverModule(2).out);  // ADD
 675             alu.out.connect(i==0 ? mm.inAddrRead1 : mm.inAddrRead2);
 676
 677             PunctuatorModule punc = proc.new PunctuatorModule(-1);
 678             punc.count.connect(proc.new ForeverModule(stride_length).out);
 679             punc.val.connect(i==0 ? mm.outRead1 : mm.outRead2);
 680             punc.out.connect(i==0 ? sm.in1 : sm.in2);
 681         }
 682
 683         UnPunctuatorModule unpunc = proc.new UnPunctuatorModule();
 684         unpunc.val.connect(sm.out);
 685         unpunc.count.connect(proc.new ForeverModule(2*stride_length).out);
 686
 687         DownCounterModule cw = proc.new DownCounterModule();
 688         cw.start.connect(proc.new OnceModule(end_of_data).out);
 689         cw.incr.connect(proc.new OnceModule(1).out);
 690
 691         MemoryModule mm2 = proc.new MemoryModule(memoryShip2);
 692         mm2.inAddrWrite.connect(cw.out);
 693         mm2.inDataWrite.connect(unpunc.out);
 694         mm2.outWrite.connect(dm.in);
 695
 696         //////////////////////////////////////////////////////////////////////////////
 697
 698         Context ctx = new Context(fp.getFleet());
 699         ctx.setAutoflush(true);
 700
 701         ArrayList<Instruction> ai = new ArrayList<Instruction>();
 702         proc.build(ctx);
 703         ctx.emit(ai);
 704         for(Instruction ins : ai) {
 705             //System.out.println(ins);
 706             fp.sendInstruction(ins);
 707         }
 708         fp.flush();
 709
 710         for(int i=0; i<vals_length; i++) {
 711             System.out.print("\rreading back... " + i+"/"+vals_length+"  ");
 712             BitVector rec = fp.recvWord();
 713             System.out.print(" (prev result: " + rec + " = " + rec.toLong() + ")");
 714         }
 715         System.out.println("\rdone.                                                                    ");
 716
 717         //if (true) return ret;
 718
 719         Context ctx2 = new Context(fp.getFleet());
 720         Dock debugIn = fleet.getShip("Debug",0).getDock("in");
 721         Dock fred = debugIn;
 722         fp.sendToken(debugIn.getInstructionDestination());
 723         fp.flush();
 724
 725         Context.LoopFactory lf = ctx2.new LoopFactory(debugIn, 0);
 726         lf.literal(0);
 727         lf.abortLoopIfTorpedoPresent();
 728         lf.recvToken();
 729         lf.deliver();
 730
 731         Gadgets.dispatch(fp, ctx2);
 732         fp.flush();
 733
 734         int count = 0;
 735
 736         Ship counter = proc.pool.allocateShip("Counter");
 737
 738         for(int phase=0; phase<=3; phase++) {
 739             System.out.println("== phase "+phase+" ==================================================================");
 740             ctx2 = new Context(fp.getFleet());
 741
 742             Destination ackDestination = counter.getDock("in2").getDataDestination();
 743             proc.reset(ctx2, phase, ackDestination);
 744
 745             Context ctx3 = new Context(fp.getFleet());
 746             lf = ctx3.new LoopFactory(counter.getDock("inOp"), 1);
 747             lf.literal(9);
 748             lf.deliver();
 749             lf.literal(5);
 750             lf.deliver();
 751             lf = ctx3.new LoopFactory(counter.getDock("in1"), 1);
 752             lf.literal(reset_count-1);
 753             lf.deliver();
 754             lf.literal(1);
 755             lf.deliver();
 756             lf = ctx3.new LoopFactory(counter.getDock("in2"), 0);
 757             lf.abortLoopIfTorpedoPresent();
 758             lf.recvWord();
 759             lf.deliver();
 760             lf = ctx3.new LoopFactory(counter.getDock("out"), 1);
 761             lf.collectWord();
 762             lf.sendToken(counter.getDock("in2").getInstructionDestination());  // HACK: we don't check to make sure this hits
 763             lf.sendToken(debugIn.getDataDestination());
 764             Gadgets.dispatch(fp, ctx3);  // HACK: we don't check to make sure that this is "firmly in place"
 765
 766             for(Dock dock : torpedoes) fp.sendToken(dock.getInstructionDestination());
 767             Gadgets.dispatch(fp, ctx2);
 768             fp.flush();
 769             System.out.println("flushed");
 770
 771             fp.recvWord();
 772             System.out.println("phase done");
 773
 774             System.out.println();
 775         }
 776
 777         fp.sendToken(debugIn.getInstructionDestination());
 778         fp.flush();
 779
 780         //System.out.println("verifying cleanup:");
 781         //verifyClean(fp);
 782
 783         System.out.println("reading back:");
 784         long[] ret = null;
 785         if (vals != null) {
 786             ret = new long[vals_length];
 787             BitVector[] mem = new BitVector[vals_length];
 788             Gadgets.readMem(fp, memoryShip2, 0, mem);
 789             for(int i=0; i<ret.length; i++) ret[i] = mem[i].toLong();
 790         }
 791         return ret;
 792     }
 793
 794     private BitVector[] longsToBitVectors(long[] initialValues) {
 795         BitVector[] bv = new BitVector[initialValues.length];
 796         for(int i=0; i<initialValues.length; i++)
 797             bv[i] = new BitVector(fleet.getWordWidth()).set(initialValues[i]);
 798         return bv;
 799     }
 800 }
 801
 802