From ab5e85e23cfb5d3d73a8d1c16588f81efd59f006 Mon Sep 17 00:00:00 2001 From: adam Date: Wed, 22 Aug 2007 11:55:24 +0100 Subject: [PATCH] reorganize mpar code --- Makefile | 2 +- src/edu/berkeley/slipway/MPARDemo.java | 855 --------------------- src/edu/berkeley/slipway/mpar/FlatNetlist.java | 246 ++++++ src/edu/berkeley/slipway/mpar/MPARDemo.java | 311 ++++++++ src/edu/berkeley/slipway/mpar/PhysicalDevice.java | 320 ++++++++ 5 files changed, 878 insertions(+), 856 deletions(-) delete mode 100644 src/edu/berkeley/slipway/MPARDemo.java create mode 100644 src/edu/berkeley/slipway/mpar/FlatNetlist.java create mode 100644 src/edu/berkeley/slipway/mpar/MPARDemo.java create mode 100644 src/edu/berkeley/slipway/mpar/PhysicalDevice.java diff --git a/Makefile b/Makefile index dbb153c..48d624e 100644 --- a/Makefile +++ b/Makefile @@ -117,7 +117,7 @@ upstream/avr-libc/.built: upstream/avr-libc upstream/gcc/.built mpardemo: upstream/jhdl-edifparser.jar slipway.jar iverilog -t fpga -s main -o out.edf misc/mpardemo.v - java -cp slipway.jar:upstream/jhdl-edifparser.jar MPARDemo out.edf + java -cp slipway.jar:upstream/jhdl-edifparser.jar edu.berkeley.slipway.mpar.MPARDemo out.edf ## edif parser ########################################################################## diff --git a/src/edu/berkeley/slipway/MPARDemo.java b/src/edu/berkeley/slipway/MPARDemo.java deleted file mode 100644 index 999c0d2..0000000 --- a/src/edu/berkeley/slipway/MPARDemo.java +++ /dev/null @@ -1,855 +0,0 @@ -import com.atmel.fpslic.*; -import byucc.edif.tools.merge.*; -import byucc.edif.*; -import java.io.*; -import java.util.*; -import edu.berkeley.slipway.*; -import com.atmel.fpslic.*; -import static com.atmel.fpslic.FpslicConstants.*; - -// FIXME: sometimes gets stuck in a loop routing the last few nets - -// FEATURE: ability to rip up only one branch of a multi-terminal net - -// FEATURE: re-placement based on routing congestion -// note: must assign a cost to "bare wire" -- if not, the -// placer will fail to recognize moves that put blocks closer -// together, thereby decreasing the potential for future -// congestion. - -// FEATURE: A* search (chap7 of independence thesis) - -// FIXME: distinguish out,xo,yo -// FIXME: y-axis shortcuts -// FEATURE: ability to use a cell for routing purposes -// FEATURE: global two-sector-long wires - -public class MPARDemo { - - public static final double alphaParameter = 00.9; - public static final double betaParameter = 02.5; - public static final double gammaParameter = 1.0; - - public static class FlatNetlist { - - private HashMap ids = new HashMap(); - - public HashSet nodes = new HashSet(); - public HashSet nets = new HashSet(); - - /** a node is some primitive element; a potential configuration of a CLB */ - public class Node { - public PhysicalDevice.PhysicalCell physicalCell = null; - private final String type; - private final int id; - - public int x = -1; - public int y = -1; - - private HashMap ports = new HashMap(); - - public Node(String type) { - nodes.add(this); - this.type = type.toLowerCase(); - Integer num = ids.get(type); - this.id = num == null ? 0 : num.intValue(); - ids.put(type, this.id+1); - } - public String getType() { return type; } - public String toString() { - if (x==-1 || y==-1) - return type + "["+id+"]"; - return type + "@("+x+","+y+")"; - } - public Port getPort(String name, boolean driver) { - Port p = ports.get(name); - if (p==null) ports.put(name, p = new Port(name, driver)); - return p; - } - - public Fpslic.Cell getPlacement(Fpslic fpslic) { return fpslic.cell(x, y); } - public void place(Fpslic fpslic) { - Fpslic.Cell cell = fpslic.cell(x,y); - cell.c(XLUT); - cell.b(false); - cell.f(false); - cell.xi(NW); - cell.yi(EAST); - if (type.equals("and2")) cell.xlut(LUT_SELF & LUT_OTHER); - else if (type.equals("or2")) cell.xlut(LUT_SELF | LUT_OTHER); - else if (type.equals("xor2")) cell.xlut(LUT_SELF ^ LUT_OTHER); - else if (type.equals("buf")) cell.xlut(LUT_SELF); - else if (type.equals("inv")) cell.xlut(~LUT_SELF); - else if (type.equals("cell0")) return; - } - - private int portIndex = 0; - - /** a port is an input or output to a Node */ - public class Port { - private final String name; - private final boolean driver; - Net net; - public final int index; - public Port(String name, boolean driver) { - this.name = name; - this.driver = driver; - this.index = driver ? 0 : portIndex++; - } - public String toString() { return Node.this + "." + name; } - public Node getNode() { return Node.this; } - public void connect(Port p) { - if (net != null) { net.add(p); - } else if (p.net != null) { p.net.add(this); - } else { - new Net().add(this); - this.net.add(p); - } - } - public void route(Fpslic fpslic, Port[] dests, PhysicalDevice pd, FlatNetlist.Net owner) { - PhysicalDevice.PhysicalNet[] destsp = new PhysicalDevice.PhysicalNet[dests.length]; - for(int i=0; i= 5) throw new RuntimeException("unroutable!"); - Fpslic.Cell turnCell = fpslic.cell(dest.getNode().x, getNode().y); - driverCell.out(free, true); - driverCell.h(free, true); - turnCell.h(free, true); - turnCell.v(free, true); - switch(dest.index) { - case 0: destCell.xi(L0 + free); break; - case 1: destCell.yi(L0 + free); break; - case 2: destCell.wi(L0 + free); break; - case 3: destCell.zi(L0 + free); break; - default: throw new RuntimeException("error"); - } - destCell.v(free, true); - System.out.println("route " + this + " -> " + dest + " on planes " + free); - */ - } - } - } - - /** a Net is a collection of ports which are wired together */ - public class Net implements Iterable { - private Node.Port driver = null; - private HashSet ports = new HashSet(); - public Net() { nets.add(this); } - public Iterator iterator() { return ports.iterator(); } - public int getSize() { return ports.size(); } - public HashSet pips = new HashSet(); - public HashSet pns = new HashSet(); - public boolean routed = false; - public void unroute() { - for(PhysicalDevice.PhysicalPip pip : pips) - pip.set(false); - for(PhysicalDevice.PhysicalNet net : pns) { - net.owners.remove(this); - net.load--; - } - pips.clear(); - pns.clear(); - routed = false; - } - public void route(Fpslic fpslic, PhysicalDevice pd) { - if (driver == null) return; - if (routed) return; - //System.out.println(); - //System.out.println("routing " + this); - Node.Port[] dests = new Node.Port[ports.size() - (ports.contains(driver) ? 1 : 0)]; - int i = 0; - for(Node.Port p : ports) - if (p != driver) - dests[i++] = p; - driver.route(fpslic, dests, pd, this); - routed = true; - } - public void add(Node.Port p) { - if (p.driver) { - if (driver != null && driver != p) - throw new RuntimeException("two drivers on a port!\n "+driver+"\n "+p); - driver = p; - } - if (p.net==this || ports.contains(p)) return; - ports.add(p); - add(p.net); - p.net = this; - } - public void add(Net n) { - if (n==this || n==null) return; - for(Node.Port p : n) add(p); - nets.remove(n); - } - public String toString() { - StringBuffer ret = new StringBuffer(); - ret.append(driver==null ? "()" : driver.toString()); - ret.append(" -> "); - for(Node.Port p : this) - if (p!=driver) - ret.append(p+" "); - return ret.toString(); - } - } - - - public HashMap cache = - new HashMap(); - public HashMap top = - new HashMap(); - - public FlatNetlist.Node createNode(EdifCellInstance eci, String portName) { - FlatNetlist.Node n = eci==null ? top.get(portName) : cache.get(eci); - if (n != null) return n; - if (eci==null) { - n = new FlatNetlist.Node("top_"+portName); - top.put(portName, n); - return n; - } else { - n = new FlatNetlist.Node(eci.getType()); - cache.put(eci,n); - } - for(EdifPortRef epr : eci.getAllEPRs()) { - EdifPort ep = epr.getPort(); - EdifNet en = epr.getNet(); - String name = ep.getOldName(); - boolean driver = ep.getDirection()==ep.OUT; - if (eci==null) driver = !driver; - if (eci==null) name = driver ? "out" : "xi"; - FlatNetlist.Node.Port p = n.getPort(name, driver); - for(EdifPortRef epr2 : en.getConnectedPortRefs()) { - EdifCellInstance eci2 = epr2.getCellInstance(); - EdifPort ep2 = epr2.getPort(); - Node n2 = createNode(eci2, ep2.getOldName()); - driver = ep2.getDirection()==ep.OUT; - name = ep2.getOldName(); - if (eci2==null) driver = !driver; - if (eci2==null) name = driver ? "out" : "xi"; - FlatNetlist.Node.Port p2 = n2.getPort(name, driver); - p.connect(p2); - } - } - return n; - } - } - - /* - test code for inter-sector switchboxes - public static void main2() throws Exception { - Fpslic fpslic = new FtdiBoard(); - // set up scan cell - fpslic.cell(23,15).h(3, true); - fpslic.cell(23,15).yi(L3); - fpslic.cell(23,15).ylut(0xAA); - fpslic.iob_right(15, true).enableOutput(WEST); - fpslic.cell(23,0).ylut(0x00); - fpslic.iob_right(0, true).enableOutput(WEST); - fpslic.flush(); - for(int x=0; x<20; x++) { - for(int y=0; y<20; y++) { - for(int l=0; l<5; l++) { - for(int v = 0; v <= 1; v++) { - boolean vert = v==1; - int newx = vert ? x : x-1; - int newy = vert ? y-1 : y; - if (newx<0 || newy<0) continue; - if (vert && (y%4) != 0) continue; - if (!vert && (x%4) != 0) continue; - - int layer = l; - if (layer==3) continue; - Fpslic.Cell c = fpslic.cell(x, y); - Fpslic.Cell c2 = fpslic.cell(newx, newy); - Fpslic.SectorWire sw1 = vert ? c.vwire(layer) : c.hwire(layer); - Fpslic.SectorWire sw2 = vert ? c2.vwire(layer) : c2.hwire(layer); - sw1.drives(sw2, true); - - c.c(YLUT); - if (vert) c.v(L0 + layer, true); - else c.h(L0 + layer, true); - c.out(L0 + layer, true); - c.b(false); - - c2.yi(L0 + layer); - if (vert) c2.v(L0 + layer, true); - else c2.h(L0 + layer, true); - c2.ylut(LUT_SELF); - c2.c(YLUT); - c2.b(false); - - System.out.print(x+","+y+","+l+","+(vert?"v":"h")+": "); - c.ylut(0x00); - fpslic.flush(); - boolean good = scan(fpslic, c2)==0; - if (!good) fails++; - System.out.print(good ? "ok " : "bad "); - c.ylut(0xff); - fpslic.flush(); - good = scan(fpslic, c2)!=0; - if (!good) fails++; - System.out.print(good ? "ok " : "bad "); - System.out.println(); - sw1.drives(sw2, false); - if (vert) c.v(layer, false); - else c.h(layer, false); - c.out(layer, false); - } - } - } - } - System.out.println("fails = " + fails); - - } - public static int fails = 0; - */ - - public static void main(String[] s) throws Exception { - EdifEnvironment topEnv = new EdifEnvironment("top"); - EdifLibraryManager elm = new EdifLibraryManager(topEnv); - EdifLibrary initLib = new EdifLibrary(elm, "initLib"); - EdifEnvironment env = EdifMergeParser.parseAndMerge(s, initLib); - System.out.println("top is " + env.getTopCell()); - FlatNetlist fnl = new FlatNetlist(); - - for(Iterator it = (Iterator)env.getTopCell().cellInstanceIterator(); - it.hasNext(); - ) { - FlatNetlist.Node n = fnl.createNode(it.next(), null); - } - - Fpslic fpslic = new FtdiBoard(); - PhysicalDevice pd = new PhysicalDevice(fpslic, 20, 20); - - int px = 0; - int py = 0; - - // crude map - Random rand = new Random(); - boolean[][] used = new boolean[pd.width][pd.height]; - for(FlatNetlist.Node n : fnl.nodes) { - while(true) { - px = Math.abs(rand.nextInt()) % pd.width; - py = Math.abs(rand.nextInt()) % pd.height; - if (!used[px][py]) { - used[px][py] = true; - n.x = px; - n.y = py; - n.physicalCell = pd.getCell(px, py); - System.out.println("placed " + n + " at ("+px+","+py+")"); - n.place(fpslic); - break; - } - } - } - - int trial = 0; - HashSet needUnroute = new HashSet(); - while(true) { - System.out.println(); - System.out.println("routing trial " + (++trial)); - for(FlatNetlist.Net net : fnl.nets) { - if (net.getSize() <= 1) continue; - net.route(fpslic, pd); - } - double congestion = 0; - int overrouted = 0; - needUnroute.clear(); - for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets) { - if (pn.load > 1) { - //System.out.println("overrouted: " + pn + ", congestion="+pn.congestion + ", load=" + pn.load); - overrouted++; - congestion += pn.congestion; - } - pn.congestion = pn.congestion * alphaParameter; - if (pn.load > 1) { - pn.congestion += betaParameter; - // don't do this here - //pn.congestion += betaParameter; - for(FlatNetlist.Net n : pn.owners) - needUnroute.add(n); - } - } - System.out.println(" overrouted="+overrouted+", congestion="+congestion +", ripping up " + needUnroute.size() +" nets of " + fnl.nets.size()); - if (overrouted <= 0) break; - //for(FlatNetlist.Net net : fnl.nets) - for(FlatNetlist.Net net : needUnroute) - net.unroute(); - /* - for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets) - for(PhysicalDevice.PhysicalPip pip : pn) { - pip.set(false); - } - */ - } - - // set up scan cell - fpslic.cell(23,15).h(3, true); - fpslic.cell(23,15).yi(L3); - fpslic.cell(23,15).ylut(0xAA); - fpslic.iob_right(15, true).enableOutput(WEST); - fpslic.cell(23,0).ylut(0x00); - fpslic.iob_right(0, true).enableOutput(WEST); - fpslic.flush(); - - int width = 8; - while(true) { - int a = Math.abs(rand.nextInt()) % (1 << width); - int b = Math.abs(rand.nextInt()) % (1 << width); - setInput(fnl, fpslic, "a", a); - setInput(fnl, fpslic, "b", b); - setInput(fnl, fpslic, "ci", 0); - int result = getOutput(fnl, fpslic, "out"); - System.out.println(Integer.toString(a,16) + " + " + - Integer.toString(b,16) + " = " + - Integer.toString(result,16) + - " [ " + (a+b==result ? "ok" : "bad" ) + " ] "); - } - } - - public static class PhysicalDevice { - private final Fpslic fpslic; - - public final int width; - public final int height; - private final PhysicalNet[][][][] sectorWires; - private final PhysicalCell[][] cells; - - public PhysicalCell getCell(int col, int row) { - if (col<0) return null; - if (row<0) return null; - if (col>=width) return null; - if (row>=height) return null; - return cells[col][row]; - } - - public PhysicalDevice(final Fpslic fpslic, int width, int height) { - this.fpslic = fpslic; - this.width = width; - this.height = height; - sectorWires = new PhysicalNet[width][height][5][2]; - for(int x=0; x remainingDests = new HashSet(); - for(PhysicalNet dest : dests) remainingDests.add(dest); - - HashSet needsReset = new HashSet(); - PriorityQueue pq = new PriorityQueue(); - needsReset.add(source); - source.distance = 0; - pq.add(source); - - OUTER: while(true) { - PhysicalNet pn = pq.poll(); - if (pn==null) throw new Error("unroutable! " + source + " -> " + dests[0]); - double frontier = pn.distance; - for(PhysicalPip pip : pn) - for(PhysicalNet net : pip.getDrivenNets()) { - double newfrontier = frontier + 0.05 + net.congestion; - - // penalty for using any net already routed in this iteration (makes routing order-sensitive) - if (net.load >= 1) newfrontier = newfrontier + 20; - - if (net.distance <= newfrontier) continue; - pq.remove(net); // if already in there - net.distance = newfrontier; - pq.add(net); - needsReset.add(net); - net.backpointer = pn; - if (remainingDests.contains(net)) { - remainingDests.remove(net); - if (remainingDests.size()==0) break OUTER; - - // Vaughn Betz style multiterminal routing: once we reach one sink, make every node on the path - // "distance zero" from the source. - for(PhysicalNet pnx = net; pnx != null; pnx = pnx.backpointer) { - //pnx.distance = 0; - pq.add(pnx); - } - break; - } - } - } - - for(PhysicalNet dest : dests) { - PhysicalNet pn = dest; - while(pn != null && pn.backpointer != null) { - pn.owners.add(owner); - owner.pns.add(pn); - if (pn.distance != Double.MAX_VALUE) { - pn.distance = Double.MAX_VALUE; - pn.load++; - if (pn.load>=2) pn.congestion += betaParameter; - } - PhysicalPip pip = pn.getPipFrom(pn.backpointer); - pip.set(true); - owner.pips.add(pip); - pn = pn.backpointer; - } - // FIXME: check pn==source at this point - } - - for(PhysicalNet pn : needsReset) { - pn.distance = Double.MAX_VALUE; - pn.backpointer = null; - } - } - public HashSet allPhysicalNets = new HashSet(); - public class PhysicalNet implements Iterable, Comparable { - public double congestion = 0; - public int load = 0; - public double distance = Double.MAX_VALUE; - public PhysicalNet backpointer = null; - - public int compareTo(PhysicalNet pn) { - double x = distance - pn.distance; - return distance > pn.distance - ? 1 - : distance < pn.distance - ? -1 - : 0; - } - - private final HashSet pips = new HashSet(); - public Iterator iterator() { return pips.iterator(); } - private String name; - public PhysicalNet(String name) { - this.name = name; - allPhysicalNets.add(this); - } - public String toString() { return name; } - private void addPip(PhysicalPip pip) { pips.add(pip); } - public PhysicalPip getPipFrom(PhysicalNet pn) { - for(PhysicalPip pip : pn) - for(PhysicalNet pn2 : pip.getDrivenNets()) - if (pn2==this) - return pip; - return null; - } - public HashSet owners = new HashSet(); - } - - public abstract class PhysicalPip { - private PhysicalNet driver; - private PhysicalNet[] driven; - private String name; - private int defaultCost; - public String toString() { return name; } - public PhysicalNet getDriverNet() { return driver; } - public PhysicalNet[] getDrivenNets() { return driven; } - public int getCost(PhysicalNet in, PhysicalNet out) { return defaultCost; } - public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven) { this(name, driver, driven, 100); } - public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven, int defaultCost) { - this.name = name; - this.driver = driver; - this.driven = driven; - this.defaultCost = defaultCost; - if (driver != null) driver.addPip(this); - for(PhysicalNet pn : driven) pn.addPip(this); - } - public abstract void set(boolean connected); - } - - } - - private static int ret; - public static synchronized int scan(final Fpslic device, final Fpslic.Cell cell) { - try { - scan(device, cell, YLUT, true); - ((FtdiBoard)device).readBus(new FtdiBoard.ByteCallback() { - public void call(byte b) throws Exception { - ret = b; - synchronized(device) { - device.notifyAll(); - } - } - }); - synchronized(device) { - try { - device.wait(); - } catch (Exception e) { throw new RuntimeException(e); } - } - scan(device, cell, YLUT, false); - return ret; - } catch (Exception e) { throw new RuntimeException(e); } - } - - public static void scan(Fpslic dev, Fpslic.Cell cell, int source, boolean setup) { - if (setup) { - //if (source != NONE) cell.c(source); - if (cell.b()) cell.b(false); - if (cell.f()) cell.f(false); - } - if (cell.out(L3)!=setup) cell.out(L3, setup); - if (cell.vx(L3)!=setup) cell.v(L3, setup); - - Fpslic.SectorWire sw = cell.vwire(L3); - //System.out.println("wire is: " + sw); - - if (sw.row > (12 & ~0x3) && sw.north()!=null && sw.north().drives(sw)) - sw.north().drives(sw, false); - while(sw.row > (12 & ~0x3) && sw.south() != null) { - //System.out.println(sw + " -> " + sw.south()); - if (sw.drives(sw.south())!=setup) sw.drives(sw.south(), setup); - sw = sw.south(); - } - if (sw.row < (12 & ~0x3) && sw.south() != null && sw.south().drives(sw)) - sw.north().drives(sw, false); - while(sw.row < (12 & ~0x3) && sw.north() != null) { - //System.out.println(sw + " -> " + sw.north()); - if (sw.drives(sw.north())!=setup) sw.drives(sw.north(), setup); - sw = sw.north(); - } - - //cell = dev.cell(19, 15); - cell = dev.cell(cell.col, 15); - /* - System.out.println("cell is " + cell); - cell.xlut(0xff); - cell.ylut(0xff); - cell.b(false); - cell.f(false); - cell.c(XLUT); - cell.out(L3, true); - cell.oe(NONE); - */ - if (cell.hx(L3) != setup) cell.h(L3, setup); - if (cell.vx(L3) != setup) cell.v(L3, setup); - sw = cell.hwire(L3); - - if (sw.west()!=null && sw.west().drives(sw)) { sw.west().drives(sw, false); } - while(sw.east() != null) { - //System.out.println(sw + " -> " + sw.east()); - if (sw.drives(sw.east())!=setup) sw.drives(sw.east(), setup); - sw = sw.east(); - } - - } - - public static void setInput(FlatNetlist fnl, Fpslic fpslic, String prefix, int val) { - for(int i=0; ; i++) { - FlatNetlist.Node n = fnl.top.get(prefix + "["+i+"]"); - if (n==null && i==0) n = fnl.top.get(prefix); - if (n==null) return; - Fpslic.Cell c = n.getPlacement(fpslic); - c.c(XLUT); - c.b(false); - c.xlut((val & 0x1)==0 ? 0x00 : 0xff); - val = val >> 1; - } - } - public static int getOutput(FlatNetlist fnl, Fpslic fpslic, String prefix) { - int val = 0; - for(int i=0; ; i++) { - FlatNetlist.Node n = fnl.top.get(prefix+"["+i+"]"); - if (n==null && i==0) n = fnl.top.get(prefix); - if (n==null) return val; - Fpslic.Cell c = n.getPlacement(fpslic); - c.xlut(LUT_SELF); - c.c(XLUT); - c.b(false); - fpslic.flush(); - int scan = scan(fpslic, c); - val |= ((scan==0 ? 0 : 1) << i); - } - } - - -} \ No newline at end of file diff --git a/src/edu/berkeley/slipway/mpar/FlatNetlist.java b/src/edu/berkeley/slipway/mpar/FlatNetlist.java new file mode 100644 index 0000000..db54690 --- /dev/null +++ b/src/edu/berkeley/slipway/mpar/FlatNetlist.java @@ -0,0 +1,246 @@ +package edu.berkeley.slipway.mpar; +import com.atmel.fpslic.*; +import byucc.edif.tools.merge.*; +import byucc.edif.*; +import java.io.*; +import java.util.*; +import edu.berkeley.slipway.*; +import com.atmel.fpslic.*; +import static com.atmel.fpslic.FpslicConstants.*; +import static edu.berkeley.slipway.mpar.MPARDemo.*; + +public class FlatNetlist { + + private HashMap ids = new HashMap(); + + public HashSet nodes = new HashSet(); + public HashSet nets = new HashSet(); + + /** a node is some primitive element; a potential configuration of a CLB */ + public class Node { + public PhysicalDevice.PhysicalCell physicalCell = null; + private final String type; + private final int id; + + public int x = -1; + public int y = -1; + + private HashMap ports = new HashMap(); + + public Node(String type) { + nodes.add(this); + this.type = type.toLowerCase(); + Integer num = ids.get(type); + this.id = num == null ? 0 : num.intValue(); + ids.put(type, this.id+1); + } + public String getType() { return type; } + public String toString() { + if (x==-1 || y==-1) + return type + "["+id+"]"; + return type + "@("+x+","+y+")"; + } + public Port getPort(String name, boolean driver) { + Port p = ports.get(name); + if (p==null) ports.put(name, p = new Port(name, driver)); + return p; + } + + public Fpslic.Cell getPlacement(Fpslic fpslic) { return fpslic.cell(x, y); } + public void place(Fpslic fpslic) { + Fpslic.Cell cell = fpslic.cell(x,y); + cell.c(XLUT); + cell.b(false); + cell.f(false); + cell.xi(NW); + cell.yi(EAST); + if (type.equals("and2")) cell.xlut(LUT_SELF & LUT_OTHER); + else if (type.equals("or2")) cell.xlut(LUT_SELF | LUT_OTHER); + else if (type.equals("xor2")) cell.xlut(LUT_SELF ^ LUT_OTHER); + else if (type.equals("buf")) cell.xlut(LUT_SELF); + else if (type.equals("inv")) cell.xlut(~LUT_SELF); + else if (type.equals("cell0")) return; + } + + private int portIndex = 0; + + /** a port is an input or output to a Node */ + public class Port { + private final String name; + private final boolean driver; + Net net; + public final int index; + public Port(String name, boolean driver) { + this.name = name; + this.driver = driver; + this.index = driver ? 0 : portIndex++; + } + public String toString() { return Node.this + "." + name; } + public Node getNode() { return Node.this; } + public void connect(Port p) { + if (net != null) { net.add(p); + } else if (p.net != null) { p.net.add(this); + } else { + new Net().add(this); + this.net.add(p); + } + } + public void route(Fpslic fpslic, Port[] dests, PhysicalDevice pd, FlatNetlist.Net owner) { + PhysicalDevice.PhysicalNet[] destsp = new PhysicalDevice.PhysicalNet[dests.length]; + for(int i=0; i= 5) throw new RuntimeException("unroutable!"); + Fpslic.Cell turnCell = fpslic.cell(dest.getNode().x, getNode().y); + driverCell.out(free, true); + driverCell.h(free, true); + turnCell.h(free, true); + turnCell.v(free, true); + switch(dest.index) { + case 0: destCell.xi(L0 + free); break; + case 1: destCell.yi(L0 + free); break; + case 2: destCell.wi(L0 + free); break; + case 3: destCell.zi(L0 + free); break; + default: throw new RuntimeException("error"); + } + destCell.v(free, true); + System.out.println("route " + this + " -> " + dest + " on planes " + free); + */ + } + } + } + + /** a Net is a collection of ports which are wired together */ + public class Net implements Iterable { + private Node.Port driver = null; + private HashSet ports = new HashSet(); + public Net() { nets.add(this); } + public Iterator iterator() { return ports.iterator(); } + public int getSize() { return ports.size(); } + public HashSet pips = new HashSet(); + public HashSet pns = new HashSet(); + public boolean routed = false; + public void unroute() { + for(PhysicalDevice.PhysicalPip pip : pips) + pip.set(false); + for(PhysicalDevice.PhysicalNet net : pns) { + net.owners.remove(this); + net.load--; + } + pips.clear(); + pns.clear(); + routed = false; + } + public void route(Fpslic fpslic, PhysicalDevice pd) { + if (driver == null) return; + if (routed) return; + //System.out.println(); + //System.out.println("routing " + this); + Node.Port[] dests = new Node.Port[ports.size() - (ports.contains(driver) ? 1 : 0)]; + int i = 0; + for(Node.Port p : ports) + if (p != driver) + dests[i++] = p; + driver.route(fpslic, dests, pd, this); + routed = true; + } + public void add(Node.Port p) { + if (p.driver) { + if (driver != null && driver != p) + throw new RuntimeException("two drivers on a port!\n "+driver+"\n "+p); + driver = p; + } + if (p.net==this || ports.contains(p)) return; + ports.add(p); + add(p.net); + p.net = this; + } + public void add(Net n) { + if (n==this || n==null) return; + for(Node.Port p : n) add(p); + nets.remove(n); + } + public String toString() { + StringBuffer ret = new StringBuffer(); + ret.append(driver==null ? "()" : driver.toString()); + ret.append(" -> "); + for(Node.Port p : this) + if (p!=driver) + ret.append(p+" "); + return ret.toString(); + } + } + + + public HashMap cache = + new HashMap(); + public HashMap top = + new HashMap(); + + public FlatNetlist.Node createNode(EdifCellInstance eci, String portName) { + FlatNetlist.Node n = eci==null ? top.get(portName) : cache.get(eci); + if (n != null) return n; + if (eci==null) { + n = new FlatNetlist.Node("top_"+portName); + top.put(portName, n); + return n; + } else { + n = new FlatNetlist.Node(eci.getType()); + cache.put(eci,n); + } + for(EdifPortRef epr : eci.getAllEPRs()) { + EdifPort ep = epr.getPort(); + EdifNet en = epr.getNet(); + String name = ep.getOldName(); + boolean driver = ep.getDirection()==ep.OUT; + if (eci==null) driver = !driver; + if (eci==null) name = driver ? "out" : "xi"; + FlatNetlist.Node.Port p = n.getPort(name, driver); + for(EdifPortRef epr2 : en.getConnectedPortRefs()) { + EdifCellInstance eci2 = epr2.getCellInstance(); + EdifPort ep2 = epr2.getPort(); + Node n2 = createNode(eci2, ep2.getOldName()); + driver = ep2.getDirection()==ep.OUT; + name = ep2.getOldName(); + if (eci2==null) driver = !driver; + if (eci2==null) name = driver ? "out" : "xi"; + FlatNetlist.Node.Port p2 = n2.getPort(name, driver); + p.connect(p2); + } + } + return n; + } +} diff --git a/src/edu/berkeley/slipway/mpar/MPARDemo.java b/src/edu/berkeley/slipway/mpar/MPARDemo.java new file mode 100644 index 0000000..f1c7ad7 --- /dev/null +++ b/src/edu/berkeley/slipway/mpar/MPARDemo.java @@ -0,0 +1,311 @@ +package edu.berkeley.slipway.mpar; +import com.atmel.fpslic.*; +import byucc.edif.tools.merge.*; +import byucc.edif.*; +import java.io.*; +import java.util.*; +import edu.berkeley.slipway.*; +import com.atmel.fpslic.*; +import static com.atmel.fpslic.FpslicConstants.*; + +// FIXME: sometimes gets stuck in a loop routing the last few nets + +// FEATURE: ability to rip up only one branch of a multi-terminal net + +// FEATURE: re-placement based on routing congestion +// note: must assign a cost to "bare wire" -- if not, the +// placer will fail to recognize moves that put blocks closer +// together, thereby decreasing the potential for future +// congestion. + +// FEATURE: A* search (chap7 of independence thesis) + +// FIXME: distinguish out,xo,yo +// FIXME: y-axis shortcuts +// FEATURE: ability to use a cell for routing purposes +// FEATURE: global two-sector-long wires + +public class MPARDemo { + + public static final double alphaParameter = 00.9; + public static final double betaParameter = 02.5; + public static final double gammaParameter = 1.0; + + /* + test code for inter-sector switchboxes + public static void main2() throws Exception { + Fpslic fpslic = new FtdiBoard(); + // set up scan cell + fpslic.cell(23,15).h(3, true); + fpslic.cell(23,15).yi(L3); + fpslic.cell(23,15).ylut(0xAA); + fpslic.iob_right(15, true).enableOutput(WEST); + fpslic.cell(23,0).ylut(0x00); + fpslic.iob_right(0, true).enableOutput(WEST); + fpslic.flush(); + for(int x=0; x<20; x++) { + for(int y=0; y<20; y++) { + for(int l=0; l<5; l++) { + for(int v = 0; v <= 1; v++) { + boolean vert = v==1; + int newx = vert ? x : x-1; + int newy = vert ? y-1 : y; + if (newx<0 || newy<0) continue; + if (vert && (y%4) != 0) continue; + if (!vert && (x%4) != 0) continue; + + int layer = l; + if (layer==3) continue; + Fpslic.Cell c = fpslic.cell(x, y); + Fpslic.Cell c2 = fpslic.cell(newx, newy); + Fpslic.SectorWire sw1 = vert ? c.vwire(layer) : c.hwire(layer); + Fpslic.SectorWire sw2 = vert ? c2.vwire(layer) : c2.hwire(layer); + sw1.drives(sw2, true); + + c.c(YLUT); + if (vert) c.v(L0 + layer, true); + else c.h(L0 + layer, true); + c.out(L0 + layer, true); + c.b(false); + + c2.yi(L0 + layer); + if (vert) c2.v(L0 + layer, true); + else c2.h(L0 + layer, true); + c2.ylut(LUT_SELF); + c2.c(YLUT); + c2.b(false); + + System.out.print(x+","+y+","+l+","+(vert?"v":"h")+": "); + c.ylut(0x00); + fpslic.flush(); + boolean good = scan(fpslic, c2)==0; + if (!good) fails++; + System.out.print(good ? "ok " : "bad "); + c.ylut(0xff); + fpslic.flush(); + good = scan(fpslic, c2)!=0; + if (!good) fails++; + System.out.print(good ? "ok " : "bad "); + System.out.println(); + sw1.drives(sw2, false); + if (vert) c.v(layer, false); + else c.h(layer, false); + c.out(layer, false); + } + } + } + } + System.out.println("fails = " + fails); + + } + public static int fails = 0; + */ + + public static void main(String[] s) throws Exception { + EdifEnvironment topEnv = new EdifEnvironment("top"); + EdifLibraryManager elm = new EdifLibraryManager(topEnv); + EdifLibrary initLib = new EdifLibrary(elm, "initLib"); + EdifEnvironment env = EdifMergeParser.parseAndMerge(s, initLib); + System.out.println("top is " + env.getTopCell()); + FlatNetlist fnl = new FlatNetlist(); + + for(Iterator it = (Iterator)env.getTopCell().cellInstanceIterator(); + it.hasNext(); + ) { + FlatNetlist.Node n = fnl.createNode(it.next(), null); + } + + Fpslic fpslic = new FtdiBoard(); + PhysicalDevice pd = new PhysicalDevice(fpslic, 20, 20); + + int px = 0; + int py = 0; + + // crude map + Random rand = new Random(); + boolean[][] used = new boolean[pd.width][pd.height]; + for(FlatNetlist.Node n : fnl.nodes) { + while(true) { + px = Math.abs(rand.nextInt()) % pd.width; + py = Math.abs(rand.nextInt()) % pd.height; + if (!used[px][py]) { + used[px][py] = true; + n.x = px; + n.y = py; + n.physicalCell = pd.getCell(px, py); + System.out.println("placed " + n + " at ("+px+","+py+")"); + n.place(fpslic); + break; + } + } + } + + int trial = 0; + HashSet needUnroute = new HashSet(); + while(true) { + System.out.println(); + System.out.println("routing trial " + (++trial)); + for(FlatNetlist.Net net : fnl.nets) { + if (net.getSize() <= 1) continue; + net.route(fpslic, pd); + } + double congestion = 0; + int overrouted = 0; + needUnroute.clear(); + for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets) { + if (pn.load > 1) { + //System.out.println("overrouted: " + pn + ", congestion="+pn.congestion + ", load=" + pn.load); + overrouted++; + congestion += pn.congestion; + } + pn.congestion = pn.congestion * alphaParameter; + if (pn.load > 1) { + pn.congestion += betaParameter; + // don't do this here + //pn.congestion += betaParameter; + for(FlatNetlist.Net n : pn.owners) + needUnroute.add(n); + } + } + System.out.println(" overrouted="+overrouted+", congestion="+congestion +", ripping up " + needUnroute.size() +" nets of " + fnl.nets.size()); + if (overrouted <= 0) break; + //for(FlatNetlist.Net net : fnl.nets) + for(FlatNetlist.Net net : needUnroute) + net.unroute(); + /* + for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets) + for(PhysicalDevice.PhysicalPip pip : pn) { + pip.set(false); + } + */ + } + + // set up scan cell + fpslic.cell(23,15).h(3, true); + fpslic.cell(23,15).yi(L3); + fpslic.cell(23,15).ylut(0xAA); + fpslic.iob_right(15, true).enableOutput(WEST); + fpslic.cell(23,0).ylut(0x00); + fpslic.iob_right(0, true).enableOutput(WEST); + fpslic.flush(); + + int width = 8; + while(true) { + int a = Math.abs(rand.nextInt()) % (1 << width); + int b = Math.abs(rand.nextInt()) % (1 << width); + setInput(fnl, fpslic, "a", a); + setInput(fnl, fpslic, "b", b); + setInput(fnl, fpslic, "ci", 0); + int result = getOutput(fnl, fpslic, "out"); + System.out.println(Integer.toString(a,16) + " + " + + Integer.toString(b,16) + " = " + + Integer.toString(result,16) + + " [ " + (a+b==result ? "ok" : "bad" ) + " ] "); + } + } + + + private static int ret; + public static synchronized int scan(final Fpslic device, final Fpslic.Cell cell) { + try { + scan(device, cell, YLUT, true); + ((FtdiBoard)device).readBus(new FtdiBoard.ByteCallback() { + public void call(byte b) throws Exception { + ret = b; + synchronized(device) { + device.notifyAll(); + } + } + }); + synchronized(device) { + try { + device.wait(); + } catch (Exception e) { throw new RuntimeException(e); } + } + scan(device, cell, YLUT, false); + return ret; + } catch (Exception e) { throw new RuntimeException(e); } + } + + public static void scan(Fpslic dev, Fpslic.Cell cell, int source, boolean setup) { + if (setup) { + //if (source != NONE) cell.c(source); + if (cell.b()) cell.b(false); + if (cell.f()) cell.f(false); + } + if (cell.out(L3)!=setup) cell.out(L3, setup); + if (cell.vx(L3)!=setup) cell.v(L3, setup); + + Fpslic.SectorWire sw = cell.vwire(L3); + //System.out.println("wire is: " + sw); + + if (sw.row > (12 & ~0x3) && sw.north()!=null && sw.north().drives(sw)) + sw.north().drives(sw, false); + while(sw.row > (12 & ~0x3) && sw.south() != null) { + //System.out.println(sw + " -> " + sw.south()); + if (sw.drives(sw.south())!=setup) sw.drives(sw.south(), setup); + sw = sw.south(); + } + if (sw.row < (12 & ~0x3) && sw.south() != null && sw.south().drives(sw)) + sw.north().drives(sw, false); + while(sw.row < (12 & ~0x3) && sw.north() != null) { + //System.out.println(sw + " -> " + sw.north()); + if (sw.drives(sw.north())!=setup) sw.drives(sw.north(), setup); + sw = sw.north(); + } + + //cell = dev.cell(19, 15); + cell = dev.cell(cell.col, 15); + /* + System.out.println("cell is " + cell); + cell.xlut(0xff); + cell.ylut(0xff); + cell.b(false); + cell.f(false); + cell.c(XLUT); + cell.out(L3, true); + cell.oe(NONE); + */ + if (cell.hx(L3) != setup) cell.h(L3, setup); + if (cell.vx(L3) != setup) cell.v(L3, setup); + sw = cell.hwire(L3); + + if (sw.west()!=null && sw.west().drives(sw)) { sw.west().drives(sw, false); } + while(sw.east() != null) { + //System.out.println(sw + " -> " + sw.east()); + if (sw.drives(sw.east())!=setup) sw.drives(sw.east(), setup); + sw = sw.east(); + } + + } + + public static void setInput(FlatNetlist fnl, Fpslic fpslic, String prefix, int val) { + for(int i=0; ; i++) { + FlatNetlist.Node n = fnl.top.get(prefix + "["+i+"]"); + if (n==null && i==0) n = fnl.top.get(prefix); + if (n==null) return; + Fpslic.Cell c = n.getPlacement(fpslic); + c.c(XLUT); + c.b(false); + c.xlut((val & 0x1)==0 ? 0x00 : 0xff); + val = val >> 1; + } + } + public static int getOutput(FlatNetlist fnl, Fpslic fpslic, String prefix) { + int val = 0; + for(int i=0; ; i++) { + FlatNetlist.Node n = fnl.top.get(prefix+"["+i+"]"); + if (n==null && i==0) n = fnl.top.get(prefix); + if (n==null) return val; + Fpslic.Cell c = n.getPlacement(fpslic); + c.xlut(LUT_SELF); + c.c(XLUT); + c.b(false); + fpslic.flush(); + int scan = scan(fpslic, c); + val |= ((scan==0 ? 0 : 1) << i); + } + } + + +} \ No newline at end of file diff --git a/src/edu/berkeley/slipway/mpar/PhysicalDevice.java b/src/edu/berkeley/slipway/mpar/PhysicalDevice.java new file mode 100644 index 0000000..8d8b9ed --- /dev/null +++ b/src/edu/berkeley/slipway/mpar/PhysicalDevice.java @@ -0,0 +1,320 @@ +package edu.berkeley.slipway.mpar; +import com.atmel.fpslic.*; +import byucc.edif.tools.merge.*; +import byucc.edif.*; +import java.io.*; +import java.util.*; +import edu.berkeley.slipway.*; +import com.atmel.fpslic.*; +import static com.atmel.fpslic.FpslicConstants.*; +import static edu.berkeley.slipway.mpar.MPARDemo.*; + +public class PhysicalDevice { + private final Fpslic fpslic; + + public final int width; + public final int height; + private final PhysicalNet[][][][] sectorWires; + private final PhysicalCell[][] cells; + + public PhysicalCell getCell(int col, int row) { + if (col<0) return null; + if (row<0) return null; + if (col>=width) return null; + if (row>=height) return null; + return cells[col][row]; + } + + public PhysicalDevice(final Fpslic fpslic, int width, int height) { + this.fpslic = fpslic; + this.width = width; + this.height = height; + sectorWires = new PhysicalNet[width][height][5][2]; + for(int x=0; x remainingDests = new HashSet(); + for(PhysicalNet dest : dests) remainingDests.add(dest); + + HashSet needsReset = new HashSet(); + PriorityQueue pq = new PriorityQueue(); + needsReset.add(source); + source.distance = 0; + pq.add(source); + + OUTER: while(true) { + PhysicalNet pn = pq.poll(); + if (pn==null) throw new Error("unroutable! " + source + " -> " + dests[0]); + double frontier = pn.distance; + for(PhysicalPip pip : pn) + for(PhysicalNet net : pip.getDrivenNets()) { + double newfrontier = frontier + 0.05 + net.congestion; + + // penalty for using any net already routed in this iteration (makes routing order-sensitive) + if (net.load >= 1) newfrontier = newfrontier + 20; + + if (net.distance <= newfrontier) continue; + pq.remove(net); // if already in there + net.distance = newfrontier; + pq.add(net); + needsReset.add(net); + net.backpointer = pn; + if (remainingDests.contains(net)) { + remainingDests.remove(net); + if (remainingDests.size()==0) break OUTER; + + // Vaughn Betz style multiterminal routing: once we reach one sink, make every node on the path + // "distance zero" from the source. + for(PhysicalNet pnx = net; pnx != null; pnx = pnx.backpointer) { + //pnx.distance = 0; + pq.add(pnx); + } + break; + } + } + } + + for(PhysicalNet dest : dests) { + PhysicalNet pn = dest; + while(pn != null && pn.backpointer != null) { + pn.owners.add(owner); + owner.pns.add(pn); + if (pn.distance != Double.MAX_VALUE) { + pn.distance = Double.MAX_VALUE; + pn.load++; + if (pn.load>=2) pn.congestion += betaParameter; + } + PhysicalPip pip = pn.getPipFrom(pn.backpointer); + pip.set(true); + owner.pips.add(pip); + pn = pn.backpointer; + } + // FIXME: check pn==source at this point + } + + for(PhysicalNet pn : needsReset) { + pn.distance = Double.MAX_VALUE; + pn.backpointer = null; + } + } + public HashSet allPhysicalNets = new HashSet(); + public class PhysicalNet implements Iterable, Comparable { + public double congestion = 0; + public int load = 0; + public double distance = Double.MAX_VALUE; + public PhysicalNet backpointer = null; + + public int compareTo(PhysicalNet pn) { + double x = distance - pn.distance; + return distance > pn.distance + ? 1 + : distance < pn.distance + ? -1 + : 0; + } + + private final HashSet pips = new HashSet(); + public Iterator iterator() { return pips.iterator(); } + private String name; + public PhysicalNet(String name) { + this.name = name; + allPhysicalNets.add(this); + } + public String toString() { return name; } + private void addPip(PhysicalPip pip) { pips.add(pip); } + public PhysicalPip getPipFrom(PhysicalNet pn) { + for(PhysicalPip pip : pn) + for(PhysicalNet pn2 : pip.getDrivenNets()) + if (pn2==this) + return pip; + return null; + } + public HashSet owners = new HashSet(); + } + + public abstract class PhysicalPip { + private PhysicalNet driver; + private PhysicalNet[] driven; + private String name; + private int defaultCost; + public String toString() { return name; } + public PhysicalNet getDriverNet() { return driver; } + public PhysicalNet[] getDrivenNets() { return driven; } + public int getCost(PhysicalNet in, PhysicalNet out) { return defaultCost; } + public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven) { this(name, driver, driven, 100); } + public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven, int defaultCost) { + this.name = name; + this.driver = driver; + this.driven = driven; + this.defaultCost = defaultCost; + if (driver != null) driver.addPip(this); + for(PhysicalNet pn : driven) pn.addPip(this); + } + public abstract void set(boolean connected); + } + +} -- 1.7.10.4