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