X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fslipway%2Fmpar%2FMPARDemo.java;h=640727dfb4aea67a7d987a7c34cca4e7fbe70030;hb=1f1bff1ef60e5444ac0cd86657edfd9058993cd3;hp=f1c7ad7b16a8e61c9c07a79a02b00363882feec4;hpb=ab5e85e23cfb5d3d73a8d1c16588f81efd59f006;p=slipway.git

diff --git a/src/edu/berkeley/slipway/mpar/MPARDemo.java b/src/edu/berkeley/slipway/mpar/MPARDemo.java
index f1c7ad7..640727d 100644
--- a/src/edu/berkeley/slipway/mpar/MPARDemo.java
+++ b/src/edu/berkeley/slipway/mpar/MPARDemo.java
@@ -1,12 +1,15 @@
 package edu.berkeley.slipway.mpar;
 import com.atmel.fpslic.*;
+import java.awt.*;
 import byucc.edif.tools.merge.*;
 import byucc.edif.*;
 import java.io.*;
 import java.util.*;
 import edu.berkeley.slipway.*;
+//import edu.berkeley.abits.*;
 import com.atmel.fpslic.*;
 import static com.atmel.fpslic.FpslicConstants.*;
+import static edu.berkeley.slipway.mpar.PhysicalFpslic.*;
 
 // FIXME: sometimes gets stuck in a loop routing the last few nets
 
