- public void route(PhysicalNet[] dests, NetList.LogicalNet logicalNet) {
- HashSet<PhysicalNet> remainingDests = new HashSet<PhysicalNet>();
- for(PhysicalNet dest : dests) remainingDests.add(dest);
-
- HashSet<PhysicalNet> needsReset = new HashSet<PhysicalNet>();
- PriorityQueue<PhysicalNet> pq = new PriorityQueue<PhysicalNet>();
- 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;
- }
- }