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

   1 package edu.berkeley.slipway.mpar;
   2 import com.atmel.fpslic.*;
   3 import java.awt.*;
   4 import byucc.edif.tools.merge.*;
   5 import byucc.edif.*;
   6 import java.io.*;
   7 import java.util.*;
   8 import edu.berkeley.slipway.*;
   9 import edu.berkeley.abits.*;
  10 import com.atmel.fpslic.*;
  11 import static com.atmel.fpslic.FpslicConstants.*;
  12 import static edu.berkeley.slipway.mpar.PhysicalDevice.*;
  13 import static edu.berkeley.slipway.mpar.NetList.*;
  14
  15
  16 // FIXME: make sure everything is O(design), not O(device)
  17 public class Routing {
  18
  19     public final Placement placement;
  20     public final NetList netlist;
  21     public final PhysicalDevice pd;
  22
  23     private HashSet<Route> removed = new HashSet<Route>();
  24     private HashSet<Route> added   = new HashSet<Route>();
  25     public void checkpoint() {
  26         removed.clear();
  27         added.clear();
  28     }
  29     public void rollback() {
  30         for (Route r : added) r.remove(false);
  31         for (Route r : removed) r.add();
  32     }
  33
  34     public Routing(Placement p) {
  35         this.placement = p;
  36         this.netlist = p.netlist;
  37         this.pd = p.pd;
  38         congestion = new double[pd.getNumPhysicalNets()];
  39         load       = new int[pd.getNumPhysicalNets()];
  40     }
  41
  42     private double[] congestion;
  43     private int[]    load;
  44     public HashMap<NetList.LogicalNet, Route> routes =
  45         new HashMap<NetList.LogicalNet, Route>();
  46
  47     private class Route {
  48         private NetList.LogicalNet logicalNet;
  49         private HashSet<PhysicalDevice.PhysicalNet> nets;
  50         private HashSet<PhysicalDevice.PhysicalPip> pips;
  51         double timingpenalty;
  52         public Route(NetList.LogicalNet logicalNet,
  53                      HashSet<PhysicalDevice.PhysicalNet> nets,
  54                      HashSet<PhysicalDevice.PhysicalPip> pips
  55                      ) {
  56             this.logicalNet = logicalNet;
  57             this.nets = nets;
  58             this.pips = pips;
  59         }
  60         public void add() {
  61             for(PhysicalDevice.PhysicalNet net : nets)
  62                 load[net.idx]++;
  63             added.add(this);
  64             routes.put(logicalNet, this);
  65         }
  66         public void remove() { remove(true); }
  67         public void remove(boolean note) {
  68             for(PhysicalDevice.PhysicalNet net : nets)
  69                 load[net.idx]--;
  70             if (note) removed.add(this);
  71             routes.remove(logicalNet);
  72         }
  73     }
  74
  75     public void setPips(boolean on) {
  76         for (Route r : routes.values())
  77             for (PhysicalDevice.PhysicalPip pip : r.pips)
  78                 pip.set(on);
  79     }
  80
  81     public int getLoad(PhysicalDevice.PhysicalNet pn) { return load[pn.idx]; }
  82     public double getCongestion(PhysicalDevice.PhysicalNet pn) { return congestion[pn.idx]; }
  83
  84     public void routeAll() throws RoutingFailedException {
  85         for(NetList.LogicalNet net : netlist.nets)
  86             route(net);
  87     }
  88     public void reRouteAll() throws RoutingFailedException {
  89         for(NetList.LogicalNet net : netlist.nets) {
  90             unroute(net);
  91             route(net);
  92         }
  93     }
  94     public void unRouteAll() {
  95         for(NetList.LogicalNet signal : netlist.getLogicalNets())
  96             unroute(signal);
  97     }
  98
  99
 100     public void unroute(NetList.Node node) {
 101         if (node==null) return;
 102         for(NetList.Node.Port p : node)
 103             unroute(p.net);
 104     }
 105     /*
 106     public void unroute(PhysicalDevice.PhysicalNet net) {
 107         while(netToSignals.size(net) > 0)
 108             unroute(netToSignals.getAll(net).iterator().next());
 109     }
 110     */
 111     public void unroute(NetList.LogicalNet signal) {
 112         if (signal==null) return;
 113         Route r = routes.get(signal);
 114         if (r != null) r.remove();
 115     }
 116
 117     public void unrouteOverloaded() {
 118         /*
 119           FIXME
 120         for(PhysicalDevice.PhysicalNet pn : pd)
 121             if (getLoad(pn) > 1)
 122                 unroute(pn);
 123         */
 124     }
 125
 126     public void updateCongestion(double alphaParameter, double betaParameter) {
 127         for(PhysicalDevice.PhysicalNet net : pd) {
 128             double c = getCongestion(net);
 129             c = c * alphaParameter;
 130             if (getLoad(net) > 1) c += betaParameter;
 131             congestion[net.idx] = c;
 132         }
 133     }
 134
 135     public static class RoutingFailedException extends Exception { }
 136
 137     public static int iteration = 1;
 138
 139     private HashSet<PhysicalDevice.PhysicalNet> remainingDests = new HashSet<PhysicalDevice.PhysicalNet>();
 140     private PriorityQueue<PhysicalDevice.PhysicalNet> pq = new PriorityQueue<PhysicalDevice.PhysicalNet>();
 141     public void route(NetList.LogicalNet logicalNet) throws RoutingFailedException {
 142         double maxDelay = 10;
 143         boolean tryHard = true;
 144         double ts = 0;
 145         if (logicalNet.driver == null) return;
 146         if (logicalNet.getSize() <= 1) return;
 147         if (isRouted(logicalNet)) return;
 148
 149         int remaining = 0;
 150         for(NetList.Node.Port p : logicalNet.ports)
 151             if (p != logicalNet.driver) {
 152                 PhysicalDevice.PhysicalNet dest;
 153                 switch(p.index) {
 154                     case 0: dest = placement.nodeToCell(p.getNode()).getNet("xi"); break;
 155                     case 1: dest = placement.nodeToCell(p.getNode()).getNet("yi"); break;
 156                     default: throw new Error();
 157                 }
 158                 dest.remaining = true;
 159                 remaining++;
 160             }
 161         iteration++;
 162
 163         PhysicalDevice.PhysicalNet source = placement.nodeToCell(logicalNet.driver.getNode()).getNet("out");
 164         pq.clear();
 165         source.distance = -1 * maxDelay;
 166         source.depth = 0;
 167         source.iteration = iteration;
 168         pq.add(source);
 169
 170         HashSet<PhysicalDevice.PhysicalNet> nets = new HashSet<PhysicalDevice.PhysicalNet>();
 171         HashSet<PhysicalDevice.PhysicalPip> pips = new HashSet<PhysicalDevice.PhysicalPip>();
 172         OUTER: while(true) {
 173             PhysicalDevice.PhysicalNet pn = pq.poll();
 174             if (pn==null) throw new RoutingFailedException();
 175             double frontier = pn.distance;
 176             for(PhysicalDevice.PhysicalPip pip : pn) {
 177                 for(PhysicalDevice.PhysicalNet net : pip.getDrivenNets()) {
 178                     if (net.iteration != iteration) {
 179                         net.iteration = iteration;
 180                         net.distance = Double.MAX_VALUE;
 181                     }
 182                     double newfrontier = frontier + pip.getCost(pn, net);
 183                     newfrontier += getCongestion(net);
 184                     if (getLoad(net) > 0) newfrontier += 1000;
 185
 186                     // penalty for using any net already routed in this iteration (makes routing order-sensitive)
 187                     //if (net.load >= 1) newfrontier = newfrontier + 20;
 188
 189                     if (net.distance <= newfrontier) continue;
 190                     net.distance = newfrontier;
 191                     pq.add(net);
 192                     net.backpointer = pn;
 193                     net.depth = pn.depth+1;
 194
 195                     if (!net.remaining) continue;
 196                     remaining--;
 197                     net.remaining = false;
 198                     // Vaughn Betz style multiterminal routing: once we reach one sink, make every node on the path
 199                     // "distance zero" from the source.
 200                     nets.add(source);
 201                     if (newfrontier > 0) ts += newfrontier;
 202                     for(PhysicalDevice.PhysicalNet p = net; p != source; p = p.backpointer) {
 203                         PhysicalDevice.PhysicalPip pipx = p.getPipFrom(p.backpointer);  // FIXME: this call is actually slow
 204                         pips.add(pipx);
 205                         if (pipx.driver != null) nets.add(pipx.driver);
 206                         for(PhysicalDevice.PhysicalNet n : pipx.driven) nets.add(n);
 207                         p.distance = source.distance;
 208                         pq.add(p);
 209                         nets.add(p);
 210                     }
 211                     if (remaining==0) break OUTER;
 212                 }
 213             }
 214         }
 215         Route r = new Route(logicalNet, nets, pips);
 216         r.add();
 217         r.timingpenalty = ts;
 218     }
 219
 220
 221     public boolean isRouted(NetList.LogicalNet n) { return routes.get(n) != null; }
 222     //public boolean isRouted(PhysicalDevice.PhysicalNet pn) { return netToSignal.get(pn) != null; }
 223     //public PhysicalDevice.PhysicalNet signalToNet(NetList.LogicalNet n) { return signalToNets.get(n); }
 224     //public NetList.LogicalNet netToSignal(PhysicalDevice.PhysicalNet pn) { return netToSignals.get(pn); }
 225
 226     public double measureCongestion() {
 227         double congestion = 0;
 228         for(PhysicalDevice.PhysicalNet pn : pd)
 229             if (getLoad(pn) > 1)
 230                 congestion += getLoad(pn)-1;
 231         for(NetList.LogicalNet ln : netlist.nets)
 232             if (!isRouted(ln))
 233                 congestion = Double.MAX_VALUE;
 234         return congestion;
 235     }
 236
 237     public double measureWireCost() {
 238         double cong = 0;
 239         for(PhysicalDevice.PhysicalNet pn : pd)
 240             cong += getLoad(pn);
 241         return cong;
 242     }
 243
 244     public double measureTimingpenalty() {
 245         double ret = 0;
 246         for(Route r : routes.values())
 247             ret += r.timingpenalty;
 248         return ret;
 249     }
 250
 251     public int measureOverloaded() {
 252         int ret = 0;
 253         for(PhysicalDevice.PhysicalNet pn : pd)
 254             if (getLoad(pn) > 1)
 255                 ret++;
 256         return ret;
 257     }
 258
 259     public double measureWireUtilization() {
 260         int numwires = 0;
 261         int used = 0;
 262         for(PhysicalDevice.PhysicalNet pn : pd) {
 263             numwires++;
 264             used += getLoad(pn);
 265         }
 266         return ((double)used)/((double)numwires);
 267     }
 268
 269     public void draw(Graphics2D g) {
 270         for(NetList.LogicalNet signal : netlist.nets)
 271             draw(g, signal);
 272     }
 273     public void draw(Graphics2D g, NetList.LogicalNet signal) {
 274         g.setColor(/*getLoad(pip1.driver) >= 2 ? Color.red :*/ Color.blue);
 275         for(Route r : routes.values()) {
 276             for(PhysicalDevice.PhysicalNet net : r.nets) {
 277                 for(PhysicalDevice.PhysicalPip pip1 : net) {
 278                     if (!r.pips.contains(pip1)) continue;
 279                     for(PhysicalDevice.PhysicalPip pip2 : net) {
 280                         if (!r.pips.contains(pip2)) continue;
 281
 282                         g.drawLine(pip1.getX(),
 283                                    pip1.getY(),
 284                                    pip2.getX(),
 285                                    pip2.getY());
 286
 287                     }
 288                 }
 289             }
 290         }
 291     }
 292 }