1 package edu.berkeley.slipway.mpar;
2 import byucc.edif.tools.merge.*;
6 import edu.berkeley.slipway.*;
7 import static edu.berkeley.slipway.mpar.MPARDemo.*;
9 public abstract class PhysicalDevice implements Iterable<PhysicalDevice.PhysicalNet> {
11 public abstract PhysicalCell getCell(int col, int row);
13 private HashSet<PhysicalNet> allPhysicalNets = new HashSet<PhysicalNet>();
14 public Iterator<PhysicalNet> iterator() { return allPhysicalNets.iterator(); }
16 public abstract class PhysicalCell {
17 public abstract PhysicalNet getNet(String name);
18 public abstract void setFunction(String type);
19 public abstract void place(NetList.Node n);
22 public class PhysicalNet implements Iterable<PhysicalPip>, Comparable<PhysicalNet> {
24 // per-par-iteration variables
25 private double congestion = 0;
28 // temporary variables used during route searches
29 private double distance = Double.MAX_VALUE;
30 private PhysicalNet backpointer = null;
33 private final HashSet<PhysicalPip> pips = new HashSet<PhysicalPip>();
37 // logical nets currently mapped onto this physical net
38 private HashSet<NetList.LogicalNet> logicalNets = new HashSet<NetList.LogicalNet>();
40 public double getCongestion() { return congestion; }
41 public boolean isCongested() { return load >= 2; }
42 public void updateCongestion() {
43 congestion = congestion * alphaParameter;
44 if (isCongested()) congestion += betaParameter;
47 public Iterable<NetList.LogicalNet> getLogicalNets() { return logicalNets; }
48 public void addLogicalNet(NetList.LogicalNet net) {
49 if (logicalNets.contains(net)) return;
52 if (load >= 2) congestion += betaParameter;
53 net.addPhysicalNet(this);
55 public void removeLogicalNet(NetList.LogicalNet net) {
56 if (!logicalNets.contains(net)) return;
57 logicalNets.remove(net);
59 net.removePhysicalNet(this);
62 /** ordering is based on distance so we can use the Java PriorityQueue class */
63 public int compareTo(PhysicalNet pn) {
64 double x = distance - pn.distance;
65 return distance > pn.distance
67 : distance < pn.distance
72 public Iterator<PhysicalPip> iterator() { return pips.iterator(); }
73 public PhysicalNet(String name) {
75 allPhysicalNets.add(this);
77 public String toString() { return name; }
78 private void addPip(PhysicalPip pip) { pips.add(pip); }
79 public PhysicalPip getPipFrom(PhysicalNet pn) {
80 for(PhysicalPip pip : pn)
81 for(PhysicalNet pn2 : pip.getDrivenNets())
86 public void route(PhysicalNet[] dests, NetList.LogicalNet logicalNet) {
87 HashSet<PhysicalNet> remainingDests = new HashSet<PhysicalNet>();
88 for(PhysicalNet dest : dests) remainingDests.add(dest);
90 HashSet<PhysicalNet> needsReset = new HashSet<PhysicalNet>();
91 PriorityQueue<PhysicalNet> pq = new PriorityQueue<PhysicalNet>();
97 PhysicalNet pn = pq.poll();
98 if (pn==null) throw new Error("unroutable! " + this + " -> " + dests[0]);
99 double frontier = pn.distance;
100 for(PhysicalPip pip : pn)
101 for(PhysicalNet net : pip.getDrivenNets()) {
102 double newfrontier = frontier + pip.getCost(pn, net) + net.getCongestion();
104 // penalty for using any net already routed in this iteration (makes routing order-sensitive)
105 if (net.load >= 1) newfrontier = newfrontier + 20;
107 if (net.distance <= newfrontier) continue;
108 pq.remove(net); // if already in there
109 net.distance = newfrontier;
112 net.backpointer = pn;
114 if (remainingDests.contains(net)) {
115 remainingDests.remove(net);
116 if (remainingDests.size()==0) break OUTER;
117 // Vaughn Betz style multiterminal routing: once we reach one sink, make every node on the path
118 // "distance zero" from the source.
119 for(PhysicalNet pnx = net; pnx != null; pnx = pnx.backpointer) {
128 for(PhysicalNet dest : dests)
129 for(PhysicalNet pn = dest; pn != null && pn.backpointer != null; pn = pn.backpointer) {
130 pn.addLogicalNet(logicalNet);
131 pn.distance = Double.MAX_VALUE;
132 PhysicalPip pip = pn.getPipFrom(pn.backpointer);
134 logicalNet.addPhysicalPip(pip);
137 for(PhysicalNet pn : needsReset) {
138 pn.distance = Double.MAX_VALUE;
139 pn.backpointer = null;
144 public abstract class PhysicalPip {
145 private PhysicalNet driver;
146 private PhysicalNet[] driven;
148 private double defaultCost;
149 public String toString() { return name; }
150 public PhysicalNet getDriverNet() { return driver; }
151 public PhysicalNet[] getDrivenNets() { return driven; }
152 public double getCost(PhysicalNet in, PhysicalNet out) { return defaultCost; }
153 public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven) { this(name, driver, driven, 0.05); }
154 public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven, double defaultCost) {
156 this.driver = driver;
157 this.driven = driven;
158 this.defaultCost = defaultCost;
159 if (driver != null) driver.addPip(this);
160 for(PhysicalNet pn : driven) pn.addPip(this);
162 public abstract void set(boolean connected);