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) {
 131                 if (peer==null && pattern.length==1 && pattern[0]==null) return;
 132                 build(ctx, ctx.new LoopFactory(dock, 1));
 133             }
 134             // number-in-flight is considered a property of the input dock in a pair
 135             //public int getInflight() { return 4; }
 136             public int getInflight() { return 1; }
 137             public int getTokensToAbsorb() { return getInflight(); }
 138             public void reset(Context ctx, int phase) {
 139                 if (dock.getShip().getType().equals("Debug")) {
 140                     return;
 141                 }
 142                 if (peer==null && pattern.length==1 && pattern[0]==null) return;
 143                 switch(phase) {
 144                     case 0: {
 145                         torpedoes.add(dock);
 146                         break;
 147                     }
 148                     case 1: {
 149                         // FIXME
 150                         reset_count++;
 151                         Context.LoopFactory lf = ctx.new LoopFactory(dock, 1);
 152                         lf.sendToken(fleet.getShip("Debug",0).getDock("in").getDataDestination());
 153                         if (peer != null && peer instanceof DockOutPort) {
 154                             DockOutPort dop_peer = (DockOutPort)peer;
 155                             lf = lf.makeNext(0);
 156                             lf.abortLoopIfTorpedoPresent();
 157                             lf.recvToken();
 158                             lf.sendToken(dop_peer.dock.getDataDestination());
 159                         }
 160                         break;
 161                     }
 162                     case 2: {
 163                         if (peer != null && peer instanceof DockOutPort) {
 164                             torpedoes.add(dock);
 165                         }
 166                         break;
 167                     }
 168                 }
 169             }
 170             protected void build(Context ctx, Context.LoopFactory lf) {
 171                 if (peer==null && pattern.length==1 && pattern[0]==null) return;
 172                 int inflight = (count != 0 && count < getInflight()) ? count : getInflight();
 173
 174                 if (peer!=null)
 175                     for(int i=0; i<inflight; i++) peer.sendToken(lf);
 176
 177                 lf = lf.makeNext(count);
 178                 for(int i=0; i<pattern.length; i++) {
 179                     if (pattern[i]==null) {
 180                         lf.abortLoopIfTorpedoPresent();
 181                         peer.recvWord(lf);
 182                         lf.deliver();
 183                         peer.sendToken(lf);
 184                     } else {
 185                         lf.literal(pattern[i]);
 186                         lf.abortLoopIfTorpedoPresent();
 187                         lf.deliver();
 188                     }
 189                 }
 190
 191                 if (count!=0) {
 192                     // "torpedoable nop" to keep the dock in a receptive state
 193                     lf.abortLoopIfTorpedoPresent();
 194                     lf.recvToken();
 195                 }
 196             }
 197         }
 198
 199         public /*final*/ class DockOutPort extends OutPort {
 200             public final Dock dock;
 201             public final int count;
 202             public DockOutPort(String name, Dock dock) { this(name, dock, 0); }
 203             public DockOutPort(String name, Dock dock, int count) { super(name); this.dock = dock; this.count = count; }
 204             public void sendToken(Context.LoopFactory lf) { lf.sendToken(dock.getDataDestination()); }
 205             public void recvWord(Context.LoopFactory lf) { lf.recvWord(); }
 206             public void build(Context ctx) { build(ctx, ctx.new LoopFactory(dock, 1)); }
 207             protected void build(Context ctx, Context.LoopFactory lf) {
 208                 if (peer==null) return;
 209                 // FIXME: no setup?
 210                 lf = lf.makeNext(count);
 211                 lf.abortLoopIfTorpedoPresent();
 212                 peer.recvToken(lf);
 213                 //lf.abortLoopIfTorpedoPresent();  // FIXME: do I need this twice?
 214                 lf.collectWord();
 215                 peer.sendWord(lf);
 216                 // FIXME: cleanup
 217             }
 218             public void reset(Context ctx, int phase) {
 219                 switch(phase) {
 220                     case 0: {
 221                         torpedoes.add(dock);
 222                         break;
 223                     }
 224                     case 1: {
 225                         reset_count++;
 226                         Context.LoopFactory lf = ctx.new LoopFactory(dock, 1);
 227
 228                         //System.out.println("absorbing tokens from " + dip_peer.dock + " to " + dock + "(a "+Module.this.getClass().getName()+")");
 229                         for(int i=0; i<peer.getTokensToAbsorb(); i++) {
 230                             lf.recvToken();
 231                         }
 232                         //lf.sendToken(dip_peer.dock.getInstructionDestination());
 233
 234                         lf.sendToken(fleet.getShip("Debug",0).getDock("in").getDataDestination());
 235                         lf = lf.makeNext(0);
 236                         lf.abortLoopIfTorpedoPresent();
 237                         lf.collectWord();
 238                         break;
 239                     }
 240                     case 2: {
 241                         torpedoes.add(dock);
 242                         break;
 243                     }
 244                 }
 245             }
 246         }
 247     }
 248
 249     private BitVector bv(long l) { return new BitVector(fleet.getWordWidth()).set(l); }
 250
 251     /**
 252      *  For every datum transmitted to in, pass it along to out and
 253      *  deliver the constant at out.  Flow control in<->out is
 254      *  maintained, but out is not flow-controlled, so be sure
 255      *  that every datum sent there is consumed synchronously wiht
 256      *  data items sent to out.
 257      */
 258     public class ForeverModule extends Module {
 259         private BitVector bv;
 260         public final OutPort out = new OutPort("out") {
 261                 public void sendToken(Context.LoopFactory lf) { }
 262                 public void recvWord(Context.LoopFactory lf) { }
 263                 public void build(Context ctx) { }
 264                 public void reset(Context ctx, int phase) { }
 265                 public void setPeer(InPort peer) {
 266                     this.peer = peer;
 267                     DockInPort pip = ((DockInPort)peer);
 268                     for(int i=0; i<pip.pattern.length; i++) {
 269                         if (pip.pattern[i]==null)
 270                             pip.pattern[i] = bv;
 271                     }
 272                 }
 273             };
 274         public ForeverModule(long l) { this(new BitVector(fleet.getWordWidth()).set(l)); }
 275         public ForeverModule(final BitVector bv) { this.bv = bv; }
 276     }
 277
 278     public class OnceModule extends Module {
 279         private BitVector bv;
 280         public final OutPort out = new OutPort("out") {
 281                 public void sendToken(Context.LoopFactory lf) { }
 282                 public void recvWord(Context.LoopFactory lf) { }
 283                 public void build(Context ctx) { }
 284                 public void reset(Context ctx, int phase) { }
 285                 public void setPeer(InPort peer) {
 286                     this.peer = peer;
 287                     DockInPort pip = ((DockInPort)peer);
 288                     BitVector[] pip_pattern = pip.pattern;
 289                     BitVector[] temp = new BitVector[pip_pattern.length * 2];
 290                     int j = 0;
 291                     int i = 0;
 292                     boolean done = false;
 293                     // FIXME: if peer.count is already 1, this gets simpler and different
 294                     for(i=0; i<temp.length; i++) {
 295                         if (pip_pattern[j] != null) {
 296                             temp[i] = pip_pattern[j];
 297                         } else {
 298                             if (done) break;
 299                             done = true;
 300                             temp[i] = bv;
 301                         }
 302                         j++;
 303                         if (j >= pip_pattern.length) j = 0;
 304                     }
 305                     pip.pattern = new BitVector[i];
 306                     System.arraycopy(temp, 0, pip.pattern, 0, i);
 307                     pip.count = 1;
 308                 }
 309             };
 310         public OnceModule(long l) { this(new BitVector(fleet.getWordWidth()).set(l)); }
 311         public OnceModule(final BitVector bv) { this.bv = bv; }
 312     }
 313
 314     public class DebugModule extends Module {
 315         public final Ship ship = pool.allocateShip("Debug");
 316         public final InPort in = new DockInPort("in", ship.getDock("in"));
 317         // NOTE: shutdown needs to treat this specially
 318         public DebugModule() { }
 319     }
 320
 321     public class UnPunctuatorModule extends Module {
 322         private final Ship    ship  = pool.allocateShip("Counter");
 323         public  final OutPort out   = new DockOutPort("out", ship.getDock("out"));
 324         public  final InPort  val   = new DockInPort("in1",  ship.getDock("in1"));
 325         public  final InPort  count = new DockInPort("in2",  ship.getDock("in2"), 0, new BitVector[] { null, bv(1) });
 326         public  final InPort  op    = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(6 /*PASS_C2_V1*/), bv(10 /*DROP_C2_V1*/) } );
 327         public UnPunctuatorModule() { }
 328     }
 329
 330     public class PunctuatorModule extends Module {
 331         private final long    punc;
 332         private final Ship    ship  = pool.allocateShip("Counter");
 333         public  final OutPort out   = new DockOutPort("out", ship.getDock("out"));
 334         public  final InPort  val   = new DockInPort("in1",  ship.getDock("in1"));
 335         public  final InPort  op    = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(6 /*PASS_C2_V1*/), bv(7 /*PASS_C2_V2*/) } );
 336         public  final InPort  count;
 337         public PunctuatorModule(long punc) {
 338             this.punc = punc;
 339             this.count = new DockInPort("in2",  ship.getDock("in2"), 0, new BitVector[] { null, bv(1), bv(punc) });
 340         }
 341     }
 342
 343     public class AluModule extends Module {
 344         public final Ship    ship = pool.allocateShip("Alu");
 345         public final InPort  in1 = new DockInPort("in1",  ship.getDock("in1"));
 346         public final InPort  in2 = new DockInPort("in2",  ship.getDock("in2"));
 347         public final InPort  inOp = new DockInPort("inOp", ship.getDock("inOp"));
 348         public final OutPort out  = new DockOutPort("out", ship.getDock("out"));
 349         public AluModule() { }
 350     }
 351
 352     public class DownCounterModule extends Module {
 353         public final Ship    ship  = pool.allocateShip("Counter");
 354         public final InPort  start = new DockInPort("in1",  ship.getDock("in1"));
 355         public final InPort  incr  = new DockInPort("in2",  ship.getDock("in2"));
 356         public final InPort  inOp  = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(12 /*COUNTDOWN*/) });
 357         public final OutPort out   = new DockOutPort("out", ship.getDock("out"));
 358         public DownCounterModule() { }
 359     }
 360
 361     public class RepeatModule extends Module {
 362         public final Ship    ship   = pool.allocateShip("Counter");
 363         public final InPort  count  = new DockInPort("in1",  ship.getDock("in1"));
 364         public final InPort  val    = new DockInPort("in2",  ship.getDock("in2"));
 365         public final InPort  inOP   = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(1 /*REPEAT_C1_V2*/) });
 366         public final OutPort out    = new DockOutPort("out", ship.getDock("out"));
 367         public RepeatModule() { }
 368     }
 369
 370     public class SortedMergeModule extends Module {
 371         public final Ship    ship = pool.allocateShip("Alu");
 372         public final InPort  in1  = new DockInPort("in1",  ship.getDock("in1"));
 373         public final InPort  in2  = new DockInPort("in2",  ship.getDock("in2"));
 374         public final InPort  inOp = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(9 /*MAXMERGE*/) });
 375         public final OutPort out  = new DockOutPort("out", ship.getDock("out"));
 376         public SortedMergeModule() { }
 377     }
 378
 379     public class MemoryModule extends Module {
 380         public final Ship    ship;
 381         public final InPort  inAddrRead1;
 382         public final InPort  inAddrRead2;
 383         public final InPort  inAddrWrite;
 384         public final InPort  inDataWrite;
 385         public final OutPort outRead1;
 386         public final OutPort outRead2;
 387         public MemoryModule(Ship memoryShip) {
 388             this.ship = memoryShip;
 389             this.inAddrWrite  = new DockInPort("inAddrWrite", ship.getDock("inAddrWrite"));
 390             this.inDataWrite  = new DockInPort("inDataWrite", ship.getDock("inDataWrite"));
 391             this.inAddrRead1  = new InPort("inAddrRead1") {
 392                     public void recvToken(Context.LoopFactory lf) { lf.recvToken(); }
 393                     public void sendWord(Context.LoopFactory lf) { lf.sendWord(ship.getDock("inAddrRead").getDataDestination(), new BitVector(1).set(0)); }
 394                     public void build(Context ctx) { }
 395                     public int getTokensToAbsorb() { return outRead1.peer.getTokensToAbsorb(); }
 396                     public void reset(Context ctx, int phase) {
 397                         if (phase==2) {
 398                             torpedoes.add(ship.getDock("inAddrRead"));
 399                             torpedoes.add(ship.getDock("out"));
 400                         }
 401                     }
 402                 };
 403             this.inAddrRead2  = new InPort("inAddrRead2") {
 404                     public void recvToken(Context.LoopFactory lf) { lf.recvToken(); }
 405                     public void sendWord(Context.LoopFactory lf) { lf.sendWord(ship.getDock("inAddrRead").getDataDestination(), new BitVector(1).set(1)); }
 406                     public void build(Context ctx) { }
 407                     public int getTokensToAbsorb() { return outRead2.peer.getTokensToAbsorb(); }
 408                     public void reset(Context ctx, int phase) {
 409                         if (phase==2) {
 410                             torpedoes.add(ship.getDock("inAddrRead"));
 411                             torpedoes.add(ship.getDock("out"));
 412                         }
 413                     }
 414                 };
 415             this.outRead1 = new OutPort("outRead1") {
 416                     public void sendToken(Context.LoopFactory lf) { inAddrRead1.peer.sendToken(lf); }
 417                     public void recvWord(Context.LoopFactory lf) { lf.recvWord(); }
 418                     public void build(Context ctx) { }
 419                     public void reset(Context ctx, int phase) { }
 420                 };
 421             this.outRead2 = new OutPort("outRead2") {
 422                     public void sendToken(Context.LoopFactory lf) { inAddrRead2.peer.sendToken(lf); }
 423                     public void recvWord(Context.LoopFactory lf) { lf.recvWord(); }
 424                     public void build(Context ctx) { }
 425                     public void reset(Context ctx, int phase) { }
 426                 };
 427         }
 428         public void build(Context ctx) {
 429             super.build(ctx);
 430             Context.LoopFactory lf;
 431
 432             lf = ctx.new LoopFactory(ship.getDock("inAddrRead"), 0);
 433             lf.abortLoopIfTorpedoPresent();
 434             lf.recvWord();
 435             lf.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO);
 436             lf.setPredicate(Predicate.NotFlagA);
 437             lf.sendToken(ship.getDock("out").getDataDestination(), new BitVector(1).set(0));
 438             lf.setPredicate(Predicate.FlagA);
 439             lf.sendToken(ship.getDock("out").getDataDestination(), new BitVector(1).set(1));
 440             lf.setPredicate(null);
 441             lf.deliver();
 442
 443             lf = ctx.new LoopFactory(ship.getDock("out"), 0);
 444             lf.abortLoopIfTorpedoPresent();
 445             lf.collectWord();
 446             lf.setFlags(FlagFunction.ZERO, FlagFunction.ZERO.add(FlagC));
 447             lf.setPredicate(Predicate.FlagB);
 448             // here: any code to be executed when inDataWrite gets completed
 449             lf.setPredicate(Predicate.NotFlagB);
 450             lf.abortLoopIfTorpedoPresent();
 451             lf.recvToken();
 452             lf.setFlags(FlagFunction.ZERO.add(NotFlagC).add(FlagB), FlagFunction.ZERO.add(FlagC).add(FlagB));
 453             if (outRead1.peer != null) {
 454                 lf.setPredicate(Predicate.NotFlagB);
 455                 outRead1.peer.sendWord(lf);
 456             }
 457             if (outRead2.peer != null) {
 458                 lf.setPredicate(Predicate.NotFlagA);
 459                 outRead2.peer.sendWord(lf);
 460             }
 461             lf.setPredicate(null);
 462         }
 463     }
 464
 465     public static void main(String[] s) throws Exception {
 466         Fleet fleet = new Fpga();
 467         Random random = new Random(System.currentTimeMillis());
 468         long[] vals = new long[256];
 469         for(int i=0; i<vals.length; i++) {
 470             vals[i] = Math.abs(random.nextInt());
 471         }
 472
 473         FleetProcess fp;
 474         int stride = 1;
 475         fp = null;
 476         while(stride < vals.length) {
 477             if (fp==null) fp = fleet.run(new Instruction[0]);
 478             System.out.println("stride " + stride);
 479             vals = mergeSort(fp, fleet, vals, stride);
 480             stride = stride * 2;
 481             //fp.terminate(); fp = null;
 482             System.out.println();
 483             System.out.println("results:");
 484             for(int i=0; i<vals.length; i++)
 485                 System.out.println(vals[i]);
 486         }
 487     }
 488
 489     // won't verify that the switch fabric is empty, however
 490     public static void verifyClean(FleetProcess fp) {
 491         Ship debug   = fp.getFleet().getShip("Debug", 0);
 492         Dock debugIn = debug.getDock("in");
 493
 494         Context ctx;
 495         Context.LoopFactory lf;
 496
 497         ctx = new Context(fp.getFleet());
 498         lf = ctx.new LoopFactory(debugIn, 1);
 499         lf.literal(12);
 500         lf.deliver();
 501         lf.literal(5);
 502         lf.deliver();
 503         ArrayList<Instruction> ai = new ArrayList<Instruction>();
 504         ctx.emit(ai);
 505         for(Instruction ins : ai) fp.sendInstruction(ins);
 506         fp.flush();
 507
 508         System.out.println("checking debug.in");
 509         if (fp.recvWord().toLong() != 12) throw new RuntimeException("debug dock not properly initialized");
 510         if (fp.recvWord().toLong() != 5)  throw new RuntimeException("debug dock not properly initialized");
 511
 512         long k = 0;
 513         for(Ship ship : fp.getFleet())
 514             if (!"Debug".equals(ship.getType()))
 515                 for (Dock dock : ship) {
 516                     System.out.println("checking " + dock);
 517
 518                     k = (k + 23) % 65535;
 519                     ctx = new Context(fp.getFleet());
 520
 521                     boolean reverse = (k%2)==0;
 522
 523                     lf = ctx.new LoopFactory(debugIn, 2);
 524                     lf.recvToken();
 525                     lf.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO);
 526                     lf.setPredicate(Predicate.NotFlagA);
 527                     lf.literal(k);
 528                     lf.setPredicate(Predicate.FlagA);
 529                     lf.literal(k+1);
 530                     lf.setPredicate(null);
 531                     lf.deliver();
 532
 533                     lf = ctx.new LoopFactory(dock, 1);
 534                     lf.sendToken(dock.getDataDestination(), new BitVector(1).set(reverse ? 1 : 0));
 535                     lf.sendToken(dock.getDataDestination(), new BitVector(1).set(reverse ? 0 : 1));
 536                     lf = lf.makeNext(2);
 537                     lf.recvToken();
 538                     lf.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO);
 539                     lf.setPredicate(Predicate.NotFlagA);
 540                     lf.sendToken(debugIn.getDataDestination(), new BitVector(1).set(0));
 541                     lf.setPredicate(Predicate.FlagA);
 542                     lf.sendToken(debugIn.getDataDestination(), new BitVector(1).set(1));
 543                     lf.setPredicate(null);
 544
 545                     ai = new ArrayList<Instruction>();
 546                     ctx.emit(ai);
 547                     for(Instruction ins : ai) fp.sendInstruction(ins);
 548                     fp.flush();
 549
 550                     long kk;
 551                     kk = fp.recvWord().toLong();
 552                     if (kk != (reverse ? k+1 : k))
 553                         throw new RuntimeException(dock+" not properly initialized (1)");
 554                     kk = fp.recvWord().toLong();
 555                     if (kk != (reverse ? k   : k+1))
 556                         throw new RuntimeException(dock+" not properly initialized (2)");
 557                 }
 558     }
 559
 560     // FIXME: numbers seem to get duplicated when stride=2
 561     public static long[] mergeSort(FleetProcess fp, Fleet fleet, long[] vals, int stride_length) throws Exception {
 562
 563         BitVector[] mem = new BitVector[vals.length];
 564         for(int i=0; i<mem.length; i++) mem[i] = new BitVector(fleet.getWordWidth()).set(vals[i]);
 565
 566         Ship memoryShip = fleet.getShip("DRAM", 0);
 567         Gadgets.writeMem(fp, memoryShip, 0, mem);
 568
 569         //////////////////////////////////////////////////////////////////////////////
 570
 571         Process proc = new Process(fleet);
 572         DebugModule dm = proc.new DebugModule();
 573
 574         int end_of_data = vals.length;
 575         int num_strides = end_of_data / (stride_length * 2);
 576
 577         MemoryModule mm = proc.new MemoryModule(memoryShip);
 578         SortedMergeModule sm = proc.new SortedMergeModule();
 579
 580
 581         for(int i=0; i<2; i++) {
 582
 583             Module.OutPort stride_length_1       = proc.new OnceModule(stride_length).out;
 584             Module.OutPort stride_length_2       = proc.new OnceModule(stride_length).out;
 585             Module.OutPort twice_stride_length_1 = proc.new OnceModule(stride_length*2).out;
 586             Module.OutPort end_of_data_1         = proc.new OnceModule(end_of_data + i*stride_length).out;
 587
 588             Module.OutPort num_strides_1         = proc.new OnceModule(num_strides).out;
 589             Module.OutPort num_strides_2         = proc.new OnceModule(num_strides).out;
 590
 591             RepeatModule r0 = proc.new RepeatModule();
 592             RepeatModule r1 = proc.new RepeatModule();
 593             RepeatModule r2 = proc.new RepeatModule();
 594             DownCounterModule c0 = proc.new DownCounterModule();
 595             DownCounterModule c1 = proc.new DownCounterModule();
 596             ForeverModule fmm  = proc.new ForeverModule(1);
 597             ForeverModule fmm2 = proc.new ForeverModule(2); // 2=ADD
 598             AluModule alu = proc.new AluModule();
 599
 600             stride_length_1.connect(r0.val);
 601             num_strides_1.connect(r0.count);
 602             r0.out.connect(c0.start);
 603             fmm.out.connect(c0.incr);
 604             c0.out.connect(alu.in2);
 605
 606             end_of_data_1.connect(c1.start);
 607             twice_stride_length_1.connect(c1.incr);
 608             c1.out.connect(r1.val);
 609             stride_length_2.connect(r2.val);
 610             num_strides_2.connect(r2.count);
 611             r2.out.connect(r1.count);
 612             r1.out.connect(alu.in1);
 613             fmm2.out.connect(alu.inOp);
 614
 615             alu.out.connect(i==0 ? mm.inAddrRead1 : mm.inAddrRead2);
 616
 617             ForeverModule fm = proc.new ForeverModule(stride_length);
 618             PunctuatorModule punc = proc.new PunctuatorModule(-1);
 619             fm.out.connect(punc.count);
 620             (i==0 ? mm.outRead1 : mm.outRead2).connect(punc.val);
 621             punc.out.connect(i==0 ? sm.in1 : sm.in2);
 622         }
 623
 624         ForeverModule fm = proc.new ForeverModule(2*stride_length);
 625         UnPunctuatorModule unpunc = proc.new UnPunctuatorModule();
 626         sm.out.connect(unpunc.val);
 627         fm.out.connect(unpunc.count);
 628         unpunc.out.connect(dm.in);
 629
 630         //////////////////////////////////////////////////////////////////////////////
 631
 632         Context ctx = new Context(fp.getFleet());
 633         ctx.setAutoflush(true);
 634
 635         ArrayList<Instruction> ai = new ArrayList<Instruction>();
 636         proc.build(ctx);
 637         ctx.emit(ai);
 638         for(Instruction ins : ai) {
 639             System.out.println(ins);
 640             fp.sendInstruction(ins);
 641         }
 642         fp.flush();
 643
 644         System.out.println("reading back...");
 645         int inc=0;
 646         for(int i=0; i<vals.length; i++) {
 647             inc++;
 648             BitVector bv = fp.recvWord();
 649             System.out.println("\r"+bv + " " + bv.toLong() + "          #read="+inc);
 650             mem[i] = bv;
 651         }
 652         System.out.println("\rdone.                                                                    ");
 653         long[] ret = new long[vals.length];
 654         for(int i=0; i<ret.length; i++) ret[i] = mem[ret.length-i-1].toLong();
 655
 656         //if (true) return ret;
 657
 658         Context ctx2 = new Context(fp.getFleet());
 659         Dock debugIn = fleet.getShip("Debug",0).getDock("in");
 660         Dock fred = debugIn;
 661         fp.sendToken(debugIn.getInstructionDestination());
 662
 663         Context.LoopFactory lf = ctx2.new LoopFactory(debugIn, 0);
 664         lf.literal(0);
 665         lf.abortLoopIfTorpedoPresent();
 666         lf.recvToken();
 667         lf.deliver();
 668
 669         ctx2.emit(ai = new ArrayList<Instruction>());
 670         for(Instruction ins : ai)
 671             fp.sendInstruction(ins);
 672         fp.flush();
 673
 674         int count = 0;
 675
 676         for(int phase=0; phase<=2; phase++) {
 677             System.out.println("== phase "+phase+" ==================================================================");
 678             ctx2 = new Context(fp.getFleet());
 679             proc.reset(ctx2, phase);
 680             for(Dock dock : torpedoes) fp.sendToken(dock.getInstructionDestination());
 681             ctx2.emit(ai = new ArrayList<Instruction>());
 682             for(Instruction ins : ai) fp.sendInstruction(ins);
 683             fp.flush();
 684             System.out.println("flushed");
 685             for(int ii=0; ii<reset_count; ii++)
 686                 System.out.print("\r phase "+phase+" ==> " + fp.recvWord().toLong() + " " + (ii+1) + " / " + reset_count);
 687             System.out.println();
 688         }
 689
 690         /*
 691         ctx2 = new Context(fp.getFleet());
 692         ai = new ArrayList<Instruction>();
 693         for(Ship ship : ctx.allocatedShips)
 694             if (!ship.getType().equals("Debug"))
 695                 for(Dock dock : ship)
 696                     if (dock.isInputDock()) {
 697                         lf = ctx2.new LoopFactory(dock, 0);
 698                         lf.recvWord();
 699
 700                     }
 701         */
 702
 703         fp.sendToken(debugIn.getInstructionDestination());
 704         fp.flush();
 705
 706         //System.out.println("verifying cleanup:");
 707         //verifyClean(fp);
 708         return ret;
 709     }
 710
 711     private BitVector[] longsToBitVectors(long[] initialValues) {
 712         BitVector[] bv = new BitVector[initialValues.length];
 713         for(int i=0; i<initialValues.length; i++)
 714             bv[i] = new BitVector(fleet.getWordWidth()).set(initialValues[i]);
 715         return bv;
 716     }
 717 }
 718
 719