src/edu/berkeley/fleet/dataflow/SortingDemo.java

   1 package edu.berkeley.fleet.dataflow;
   2 import java.util.*;
   3 import java.io.*;
   4 import edu.berkeley.fleet.loops.*;
   5 import edu.berkeley.fleet.api.*;
   6 import edu.berkeley.fleet.fpga.*;
   7 import edu.berkeley.fleet.interpreter.*;
   8 import org.ibex.graphics.*;
   9
  10 public class SortingDemo {
  11
  12     public static void main(String[] s) throws Exception {
  13         //mergeSort(1024*64, 4, "Dvi",
  14         mergeSort(1024*128, 4, "Dvi",
  15                   4194304
  16                   );
  17                   //548*478);
  18     }
  19
  20     /** demo */
  21     public static void main0(String[] s) throws Exception {
  22         PrintWriter pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream("stats.txt")));
  23         //int inflight = 1;
  24         for(int inflight=1; inflight <= 8; inflight++)
  25         for(int count = 32; count < 2097152; count *= 2) {
  26             System.out.println("==============================================================================");
  27             System.out.println("count="+count);
  28             System.out.println("inflight="+inflight);
  29             //long time = timeit(count, inflight);
  30             long time = mergeSort(count, inflight, "DDR2", 0);
  31             pw.println(inflight + ", " + count + ", " + time);
  32             pw.flush();
  33         }
  34     }
  35
  36     public static long timeit(int count, int inflight) throws Exception {
  37         Fleet fleet = Fleet.getDefaultImpl();
  38         FleetProcess fp = fleet.run(new Instruction[0]);
  39         ShipPool pool = new ShipPool(fleet);
  40         //Program program = new Program(pool.allocateShip("Memory"));
  41         CodeBag cb = new CodeBag(fleet);
  42
  43         Ship counter1 = pool.allocateShip("Counter");
  44         Ship counter2 = pool.allocateShip("Counter");
  45
  46         Ship timer    = pool.allocateShip("Timer");
  47         Ship debug    = pool.allocateShip("Debug");
  48
  49         LoopFactory lf;
  50
  51         lf = cb.loopFactory(debug.getDock("in"), 2);
  52         lf.recvWord();
  53         lf.deliver();
  54
  55
  56         // First counter //////////////////////////////////////////////////////////////////////////////
  57
  58         lf = cb.loopFactory(counter1.getDock("in1"), 1);
  59         lf.recvToken();
  60         lf.literal(count);
  61         lf.deliver();
  62
  63         lf = cb.loopFactory(counter1.getDock("in2"), 1);
  64         lf.literal(1);
  65         lf.deliver();
  66
  67         lf = cb.loopFactory(counter1.getDock("inOp"), 1);
  68         lf.literal("COUNT");
  69         lf.deliver();
  70
  71         lf = cb.loopFactory(counter1.getDock("out"), 0);
  72         lf.recvToken();
  73         lf.collectWord();
  74         lf.sendWord(counter2.getDock("in2"));
  75
  76
  77         // Second counter //////////////////////////////////////////////////////////////////////////////
  78
  79         lf = cb.loopFactory(counter2.getDock("in1"), 1);
  80         lf.literal(count);
  81         lf.deliver();
  82         lf.literal(1);
  83         lf.deliver();
  84         lf.literal(1);
  85         lf.deliver();
  86
  87         lf = cb.loopFactory(counter2.getDock("in2"), 1);
  88         for(int i=0; i<inflight; i++)
  89             lf.sendToken(counter1.getDock("out"));
  90         lf = lf.makeNext(0);
  91         lf.recvWord();
  92         lf.sendToken(counter1.getDock("out"));
  93         lf.deliver();
  94
  95         lf = cb.loopFactory(counter2.getDock("inOp"), 1);
  96         lf.literal("DROP_C1_V2");
  97         lf.deliver();
  98         lf.literal("PASS_C1_V1");
  99         lf.deliver();
 100
 101         lf = cb.loopFactory(counter2.getDock("out"), 1);
 102         lf.collectWord();
 103         lf.sendToken(timer.getDock("out"));
 104
 105
 106         // Timer //////////////////////////////////////////////////////////////////////////////
 107
 108         lf = cb.loopFactory(timer.getDock("out"), 1);
 109         // collect twice just to be safe
 110         lf.collectWord();
 111         lf.collectWord();
 112         lf.sendToken(counter1.getDock("in1"));
 113         lf.sendWord(debug.getDock("in"));
 114         lf.recvToken();
 115         // collect twice just to be safe
 116         lf.collectWord();
 117         lf.collectWord();
 118         lf.sendWord(debug.getDock("in"));
 119
 120         Dock out = (Dock)counter1.getDock("out");
 121         Dock in  = (Dock)counter2.getDock("in2");
 122         //System.out.println("distance is " + out.getPathLength((FpgaDestination)in.getDataDestination()));
 123         //System.out.println("reverse distance is " + in.getPathLength((FpgaDestination)out.getDataDestination()));
 124
 125         for(Instruction i : cb.emit()) System.out.println(i);
 126         cb.dispatch(fp, true);
 127         long time1 = fp.recvWord().toLong();
 128         System.out.println("got " + time1);
 129         long time2 = fp.recvWord().toLong();
 130         System.out.println("got " + time2);
 131         System.out.println("diff=" + (time2-time1));
 132
 133         fp.terminate();
 134
 135         return (time2-time1);
 136     }
 137
 138     public static long mergeSort(int vals_length, int inflight, String shipType, int clearAmount) throws Exception {
 139         Node.CAPACITY = inflight;
 140
 141         Fleet fleet = Fleet.getDefaultImpl();
 142         FleetProcess fp = fleet.run(new Instruction[0]);
 143         ShipPool pool = new ShipPool(fleet);
 144         Ship mem1 = pool.allocateShip(shipType);
 145
 146         if (clearAmount > 0)
 147             randomizeMemory(fp, pool, mem1, 0, clearAmount, false);
 148
 149         //randomizeMemory(fp, pool, mem1, 0, vals_length, true);
 150
 151         BitVector[] bvs = new BitVector[vals_length];
 152
 153         long index = 0;
 154         Picture p = new Picture(new FileInputStream("campus.png"));
 155         for(int y=0; y<(478/2); y++)
 156             for(int x=0; x<544; x++) {
 157                 if (index >= vals_length) break;
 158                 int pixel = (x>=p.width) ? 0 : p.data[p.width*y+x];
 159                 long r = (pixel>>0)  & 0xff;
 160                 long g = (pixel>>8)  & 0xff;
 161                 long b = (pixel>>16) & 0xff;
 162                 r >>= 2;
 163                 g >>= 2;
 164                 b >>= 2;
 165                 //r = ~(-1L<<6);
 166                 //g = ~(-1L<<6);
 167                 //b = ~(-1L<<6);
 168                 bvs[(int)index] = new BitVector(fleet.getWordWidth()).set( r | (g<<6) | (b<<12) | (index<<18) );
 169                 index++;
 170             }
 171
 172         for(; index<vals_length; index++) {
 173             long tag = index<<18;
 174             bvs[(int)index] = new BitVector(fleet.getWordWidth()).set( tag );
 175         }
 176
 177         System.out.println("final index " + index);
 178
 179         Random random = new Random(System.currentTimeMillis());
 180         for(int i=0; i<bvs.length*10; i++) {
 181             int from = Math.abs(random.nextInt()) % bvs.length;
 182             int to   = Math.abs(random.nextInt()) % bvs.length;
 183             BitVector bv = bvs[from];
 184             bvs[from] = bvs[to];
 185             bvs[to] = bv;
 186         }
 187
 188         int offset = 40;
 189         MemoryUtils.writeMem(fp, pool, mem1, 40, bvs);
 190
 191         Ship mem = pool.allocateShip("Memory");
 192         Program program = new Program(mem);
 193         CodeBag cb_ = new MergeSort(fleet, program, pool, 2, mem1, mem1).makeInstance(offset, vals_length);
 194         cb_.seal();
 195         Ship button = pool.allocateShip("Button");
 196         CodeBag cb = new CodeBag(fleet, program);
 197         LoopFactory lf = cb.loopFactory(button.getDock("out"), 1);
 198         lf.collectWord();
 199         lf.literal(cb_.getDescriptor());
 200         lf.sendWord(program.getCBDDestination());
 201         cb.seal();
 202
 203         ShipPool pool2 = new ShipPool(fp.getFleet());
 204         pool2.allocateShip(program.memoryShip);
 205         // FIXME
 206         long ret = program.run(fp, cb, pool2);
 207         pool2.releaseShip(program.memoryShip);
 208
 209         //long ret = 0;
 210         // verify the cleanup?
 211         //CleanupUtils.verifyClean(fp);
 212         //MemoryUtils.readMem(fp, new ShipPool(fp.getFleet()), mem1, 0, bvs);
 213
 214         BitVector[] bvx = new BitVector[1024];
 215         pool.allocateShip(mem);
 216         MemoryUtils.readMem(fp, new ShipPool(fp.getFleet()), mem1, 0, bvx);
 217         for(int i=0; i<bvx.length; i++)
 218             System.out.println(bvx[i]);
 219         /*
 220         System.out.println("results:");
 221         for(int i=0; i<vals_length-1; i++)
 222             if ( (bvs[i].toLong() & ~(-1L<<18)) != ~(-1L<<18))
 223                 System.out.println(bvs[i]);
 224         */
 225         /*
 226         for(int i=0; i<vals_length-1; i++) {
 227             if (bvs[i].toLong() > bvs[i+1].toLong())
 228                 System.out.println("sort failure at "+i+":\n  "+bvs[i]+"\n  "+bvs[i+1]);
 229         }
 230         */
 231         fp.terminate();
 232         return ret;
 233     }
 234
 235     //static int offset = 32;
 236     //static int offset = 544*2;
 237     //static int offset = 544;
 238
 239     public static void randomizeMemory(FleetProcess fp, ShipPool pool_, Ship memory, long start, long length, boolean randomize) {
 240         ShipPool pool = new ShipPool(pool_);
 241         Ship mem = pool.allocateShip("Memory");
 242         Program prog = new Program(mem);
 243
 244         DataFlowGraph dfg = new DataFlowGraph(fp.getFleet(), pool);
 245         DownCounterNode dcn = new DownCounterNode(dfg);
 246         dcn.start.connectOnce(length);
 247         dcn.incr.connectOnce(1);
 248
 249         AluNode alu = new AluNode(dfg, "ADD");
 250         alu.in1.connectForever(start);
 251         alu.in2.connect(dcn.out);
 252
 253         MemoryNode mn = new MemoryNode(dfg, memory);
 254         mn.inAddrWrite.connect(alu.out);
 255
 256         AluNode aluAnd = new AluNode(dfg, "AND");
 257         if (randomize) {
 258             aluAnd.in1.connect(new RandomNode(dfg).out);
 259         } else {
 260             //aluAnd.in1.connectForever( ~(-1L<<36) );
 261             aluAnd.in1.connectForever( 0 );
 262         }
 263         aluAnd.in2.connectForever( ~(-1<<18) );
 264         mn.inDataWrite.connect(aluAnd.out);
 265
 266         UnPunctuatorNode discard = new UnPunctuatorNode(dfg, true);
 267         discard.count.connectOnce(length);
 268         discard.val.connect(mn.outWrite);
 269         DoneNode done = new DoneNode(dfg, prog);
 270         discard.out.connect(done.in);
 271
 272         CodeBag cb = new CodeBag(fp.getFleet(), prog);
 273         dfg.build(cb);
 274         cb.seal();
 275
 276         CodeBag cb2 = new CodeBag(fp.getFleet(), prog);
 277         Ship button = fp.getFleet().getShip("Button",0);
 278
 279         LoopFactory lf = cb2.loopFactory(button.getDock("out"), 1);
 280         //lf.collectWord();
 281         lf.literal(prog.getEndProgramCodeBag().getDescriptor());
 282         lf.sendWord(done.getDestinationToSendNextCodeBagDescriptorTo());
 283         lf.literal(cb.getDescriptor());
 284         lf.sendWord(prog.getCBDDestination());
 285         cb2.seal();
 286
 287         System.out.println("dispatching randomization codebag...");
 288         prog.run(fp, cb2, pool);
 289         System.out.println("  randomization done.");
 290         pool.releaseAll();
 291     }
 292
 293 }