From 84373ca83373e988b8f9eaec0d9de0ac8a737a5f Mon Sep 17 00:00:00 2001 From: adam Date: Mon, 3 Nov 2008 11:19:25 +0100 Subject: [PATCH] add src/edu/berkeley/fleet/ir/Process.java --- src/edu/berkeley/fleet/ir/Process.java | 679 ++++++++++++++++++++++++++++++++ 1 file changed, 679 insertions(+) create mode 100644 src/edu/berkeley/fleet/ir/Process.java diff --git a/src/edu/berkeley/fleet/ir/Process.java b/src/edu/berkeley/fleet/ir/Process.java new file mode 100644 index 0000000..e63e905 --- /dev/null +++ b/src/edu/berkeley/fleet/ir/Process.java @@ -0,0 +1,679 @@ +package edu.berkeley.fleet.ir; +import java.util.*; +import java.net.*; +import edu.berkeley.fleet.two.*; +import edu.berkeley.fleet.api.*; +import edu.berkeley.fleet.fpga.*; +import edu.berkeley.fleet.api.Instruction.*; +import edu.berkeley.fleet.api.Instruction.Set; +import edu.berkeley.fleet.api.Instruction.Set.*; +import static edu.berkeley.fleet.api.Predicate.*; +import static edu.berkeley.fleet.util.BitManipulations.*; + + +/* + - refactor the cleanup into the subclasses of Port (phase1, phase2, etc) + */ + +// does peer.recvWord() have to honor the currently-set predicate? + +// public class ReplaceModule extends Module { } +// public class CountMergeModule extends Module { } +// public class SortMergeModule extends Module { } +// public class FanOutModule extends Module { } +// public class MemoryModule extends Module { } +// public class DoneModule extends Module { } + +public class Process { + + public static int reset_count = 0; + public static HashSet torpedoes = new HashSet(); + + public final Fleet fleet; + public final ShipPool pool; + + public Process(Fleet fleet) { + this.fleet = fleet; + this.pool = new ShipPool(fleet); + } + + private HashSet modules = new HashSet(); + + public void build(Context ctx) { + for(Module mod : modules) + mod.build(ctx); + } + public void reset(Context ctx, int phase) { + reset_count = 0; + torpedoes.clear(); + for(Module mod : modules) + mod.reset(ctx, phase); + } + + public class Module { + + public Module() { + Process.this.modules.add(this); + } + + private HashMap ports = new HashMap(); + + public InPort getInPort(String name) { return (InPort)ports.get(name); } + public OutPort getOutPort(String name) { return (OutPort)ports.get(name); } + + public void build(Context ctx) { for(Port p : ports.values()) p.build(ctx); } + public void reset(Context ctx, int phase) { for(Port p : ports.values()) p.reset(ctx, phase); } + + public abstract class Port { + public final String name; + public Port(String name) { + this.name = name; + if (Module.this.ports.get(name)!=null) throw new RuntimeException(); + Module.this.ports.put(name,this); + } + public abstract void build(Context ctx); + public abstract void reset(Context ctx, int phase); + } + + public abstract class InPort extends Port { + OutPort peer; + public InPort(String name) { super(name); } + public void connect(OutPort peer) { + this.setPeer(peer); + peer.setPeer(this); + } + public void setPeer(OutPort peer) { + if (this.peer!=null) throw new RuntimeException("cannot call setPeer() twice"); + this.peer = peer; + } + + /** this port's peer (an OutPort) invokes this to have "recvToken" or equivalent inserted */ + public abstract void recvToken(Context.LoopFactory loopfactory_at_output_dock); + /** this port's peer (an OutPort) invokes this to have "sendWord" or equivalent inserted */ + public abstract void sendWord(Context.LoopFactory loopfactory_at_output_dock); + } + + public abstract class OutPort extends Port { + InPort peer; + public OutPort(String name) { super(name); } + public void connect(InPort peer) { + this.setPeer(peer); + peer.setPeer(this); + } + public void setPeer(InPort peer) { + if (this.peer!=null) throw new RuntimeException("cannot call setPeer() twice"); + this.peer = peer; + } + + /** this port's peer (an InPort) invokes this to have "sendToken" or equivalent inserted */ + public abstract void sendToken(Context.LoopFactory loopfactory_at_input_dock); + /** this port's peer (an InPort) invokes this to have "recvWord" or equivalent inserted */ + public abstract void recvWord(Context.LoopFactory loopfactory_at_input_dock); + } + + public final class DockInPort extends InPort { + final Dock dock; + int count; + BitVector[] pattern; + public DockInPort(String name, Dock dock) { this(name, dock, 0); } + public DockInPort(String name, Dock dock, int count) { this(name, dock, count, new BitVector[] { null }); } + public DockInPort(String name, Dock dock, int count, BitVector[] pattern) { + super(name); + this.dock = dock; + this.count = count; + this.pattern = pattern; + } + public void recvToken(Context.LoopFactory lf) { lf.recvToken(); } + public void sendWord(Context.LoopFactory lf) { lf.sendWord(dock.getDataDestination()); } + public void build(Context ctx) { build(ctx, ctx.new LoopFactory(dock, 1)); } + // number-in-flight is considered a property of the input dock in a pair + //public int getInflight() { return 4; } + public int getInflight() { return 1; } + public void reset(Context ctx, int phase) { + if (dock.getShip().getType().equals("Debug")) { + return; + } + switch(phase) { + case 0: { + torpedoes.add(dock); + break; + } + case 1: { + // FIXME + reset_count++; + Context.LoopFactory lf = ctx.new LoopFactory(dock, 1); + lf.sendToken(fleet.getShip("Debug",0).getDock("in").getDataDestination()); + if (peer != null && peer instanceof DockOutPort) { + DockOutPort dop_peer = (DockOutPort)peer; + lf = lf.makeNext(0); + lf.abortLoopIfTorpedoPresent(); + lf.recvToken(); + lf.sendToken(dop_peer.dock.getDataDestination()); + } + break; + } + case 2: { + if (peer != null && peer instanceof DockOutPort) { + torpedoes.add(dock); + } + break; + } + } + } + protected void build(Context ctx, Context.LoopFactory lf) { + int inflight = (count != 0 && count < getInflight()) ? count : getInflight(); + + if (peer!=null) + for(int i=0; iout is + * maintained, but out is not flow-controlled, so be sure + * that every datum sent there is consumed synchronously wiht + * data items sent to out. + */ + public class ForeverModule extends Module { + private BitVector bv; + public final OutPort out = new OutPort("out") { + public void sendToken(Context.LoopFactory lf) { } + public void recvWord(Context.LoopFactory lf) { } + public void build(Context ctx) { } + public void reset(Context ctx, int phase) { } + public void setPeer(InPort peer) { + this.peer = peer; + DockInPort pip = ((DockInPort)peer); + for(int i=0; i= pip_pattern.length) j = 0; + } + pip.pattern = new BitVector[i]; + System.arraycopy(temp, 0, pip.pattern, 0, i); + pip.count = 1; + } + }; + public OnceModule(long l) { this(new BitVector(fleet.getWordWidth()).set(l)); } + public OnceModule(final BitVector bv) { this.bv = bv; } + } + + public class DebugModule extends Module { + public final Ship ship = pool.allocateShip("Debug"); + public final InPort in = new DockInPort("in", ship.getDock("in")); + // NOTE: shutdown needs to treat this specially + public DebugModule() { } + } + + public class UnPunctuatorModule extends Module { + private final Ship ship = pool.allocateShip("Counter"); + public final OutPort out = new DockOutPort("out", ship.getDock("out")); + public final InPort val = new DockInPort("in1", ship.getDock("in1")); + public final InPort count = new DockInPort("in2", ship.getDock("in2"), 0, new BitVector[] { null, bv(1) }); + public final InPort op = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(6 /*PASS_C2_V1*/), bv(10 /*DROP_C2_V1*/) } ); + public UnPunctuatorModule() { } + } + + public class PunctuatorModule extends Module { + private final long punc; + private final Ship ship = pool.allocateShip("Counter"); + public final OutPort out = new DockOutPort("out", ship.getDock("out")); + public final InPort val = new DockInPort("in1", ship.getDock("in1")); + public final InPort op = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(6 /*PASS_C2_V1*/), bv(7 /*PASS_C2_V2*/) } ); + public final InPort count; + public PunctuatorModule(long punc) { + this.punc = punc; + this.count = new DockInPort("in2", ship.getDock("in2"), 0, new BitVector[] { null, bv(1), bv(punc) }); + } + } + + public class AluModule extends Module { + public final Ship ship = pool.allocateShip("Alu"); + public final InPort in1 = new DockInPort("in1", ship.getDock("in1")); + public final InPort in2 = new DockInPort("in2", ship.getDock("in2")); + public final InPort inOp = new DockInPort("inOp", ship.getDock("inOp")); + public final OutPort out = new DockOutPort("out", ship.getDock("out")); + public AluModule() { } + } + + public class DownCounterModule extends Module { + public final Ship ship = pool.allocateShip("Counter"); + public final InPort start = new DockInPort("in1", ship.getDock("in1")); + public final InPort incr = new DockInPort("in2", ship.getDock("in2")); + public final InPort inOp = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(12 /*COUNTDOWN*/) }); + public final OutPort out = new DockOutPort("out", ship.getDock("out")); + public DownCounterModule() { } + } + + public class RepeatModule extends Module { + public final Ship ship = pool.allocateShip("Counter"); + public final InPort count = new DockInPort("in1", ship.getDock("in1")); + public final InPort val = new DockInPort("in2", ship.getDock("in2")); + public final InPort inOP = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(1 /*REPEAT_C1_V2*/) }); + public final OutPort out = new DockOutPort("out", ship.getDock("out")); + public RepeatModule() { } + } + + public class SortedMergeModule extends Module { + public final Ship ship = pool.allocateShip("Alu"); + public final InPort in1 = new DockInPort("in1", ship.getDock("in1")); + public final InPort in2 = new DockInPort("in2", ship.getDock("in2")); + public final InPort inOp = new DockInPort("inOp", ship.getDock("inOp"), 0, new BitVector[] { bv(9 /*MAXMERGE*/) }); + public final OutPort out = new DockOutPort("out", ship.getDock("out")); + public SortedMergeModule() { } + } + + public class MemoryModule extends Module { + public final Ship ship; + public final InPort inAddrRead1; + public final InPort inAddrRead2; + //public final InPort inAddrWrite; + //public final InPort inDataWrite; + public final OutPort outRead1; + public final OutPort outRead2; + public MemoryModule(Ship memoryShip) { + this.ship = memoryShip; + this.inAddrRead1 = new InPort("inAddrRead1") { + public void recvToken(Context.LoopFactory lf) { lf.recvToken(); } + public void sendWord(Context.LoopFactory lf) { lf.sendWord(ship.getDock("inAddrRead").getDataDestination(), new BitVector(1).set(0)); } + public void build(Context ctx) { } + public void reset(Context ctx, int phase) { + if (phase==2) { + torpedoes.add(ship.getDock("inAddrRead")); + torpedoes.add(ship.getDock("out")); + } + } + }; + this.inAddrRead2 = new InPort("inAddrRead2") { + public void recvToken(Context.LoopFactory lf) { lf.recvToken(); } + public void sendWord(Context.LoopFactory lf) { lf.sendWord(ship.getDock("inAddrRead").getDataDestination(), new BitVector(1).set(1)); } + public void build(Context ctx) { } + public void reset(Context ctx, int phase) { + if (phase==2) { + torpedoes.add(ship.getDock("inAddrRead")); + torpedoes.add(ship.getDock("out")); + } + } + }; + this.outRead1 = new OutPort("outRead1") { + public void sendToken(Context.LoopFactory lf) { inAddrRead1.peer.sendToken(lf); } + public void recvWord(Context.LoopFactory lf) { lf.recvWord(); } + public void build(Context ctx) { } + public void reset(Context ctx, int phase) { } + }; + this.outRead2 = new OutPort("outRead2") { + public void sendToken(Context.LoopFactory lf) { inAddrRead2.peer.sendToken(lf); } + public void recvWord(Context.LoopFactory lf) { lf.recvWord(); } + public void build(Context ctx) { } + public void reset(Context ctx, int phase) { } + }; + } + public void build(Context ctx) { + super.build(ctx); + Context.LoopFactory lf; + + lf = ctx.new LoopFactory(ship.getDock("inAddrRead"), 0); + lf.abortLoopIfTorpedoPresent(); + lf.recvWord(); + lf.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO); + lf.setPredicate(Predicate.NotFlagA); + lf.sendToken(ship.getDock("out").getDataDestination(), new BitVector(1).set(0)); + lf.setPredicate(Predicate.FlagA); + lf.sendToken(ship.getDock("out").getDataDestination(), new BitVector(1).set(1)); + lf.setPredicate(null); + lf.deliver(); + + lf = ctx.new LoopFactory(ship.getDock("out"), 0); + lf.abortLoopIfTorpedoPresent(); + lf.collectWord(); + lf.abortLoopIfTorpedoPresent(); + lf.recvToken(); + lf.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO); + if (outRead1.peer != null) { + lf.setPredicate(Predicate.NotFlagA); + outRead1.peer.sendWord(lf); + } + if (outRead2.peer != null) { + lf.setPredicate(Predicate.FlagA); + outRead2.peer.sendWord(lf); + } + lf.setPredicate(null); + } + } + + public static void main(String[] s) throws Exception { + Fleet fleet = new Fpga(); + Random random = new Random(System.currentTimeMillis()); + long[] vals = new long[256]; + for(int i=0; i ai = new ArrayList(); + ctx.emit(ai); + for(Instruction ins : ai) fp.sendInstruction(ins); + fp.flush(); + + System.out.println("checking debug.in"); + if (fp.recvWord().toLong() != 12) throw new RuntimeException("debug dock not properly initialized"); + if (fp.recvWord().toLong() != 5) throw new RuntimeException("debug dock not properly initialized"); + + int k = 0; + for(Ship ship : fp.getFleet()) + if (!"Debug".equals(ship.getType())) + for (Dock dock : ship) { + System.out.println("checking " + dock); + + k = (k + 23) % 65535; + ctx = new Context(fp.getFleet()); + lf = ctx.new LoopFactory(debugIn, 1); + lf.literal(k); + lf.recvToken(); + lf.deliver(); + lf = ctx.new LoopFactory(dock, 1); + lf.sendToken(debugIn.getDataDestination()); + ai = new ArrayList(); + ctx.emit(ai); + for(Instruction ins : ai) fp.sendInstruction(ins); + fp.flush(); + + if (fp.recvWord().toLong() != k) + throw new RuntimeException(dock+" not properly initialized"); + } + } + + // FIXME: numbers seem to get duplicated when stride=2 + public static long[] mergeSort(FleetProcess fp, Fleet fleet, long[] vals, int stride_length) throws Exception { + + BitVector[] mem = new BitVector[vals.length]; + for(int i=0; i ai = new ArrayList(); + proc.build(ctx); + ctx.emit(ai); + for(Instruction ins : ai) { + System.out.println(ins); + fp.sendInstruction(ins); + } + fp.flush(); + + System.out.println("reading back..."); + int inc=0; + for(int i=0; i()); + for(Instruction ins : ai) + fp.sendInstruction(ins); + fp.flush(); + + int count = 0; + + for(int phase=0; phase<=2; phase++) { + System.out.println("== phase "+phase+" =================================================================="); + ctx2 = new Context(fp.getFleet()); + proc.reset(ctx2, phase); + for(Dock dock : torpedoes) fp.sendToken(dock.getInstructionDestination()); + ctx2.emit(ai = new ArrayList()); + for(Instruction ins : ai) fp.sendInstruction(ins); + fp.flush(); + System.out.println("flushed"); + for(int ii=0; ii " + fp.recvWord().toLong() + " " + (ii+1) + " / " + reset_count); + System.out.println(); + } + + /* + ctx2 = new Context(fp.getFleet()); + ai = new ArrayList(); + for(Ship ship : ctx.allocatedShips) + if (!ship.getType().equals("Debug")) + for(Dock dock : ship) + if (dock.isInputDock()) { + lf = ctx2.new LoopFactory(dock, 0); + lf.recvWord(); + + } + */ + + fp.sendToken(debugIn.getInstructionDestination()); + fp.flush(); + + //System.out.println("verifying cleanup:"); + //verifyClean(fp); + return ret; + } + + private BitVector[] longsToBitVectors(long[] initialValues) { + BitVector[] bv = new BitVector[initialValues.length]; + for(int i=0; i