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

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