- public CodeBag build(DataFlowGraph dfg,
- CodeBag ctx,
- int vals_length, int stride_length,
- long base1,
- long base2,
- CodeBag next) throws Exception {
-
- for(int i=0; i<arity; i++) {
- if (pn0[i]!=null) pn0[i].set(ctx, stride_length);
- if (pn1[i]!=null) pn1[i].set(ctx, vals_length + i*stride_length);
- if (pn2[i]!=null) pn2[i].set(ctx, 2*stride_length);
- if (pn3[i]!=null) pn3[i].set(ctx, stride_length);
- if (pn4[i]!=null) pn4[i].set(ctx, stride_length);
- if (pn_base1[i]!=null) pn_base1[i].set(ctx, base1);
- }
- pn5.set(ctx, vals_length);
- pn6.set(ctx, 2*stride_length+1);
- pn_base2.set(ctx, base2);
- pn_end.set(ctx, vals_length);
- ctx.sendWord(cb2.getDescriptor(), program.getCBDDestination());
- ctx.sendWord(next.getDescriptor(), next_dest);
- ctx.seal();
-
- return ctx;
- }
-
- public static void main(String[] s) throws Exception {
- //mergeSort(1024*64, 4, "Dvi",
- mergeSort(1024*128, 4, "Dvi",
- 4194304
- );
- //548*478);
- }
-
- /** demo */
- public static void main0(String[] s) throws Exception {
- PrintWriter pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream("stats.txt")));
- //int inflight = 1;
- for(int inflight=1; inflight <= 8; inflight++)
- for(int count = 32; count < 2097152; count *= 2) {
- System.out.println("==============================================================================");
- System.out.println("count="+count);
- System.out.println("inflight="+inflight);
- //long time = timeit(count, inflight);
- long time = mergeSort(count, inflight, "DDR2", 0);
- pw.println(inflight + ", " + count + ", " + time);
- pw.flush();
- }
- }
-
- public static long timeit(int count, int inflight) throws Exception {
- Fleet fleet = new Fpga();
- FleetProcess fp = fleet.run(new Instruction[0]);
- ShipPool pool = new ShipPool(fleet);
- //Program program = new Program(pool.allocateShip("Memory"));
- CodeBag cb = new CodeBag(fleet);
-
- Ship counter1 = pool.allocateShip("Counter");
- Ship counter2 = pool.allocateShip("Counter");
-
- Ship timer = pool.allocateShip("Timer");
- Ship debug = pool.allocateShip("Debug");
-
- LoopFactory lf;
-
- lf = cb.loopFactory(debug.getDock("in"), 2);
- lf.recvWord();
- lf.deliver();
-
-
- // First counter //////////////////////////////////////////////////////////////////////////////
-
- lf = cb.loopFactory(counter1.getDock("in1"), 1);
- lf.recvToken();
- lf.literal(count);
- lf.deliver();
-
- lf = cb.loopFactory(counter1.getDock("in2"), 1);
- lf.literal(1);
- lf.deliver();
-
- lf = cb.loopFactory(counter1.getDock("inOp"), 1);
- lf.literal("COUNT");
- lf.deliver();
-
- lf = cb.loopFactory(counter1.getDock("out"), 0);
- lf.recvToken();
- lf.collectWord();
- lf.sendWord(counter2.getDock("in2"));
-
-
- // Second counter //////////////////////////////////////////////////////////////////////////////
-
- lf = cb.loopFactory(counter2.getDock("in1"), 1);
- lf.literal(count);
- lf.deliver();
- lf.literal(1);
- lf.deliver();
- lf.literal(1);
- lf.deliver();
-
- lf = cb.loopFactory(counter2.getDock("in2"), 1);
- for(int i=0; i<inflight; i++)
- lf.sendToken(counter1.getDock("out"));
- lf = lf.makeNext(0);
- lf.recvWord();
- lf.sendToken(counter1.getDock("out"));
- lf.deliver();
-
- lf = cb.loopFactory(counter2.getDock("inOp"), 1);
- lf.literal("DROP_C1_V2");
- lf.deliver();
- lf.literal("PASS_C1_V1");
- lf.deliver();
-
- lf = cb.loopFactory(counter2.getDock("out"), 1);
- lf.collectWord();
- lf.sendToken(timer.getDock("out"));
-
-
- // Timer //////////////////////////////////////////////////////////////////////////////
-
- lf = cb.loopFactory(timer.getDock("out"), 1);
- lf.collectWord();
- lf.sendToken(counter1.getDock("in1"));
- lf.sendWord(debug.getDock("in"));
- lf.recvToken();
- lf.collectWord();
- lf.sendWord(debug.getDock("in"));
-
- FpgaDock out = (FpgaDock)counter1.getDock("out");
- FpgaDock in = (FpgaDock)counter2.getDock("in2");
- System.out.println("distance is " + out.getPathLength((FpgaDestination)in.getDataDestination()));
- System.out.println("reverse distance is " + in.getPathLength((FpgaDestination)out.getDataDestination()));
-
- for(Instruction i : cb.emit()) System.out.println(i);
- cb.dispatch(fp, true);
- long time1 = fp.recvWord().toLong();
- System.out.println("got " + time1);
- long time2 = fp.recvWord().toLong();
- System.out.println("got " + time2);
- System.out.println("diff=" + (time2-time1));
-
- fp.terminate();
-
- return (time2-time1);
- }
-
- public static long mergeSort(int vals_length, int inflight, String shipType, int clearAmount) throws Exception {
- Node.CAPACITY = inflight;
-
- Fleet fleet = new Fpga();
- FleetProcess fp = fleet.run(new Instruction[0]);
- ShipPool pool = new ShipPool(fleet);
- Ship mem1 = pool.allocateShip(shipType);
-
-
- if (clearAmount > 0)
- randomizeMemory(fp, pool, mem1, 0, clearAmount, false);
-
- //randomizeMemory(fp, pool, mem1, 0, vals_length, true);
-
- BitVector[] bvs = new BitVector[vals_length];
-
- long index = 0;
- Picture p = new Picture(new FileInputStream("campus.png"));
- for(int y=0; y<(478/2); y++)
- for(int x=0; x<544; x++) {
- if (index >= vals_length) break;
- int pixel = (x>=p.width) ? 0 : p.data[p.width*y+x];
- long r = (pixel>>0) & 0xff;
- long g = (pixel>>8) & 0xff;
- long b = (pixel>>16) & 0xff;
- r >>= 2;
- g >>= 2;
- b >>= 2;
- //r = ~(-1L<<6);
- //g = ~(-1L<<6);
- //b = ~(-1L<<6);
- bvs[(int)index] = new BitVector(fleet.getWordWidth()).set( r | (g<<6) | (b<<12) | (index<<18) );
- index++;
- }
-
- for(; index<vals_length; index++) {
- long tag = index<<18;
- bvs[(int)index] = new BitVector(fleet.getWordWidth()).set( tag );
- }
-
- System.out.println("final index " + index);
-
- Random random = new Random(System.currentTimeMillis());
- for(int i=0; i<bvs.length*10; i++) {
- int from = Math.abs(random.nextInt()) % bvs.length;
- int to = Math.abs(random.nextInt()) % bvs.length;
- BitVector bv = bvs[from];
- bvs[from] = bvs[to];
- bvs[to] = bv;
- }
-
- MemoryUtils.writeMem(fp, pool, mem1, offset, bvs);
-
- Program program = new Program(pool.allocateShip("Memory"));
- long ret = new MergeSort(fleet, program, pool, 2, mem1, mem1).main(fp, vals_length);
-
- //long ret = 0;
- // verify the cleanup?
- //CleanupUtils.verifyClean(fp);
- //MemoryUtils.readMem(fp, new ShipPool(fp.getFleet()), mem1, 0, bvs);
-
- BitVector[] bvx = new BitVector[1024];
- MemoryUtils.readMem(fp, new ShipPool(fp.getFleet()), mem1, 0, bvx);
- for(int i=0; i<bvx.length; i++)
- System.out.println(bvx[i]);
- /*
- System.out.println("results:");
- for(int i=0; i<vals_length-1; i++)
- if ( (bvs[i].toLong() & ~(-1L<<18)) != ~(-1L<<18))
- System.out.println(bvs[i]);
- */
- /*
- for(int i=0; i<vals_length-1; i++) {
- if (bvs[i].toLong() > bvs[i+1].toLong())
- System.out.println("sort failure at "+i+":\n "+bvs[i]+"\n "+bvs[i+1]);
- }
- */
- fp.terminate();
- return ret;
- }
-
- static int offset = 40;
-
- //static int offset = 32;
- //static int offset = 544*2;
- //static int offset = 544;
-
- public long main(FleetProcess fp, int vals_length) throws Exception {