@@ -27,158 +30,134 @@ import static com.atmel.fpslic.FpslicConstants.*;
 
 public class MPARDemo {
 
-    public static final double alphaParameter = 00.9;
-    public static final double betaParameter  = 02.5;
-    public static final double gammaParameter =  1.0;
 
-    /*
-      test code for inter-sector switchboxes
-    public static void main2() throws Exception {
-        Fpslic fpslic = new FtdiBoard();
-        // set up scan cell
-        fpslic.cell(23,15).h(3, true);
-        fpslic.cell(23,15).yi(L3);
-        fpslic.cell(23,15).ylut(0xAA);
-        fpslic.iob_right(15, true).enableOutput(WEST);
-        fpslic.cell(23,0).ylut(0x00);
-        fpslic.iob_right(0, true).enableOutput(WEST);
-        fpslic.flush();
-        for(int x=0; x<20; x++) {
-            for(int y=0; y<20; y++) {
-                for(int l=0; l<5; l++) {
-                    for(int v = 0; v <= 1; v++) {
-                        boolean vert = v==1;
-                        int newx = vert ? x   : x-1;
-                        int newy = vert ? y-1 : y;
-                        if (newx<0 || newy<0) continue;
-                        if (vert  && (y%4) != 0) continue;
-                        if (!vert && (x%4) != 0) continue;
-
-                        int layer = l;
-                        if (layer==3) continue;
-                        Fpslic.Cell c  = fpslic.cell(x, y);
-                        Fpslic.Cell c2 = fpslic.cell(newx, newy);
-                        Fpslic.SectorWire sw1 = vert ? c.vwire(layer)  : c.hwire(layer);
-                        Fpslic.SectorWire sw2 = vert ? c2.vwire(layer) : c2.hwire(layer);
-                        sw1.drives(sw2, true);
-
-                        c.c(YLUT);
-                        if (vert) c.v(L0 + layer, true);
-                        else      c.h(L0 + layer, true);
-                        c.out(L0 + layer, true);
-                        c.b(false);
-                        
-                        c2.yi(L0 + layer);
-                        if (vert) c2.v(L0 + layer, true);
-                        else      c2.h(L0 + layer, true);
-                        c2.ylut(LUT_SELF);
-                        c2.c(YLUT);
-                        c2.b(false);
-                        
-                        System.out.print(x+","+y+","+l+","+(vert?"v":"h")+": ");
-                        c.ylut(0x00);
-                        fpslic.flush();
-                        boolean good = scan(fpslic, c2)==0;
-                        if (!good) fails++;
-                        System.out.print(good ? "ok " : "bad ");
-                        c.ylut(0xff);
-                        fpslic.flush();
-                        good = scan(fpslic, c2)!=0;
-                        if (!good) fails++;
-                        System.out.print(good ? "ok " : "bad ");
-                        System.out.println();
-                        sw1.drives(sw2, false);
-                        if (vert) c.v(layer, false);
-                        else      c.h(layer, false);
-                        c.out(layer, false);
-                    }
-                }
-            }
-        }
-        System.out.println("fails = " + fails);
-        
-    }
-    public static int fails = 0;
-    */
+    public static final double alphaParameter    =   0.9;
+    public static final double betaParameter     =   0.5;
+    public static final double wireCost          =   0.005;  
+    public static final double wireCostPlacement =   0.01;   // cost of an uncongested net (cost of congested net is 1)
+    //public static final double gammaParameter  =   1.0;
+    public static final double lambda            =  0.7;
+
+    public static double temperature = 300.0;
+    public static double congestion = 0;
+    public static double timingpenalty = 0;
 
     public static void main(String[] s) throws Exception {
-        EdifEnvironment topEnv = new EdifEnvironment("top");
-        EdifLibraryManager elm = new EdifLibraryManager(topEnv);
-        EdifLibrary initLib = new EdifLibrary(elm, "initLib");
-        EdifEnvironment env = EdifMergeParser.parseAndMerge(s, initLib);
-        System.out.println("top is " + env.getTopCell());
-        FlatNetlist fnl = new FlatNetlist();
-
-        for(Iterator<EdifCellInstance> it = (Iterator<EdifCellInstance>)env.getTopCell().cellInstanceIterator();
-            it.hasNext();
-            ) {
-            FlatNetlist.Node n = fnl.createNode(it.next(), null);
-        }
 
-        Fpslic fpslic = new FtdiBoard();
-        PhysicalDevice pd = new PhysicalDevice(fpslic, 20, 20);
+        NetList fnl = new NetList(s[0]);
+        int width = 12;
+        int height = 12;
+
+        //SlipwayBoard slipway = new SlipwayBoard();
+        FakeFpslicBoard slipway = new FakeFpslicBoard(24, 24);
 
-        int px = 0;
-        int py = 0;
+        FpslicDevice fpslic = (FpslicDevice)slipway.getDevice();
+        while(true) {
+        PhysicalDevice pd = new PhysicalFpslic(fpslic, width, height);
 
-        // crude map
+        Placement placement = new Placement(fnl, pd);
+        Routing routing = new Routing(placement);
         Random rand = new Random();
-        boolean[][] used = new boolean[pd.width][pd.height];
-        for(FlatNetlist.Node n : fnl.nodes) {
-            while(true) {
-                px = Math.abs(rand.nextInt()) % pd.width;
-                py = Math.abs(rand.nextInt()) % pd.height;
-                if (!used[px][py]) {
-                    used[px][py] = true;
-                    n.x = px;
-                    n.y = py;
-                    n.physicalCell = pd.getCell(px, py);
-                    System.out.println("placed " + n + " at ("+px+","+py+")");
-                    n.place(fpslic);
-                    break;
-                }
-            }
-        }
+        placement.random(rand);
+        routing.routeAll();
 
         int trial = 0;
-        HashSet<FlatNetlist.Net> needUnroute = new HashSet<FlatNetlist.Net>();
-        while(true) {
+        int num_moves = width*height;
+
+        Visualization vis = new Visualization((PhysicalFpslic)pd);
+
+        boolean alldone = false;
+        long lastDraw = System.currentTimeMillis();
+        OUT: while(true) {
             System.out.println();
-            System.out.println("routing trial " + (++trial));
-            for(FlatNetlist.Net net : fnl.nets) {
-                if (net.getSize() <= 1) continue;
-                net.route(fpslic, pd);
-            }
-            double congestion = 0;
-            int overrouted = 0;
-            needUnroute.clear();
-            for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets) {
-                if (pn.load > 1) {
-                    //System.out.println("overrouted: " + pn + ", congestion="+pn.congestion + ", load=" + pn.load);
-                    overrouted++;
-                    congestion += pn.congestion;
-                }
-                pn.congestion = pn.congestion * alphaParameter;
-                if (pn.load > 1) {
-                    pn.congestion += betaParameter;
-                    // don't do this here
-                    //pn.congestion += betaParameter;
-                    for(FlatNetlist.Net n : pn.owners)
-                        needUnroute.add(n);
+            double max_swap_dist = 3 * Math.max(width,height) * Math.exp(-1 / temperature);
+            System.out.println("round " + (++trial) + "  (temp="+temperature+", maxdist="+max_swap_dist+")");
+            
+            if (alldone) break;
+
+            congestion = routing.measureCongestion();
+            timingpenalty = routing.measureTimingpenalty();
+            double wirecost = routing.measureWireCost();
+            int swaps = 0;
+            num_moves = 200;
+
+            for(int i=0; i<num_moves; i++) {
+                System.out.print("\r  [place: " + i + "/" + num_moves + "  congestion="+congestion+"]");
+                NetList.Node node1 = fnl.randomNode(rand);
+                PhysicalDevice.PhysicalCell cell1 = placement.nodeToCell(node1);
+                PhysicalDevice.PhysicalCell cell2 = cell1.randomCellWithin(rand, max_swap_dist);
+                NetList.Node node2 = placement.cellToNode(cell2);
+
+                // FIXME: cache and reuse "newrouting"
+                // also: fold down newrouting to collapse parentage
+                routing.checkpoint();
+                routing.unroute(node1);
+                routing.unroute(node2);
+                placement.unplace(cell1);
+                placement.unplace(cell2);
+                placement.place(node1, cell2);
+                placement.place(node2, cell1);
+                routing.routeAll();
+
+                double newcongestion = routing.measureCongestion();
+                double newwirecost = routing.measureWireCost();
+                double newtimingpenalty = routing.measureTimingpenalty();
+                double lam = 0.1;
+                double deltaCost =
+                    lam * ((newcongestion - congestion) / Math.max(0.001, congestion))
+                    +
+                    //(1-lam) * ((newwirecost - wirecost) / wirecost)
+                    //+
+                    (1-lam) * ((newtimingpenalty - timingpenalty) / Math.max(0.001, timingpenalty))
+                    ;
+                double swapProbability = Math.exp((-1 * deltaCost) / temperature);
+                //double dist = Math.sqrt( (5-p2x)*(5-p2x) + (5-p2y)*(5-p2y) );
+                double rad = 4;
+                /*
+                if (rand2 == null)
+                    swapProbability = Math.max(0, Math.min(swapProbability, dist / Math.sqrt(rad+rad)));
+                */
+                boolean doSwap = Math.random() < swapProbability;
+                if (doSwap) {
+                    swaps++;
+                    congestion = newcongestion;
+                    wirecost = newwirecost;
+                    timingpenalty = newtimingpenalty;
+                } else {
+                    placement.unplace(cell1);
+                    placement.unplace(cell2);
+                    placement.place(node1, cell1);
+                    placement.place(node2, cell2);
+                    routing.rollback();
                 }
             }
-            System.out.println("  overrouted="+overrouted+", congestion="+congestion +", ripping up " + needUnroute.size() +" nets of " + fnl.nets.size());
-            if (overrouted <= 0) break;
-            //for(FlatNetlist.Net net : fnl.nets)
-            for(FlatNetlist.Net net : needUnroute)
-                net.unroute();
-            /*
-            for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets)
-                for(PhysicalDevice.PhysicalPip pip : pn) {
-                    pip.set(false);
-                }
-            */
+            double acceptance = ((double)swaps) / num_moves;
+            double gamma = 0;
+            if (acceptance > 0.96) gamma = 0.5;
+            else if (acceptance > 0.8) gamma = 0.9;
+            else if (acceptance > 0.15) gamma = 0.95;
+            else gamma = 0.8;
+
+            System.out.println("  acceptance="+acceptance);
+            temperature = temperature * gamma;
+            int num_routes = num_moves - swaps;
+            num_routes = 2;
+            for(int i=0; i<num_routes; i++) {
+                int overrouted = routing.measureOverloaded();
+                routing.unrouteOverloaded();
+                routing.reRouteAll();
+                System.out.print("\r  [route "+i+"/"+num_routes+"] overrouted="+overrouted+" congestion="+routing.measureCongestion()+"     penalty="+timingpenalty);
+                routing.updateCongestion(alphaParameter, betaParameter);
+                if (overrouted==0 && timingpenalty < 1) alldone = true;
+            }
+            num_moves = (int)(300 * gamma * gamma);
+            vis.draw(placement, routing, false);
+            System.out.println();
         }
+        vis.draw(placement, routing, true);
+        placement.setPlacement();
+        routing.setPips(true);
+        System.out.println("wire utilization: " + Math.round(routing.measureWireUtilization()*100));
 
         // set up scan cell
         fpslic.cell(23,15).h(3, true);
@@ -188,28 +167,32 @@ public class MPARDemo {
         fpslic.cell(23,0).ylut(0x00);
         fpslic.iob_right(0, true).enableOutput(WEST);
         fpslic.flush();
-
-        int width = 8;
-        while(true) {
-            int a = Math.abs(rand.nextInt()) % (1 << width);
-            int b = Math.abs(rand.nextInt()) % (1 << width);
-            setInput(fnl, fpslic, "a",  a);
-            setInput(fnl, fpslic, "b",  b);
-            setInput(fnl, fpslic, "ci", 0);
-            int result = getOutput(fnl, fpslic, "out");
+        /*
+        int xwidth = 8;
+        temperature = 0;
+        while(temperature==0) {
+            int a = Math.abs(rand.nextInt()) % (1 << xwidth);
+            int b = Math.abs(rand.nextInt()) % (1 << xwidth);
+            setInput(fnl, fpslic, "a",  a, placement);
+            setInput(fnl, fpslic, "b",  b, placement);
+            setInput(fnl, fpslic, "ci", 0, placement);
+            int result = getOutput(fnl, fpslic, slipway, "out", placement);
+            int expect = (a+b) & ~(-1 << (xwidth+1));
             System.out.println(Integer.toString(a,16) + " + " +
                                Integer.toString(b,16) + " = " +
                                Integer.toString(result,16) +
-                               " [ " + (a+b==result ? "ok" : "bad" ) + " ] ");
+                               " [ " + (expect==result ? "ok" : "bad" ) + " ] " + (Integer.toString((result^(expect)),16)));
         }
+        */
+    }
     }
 
 
     private static int ret;
-    public static synchronized int scan(final Fpslic device, final Fpslic.Cell cell) {
+    public static synchronized int scan(final FpslicDevice device, final SlipwayBoard slipway, final FpslicDevice.Cell cell) {
         try {
-            scan(device, cell, YLUT, true);
-            ((FtdiBoard)device).readBus(new FtdiBoard.ByteCallback() {
+            scan(device, cell, XLUT, true);
+            slipway.readFpgaData(new SlipwayBoard.ByteCallback() {
                     public void call(byte b) throws Exception {
                         ret = b;
                         synchronized(device) {
@@ -222,12 +205,12 @@ public class MPARDemo {
                     device.wait();
                 } catch (Exception e) { throw new RuntimeException(e); }
             }
-            scan(device, cell, YLUT, false);
+            scan(device, cell, XLUT, false);
             return ret;
         } catch (Exception e) { throw new RuntimeException(e); }
     }
 
-    public static void scan(Fpslic dev, Fpslic.Cell cell, int source, boolean setup) {
+    public static void scan(FpslicDevice dev, FpslicDevice.Cell cell, int source, boolean setup) {
         if (setup) {
             //if (source != NONE) cell.c(source);
             if (cell.b()) cell.b(false);
@@ -236,7 +219,7 @@ public class MPARDemo {
         if (cell.out(L3)!=setup) cell.out(L3, setup);
         if (cell.vx(L3)!=setup) cell.v(L3, setup);
 
-        Fpslic.SectorWire sw = cell.vwire(L3);
+        FpslicDevice.SectorWire sw = cell.vwire(L3);
         //System.out.println("wire is: " + sw);
 
         if (sw.row > (12 & ~0x3) && sw.north()!=null && sw.north().drives(sw))
@@ -279,30 +262,30 @@ public class MPARDemo {
 
     }
 
-        public static void setInput(FlatNetlist fnl, Fpslic fpslic, String prefix, int val) {
-            for(int i=0; ; i++) {
-                FlatNetlist.Node n = fnl.top.get(prefix + "["+i+"]");
-                if (n==null && i==0) n = fnl.top.get(prefix);
-                if (n==null) return;
-                Fpslic.Cell c = n.getPlacement(fpslic);
-                c.c(XLUT);
-                c.b(false);
-                c.xlut((val & 0x1)==0 ? 0x00 : 0xff);
-                val = val >> 1;
-            }
+    public static void setInput(NetList fnl, FpslicDevice fpslic, String prefix, int val, Placement placement) {
+        for(int i=0; ; i++) {
+            NetList.Node n = fnl.top.get(prefix + "["+i+"]");
+            if (n==null && i==0) n = fnl.top.get(prefix);
+            if (n==null) return;
+            FpslicDevice.Cell c = ((PhysicalFpslic.PhysicalFpslicCell)placement.nodeToCell(n)).cell();
+            c.c(XLUT);
+            c.b(false);
+            c.xlut((val & 0x1)==0 ? 0x00 : 0xff);
+            val = val >> 1;
         }
-        public static int getOutput(FlatNetlist fnl, Fpslic fpslic, String prefix) {
+    }
+    public static int getOutput(NetList fnl, FpslicDevice fpslic, SlipwayBoard slipway, String prefix, Placement placement) {
             int val = 0;
             for(int i=0; ; i++) {
-                FlatNetlist.Node n = fnl.top.get(prefix+"["+i+"]");
+                NetList.Node n = fnl.top.get(prefix+"["+i+"]");
                 if (n==null && i==0) n = fnl.top.get(prefix);
                 if (n==null) return val;
-                Fpslic.Cell c = n.getPlacement(fpslic);
+                FpslicDevice.Cell c = ((PhysicalFpslic.PhysicalFpslicCell)placement.nodeToCell(n)).cell();
                 c.xlut(LUT_SELF);
                 c.c(XLUT);
                 c.b(false);
                 fpslic.flush();
-                int scan = scan(fpslic, c);
+                int scan = scan(fpslic, slipway, c);
                 val |= ((scan==0 ? 0 : 1) << i);
             }
         }