X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Ffleet%2Fdataflow%2FMergeSort.java;h=459bab55c49993c386f4be017f3a1353c3716cb7;hb=f51ad92a4881b7f2f78eb77bb2a147ee99e9d692;hp=057db66eaa7f7540a8da6a8f15061002f0eb521e;hpb=8c0ded5d44a56e0970895ad1b347130dc529ba25;p=fleet.git

diff --git a/src/edu/berkeley/fleet/dataflow/MergeSort.java b/src/edu/berkeley/fleet/dataflow/MergeSort.java
index 057db66..459bab5 100644
--- a/src/edu/berkeley/fleet/dataflow/MergeSort.java
+++ b/src/edu/berkeley/fleet/dataflow/MergeSort.java
@@ -3,8 +3,9 @@ import java.util.*;
 import java.io.*;
 import edu.berkeley.fleet.loops.*;
 import edu.berkeley.fleet.api.*;
+import edu.berkeley.fleet.interpreter.*;
 import edu.berkeley.fleet.fpga.*;
-//import org.ibex.graphics.*;
+import org.ibex.graphics.*;
 
 public class MergeSort {
 
@@ -38,22 +39,16 @@ public class MergeSort {
         this.pool = pool;
         this.program = program;
         this.dfg = new DataFlowGraph(fleet, pool);
-        /*
-        pool.allocateShip(mem1);
-        if (mem2 != mem1) pool.allocateShip(mem2);
-        */
-        next_dest = makeDfgCodeBag(dfg);
+        next_dest = makeDfgCodeBag(dfg, program);
         cb2 = dfg.build(new CodeBag(dfg.fleet, program));
         cb2.seal();
     }
 
-    public Destination makeDfgCodeBag(DataFlowGraph dfg) {
+    public Destination makeDfgCodeBag(DataFlowGraph dfg, Program program) {
 
         MemoryNode mem_read  = new MemoryNode(dfg, mem1);
         MemoryNode mem_write = (mem1==mem2) ? mem_read : new MemoryNode(dfg, mem2);
 
-        AluNode sm = new AluNode(dfg, "MAXMERGE");
-
         pn0 = new ParameterNode[arity];
         pn1 = new ParameterNode[arity];
         pn2 = new ParameterNode[arity];
@@ -65,14 +60,15 @@ public class MergeSort {
         pn5 = new ParameterNode(dfg);
         pn6 = new ParameterNode(dfg, true);
 
+        AluNode sm = new AluNode(dfg, "MAXMERGE");
         // So far: we have four spare Counter ships; one can be used for resetting
         for(int i=0; i<arity; i++) {
 
             DownCounterNode c0 = new DownCounterNode(dfg);
-            DownCounterNode c1 = new DownCounterNode(dfg);
-
             c0.start.connect((pn0[i] = new ParameterNode(dfg, true)).out);
             c0.incr.connect(new ForeverNode(dfg, 1).out);
+
+            DownCounterNode c1 = new DownCounterNode(dfg);
             c1.start.connect((pn1[i] = new ParameterNode(dfg)).out);
             c1.incr.connect((pn2[i] = new ParameterNode(dfg)).out);
 
@@ -81,11 +77,12 @@ public class MergeSort {
             r1.count.connect((pn3[i] = new ParameterNode(dfg, true)).out);
 
             AluNode alu1 = new AluNode(dfg, "ADD");
-            AluNode alu2 = new AluNode(dfg, "ADD");
             alu1.in1.connect(r1.out);
             alu1.in2.connect(c0.out);
-            alu1.out.connect(alu2.in2);
+
+            AluNode alu2 = new AluNode(dfg, "ADD");
             alu2.in1.connect((pn_base1[i] = new ParameterNode(dfg, true)).out);
+            alu2.in2.connect(alu1.out);
             alu2.out.connect(i==0 ? mem_read.inAddrRead1 : mem_read.inAddrRead2);
 
             PunctuatorNode punc = new PunctuatorNode(dfg, -1);
@@ -105,6 +102,7 @@ public class MergeSort {
         AluNode alu = new AluNode(dfg, "ADD");
         alu.in1.connect(pn_base2.out);
         cw.out.connect(alu.in2);
+
         mem_write.inAddrWrite.connect(alu.out);
         mem_write.inDataWrite.connect(unpunc.out);
 
@@ -117,256 +115,16 @@ public class MergeSort {
         return done.getDestinationToSendNextCodeBagDescriptorTo();
     }
 
-    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 {
+    public CodeBag makeInstance(int offset, int length) throws Exception {
 
         long base_read = offset;
-        //long base_write = offset+((vals_length/544)+1)*544;
-        //long base_write = offset;
-        long base_write = vals_length + offset;
-
+        long base_write = length + offset;
         int stride = 1;
         ArrayList<CodeBag> codeBags = new ArrayList<CodeBag>();
         codeBags.add(new CodeBag(dfg.fleet, program));
-        for(; ;) {
+        for(;;) {
             CodeBag cb = codeBags.get(codeBags.size()-1);
-            //System.out.println("cb="+i+", stride="+stride);
-            boolean last = /*(base_write==offset) && */ (stride*2 >= vals_length);
+            boolean last = stride*2 >= length;
             CodeBag next;
             if (last) {
                 next = program.getEndProgramCodeBag();
@@ -374,79 +132,88 @@ public class MergeSort {
                 next = new CodeBag(dfg.fleet, program);
                 codeBags.add(codeBags.size(), next);
             }
-            build(dfg, cb, vals_length, stride, base_read, base_write, next);
+
+            for(int i=0; i<arity; i++) {
+                if (pn0[i]!=null) pn0[i].set(cb, stride);
+                if (pn1[i]!=null) pn1[i].set(cb, length + i*stride);
+                if (pn2[i]!=null) pn2[i].set(cb, 2*stride);
+                if (pn3[i]!=null) pn3[i].set(cb, stride);
+                if (pn4[i]!=null) pn4[i].set(cb, stride);
+                if (pn_base1[i]!=null) pn_base1[i].set(cb, base_read);
+            }
+            if (pn5!=null) pn5.set(cb, length);
+            if (pn6!=null) pn6.set(cb, 2*stride+1);
+            if (pn_base2!=null) pn_base2.set(cb, base_write);
+            if (pn_end!=null) pn_end.set(cb, length);
+            cb.sendWord(cb2.getDescriptor(), program.getCBDDestination());
+            cb.sendWord(next.getDescriptor(), next_dest);
+
             cb.seal();
             long base = base_read; base_read=base_write; base_write=base;
-            //i++;
             if (last) break;
-            if ((stride*2) < vals_length) stride *= 2;
+            if ((stride*2) < length) stride *= 2;
         }
-        System.out.println("done building codebags; installing...");
-        System.out.println("cb.length=="+codeBags.size());
-
-        Ship button = pool.allocateShip("Button");
-        CodeBag cb = new CodeBag(dfg.fleet, program);
-        LoopFactory lf = cb.loopFactory(button.getDock("out"), 1);
-        lf.collectWord();
-        lf.literal(codeBags.get(0).getDescriptor());
-        lf.sendWord(program.getCBDDestination());
-        cb.seal();
-
-        // FIXME
-        return program.run(fp, cb, new ShipPool(fp.getFleet()));
-    }
-
-    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);
+        return codeBags.get(0);
+    }
 
-        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 );
+    public static void main(String[] s) throws Exception {
+        if (s.length != 4) {
+            System.err.println("usage: java " + MergeSort.class.getName() + " <target> <shipname> <base> <length>");
+            System.exit(-1);
         }
-        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);
+        Fleet fleet = null;
+        if (s[0].equals("fpga"))             fleet = new Fpga();
+        else if (s[0].equals("interpreter")) {
+            fleet = new Interpreter();
+            Log.log = null;
+        }
+        ShipPool pool = new ShipPool(fleet);
+        Ship memory = pool.allocateShip(s[1]);
+        int base = Integer.parseInt(s[2]);
+        int length = Integer.parseInt(s[3]);
+
+        Random random = new Random(System.currentTimeMillis());        
+        BitVector[] vals  = new BitVector[length];
+        long[] longs = new long[length];
+        for(int i=0; i<vals.length; i++) {
+            vals[i] = new BitVector(fleet.getWordWidth()).set(random.nextLong());
+            for(int j=36; j<vals[i].length(); j++) vals[i].set(j, false);
+            longs[i] = vals[i].toLong();
+        }
+        Arrays.sort(longs);
 
-        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();
+        Ship codemem = pool.allocateShip("Memory");
 
-        System.out.println("dispatching randomization codebag...");
-        prog.run(fp, cb2, pool);
-        System.out.println("  randomization done.");
-        pool.releaseAll();
+        FleetProcess fp = fleet.run(new Instruction[0]);
+        ShipPool pool2 = new ShipPool(pool);
+
+        MemoryUtils.writeMem(fp, pool2, memory, base, vals);
+        pool2.releaseAll();
+
+        Program program = new Program(codemem);
+        CodeBag cb = new MergeSort(fleet, program, pool2, 2, memory, memory).makeInstance(base, length);
+        pool2.releaseAll();
+        long ret = 0;
+        ret = program.run(fp, cb, pool2);
+        pool2.releaseAll();
+
+        MemoryUtils.readMem(fp, pool2, memory, base, vals);
+        pool2.releaseAll();
+
+        System.out.println();
+        int fails = 0;
+        for(int i=0; i<vals.length; i++)
+            if (vals[i].toLong() != longs[i]) {
+                System.out.println("disagreement!  on index " +
+                                   i + "\n  expected="+
+                                   new BitVector(fleet.getWordWidth()).set(longs[i])+
+                                   "\n       got="+vals[i]);
+                fails++;
+            }
+        System.out.println("done! ("+fails+" failures)");
+        if (fails>0) System.exit(-1);
+        
     }
+    
 }