X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Ffleet%2Fdataflow%2FSortingDemo.java;fp=src%2Fedu%2Fberkeley%2Ffleet%2Fdataflow%2FSortingDemo.java;h=af89c74d734ad6710d754ae79be710bd5649dfb5;hb=390ea921b89fd293ecba9f228354f84b9933bebc;hp=0000000000000000000000000000000000000000;hpb=a9f94a821394151a990b875d7ae635448a892ff2;p=fleet.git

diff --git a/src/edu/berkeley/fleet/dataflow/SortingDemo.java b/src/edu/berkeley/fleet/dataflow/SortingDemo.java
new file mode 100644
index 0000000..af89c74
--- /dev/null
+++ b/src/edu/berkeley/fleet/dataflow/SortingDemo.java
@@ -0,0 +1,289 @@
+package edu.berkeley.fleet.dataflow;
+import java.util.*;
+import java.io.*;
+import edu.berkeley.fleet.loops.*;
+import edu.berkeley.fleet.api.*;
+import edu.berkeley.fleet.fpga.*;
+import org.ibex.graphics.*;
+
+public class SortingDemo {
+
+    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;
+        }
+
+        int offset = 40;
+        MemoryUtils.writeMem(fp, pool, mem1, 40, bvs);
+
+        Ship mem = pool.allocateShip("Memory");
+        Program program = new Program(mem);
+        CodeBag cb_ = new MergeSort(fleet, program, pool, 2, mem1, mem1).makeInstance(offset, vals_length);
+        cb_.seal();
+        Ship button = pool.allocateShip("Button");
+        CodeBag cb = new CodeBag(fleet, program);
+        LoopFactory lf = cb.loopFactory(button.getDock("out"), 1);
+        lf.collectWord();
+        lf.literal(cb_.getDescriptor());
+        lf.sendWord(program.getCBDDestination());
+        cb.seal();
+
+        ShipPool pool2 = new ShipPool(fp.getFleet());
+        pool2.allocateShip(program.memoryShip);
+        // FIXME
+        long ret = program.run(fp, cb, pool2);
+        pool2.releaseShip(program.memoryShip);
+
+        //long ret = 0;
+        // verify the cleanup?
+        //CleanupUtils.verifyClean(fp);
+        //MemoryUtils.readMem(fp, new ShipPool(fp.getFleet()), mem1, 0, bvs);
+
+        BitVector[] bvx = new BitVector[1024];
+        pool.allocateShip(mem);
+        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 = 32;
+    //static int offset = 544*2;
+    //static int offset = 544;
+
+    public static void randomizeMemory(FleetProcess fp, ShipPool pool_, Ship memory, long start, long length, boolean randomize) {
+        ShipPool pool = new ShipPool(pool_);
+        Ship mem = pool.allocateShip("Memory");
+        Program prog = new Program(mem);
+
+        DataFlowGraph dfg = new DataFlowGraph(fp.getFleet(), pool);
+        DownCounterNode dcn = new DownCounterNode(dfg);
+        dcn.start.connectOnce(length);
+        dcn.incr.connectOnce(1);
+
+        AluNode alu = new AluNode(dfg, "ADD");
+        alu.in1.connectForever(start);
+        alu.in2.connect(dcn.out);
+
+        MemoryNode mn = new MemoryNode(dfg, memory);
+        mn.inAddrWrite.connect(alu.out);
+
+        AluNode aluAnd = new AluNode(dfg, "AND");
+        if (randomize) {
+            aluAnd.in1.connect(new RandomNode(dfg).out);
+        } else {
+            //aluAnd.in1.connectForever( ~(-1L<<36) );
+            aluAnd.in1.connectForever( 0 );
+        }
+        aluAnd.in2.connectForever( ~(-1<<18) );
+        mn.inDataWrite.connect(aluAnd.out);
+        
+        UnPunctuatorNode discard = new UnPunctuatorNode(dfg, true);
+        discard.count.connectOnce(length);
+        discard.val.connect(mn.outWrite);
+        DoneNode done = new DoneNode(dfg, prog);
+        discard.out.connect(done.in);
+
+        CodeBag cb = new CodeBag(fp.getFleet(), prog);
+        dfg.build(cb);
+        cb.seal();
+
+        CodeBag cb2 = new CodeBag(fp.getFleet(), prog);
+        Ship button = fp.getFleet().getShip("Button",0);
+
+        LoopFactory lf = cb2.loopFactory(button.getDock("out"), 1);
+        //lf.collectWord();
+        lf.literal(prog.getEndProgramCodeBag().getDescriptor());
+        lf.sendWord(done.getDestinationToSendNextCodeBagDescriptorTo());
+        lf.literal(cb.getDescriptor());
+        lf.sendWord(prog.getCBDDestination());
+        cb2.seal();
+
+        System.out.println("dispatching randomization codebag...");
+        prog.run(fp, cb2, pool);
+        System.out.println("  randomization done.");
+        pool.releaseAll();
+    }
+
+}
\ No newline at end of file