src/edu/berkeley/slipway/mpar/PhysicalDevice.java

   1 package edu.berkeley.slipway.mpar;
   2 import byucc.edif.tools.merge.*;
   3 import byucc.edif.*;
   4 import java.io.*;
   5 import java.util.*;
   6 import edu.berkeley.slipway.*;
   7 import static edu.berkeley.slipway.mpar.MPARDemo.*;
   8
   9 public abstract class PhysicalDevice implements Iterable<PhysicalDevice.PhysicalNet> {
  10
  11     public abstract PhysicalCell getCell(int col, int row);
  12
  13     private HashSet<PhysicalNet> allPhysicalNets = new HashSet<PhysicalNet>();
  14     public Iterator<PhysicalNet> iterator() { return allPhysicalNets.iterator(); }
  15
  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);
  20     }
  21
  22     public class PhysicalNet implements Iterable<PhysicalPip>, Comparable<PhysicalNet> {
  23
  24         // per-par-iteration variables
  25         private  double      congestion = 0;
  26         private  int         load = 0;
  27
  28         // temporary variables used during route searches
  29         private  double      distance = Double.MAX_VALUE;
  30         private  PhysicalNet backpointer = null;
  31
  32         // adjacent pips
  33         private final HashSet<PhysicalPip> pips = new HashSet<PhysicalPip>();
  34
  35         private String name;
  36
  37         // logical nets currently mapped onto this physical net
  38         private HashSet<NetList.LogicalNet> logicalNets = new HashSet<NetList.LogicalNet>();
  39
  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;
  45         }
  46
  47         public Iterable<NetList.LogicalNet> getLogicalNets() { return logicalNets; }
  48         public void addLogicalNet(NetList.LogicalNet net) {
  49             if (logicalNets.contains(net)) return;
  50             logicalNets.add(net);
  51             load++;
  52             if (load >= 2) congestion += betaParameter;
  53             net.addPhysicalNet(this);
  54         }
  55         public void removeLogicalNet(NetList.LogicalNet net) {
  56             if (!logicalNets.contains(net)) return;
  57             logicalNets.remove(net);
  58             load--;
  59             net.removePhysicalNet(this);
  60         }
  61
  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
  66                 ? 1
  67                 : distance < pn.distance
  68                 ? -1
  69                 : 0;
  70         }
  71
  72         public Iterator<PhysicalPip> iterator() { return pips.iterator(); }
  73         public PhysicalNet(String name) {
  74             this.name = name;
  75             allPhysicalNets.add(this);
  76         }
  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())
  82                     if (pn2==this)
  83                         return pip;
  84             return null;
  85         }
  86         public void route(PhysicalNet[] dests, NetList.LogicalNet logicalNet) {
  87             HashSet<PhysicalNet> remainingDests = new HashSet<PhysicalNet>();
  88             for(PhysicalNet dest : dests) remainingDests.add(dest);
  89
  90             HashSet<PhysicalNet> needsReset = new HashSet<PhysicalNet>();
  91             PriorityQueue<PhysicalNet> pq = new PriorityQueue<PhysicalNet>();
  92             needsReset.add(this);
  93             this.distance = 0;
  94             pq.add(this);
  95
  96             OUTER: while(true) {
  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();
 103
 104                         // penalty for using any net already routed in this iteration (makes routing order-sensitive)
 105                         if (net.load >= 1) newfrontier = newfrontier + 20;
 106
 107                         if (net.distance <= newfrontier) continue;
 108                         pq.remove(net);  // if already in there
 109                         net.distance = newfrontier;
 110                         pq.add(net);
 111                         needsReset.add(net);
 112                         net.backpointer = pn;
 113
 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) {
 120                                 pnx.distance = 0;
 121                                 pq.add(pnx);
 122                             }
 123                             break;
 124                         }
 125                     }
 126             }
 127
 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);
 133                     pip.set(true);
 134                     logicalNet.addPhysicalPip(pip);
 135                 }
 136
 137             for(PhysicalNet pn : needsReset) {
 138                 pn.distance    = Double.MAX_VALUE;
 139                 pn.backpointer = null;
 140             }
 141         }
 142     }
 143
 144     public abstract class PhysicalPip {
 145         private PhysicalNet   driver;
 146         private PhysicalNet[] driven;
 147         private String name;
 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) {
 155             this.name = name;
 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);
 161         }
 162         public abstract void set(boolean connected);
 163     }
 164
 165 }