X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fslipway%2Fmpar%2FPhysicalDevice.java;fp=src%2Fedu%2Fberkeley%2Fslipway%2Fmpar%2FPhysicalDevice.java;h=e611e7aa36d337ba8e469518851182430c1065e9;hb=5301afc9e47f0dd6f96858d1c70407e0df5b53cf;hp=70397e7645465b9500b67a46c08a8e934bf4e3d6;hpb=d76f7c4ce28a3b84ada73282f3ca00a9b716cf93;p=slipway.git

diff --git a/src/edu/berkeley/slipway/mpar/PhysicalDevice.java b/src/edu/berkeley/slipway/mpar/PhysicalDevice.java
index 70397e7..e611e7a 100644
--- a/src/edu/berkeley/slipway/mpar/PhysicalDevice.java
+++ b/src/edu/berkeley/slipway/mpar/PhysicalDevice.java
@@ -9,6 +9,7 @@ import static edu.berkeley.slipway.mpar.MPARDemo.*;
 public abstract class PhysicalDevice implements Iterable<PhysicalDevice.PhysicalNet> {
 
     public abstract PhysicalCell getCell(int col, int row);
+    public abstract PhysicalCell randomCell(Random rand);
 
     private HashSet<PhysicalNet> allPhysicalNets = new HashSet<PhysicalNet>();
     public Iterator<PhysicalNet> iterator() { return allPhysicalNets.iterator(); }
@@ -17,54 +18,35 @@ public abstract class PhysicalDevice implements Iterable<PhysicalDevice.Physical
         public abstract PhysicalNet getNet(String name);
         public abstract void setFunction(String type);
         public abstract void place(NetList.Node n);
+        public abstract PhysicalCell randomCellWithin(Random rand, double percentOfDevice);
     }
 
+    private int master_idx = 0;
+
+    public int getNumPhysicalNets() { return master_idx; }
     public class PhysicalNet implements Iterable<PhysicalPip>, Comparable<PhysicalNet> {
 
-        // per-par-iteration variables
-        private  double      congestion = 0;
-        private  int         load = 0;
+        public final int idx = master_idx++;
 
         // temporary variables used during route searches
-        private  double      distance = Double.MAX_VALUE;
-        private  PhysicalNet backpointer = null;
+        double      distance = Double.MAX_VALUE;
+        double      delay = Double.MAX_VALUE;
+        PhysicalNet backpointer = null;
+        int iteration = 0;
+        int depth = 0;
+        boolean remaining = false;
 
         // adjacent pips
-        private final HashSet<PhysicalPip> pips = new HashSet<PhysicalPip>();
+        public final HashSet<PhysicalPip> pips = new HashSet<PhysicalPip>();
 
         private String name;
 
-        // logical nets currently mapped onto this physical net
-        private HashSet<NetList.LogicalNet> logicalNets = new HashSet<NetList.LogicalNet>();
-
-        public double getCongestion() { return congestion; }
-        public boolean isCongested() { return load >= 2; }
-        public void updateCongestion() {
-            congestion = congestion * alphaParameter;
-            if (isCongested()) congestion += betaParameter;
-        }
-
-        public Iterable<NetList.LogicalNet> 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);
-        }
-        public void removeLogicalNet(NetList.LogicalNet net) {
-            if (!logicalNets.contains(net)) return;
-            logicalNets.remove(net);
-            load--;
-            net.removePhysicalNet(this);
-        }
-
         /** 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
+            return x>0
                 ? 1
-                : distance < pn.distance
+                : x<0
                 ? -1
                 : 0;
         }
@@ -83,79 +65,28 @@ public abstract class PhysicalDevice implements Iterable<PhysicalDevice.Physical
                         return pip;
             return null;
         }
-        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;
-            }
-        }
     }
         
     public abstract class PhysicalPip {
-        private PhysicalNet   driver;
-        private PhysicalNet[] driven;
+        public PhysicalNet   driver;
+        public PhysicalNet[] driven;
         private String name;
-        private double defaultCost;
+        double defaultCost;
+        double defaultDelay = 1;
+        public abstract boolean prohibited();
         public String toString() { return name; }
         public PhysicalNet   getDriverNet()  { return driver; }
         public PhysicalNet[] getDrivenNets() { return driven; }
+        public double        getDelay(PhysicalNet in, PhysicalNet out) { return defaultDelay; }
         public double        getCost(PhysicalNet in, PhysicalNet out) { return defaultCost; }
-        public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven) { this(name, driver, driven, 0.05); }
+        public abstract int getX();
+        public abstract int getY();
+        public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven) { this(name, driver, driven, wireCost); }
         public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven, double defaultCost) {
             this.name = name;
             this.driver = driver;
             this.driven = driven;
-            this.defaultCost = defaultCost;
+            this.defaultCost = 1;
             if (driver != null) driver.addPip(this);
             for(PhysicalNet pn : driven) pn.addPip(this);
         }