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

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