From 7eee9ddbc137d48c8224b0e7187d5f90339ccc3f Mon Sep 17 00:00:00 2001 From: adam Date: Wed, 22 Aug 2007 12:42:11 +0100 Subject: [PATCH] major cleanup of mpar code --- src/edu/berkeley/slipway/mpar/FlatNetlist.java | 246 --------------- src/edu/berkeley/slipway/mpar/MPARDemo.java | 69 ++-- src/edu/berkeley/slipway/mpar/NetList.java | 185 +++++++++++ src/edu/berkeley/slipway/mpar/PhysicalDevice.java | 351 ++++++--------------- src/edu/berkeley/slipway/mpar/PhysicalFpslic.java | 217 +++++++++++++ 5 files changed, 528 insertions(+), 540 deletions(-) delete mode 100644 src/edu/berkeley/slipway/mpar/FlatNetlist.java create mode 100644 src/edu/berkeley/slipway/mpar/NetList.java create mode 100644 src/edu/berkeley/slipway/mpar/PhysicalAtmelDevice.java create mode 100644 src/edu/berkeley/slipway/mpar/PhysicalFpslic.java diff --git a/src/edu/berkeley/slipway/mpar/FlatNetlist.java b/src/edu/berkeley/slipway/mpar/FlatNetlist.java deleted file mode 100644 index db54690..0000000 --- a/src/edu/berkeley/slipway/mpar/FlatNetlist.java +++ /dev/null @@ -1,246 +0,0 @@ -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 index f1c7ad7..7c19aed 100644 --- a/src/edu/berkeley/slipway/mpar/MPARDemo.java +++ b/src/edu/berkeley/slipway/mpar/MPARDemo.java @@ -107,77 +107,64 @@ public class MPARDemo { EdifLibrary initLib = new EdifLibrary(elm, "initLib"); EdifEnvironment env = EdifMergeParser.parseAndMerge(s, initLib); System.out.println("top is " + env.getTopCell()); - FlatNetlist fnl = new FlatNetlist(); + NetList fnl = new NetList(); for(Iterator it = (Iterator)env.getTopCell().cellInstanceIterator(); it.hasNext(); ) { - FlatNetlist.Node n = fnl.createNode(it.next(), null); + NetList.Node n = fnl.createNode(it.next(), null); } Fpslic fpslic = new FtdiBoard(); - PhysicalDevice pd = new PhysicalDevice(fpslic, 20, 20); + int width = 20; + int height = 20; + PhysicalDevice pd = new PhysicalFpslic(fpslic, width, height); 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) { + boolean[][] used = new boolean[width][height]; + for(NetList.Node n : fnl.nodes) { while(true) { - px = Math.abs(rand.nextInt()) % pd.width; - py = Math.abs(rand.nextInt()) % pd.height; + px = Math.abs(rand.nextInt()) % width; + py = Math.abs(rand.nextInt()) % 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); + pd.getCell(px, py).place(n); break; } } } int trial = 0; - HashSet needUnroute = new HashSet(); + HashSet needUnroute = new HashSet(); while(true) { System.out.println(); System.out.println("routing trial " + (++trial)); - for(FlatNetlist.Net net : fnl.nets) { + for(NetList.LogicalNet 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); + for(PhysicalDevice.PhysicalNet pn : pd) { + if (pn.isCongested()) { overrouted++; - congestion += pn.congestion; + congestion += pn.getCongestion(); } - 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) + pn.updateCongestion(); + if (pn.isCongested()) + for(NetList.LogicalNet n : pn.getLogicalNets()) needUnroute.add(n); - } } - System.out.println(" overrouted="+overrouted+", congestion="+congestion +", ripping up " + needUnroute.size() +" nets of " + fnl.nets.size()); + 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); - } - */ + for(NetList.LogicalNet net : needUnroute) net.unroute(); } // set up scan cell @@ -189,10 +176,10 @@ public class MPARDemo { fpslic.iob_right(0, true).enableOutput(WEST); fpslic.flush(); - int width = 8; + int xwidth = 8; while(true) { - int a = Math.abs(rand.nextInt()) % (1 << width); - int b = Math.abs(rand.nextInt()) % (1 << width); + int a = Math.abs(rand.nextInt()) % (1 << xwidth); + int b = Math.abs(rand.nextInt()) % (1 << xwidth); setInput(fnl, fpslic, "a", a); setInput(fnl, fpslic, "b", b); setInput(fnl, fpslic, "ci", 0); @@ -279,9 +266,9 @@ public class MPARDemo { } - public static void setInput(FlatNetlist fnl, Fpslic fpslic, String prefix, int val) { + public static void setInput(NetList fnl, Fpslic fpslic, String prefix, int val) { for(int i=0; ; i++) { - FlatNetlist.Node n = fnl.top.get(prefix + "["+i+"]"); + NetList.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); @@ -291,10 +278,10 @@ public class MPARDemo { val = val >> 1; } } - public static int getOutput(FlatNetlist fnl, Fpslic fpslic, String prefix) { + public static int getOutput(NetList fnl, Fpslic fpslic, String prefix) { int val = 0; for(int i=0; ; i++) { - FlatNetlist.Node n = fnl.top.get(prefix+"["+i+"]"); + NetList.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); diff --git a/src/edu/berkeley/slipway/mpar/NetList.java b/src/edu/berkeley/slipway/mpar/NetList.java new file mode 100644 index 0000000..50f59b5 --- /dev/null +++ b/src/edu/berkeley/slipway/mpar/NetList.java @@ -0,0 +1,185 @@ +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 NetList { + + 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); } + + 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; + LogicalNet 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 LogicalNet().add(this); + this.net.add(p); + } + } + } + } + + /** a Net is a collection of ports which are wired together */ + public class LogicalNet implements Iterable { + private Node.Port driver = null; + private HashSet ports = new HashSet(); + private HashSet pips = new HashSet(); + private HashSet pns = new HashSet(); + + public void addPhysicalNet(PhysicalDevice.PhysicalNet pn) { pns.add(pn); } + public void removePhysicalNet(PhysicalDevice.PhysicalNet pn) { pns.remove(pn); } + public void addPhysicalPip(PhysicalDevice.PhysicalPip pip) { pips.add(pip); } + + public LogicalNet() { nets.add(this); } + public Iterator iterator() { return ports.iterator(); } + public int getSize() { return ports.size(); } + public boolean routed = false; + public void unroute() { + for(PhysicalDevice.PhysicalPip pip : pips) pip.set(false); + while(pns.size() > 0) pns.iterator().next().removeLogicalNet(this); + pips.clear(); + pns.clear(); + routed = false; + } + public void route(Fpslic fpslic, PhysicalDevice pd) { + if (driver == null) return; + if (routed) return; + Node.Port[] dests = new Node.Port[ports.size() - (ports.contains(driver) ? 1 : 0)]; + int j = 0; + for(Node.Port p : ports) + if (p != driver) + dests[j++] = p; + PhysicalDevice.PhysicalNet[] destsp = new PhysicalDevice.PhysicalNet[dests.length]; + for(int i=0; i "); + 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 NetList.Node createNode(EdifCellInstance eci, String portName) { + NetList.Node n = eci==null ? top.get(portName) : cache.get(eci); + if (n != null) return n; + if (eci==null) { + n = new NetList.Node("top_"+portName); + top.put(portName, n); + return n; + } else { + n = new NetList.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"; + NetList.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"; + NetList.Node.Port p2 = n2.getPort(name, driver); + p.connect(p2); + } + } + return n; + } +} diff --git a/src/edu/berkeley/slipway/mpar/PhysicalAtmelDevice.java b/src/edu/berkeley/slipway/mpar/PhysicalAtmelDevice.java new file mode 100644 index 0000000..e69de29 diff --git a/src/edu/berkeley/slipway/mpar/PhysicalDevice.java b/src/edu/berkeley/slipway/mpar/PhysicalDevice.java index 8d8b9ed..70397e7 100644 --- a/src/edu/berkeley/slipway/mpar/PhysicalDevice.java +++ b/src/edu/berkeley/slipway/mpar/PhysicalDevice.java @@ -1,273 +1,65 @@ 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 abstract class PhysicalDevice implements Iterable { - 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 abstract PhysicalCell getCell(int col, int 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 allPhysicalNets = new HashSet(); + public Iterator iterator() { return allPhysicalNets.iterator(); } - for(int x=4; x, Comparable { - } + // per-par-iteration variables + private double congestion = 0; + private int load = 0; - public void route(PhysicalNet source, PhysicalNet[] dests, FlatNetlist.Net owner) { - HashSet remainingDests = new HashSet(); - for(PhysicalNet dest : dests) remainingDests.add(dest); + // temporary variables used during route searches + private double distance = Double.MAX_VALUE; + private PhysicalNet backpointer = null; - HashSet needsReset = new HashSet(); - PriorityQueue pq = new PriorityQueue(); - needsReset.add(source); - source.distance = 0; - pq.add(source); + // adjacent pips + private final HashSet pips = new HashSet(); - 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; + private String name; - // penalty for using any net already routed in this iteration (makes routing order-sensitive) - if (net.load >= 1) newfrontier = newfrontier + 20; + // logical nets currently mapped onto this physical net + private HashSet logicalNets = new HashSet(); - 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; - } - } + public double getCongestion() { return congestion; } + public boolean isCongested() { return load >= 2; } + public void updateCongestion() { + congestion = congestion * alphaParameter; + if (isCongested()) congestion += betaParameter; } - 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 + public Iterable getLogicalNets() { return logicalNets; } + public void addLogicalNet(NetList.LogicalNet net) { + if (logicalNets.contains(net)) return; + logicalNets.add(net); + load++; + if (load >= 2) congestion += betaParameter; + net.addPhysicalNet(this); } - - for(PhysicalNet pn : needsReset) { - pn.distance = Double.MAX_VALUE; - pn.backpointer = null; + public void removeLogicalNet(NetList.LogicalNet net) { + if (!logicalNets.contains(net)) return; + logicalNets.remove(net); + load--; + net.removePhysicalNet(this); } - } - 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; + /** ordering is based on distance so we can use the Java PriorityQueue class */ public int compareTo(PhysicalNet pn) { double x = distance - pn.distance; return distance > pn.distance @@ -277,9 +69,7 @@ public class PhysicalDevice { : 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); @@ -293,20 +83,75 @@ public class PhysicalDevice { return pip; return null; } - public HashSet owners = new HashSet(); + public void route(PhysicalNet[] dests, NetList.LogicalNet logicalNet) { + HashSet remainingDests = new HashSet(); + for(PhysicalNet dest : dests) remainingDests.add(dest); + + HashSet needsReset = new HashSet(); + PriorityQueue pq = new PriorityQueue(); + needsReset.add(this); + this.distance = 0; + pq.add(this); + + OUTER: while(true) { + PhysicalNet pn = pq.poll(); + if (pn==null) throw new Error("unroutable! " + this + " -> " + dests[0]); + double frontier = pn.distance; + for(PhysicalPip pip : pn) + for(PhysicalNet net : pip.getDrivenNets()) { + double newfrontier = frontier + pip.getCost(pn, net) + net.getCongestion(); + + // 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) + for(PhysicalNet pn = dest; pn != null && pn.backpointer != null; pn = pn.backpointer) { + pn.addLogicalNet(logicalNet); + pn.distance = Double.MAX_VALUE; + PhysicalPip pip = pn.getPipFrom(pn.backpointer); + pip.set(true); + logicalNet.addPhysicalPip(pip); + } + + for(PhysicalNet pn : needsReset) { + pn.distance = Double.MAX_VALUE; + pn.backpointer = null; + } + } } public abstract class PhysicalPip { private PhysicalNet driver; private PhysicalNet[] driven; private String name; - private int defaultCost; + private double 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) { + public double getCost(PhysicalNet in, PhysicalNet out) { return defaultCost; } + public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven) { this(name, driver, driven, 0.05); } + public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven, double defaultCost) { this.name = name; this.driver = driver; this.driven = driven; diff --git a/src/edu/berkeley/slipway/mpar/PhysicalFpslic.java b/src/edu/berkeley/slipway/mpar/PhysicalFpslic.java new file mode 100644 index 0000000..748145f --- /dev/null +++ b/src/edu/berkeley/slipway/mpar/PhysicalFpslic.java @@ -0,0 +1,217 @@ +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 PhysicalFpslic extends PhysicalDevice { + private final Fpslic fpslic; + + public final int width; + public final int height; + private final PhysicalNet[][][][] sectorWires; + private final PhysicalFpslicCell[][] 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 PhysicalFpslic(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