1 package edu.berkeley.fleet.dataflow;
4 import edu.berkeley.fleet.loops.*;
5 import edu.berkeley.fleet.api.*;
6 import edu.berkeley.fleet.fpga.*;
7 import org.ibex.graphics.*;
9 public class SortingDemo {
11 public static void main(String[] s) throws Exception {
12 //mergeSort(1024*64, 4, "Dvi",
13 mergeSort(1024*128, 4, "Dvi",
20 public static void main0(String[] s) throws Exception {
21 PrintWriter pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream("stats.txt")));
23 for(int inflight=1; inflight <= 8; inflight++)
24 for(int count = 32; count < 2097152; count *= 2) {
25 System.out.println("==============================================================================");
26 System.out.println("count="+count);
27 System.out.println("inflight="+inflight);
28 //long time = timeit(count, inflight);
29 long time = mergeSort(count, inflight, "DDR2", 0);
30 pw.println(inflight + ", " + count + ", " + time);
35 public static long timeit(int count, int inflight) throws Exception {
36 Fleet fleet = new Fpga();
37 FleetProcess fp = fleet.run(new Instruction[0]);
38 ShipPool pool = new ShipPool(fleet);
39 //Program program = new Program(pool.allocateShip("Memory"));
40 CodeBag cb = new CodeBag(fleet);
42 Ship counter1 = pool.allocateShip("Counter");
43 Ship counter2 = pool.allocateShip("Counter");
45 Ship timer = pool.allocateShip("Timer");
46 Ship debug = pool.allocateShip("Debug");
50 lf = cb.loopFactory(debug.getDock("in"), 2);
55 // First counter //////////////////////////////////////////////////////////////////////////////
57 lf = cb.loopFactory(counter1.getDock("in1"), 1);
62 lf = cb.loopFactory(counter1.getDock("in2"), 1);
66 lf = cb.loopFactory(counter1.getDock("inOp"), 1);
70 lf = cb.loopFactory(counter1.getDock("out"), 0);
73 lf.sendWord(counter2.getDock("in2"));
76 // Second counter //////////////////////////////////////////////////////////////////////////////
78 lf = cb.loopFactory(counter2.getDock("in1"), 1);
86 lf = cb.loopFactory(counter2.getDock("in2"), 1);
87 for(int i=0; i<inflight; i++)
88 lf.sendToken(counter1.getDock("out"));
91 lf.sendToken(counter1.getDock("out"));
94 lf = cb.loopFactory(counter2.getDock("inOp"), 1);
95 lf.literal("DROP_C1_V2");
97 lf.literal("PASS_C1_V1");
100 lf = cb.loopFactory(counter2.getDock("out"), 1);
102 lf.sendToken(timer.getDock("out"));
105 // Timer //////////////////////////////////////////////////////////////////////////////
107 lf = cb.loopFactory(timer.getDock("out"), 1);
109 lf.sendToken(counter1.getDock("in1"));
110 lf.sendWord(debug.getDock("in"));
113 lf.sendWord(debug.getDock("in"));
115 FpgaDock out = (FpgaDock)counter1.getDock("out");
116 FpgaDock in = (FpgaDock)counter2.getDock("in2");
117 System.out.println("distance is " + out.getPathLength((FpgaDestination)in.getDataDestination()));
118 System.out.println("reverse distance is " + in.getPathLength((FpgaDestination)out.getDataDestination()));
120 for(Instruction i : cb.emit()) System.out.println(i);
121 cb.dispatch(fp, true);
122 long time1 = fp.recvWord().toLong();
123 System.out.println("got " + time1);
124 long time2 = fp.recvWord().toLong();
125 System.out.println("got " + time2);
126 System.out.println("diff=" + (time2-time1));
130 return (time2-time1);
133 public static long mergeSort(int vals_length, int inflight, String shipType, int clearAmount) throws Exception {
134 Node.CAPACITY = inflight;
136 Fleet fleet = new Fpga();
137 FleetProcess fp = fleet.run(new Instruction[0]);
138 ShipPool pool = new ShipPool(fleet);
139 Ship mem1 = pool.allocateShip(shipType);
143 randomizeMemory(fp, pool, mem1, 0, clearAmount, false);
145 //randomizeMemory(fp, pool, mem1, 0, vals_length, true);
147 BitVector[] bvs = new BitVector[vals_length];
150 Picture p = new Picture(new FileInputStream("campus.png"));
151 for(int y=0; y<(478/2); y++)
152 for(int x=0; x<544; x++) {
153 if (index >= vals_length) break;
154 int pixel = (x>=p.width) ? 0 : p.data[p.width*y+x];
155 long r = (pixel>>0) & 0xff;
156 long g = (pixel>>8) & 0xff;
157 long b = (pixel>>16) & 0xff;
164 bvs[(int)index] = new BitVector(fleet.getWordWidth()).set( r | (g<<6) | (b<<12) | (index<<18) );
168 for(; index<vals_length; index++) {
169 long tag = index<<18;
170 bvs[(int)index] = new BitVector(fleet.getWordWidth()).set( tag );
173 System.out.println("final index " + index);
175 Random random = new Random(System.currentTimeMillis());
176 for(int i=0; i<bvs.length*10; i++) {
177 int from = Math.abs(random.nextInt()) % bvs.length;
178 int to = Math.abs(random.nextInt()) % bvs.length;
179 BitVector bv = bvs[from];
185 MemoryUtils.writeMem(fp, pool, mem1, 40, bvs);
187 Ship mem = pool.allocateShip("Memory");
188 Program program = new Program(mem);
189 CodeBag cb_ = new MergeSort(fleet, program, pool, 2, mem1, mem1).makeInstance(offset, vals_length);
191 Ship button = pool.allocateShip("Button");
192 CodeBag cb = new CodeBag(fleet, program);
193 LoopFactory lf = cb.loopFactory(button.getDock("out"), 1);
195 lf.literal(cb_.getDescriptor());
196 lf.sendWord(program.getCBDDestination());
199 ShipPool pool2 = new ShipPool(fp.getFleet());
200 pool2.allocateShip(program.memoryShip);
202 long ret = program.run(fp, cb, pool2);
203 pool2.releaseShip(program.memoryShip);
206 // verify the cleanup?
207 //CleanupUtils.verifyClean(fp);
208 //MemoryUtils.readMem(fp, new ShipPool(fp.getFleet()), mem1, 0, bvs);
210 BitVector[] bvx = new BitVector[1024];
211 pool.allocateShip(mem);
212 MemoryUtils.readMem(fp, new ShipPool(fp.getFleet()), mem1, 0, bvx);
213 for(int i=0; i<bvx.length; i++)
214 System.out.println(bvx[i]);
216 System.out.println("results:");
217 for(int i=0; i<vals_length-1; i++)
218 if ( (bvs[i].toLong() & ~(-1L<<18)) != ~(-1L<<18))
219 System.out.println(bvs[i]);
222 for(int i=0; i<vals_length-1; i++) {
223 if (bvs[i].toLong() > bvs[i+1].toLong())
224 System.out.println("sort failure at "+i+":\n "+bvs[i]+"\n "+bvs[i+1]);
231 //static int offset = 32;
232 //static int offset = 544*2;
233 //static int offset = 544;
235 public static void randomizeMemory(FleetProcess fp, ShipPool pool_, Ship memory, long start, long length, boolean randomize) {
236 ShipPool pool = new ShipPool(pool_);
237 Ship mem = pool.allocateShip("Memory");
238 Program prog = new Program(mem);
240 DataFlowGraph dfg = new DataFlowGraph(fp.getFleet(), pool);
241 DownCounterNode dcn = new DownCounterNode(dfg);
242 dcn.start.connectOnce(length);
243 dcn.incr.connectOnce(1);
245 AluNode alu = new AluNode(dfg, "ADD");
246 alu.in1.connectForever(start);
247 alu.in2.connect(dcn.out);
249 MemoryNode mn = new MemoryNode(dfg, memory);
250 mn.inAddrWrite.connect(alu.out);
252 AluNode aluAnd = new AluNode(dfg, "AND");
254 aluAnd.in1.connect(new RandomNode(dfg).out);
256 //aluAnd.in1.connectForever( ~(-1L<<36) );
257 aluAnd.in1.connectForever( 0 );
259 aluAnd.in2.connectForever( ~(-1<<18) );
260 mn.inDataWrite.connect(aluAnd.out);
262 UnPunctuatorNode discard = new UnPunctuatorNode(dfg, true);
263 discard.count.connectOnce(length);
264 discard.val.connect(mn.outWrite);
265 DoneNode done = new DoneNode(dfg, prog);
266 discard.out.connect(done.in);
268 CodeBag cb = new CodeBag(fp.getFleet(), prog);
272 CodeBag cb2 = new CodeBag(fp.getFleet(), prog);
273 Ship button = fp.getFleet().getShip("Button",0);
275 LoopFactory lf = cb2.loopFactory(button.getDock("out"), 1);
277 lf.literal(prog.getEndProgramCodeBag().getDescriptor());
278 lf.sendWord(done.getDestinationToSendNextCodeBagDescriptorTo());
279 lf.literal(cb.getDescriptor());
280 lf.sendWord(prog.getCBDDestination());
283 System.out.println("dispatching randomization codebag...");
284 prog.run(fp, cb2, pool);
285 System.out.println(" randomization done.");