From 390ea921b89fd293ecba9f228354f84b9933bebc Mon Sep 17 00:00:00 2001 From: Adam Megacz Date: Fri, 31 Jul 2009 21:38:21 -0700 Subject: [PATCH] move graphical sorting demo into SortingDemo, make a command-line sorting regression test, add it to Makefile --- Makefile | 8 +- src/edu/berkeley/fleet/dataflow/MergeSort.java | 400 +++++----------------- src/edu/berkeley/fleet/dataflow/SortingDemo.java | 289 ++++++++++++++++ 3 files changed, 375 insertions(+), 322 deletions(-) create mode 100644 src/edu/berkeley/fleet/dataflow/SortingDemo.java diff --git a/Makefile b/Makefile index 959a27d..2c4887a 100644 --- a/Makefile +++ b/Makefile @@ -225,8 +225,12 @@ synth: runserver: fleet.jar java -Djava.library.path=lib -cp fleet.jar:lib/RXTXcomm.jar edu.berkeley.fleet.fpga.Server -test: fleet.jar; $(java) -jar fleet.jar test ships/*.ship tests -testfpga: fleet.jar; $(java) -jar fleet.jar target=fpga test ships/*.ship tests +test: fleet.jar + $(java) -jar fleet.jar test ships/*.ship tests + java -cp fleet.jar edu.berkeley.fleet.dataflow.MergeSort interpreter Memory 0 256 +testfpga: fleet.jar + $(java) -jar fleet.jar target=fpga test ships/*.ship tests + java -cp fleet.jar edu.berkeley.fleet.dataflow.MergeSort fpga Memory 0 256 ## Manual #################################################################################### diff --git a/src/edu/berkeley/fleet/dataflow/MergeSort.java b/src/edu/berkeley/fleet/dataflow/MergeSort.java index 876cf91..4faf03e 100644 --- a/src/edu/berkeley/fleet/dataflow/MergeSort.java +++ b/src/edu/berkeley/fleet/dataflow/MergeSort.java @@ -3,6 +3,7 @@ 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.*; @@ -38,16 +39,12 @@ 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); @@ -117,257 +114,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= 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 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 codeBags = new ArrayList(); 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(); @@ -375,83 +131,87 @@ 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 "); + 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(); + 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; i0) System.exit(-1); + } + } 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= 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 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 -- 1.7.10.4