src/edu/berkeley/slipway/mpar/MPARDemo.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.PhysicalFpslic.*;
  13
  14 // FIXME: sometimes gets stuck in a loop routing the last few nets
  15
  16 // FEATURE: ability to rip up only one branch of a multi-terminal net
  17
  18 // FEATURE: re-placement based on routing congestion
  19 //          note: must assign a cost to "bare wire" -- if not, the
  20 //          placer will fail to recognize moves that put blocks closer
  21 //          together, thereby decreasing the potential for future
  22 //          congestion.
  23
  24 // FEATURE: A* search (chap7 of independence thesis)
  25
  26 // FIXME: distinguish out,xo,yo
  27 // FIXME: y-axis shortcuts
  28 // FEATURE: ability to use a cell for routing purposes
  29 // FEATURE: global two-sector-long wires
  30
  31 public class MPARDemo {
  32
  33
  34     public static final double alphaParameter    =   0.9;
  35     public static final double betaParameter     =   0.5;
  36     public static final double wireCost          =   0.005;
  37     public static final double wireCostPlacement =   0.01;   // cost of an uncongested net (cost of congested net is 1)
  38     //public static final double gammaParameter  =   1.0;
  39     public static final double lambda            =  0.7;
  40
  41     public static double temperature = 300.0;
  42     public static double congestion = 0;
  43     public static double timingpenalty = 0;
  44
  45     public static void main(String[] s) throws Exception {
  46
  47         NetList fnl = new NetList(s[0]);
  48         int width = 12;
  49         int height = 12;
  50
  51         //SlipwayBoard slipway = new SlipwayBoard();
  52         FakeFpslicBoard slipway = new FakeFpslicBoard(24, 24);
  53
  54         FpslicDevice fpslic = (FpslicDevice)slipway.getDevice();
  55         while(true) {
  56         PhysicalDevice pd = new PhysicalFpslic(fpslic, width, height);
  57
  58         Placement placement = new Placement(fnl, pd);
  59         Routing routing = new Routing(placement);
  60         Random rand = new Random();
  61         placement.random(rand);
  62         routing.routeAll();
  63
  64         int trial = 0;
  65         int num_moves = width*height;
  66
  67         Visualization vis = new Visualization((PhysicalFpslic)pd);
  68
  69         boolean alldone = false;
  70         long lastDraw = System.currentTimeMillis();
  71         OUT: while(true) {
  72             System.out.println();
  73             double max_swap_dist = 3 * Math.max(width,height) * Math.exp(-1 / temperature);
  74             System.out.println("round " + (++trial) + "  (temp="+temperature+", maxdist="+max_swap_dist+")");
  75
  76             if (alldone) break;
  77
  78             congestion = routing.measureCongestion();
  79             timingpenalty = routing.measureTimingpenalty();
  80             double wirecost = routing.measureWireCost();
  81             int swaps = 0;
  82             num_moves = 200;
  83
  84             for(int i=0; i<num_moves; i++) {
  85                 System.out.print("\r  [place: " + i + "/" + num_moves + "  congestion="+congestion+"]");
  86                 NetList.Node node1 = fnl.randomNode(rand);
  87                 PhysicalDevice.PhysicalCell cell1 = placement.nodeToCell(node1);
  88                 PhysicalDevice.PhysicalCell cell2 = cell1.randomCellWithin(rand, max_swap_dist);
  89                 NetList.Node node2 = placement.cellToNode(cell2);
  90
  91                 // FIXME: cache and reuse "newrouting"
  92                 // also: fold down newrouting to collapse parentage
  93                 routing.checkpoint();
  94                 routing.unroute(node1);
  95                 routing.unroute(node2);
  96                 placement.unplace(cell1);
  97                 placement.unplace(cell2);
  98                 placement.place(node1, cell2);
  99                 placement.place(node2, cell1);
 100                 routing.routeAll();
 101
 102                 double newcongestion = routing.measureCongestion();
 103                 double newwirecost = routing.measureWireCost();
 104                 double newtimingpenalty = routing.measureTimingpenalty();
 105                 double lam = 0.1;
 106                 double deltaCost =
 107                     lam * ((newcongestion - congestion) / Math.max(0.001, congestion))
 108                     +
 109                     //(1-lam) * ((newwirecost - wirecost) / wirecost)
 110                     //+
 111                     (1-lam) * ((newtimingpenalty - timingpenalty) / Math.max(0.001, timingpenalty))
 112                     ;
 113                 double swapProbability = Math.exp((-1 * deltaCost) / temperature);
 114                 //double dist = Math.sqrt( (5-p2x)*(5-p2x) + (5-p2y)*(5-p2y) );
 115                 double rad = 4;
 116                 /*
 117                 if (rand2 == null)
 118                     swapProbability = Math.max(0, Math.min(swapProbability, dist / Math.sqrt(rad+rad)));
 119                 */
 120                 boolean doSwap = Math.random() < swapProbability;
 121                 if (doSwap) {
 122                     swaps++;
 123                     congestion = newcongestion;
 124                     wirecost = newwirecost;
 125                     timingpenalty = newtimingpenalty;
 126                 } else {
 127                     placement.unplace(cell1);
 128                     placement.unplace(cell2);
 129                     placement.place(node1, cell1);
 130                     placement.place(node2, cell2);
 131                     routing.rollback();
 132                 }
 133             }
 134             double acceptance = ((double)swaps) / num_moves;
 135             double gamma = 0;
 136             if (acceptance > 0.96) gamma = 0.5;
 137             else if (acceptance > 0.8) gamma = 0.9;
 138             else if (acceptance > 0.15) gamma = 0.95;
 139             else gamma = 0.8;
 140
 141             System.out.println("  acceptance="+acceptance);
 142             temperature = temperature * gamma;
 143             int num_routes = num_moves - swaps;
 144             num_routes = 2;
 145             for(int i=0; i<num_routes; i++) {
 146                 int overrouted = routing.measureOverloaded();
 147                 routing.unrouteOverloaded();
 148                 routing.reRouteAll();
 149                 System.out.print("\r  [route "+i+"/"+num_routes+"] overrouted="+overrouted+" congestion="+routing.measureCongestion()+"     penalty="+timingpenalty);
 150                 routing.updateCongestion(alphaParameter, betaParameter);
 151                 if (overrouted==0 && timingpenalty < 1) alldone = true;
 152             }
 153             num_moves = (int)(300 * gamma * gamma);
 154             vis.draw(placement, routing, false);
 155             System.out.println();
 156         }
 157         vis.draw(placement, routing, true);
 158         placement.setPlacement();
 159         routing.setPips(true);
 160         System.out.println("wire utilization: " + Math.round(routing.measureWireUtilization()*100));
 161
 162         // set up scan cell
 163         fpslic.cell(23,15).h(3, true);
 164         fpslic.cell(23,15).yi(L3);
 165         fpslic.cell(23,15).ylut(0xAA);
 166         fpslic.iob_right(15, true).enableOutput(WEST);
 167         fpslic.cell(23,0).ylut(0x00);
 168         fpslic.iob_right(0, true).enableOutput(WEST);
 169         fpslic.flush();
 170         /*
 171         int xwidth = 8;
 172         temperature = 0;
 173         while(temperature==0) {
 174             int a = Math.abs(rand.nextInt()) % (1 << xwidth);
 175             int b = Math.abs(rand.nextInt()) % (1 << xwidth);
 176             setInput(fnl, fpslic, "a",  a, placement);
 177             setInput(fnl, fpslic, "b",  b, placement);
 178             setInput(fnl, fpslic, "ci", 0, placement);
 179             int result = getOutput(fnl, fpslic, slipway, "out", placement);
 180             int expect = (a+b) & ~(-1 << (xwidth+1));
 181             System.out.println(Integer.toString(a,16) + " + " +
 182                                Integer.toString(b,16) + " = " +
 183                                Integer.toString(result,16) +
 184                                " [ " + (expect==result ? "ok" : "bad" ) + " ] " + (Integer.toString((result^(expect)),16)));
 185         }
 186         */
 187     }
 188     }
 189
 190
 191     private static int ret;
 192     public static synchronized int scan(final FpslicDevice device, final SlipwayBoard slipway, final FpslicDevice.Cell cell) {
 193         try {
 194             scan(device, cell, XLUT, true);
 195             slipway.readFpgaData(new SlipwayBoard.ByteCallback() {
 196                     public void call(byte b) throws Exception {
 197                         ret = b;
 198                         synchronized(device) {
 199                             device.notifyAll();
 200                         }
 201                     }
 202                 });
 203             synchronized(device) {
 204                 try {
 205                     device.wait();
 206                 } catch (Exception e) { throw new RuntimeException(e); }
 207             }
 208             scan(device, cell, XLUT, false);
 209             return ret;
 210         } catch (Exception e) { throw new RuntimeException(e); }
 211     }
 212
 213     public static void scan(FpslicDevice dev, FpslicDevice.Cell cell, int source, boolean setup) {
 214         if (setup) {
 215             //if (source != NONE) cell.c(source);
 216             if (cell.b()) cell.b(false);
 217             if (cell.f()) cell.f(false);
 218         }
 219         if (cell.out(L3)!=setup) cell.out(L3, setup);
 220         if (cell.vx(L3)!=setup) cell.v(L3, setup);
 221
 222         FpslicDevice.SectorWire sw = cell.vwire(L3);
 223         //System.out.println("wire is: " + sw);
 224
 225         if (sw.row > (12 & ~0x3) && sw.north()!=null && sw.north().drives(sw))
 226             sw.north().drives(sw, false);
 227         while(sw.row > (12 & ~0x3) && sw.south() != null) {
 228             //System.out.println(sw + " -> " + sw.south());
 229             if (sw.drives(sw.south())!=setup) sw.drives(sw.south(), setup);
 230             sw = sw.south();
 231         }
 232         if (sw.row < (12 & ~0x3) && sw.south() != null && sw.south().drives(sw))
 233             sw.north().drives(sw, false);
 234         while(sw.row < (12 & ~0x3) && sw.north() != null) {
 235             //System.out.println(sw + " -> " + sw.north());
 236             if (sw.drives(sw.north())!=setup) sw.drives(sw.north(), setup);
 237             sw = sw.north();
 238         }
 239
 240         //cell = dev.cell(19, 15);
 241         cell = dev.cell(cell.col, 15);
 242         /*
 243         System.out.println("cell is " + cell);
 244         cell.xlut(0xff);
 245         cell.ylut(0xff);
 246         cell.b(false);
 247         cell.f(false);
 248         cell.c(XLUT);
 249         cell.out(L3, true);
 250         cell.oe(NONE);
 251         */
 252         if (cell.hx(L3) != setup) cell.h(L3, setup);
 253         if (cell.vx(L3) != setup) cell.v(L3, setup);
 254         sw = cell.hwire(L3);
 255
 256         if (sw.west()!=null && sw.west().drives(sw)) { sw.west().drives(sw, false); }
 257         while(sw.east() != null) {
 258             //System.out.println(sw + " -> " + sw.east());
 259             if (sw.drives(sw.east())!=setup) sw.drives(sw.east(), setup);
 260             sw = sw.east();
 261         }
 262
 263     }
 264
 265     public static void setInput(NetList fnl, FpslicDevice fpslic, String prefix, int val, Placement placement) {
 266         for(int i=0; ; i++) {
 267             NetList.Node n = fnl.top.get(prefix + "["+i+"]");
 268             if (n==null && i==0) n = fnl.top.get(prefix);
 269             if (n==null) return;
 270             FpslicDevice.Cell c = ((PhysicalFpslic.PhysicalFpslicCell)placement.nodeToCell(n)).cell();
 271             c.c(XLUT);
 272             c.b(false);
 273             c.xlut((val & 0x1)==0 ? 0x00 : 0xff);
 274             val = val >> 1;
 275         }
 276     }
 277     public static int getOutput(NetList fnl, FpslicDevice fpslic, SlipwayBoard slipway, String prefix, Placement placement) {
 278             int val = 0;
 279             for(int i=0; ; i++) {
 280                 NetList.Node n = fnl.top.get(prefix+"["+i+"]");
 281                 if (n==null && i==0) n = fnl.top.get(prefix);
 282                 if (n==null) return val;
 283                 FpslicDevice.Cell c = ((PhysicalFpslic.PhysicalFpslicCell)placement.nodeToCell(n)).cell();
 284                 c.xlut(LUT_SELF);
 285                 c.c(XLUT);
 286                 c.b(false);
 287                 fpslic.flush();
 288                 int scan = scan(fpslic, slipway, c);
 289                 val |= ((scan==0 ? 0 : 1) << i);
 290             }
 291         }
 292
 293
 294 }