src/edu/berkeley/slipway/MPARDemo.java

   1 import com.atmel.fpslic.*;
   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 com.atmel.fpslic.*;
   8 import static com.atmel.fpslic.FpslicConstants.*;
   9
  10 // FIXME: sometimes gets stuck in a loop routing the last few nets
  11
  12 // FEATURE: ability to rip up only one branch of a multi-terminal net
  13
  14 // FEATURE: re-placement based on routing congestion
  15 //          note: must assign a cost to "bare wire" -- if not, the
  16 //          placer will fail to recognize moves that put blocks closer
  17 //          together, thereby decreasing the potential for future
  18 //          congestion.
  19
  20 // FEATURE: A* search (chap7 of independence thesis)
  21
  22 // FIXME: distinguish out,xo,yo
  23 // FIXME: y-axis shortcuts
  24 // FEATURE: ability to use a cell for routing purposes
  25 // FEATURE: global two-sector-long wires
  26
  27 public class MPARDemo {
  28
  29     public static final double alphaParameter = 00.9;
  30     public static final double betaParameter  = 02.5;
  31     public static final double gammaParameter =  1.0;
  32
  33     public static class FlatNetlist {
  34
  35         private HashMap<String,Integer> ids = new HashMap<String,Integer>();
  36
  37         public HashSet<Node> nodes = new HashSet<Node>();
  38         public HashSet<Net>  nets  = new HashSet<Net>();
  39
  40         /** a node is some primitive element; a potential configuration of a CLB */
  41         public class Node {
  42             public PhysicalDevice.PhysicalCell physicalCell = null;
  43             private final String type;
  44             private final int    id;
  45
  46             public int x = -1;
  47             public int y = -1;
  48
  49             private HashMap<String,Port> ports = new HashMap<String,Port>();
  50
  51             public Node(String type) {
  52                 nodes.add(this);
  53                 this.type = type.toLowerCase();
  54                 Integer num = ids.get(type);
  55                 this.id = num == null ? 0 : num.intValue();
  56                 ids.put(type, this.id+1);
  57             }
  58             public String getType() { return type; }
  59             public String toString() {
  60                 if (x==-1 || y==-1)
  61                     return type + "["+id+"]";
  62                 return type + "@("+x+","+y+")";
  63             }
  64             public Port getPort(String name, boolean driver) {
  65                 Port p = ports.get(name);
  66                 if (p==null) ports.put(name, p = new Port(name, driver));
  67                 return p;
  68             }
  69
  70             public Fpslic.Cell getPlacement(Fpslic fpslic) { return fpslic.cell(x, y); }
  71             public void place(Fpslic fpslic) {
  72                 Fpslic.Cell cell = fpslic.cell(x,y);
  73                 cell.c(XLUT);
  74                 cell.b(false);
  75                 cell.f(false);
  76                 cell.xi(NW);
  77                 cell.yi(EAST);
  78                 if      (type.equals("and2"))    cell.xlut(LUT_SELF & LUT_OTHER);
  79                 else if (type.equals("or2"))     cell.xlut(LUT_SELF | LUT_OTHER);
  80                 else if (type.equals("xor2"))    cell.xlut(LUT_SELF ^ LUT_OTHER);
  81                 else if (type.equals("buf"))     cell.xlut(LUT_SELF);
  82                 else if (type.equals("inv"))     cell.xlut(~LUT_SELF);
  83                 else if (type.equals("cell0"))   return;
  84             }
  85
  86             private int portIndex = 0;
  87
  88             /** a port is an input or output to a Node */
  89             public class Port {
  90                 private final String name;
  91                 private final boolean driver;
  92                 Net    net;
  93                 public final int index;
  94                 public Port(String name, boolean driver) {
  95                     this.name = name;
  96                     this.driver = driver;
  97                     this.index = driver ? 0 : portIndex++;
  98                 }
  99                 public String toString() { return Node.this + "." + name; }
 100                 public Node getNode() { return Node.this; }
 101                 public void connect(Port p) {
 102                     if (net != null)          { net.add(p);
 103                     } else if (p.net != null) { p.net.add(this);
 104                     } else {
 105                         new Net().add(this);
 106                         this.net.add(p);
 107                     }
 108                 }
 109                 public void route(Fpslic fpslic, Port[] dests, PhysicalDevice pd, FlatNetlist.Net owner) {
 110                     PhysicalDevice.PhysicalNet[] destsp = new PhysicalDevice.PhysicalNet[dests.length];
 111                     for(int i=0; i<dests.length; i++) {
 112                         Port dest = dests[i];
 113                         switch(dest.index) {
 114                             case 0: destsp[i] = dest.getNode().physicalCell.getNet("xi"); break;
 115                             case 1: destsp[i] = dest.getNode().physicalCell.getNet("yi"); break;
 116                             default: throw new Error();
 117                         }
 118                     }
 119                     //System.out.println(physicalCell.getNet("out"));
 120                     //System.out.println(destsp[0]);
 121                     pd.route(physicalCell.getNet("out"), destsp, owner);
 122
 123                     /*
 124                     Fpslic.Cell driverCell = fpslic.cell(getNode().x,getNode().y);
 125                     Fpslic.Cell destCell   = fpslic.cell(dest.getNode().x,dest.getNode().y);
 126                     boolean[] hblocked = new boolean[5];
 127                     boolean[] vblocked = new boolean[5];
 128                     hblocked[3] = true;
 129                     vblocked[3] = true;
 130                     int minx = Math.min(getNode().x, dest.getNode().x);
 131                     int miny = Math.min(getNode().y, dest.getNode().y);
 132                     int maxx = Math.max(getNode().x, dest.getNode().x);
 133                     int maxy = Math.max(getNode().y, dest.getNode().y);
 134                     for(int cx = 0; cx <= 3; cx++) {
 135                         Fpslic.Cell c = fpslic.cell(cx, getNode().y);
 136                         for(int i=0; i<5; i++)
 137                             hblocked[i] |= (c.hx(i) && !c.equals(driverCell));
 138                     }
 139                     for(int cy = 0; cy <= 3; cy++) {
 140                         Fpslic.Cell c = fpslic.cell(dest.getNode().x, cy);
 141                         for(int i=0; i<5; i++)
 142                             vblocked[i] |= (c.vx(i) && !c.equals(driverCell));
 143                     }
 144                     int free = 0;
 145                     for(; free < 5; free++) if (!hblocked[free]) break;
 146                     for(; free < 5; free++) if (!vblocked[free]) break;
 147                     if (free >= 5) throw new RuntimeException("unroutable!");
 148                     Fpslic.Cell turnCell = fpslic.cell(dest.getNode().x, getNode().y);
 149                     driverCell.out(free, true);
 150                     driverCell.h(free, true);
 151                     turnCell.h(free, true);
 152                     turnCell.v(free, true);
 153                     switch(dest.index) {
 154                         case 0: destCell.xi(L0 + free); break;
 155                         case 1: destCell.yi(L0 + free); break;
 156                         case 2: destCell.wi(L0 + free); break;
 157                         case 3: destCell.zi(L0 + free); break;
 158                         default: throw new RuntimeException("error");
 159                     }
 160                     destCell.v(free, true);
 161                     System.out.println("route " + this + " -> " + dest + " on planes " + free);
 162                     */
 163                 }
 164             }
 165         }
 166
 167         /** a Net is a collection of ports which are wired together */
 168         public class Net implements Iterable<Node.Port> {
 169             private Node.Port driver = null;
 170             private HashSet<Node.Port> ports = new HashSet<Node.Port>();
 171             public Net() { nets.add(this); }
 172             public Iterator<Node.Port> iterator() { return ports.iterator(); }
 173             public int getSize() { return ports.size(); }
 174             public HashSet<PhysicalDevice.PhysicalPip> pips = new HashSet<PhysicalDevice.PhysicalPip>();
 175             public HashSet<PhysicalDevice.PhysicalNet> pns = new HashSet<PhysicalDevice.PhysicalNet>();
 176             public boolean routed = false;
 177             public void unroute() {
 178                 for(PhysicalDevice.PhysicalPip pip : pips)
 179                     pip.set(false);
 180                 for(PhysicalDevice.PhysicalNet net : pns) {
 181                     net.owners.remove(this);
 182                     net.load--;
 183                 }
 184                 pips.clear();
 185                 pns.clear();
 186                 routed = false;
 187             }
 188             public void route(Fpslic fpslic, PhysicalDevice pd) {
 189                 if (driver == null) return;
 190                 if (routed) return;
 191                 //System.out.println();
 192                 //System.out.println("routing " + this);
 193                 Node.Port[] dests = new Node.Port[ports.size() - (ports.contains(driver) ? 1 : 0)];
 194                 int i = 0;
 195                 for(Node.Port p : ports)
 196                     if (p != driver)
 197                         dests[i++] = p;
 198                 driver.route(fpslic, dests, pd, this);
 199                 routed = true;
 200             }
 201             public void add(Node.Port p) {
 202                 if (p.driver) {
 203                     if (driver != null && driver != p)
 204                         throw new RuntimeException("two drivers on a port!\n  "+driver+"\n  "+p);
 205                     driver = p;
 206                 }
 207                 if (p.net==this || ports.contains(p)) return;
 208                 ports.add(p);
 209                 add(p.net);
 210                 p.net = this;
 211             }
 212             public void add(Net n) {
 213                 if (n==this || n==null) return;
 214                 for(Node.Port p : n) add(p);
 215                 nets.remove(n);
 216             }
 217             public String toString() {
 218                 StringBuffer ret = new StringBuffer();
 219                 ret.append(driver==null ? "()" : driver.toString());
 220                 ret.append(" -> ");
 221                 for(Node.Port p : this)
 222                     if (p!=driver)
 223                         ret.append(p+" ");
 224                 return ret.toString();
 225             }
 226         }
 227
 228
 229         public HashMap<EdifCellInstance,FlatNetlist.Node> cache =
 230             new HashMap<EdifCellInstance,FlatNetlist.Node>();
 231         public HashMap<String,FlatNetlist.Node> top =
 232             new HashMap<String,FlatNetlist.Node>();
 233
 234         public FlatNetlist.Node createNode(EdifCellInstance eci, String portName) {
 235             FlatNetlist.Node n = eci==null ? top.get(portName) : cache.get(eci);
 236             if (n != null) return n;
 237             if (eci==null) {
 238                 n = new FlatNetlist.Node("top_"+portName);
 239                 top.put(portName, n);
 240                 return n;
 241             } else {
 242                 n = new FlatNetlist.Node(eci.getType());
 243                 cache.put(eci,n);
 244             }
 245             for(EdifPortRef epr : eci.getAllEPRs()) {
 246                 EdifPort ep = epr.getPort();
 247                 EdifNet  en = epr.getNet();
 248                 String name = ep.getOldName();
 249                 boolean driver = ep.getDirection()==ep.OUT;
 250                 if (eci==null) driver = !driver;
 251                 if (eci==null) name = driver ? "out" : "xi";
 252                 FlatNetlist.Node.Port p = n.getPort(name, driver);
 253                 for(EdifPortRef epr2 : en.getConnectedPortRefs()) {
 254                     EdifCellInstance eci2 = epr2.getCellInstance();
 255                     EdifPort ep2 = epr2.getPort();
 256                     Node n2 = createNode(eci2, ep2.getOldName());
 257                     driver = ep2.getDirection()==ep.OUT;
 258                     name = ep2.getOldName();
 259                     if (eci2==null) driver = !driver;
 260                     if (eci2==null) name = driver ? "out" : "xi";
 261                     FlatNetlist.Node.Port p2 = n2.getPort(name, driver);
 262                     p.connect(p2);
 263                 }
 264             }
 265             return n;
 266         }
 267     }
 268
 269     /*
 270       test code for inter-sector switchboxes
 271     public static void main2() throws Exception {
 272         Fpslic fpslic = new FtdiBoard();
 273         // set up scan cell
 274         fpslic.cell(23,15).h(3, true);
 275         fpslic.cell(23,15).yi(L3);
 276         fpslic.cell(23,15).ylut(0xAA);
 277         fpslic.iob_right(15, true).enableOutput(WEST);
 278         fpslic.cell(23,0).ylut(0x00);
 279         fpslic.iob_right(0, true).enableOutput(WEST);
 280         fpslic.flush();
 281         for(int x=0; x<20; x++) {
 282             for(int y=0; y<20; y++) {
 283                 for(int l=0; l<5; l++) {
 284                     for(int v = 0; v <= 1; v++) {
 285                         boolean vert = v==1;
 286                         int newx = vert ? x   : x-1;
 287                         int newy = vert ? y-1 : y;
 288                         if (newx<0 || newy<0) continue;
 289                         if (vert  && (y%4) != 0) continue;
 290                         if (!vert && (x%4) != 0) continue;
 291
 292                         int layer = l;
 293                         if (layer==3) continue;
 294                         Fpslic.Cell c  = fpslic.cell(x, y);
 295                         Fpslic.Cell c2 = fpslic.cell(newx, newy);
 296                         Fpslic.SectorWire sw1 = vert ? c.vwire(layer)  : c.hwire(layer);
 297                         Fpslic.SectorWire sw2 = vert ? c2.vwire(layer) : c2.hwire(layer);
 298                         sw1.drives(sw2, true);
 299
 300                         c.c(YLUT);
 301                         if (vert) c.v(L0 + layer, true);
 302                         else      c.h(L0 + layer, true);
 303                         c.out(L0 + layer, true);
 304                         c.b(false);
 305
 306                         c2.yi(L0 + layer);
 307                         if (vert) c2.v(L0 + layer, true);
 308                         else      c2.h(L0 + layer, true);
 309                         c2.ylut(LUT_SELF);
 310                         c2.c(YLUT);
 311                         c2.b(false);
 312
 313                         System.out.print(x+","+y+","+l+","+(vert?"v":"h")+": ");
 314                         c.ylut(0x00);
 315                         fpslic.flush();
 316                         boolean good = scan(fpslic, c2)==0;
 317                         if (!good) fails++;
 318                         System.out.print(good ? "ok " : "bad ");
 319                         c.ylut(0xff);
 320                         fpslic.flush();
 321                         good = scan(fpslic, c2)!=0;
 322                         if (!good) fails++;
 323                         System.out.print(good ? "ok " : "bad ");
 324                         System.out.println();
 325                         sw1.drives(sw2, false);
 326                         if (vert) c.v(layer, false);
 327                         else      c.h(layer, false);
 328                         c.out(layer, false);
 329                     }
 330                 }
 331             }
 332         }
 333         System.out.println("fails = " + fails);
 334
 335     }
 336     public static int fails = 0;
 337     */
 338
 339     public static void main(String[] s) throws Exception {
 340         EdifEnvironment topEnv = new EdifEnvironment("top");
 341         EdifLibraryManager elm = new EdifLibraryManager(topEnv);
 342         EdifLibrary initLib = new EdifLibrary(elm, "initLib");
 343         EdifEnvironment env = EdifMergeParser.parseAndMerge(s, initLib);
 344         System.out.println("top is " + env.getTopCell());
 345         FlatNetlist fnl = new FlatNetlist();
 346
 347         for(Iterator<EdifCellInstance> it = (Iterator<EdifCellInstance>)env.getTopCell().cellInstanceIterator();
 348             it.hasNext();
 349             ) {
 350             FlatNetlist.Node n = fnl.createNode(it.next(), null);
 351         }
 352
 353         Fpslic fpslic = new FtdiBoard();
 354         PhysicalDevice pd = new PhysicalDevice(fpslic, 20, 20);
 355
 356         int px = 0;
 357         int py = 0;
 358
 359         // crude map
 360         Random rand = new Random();
 361         boolean[][] used = new boolean[pd.width][pd.height];
 362         for(FlatNetlist.Node n : fnl.nodes) {
 363             while(true) {
 364                 px = Math.abs(rand.nextInt()) % pd.width;
 365                 py = Math.abs(rand.nextInt()) % pd.height;
 366                 if (!used[px][py]) {
 367                     used[px][py] = true;
 368                     n.x = px;
 369                     n.y = py;
 370                     n.physicalCell = pd.getCell(px, py);
 371                     System.out.println("placed " + n + " at ("+px+","+py+")");
 372                     n.place(fpslic);
 373                     break;
 374                 }
 375             }
 376         }
 377
 378         int trial = 0;
 379         HashSet<FlatNetlist.Net> needUnroute = new HashSet<FlatNetlist.Net>();
 380         while(true) {
 381             System.out.println();
 382             System.out.println("routing trial " + (++trial));
 383             for(FlatNetlist.Net net : fnl.nets) {
 384                 if (net.getSize() <= 1) continue;
 385                 net.route(fpslic, pd);
 386             }
 387             double congestion = 0;
 388             int overrouted = 0;
 389             needUnroute.clear();
 390             for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets) {
 391                 if (pn.load > 1) {
 392                     //System.out.println("overrouted: " + pn + ", congestion="+pn.congestion + ", load=" + pn.load);
 393                     overrouted++;
 394                     congestion += pn.congestion;
 395                 }
 396                 pn.congestion = pn.congestion * alphaParameter;
 397                 if (pn.load > 1) {
 398                     pn.congestion += betaParameter;
 399                     // don't do this here
 400                     //pn.congestion += betaParameter;
 401                     for(FlatNetlist.Net n : pn.owners)
 402                         needUnroute.add(n);
 403                 }
 404             }
 405             System.out.println("  overrouted="+overrouted+", congestion="+congestion +", ripping up " + needUnroute.size() +" nets of " + fnl.nets.size());
 406             if (overrouted <= 0) break;
 407             //for(FlatNetlist.Net net : fnl.nets)
 408             for(FlatNetlist.Net net : needUnroute)
 409                 net.unroute();
 410             /*
 411             for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets)
 412                 for(PhysicalDevice.PhysicalPip pip : pn) {
 413                     pip.set(false);
 414                 }
 415             */
 416         }
 417
 418         // set up scan cell
 419         fpslic.cell(23,15).h(3, true);
 420         fpslic.cell(23,15).yi(L3);
 421         fpslic.cell(23,15).ylut(0xAA);
 422         fpslic.iob_right(15, true).enableOutput(WEST);
 423         fpslic.cell(23,0).ylut(0x00);
 424         fpslic.iob_right(0, true).enableOutput(WEST);
 425         fpslic.flush();
 426
 427         int width = 8;
 428         while(true) {
 429             int a = Math.abs(rand.nextInt()) % (1 << width);
 430             int b = Math.abs(rand.nextInt()) % (1 << width);
 431             setInput(fnl, fpslic, "a",  a);
 432             setInput(fnl, fpslic, "b",  b);
 433             setInput(fnl, fpslic, "ci", 0);
 434             int result = getOutput(fnl, fpslic, "out");
 435             System.out.println(Integer.toString(a,16) + " + " +
 436                                Integer.toString(b,16) + " = " +
 437                                Integer.toString(result,16) +
 438                                " [ " + (a+b==result ? "ok" : "bad" ) + " ] ");
 439         }
 440     }
 441
 442     public static class PhysicalDevice {
 443         private final Fpslic fpslic;
 444
 445         public final int width;
 446         public final int height;
 447         private final PhysicalNet[][][][] sectorWires;
 448         private final PhysicalCell[][] cells;
 449
 450         public PhysicalCell getCell(int col, int row) {
 451             if (col<0) return null;
 452             if (row<0) return null;
 453             if (col>=width) return null;
 454             if (row>=height) return null;
 455             return cells[col][row];
 456         }
 457
 458         public PhysicalDevice(final Fpslic fpslic, int width, int height) {
 459             this.fpslic = fpslic;
 460             this.width = width;
 461             this.height = height;
 462             sectorWires = new PhysicalNet[width][height][5][2];
 463             for(int x=0; x<width; x+=4)
 464                 for(int y=0; y<height; y+=4)
 465                     for(int p=0; p<5; p++) {
 466                         for(int xc=x; xc<x+4; xc++) {
 467                             PhysicalNet vwire = new PhysicalNet("("+xc+","+y+"-"+(y+3)+")");
 468                             for(int yc=y; yc<y+4; yc++)
 469                                 sectorWires[xc][yc][p][0] = vwire;
 470                         }
 471                         for(int yc=y; yc<y+4; yc++) {
 472                             PhysicalNet hwire = new PhysicalNet("("+x+"-"+(x+3)+","+yc+")");
 473                             for(int xc=x; xc<x+4; xc++)
 474                                 sectorWires[xc][yc][p][1] = hwire;
 475                         }
 476                     }
 477
 478             for(int x=4; x<width; x+=4) {
 479                 for(int y=0; y<height; y++) {
 480                     for(int p=0; p<5; p++) {
 481                         final int xc = x;
 482                         final int yc = y;
 483                         final int pc = p;
 484                         new PhysicalPip("xxx",
 485                                         sectorWires[x-1][y][p][1],
 486                                         new PhysicalNet[] { sectorWires[x][y][p][1] },
 487                                         5) {
 488                             public void set(boolean connected) {
 489                                 fpslic.cell(xc-1, yc).hwire(pc).drives(fpslic.cell(xc, yc).hwire(pc), connected);
 490                             }
 491                         };
 492                         new PhysicalPip("xxx",
 493                                         sectorWires[x][y][p][1],
 494                                         new PhysicalNet[] { sectorWires[x-1][y][p][1] },
 495                                         5) {
 496                             public void set(boolean connected) {
 497                                 fpslic.cell(xc, yc).hwire(pc).drives(fpslic.cell(xc-1, yc).hwire(pc), connected);
 498                             }
 499                         };
 500                     }
 501                 }
 502             }
 503
 504             for(int x=0; x<width; x++) {
 505                 for(int y=4; y<height; y+=4) {
 506                     for(int p=0; p<5; p++) {
 507                         final int xc = x;
 508                         final int yc = y;
 509                         final int pc = p;
 510                         new PhysicalPip("xxx",
 511                                         sectorWires[x][y-1][p][0],
 512                                         new PhysicalNet[] { sectorWires[x][y][p][0] },
 513                                         5) {
 514                             public void set(boolean connected) {
 515                                 fpslic.cell(xc, yc-1).vwire(pc).drives(fpslic.cell(xc, yc).vwire(pc), connected);
 516                             }
 517                         };
 518                         new PhysicalPip("xxx",
 519                                         sectorWires[x][y][p][0],
 520                                         new PhysicalNet[] { sectorWires[x][y-1][p][0] },
 521                                         5) {
 522                             public void set(boolean connected) {
 523                                 fpslic.cell(xc, yc).vwire(pc).drives(fpslic.cell(xc, yc-1).vwire(pc), connected);
 524                             }
 525                         };
 526                     }
 527                 }
 528             }
 529
 530             cells = new PhysicalCell[width][height];
 531             for(int x=0; x<width; x++)
 532                 for(int y=0; y<height; y++) {
 533                     cells[x][y] = new PhysicalCell(x, y);
 534                 }
 535             for(int x=0; x<width; x++)
 536                 for(int y=0; y<height; y++)
 537                     cells[x][y].link();
 538         }
 539
 540         private PhysicalNet getSectorWire(int col, int row, int plane, boolean horizontal) {
 541             return sectorWires[col][row][plane][horizontal ? 1 : 0];
 542         }
 543
 544         public class PhysicalCell {
 545
 546             public PhysicalNet getNet(String name) {
 547                 if (name.equals("out")) return outputNet;
 548                 if (name.equals("xi"))  return xin;
 549                 if (name.equals("yi"))  return yin;
 550                 throw new RuntimeException("unknown");
 551             }
 552
 553             private int col;
 554             private int row;
 555             private PhysicalNet   outputNet;
 556             private PhysicalNet   xin;
 557             private PhysicalNet   yin;
 558             private PhysicalNet[] local = new PhysicalNet[5];
 559
 560             private Fpslic.Cell cell() { return fpslic.cell(col, row); }
 561
 562             public void setFunction(String type) {
 563                 Fpslic.Cell cell = cell();
 564                 cell.c(XLUT);
 565                 cell.xo(false);
 566                 cell.b(false);
 567                 cell.f(false);
 568                 if      (type.equals("and2"))    cell.xlut(LUT_SELF & LUT_OTHER);
 569                 else if (type.equals("or2"))     cell.xlut(LUT_SELF | LUT_OTHER);
 570                 else if (type.equals("xor2"))    cell.xlut(LUT_SELF ^ LUT_OTHER);
 571                 else if (type.equals("buf"))     cell.xlut(LUT_SELF);
 572                 else if (type.equals("inv"))     cell.xlut(~LUT_SELF);
 573             }
 574
 575             public void link() {
 576                 // FIXME wow, this is a horrendous hack!
 577                 if (getCell(col-1, row+1) != null)
 578                     new PhysicalPip(this+".xiNW", getCell(col-1, row+1).getNet("out"), new PhysicalNet[] { xin }, 5) {
 579                         public void set(boolean connected) { cell().xi(connected ? NW : NONE); }
 580                     };
 581                 if (getCell(col-1, row-1) != null)
 582                     new PhysicalPip(this+".xiSW", getCell(col-1, row-1).getNet("out"), new PhysicalNet[] { xin }, 5) {
 583                         public void set(boolean connected) { cell().xi(connected ? SW : NONE); }
 584                     };
 585                 if (getCell(col+1, row+1) != null)
 586                     new PhysicalPip(this+".xiNE", getCell(col+1, row+1).getNet("out"), new PhysicalNet[] { xin }, 5) {
 587                         public void set(boolean connected) { cell().xi(connected ? NE : NONE); }
 588                     };
 589                 if (getCell(col+1, row-1) != null)
 590                     new PhysicalPip(this+".xiSE", getCell(col+1, row-1).getNet("out"), new PhysicalNet[] { xin }, 5) {
 591                         public void set(boolean connected) { cell().xi(connected ? SE : NONE); }
 592                     };
 593             }
 594
 595             private PhysicalCell(int col, int row) {
 596                 this.row = row;
 597                 this.col = col;
 598                 outputNet = new PhysicalNet(this.toString()+".out");
 599                 xin       = new PhysicalNet(this.toString()+".xi");
 600                 yin       = new PhysicalNet(this.toString()+".yi");
 601                 for(int j=0; j<5; j++) {
 602
 603                     // plane 3 is reserved for debugging
 604                     if (j==3) continue;
 605
 606                     final int i = j;
 607                     local[i] = new PhysicalNet(this.toString()+".L"+i);
 608                     new PhysicalPip(this+".h"+i,  null,      new PhysicalNet[] { local[i], getSectorWire(col, row, i, true) }) {
 609                         public void set(boolean connected) { cell().h(i, connected); }
 610                     };
 611                     new PhysicalPip(this+".v"+i,  null,      new PhysicalNet[] { local[i], getSectorWire(col, row, i, false) }) {
 612                         public void set(boolean connected) { cell().v(i, connected); }
 613                     };
 614                     new PhysicalPip(this+".xi"+i, local[i],  new PhysicalNet[] { xin }) {
 615                         public void set(boolean connected) { cell().xi(connected ? i : NONE); }
 616                     };
 617                     new PhysicalPip(this+".yi"+i, local[i],  new PhysicalNet[] { yin }) {
 618                         public void set(boolean connected) { cell().yi(connected ? i : NONE); }
 619                     };
 620                     new PhysicalPip(this+".o"+i,  outputNet, new PhysicalNet[] { local[i] }) {
 621                         public void set(boolean connected) { cell().out(i, connected); }
 622                     };
 623                 }
 624             }
 625             public  String toString() { return "cell@("+col+","+row+")"; }
 626
 627         }
 628
 629         public void route(PhysicalNet source, PhysicalNet[] dests, FlatNetlist.Net owner) {
 630             HashSet<PhysicalNet> remainingDests = new HashSet<PhysicalNet>();
 631             for(PhysicalNet dest : dests) remainingDests.add(dest);
 632
 633             HashSet<PhysicalNet> needsReset = new HashSet<PhysicalNet>();
 634             PriorityQueue<PhysicalNet> pq = new PriorityQueue<PhysicalNet>();
 635             needsReset.add(source);
 636             source.distance = 0;
 637             pq.add(source);
 638
 639             OUTER: while(true) {
 640                 PhysicalNet pn = pq.poll();
 641                 if (pn==null) throw new Error("unroutable! " + source + " -> " + dests[0]);
 642                 double frontier = pn.distance;
 643                 for(PhysicalPip pip : pn)
 644                     for(PhysicalNet net : pip.getDrivenNets()) {
 645                         double newfrontier = frontier + 0.05 + net.congestion;
 646
 647                         // penalty for using any net already routed in this iteration (makes routing order-sensitive)
 648                         if (net.load >= 1) newfrontier = newfrontier + 20;
 649
 650                         if (net.distance <= newfrontier) continue;
 651                         pq.remove(net);  // if already in there
 652                         net.distance = newfrontier;
 653                         pq.add(net);
 654                         needsReset.add(net);
 655                         net.backpointer = pn;
 656                         if (remainingDests.contains(net)) {
 657                             remainingDests.remove(net);
 658                             if (remainingDests.size()==0) break OUTER;
 659
 660                             // Vaughn Betz style multiterminal routing: once we reach one sink, make every node on the path
 661                             // "distance zero" from the source.
 662                             for(PhysicalNet pnx = net; pnx != null; pnx = pnx.backpointer) {
 663                                 //pnx.distance = 0;
 664                                 pq.add(pnx);
 665                             }
 666                             break;
 667                         }
 668                     }
 669             }
 670
 671             for(PhysicalNet dest : dests) {
 672                 PhysicalNet pn = dest;
 673                 while(pn != null && pn.backpointer != null) {
 674                     pn.owners.add(owner);
 675                     owner.pns.add(pn);
 676                     if (pn.distance != Double.MAX_VALUE) {
 677                         pn.distance = Double.MAX_VALUE;
 678                         pn.load++;
 679                         if (pn.load>=2) pn.congestion += betaParameter;
 680                     }
 681                     PhysicalPip pip = pn.getPipFrom(pn.backpointer);
 682                     pip.set(true);
 683                     owner.pips.add(pip);
 684                     pn = pn.backpointer;
 685                 }
 686                 // FIXME: check pn==source at this point
 687             }
 688
 689             for(PhysicalNet pn : needsReset) {
 690                 pn.distance    = Double.MAX_VALUE;
 691                 pn.backpointer = null;
 692             }
 693         }
 694         public HashSet<PhysicalNet> allPhysicalNets = new HashSet<PhysicalNet>();
 695         public class PhysicalNet implements Iterable<PhysicalPip>, Comparable<PhysicalNet> {
 696             public double      congestion = 0;
 697             public int         load = 0;
 698             public double      distance = Double.MAX_VALUE;
 699             public PhysicalNet backpointer = null;
 700
 701             public int compareTo(PhysicalNet pn) {
 702                 double x = distance - pn.distance;
 703                 return distance > pn.distance
 704                     ? 1
 705                     : distance < pn.distance
 706                     ? -1
 707                     : 0;
 708             }
 709
 710             private final HashSet<PhysicalPip> pips = new HashSet<PhysicalPip>();
 711             public Iterator<PhysicalPip> iterator() { return pips.iterator(); }
 712             private String name;
 713             public PhysicalNet(String name) {
 714                 this.name = name;
 715                 allPhysicalNets.add(this);
 716             }
 717             public String toString() { return name; }
 718             private void addPip(PhysicalPip pip) { pips.add(pip); }
 719             public PhysicalPip getPipFrom(PhysicalNet pn) {
 720                 for(PhysicalPip pip : pn)
 721                     for(PhysicalNet pn2 : pip.getDrivenNets())
 722                         if (pn2==this)
 723                             return pip;
 724                 return null;
 725             }
 726             public HashSet<FlatNetlist.Net> owners = new HashSet<FlatNetlist.Net>();
 727         }
 728
 729         public abstract class PhysicalPip {
 730             private PhysicalNet   driver;
 731             private PhysicalNet[] driven;
 732             private String name;
 733             private int defaultCost;
 734             public String toString() { return name; }
 735             public PhysicalNet   getDriverNet()  { return driver; }
 736             public PhysicalNet[] getDrivenNets() { return driven; }
 737             public int           getCost(PhysicalNet in, PhysicalNet out) { return defaultCost; }
 738             public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven) { this(name, driver, driven, 100); }
 739             public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven, int defaultCost) {
 740                 this.name = name;
 741                 this.driver = driver;
 742                 this.driven = driven;
 743                 this.defaultCost = defaultCost;
 744                 if (driver != null) driver.addPip(this);
 745                 for(PhysicalNet pn : driven) pn.addPip(this);
 746             }
 747             public abstract void set(boolean connected);
 748         }
 749
 750     }
 751
 752     private static int ret;
 753     public static synchronized int scan(final Fpslic device, final Fpslic.Cell cell) {
 754         try {
 755             scan(device, cell, YLUT, true);
 756             ((FtdiBoard)device).readBus(new FtdiBoard.ByteCallback() {
 757                     public void call(byte b) throws Exception {
 758                         ret = b;
 759                         synchronized(device) {
 760                             device.notifyAll();
 761                         }
 762                     }
 763                 });
 764             synchronized(device) {
 765                 try {
 766                     device.wait();
 767                 } catch (Exception e) { throw new RuntimeException(e); }
 768             }
 769             scan(device, cell, YLUT, false);
 770             return ret;
 771         } catch (Exception e) { throw new RuntimeException(e); }
 772     }
 773
 774     public static void scan(Fpslic dev, Fpslic.Cell cell, int source, boolean setup) {
 775         if (setup) {
 776             //if (source != NONE) cell.c(source);
 777             if (cell.b()) cell.b(false);
 778             if (cell.f()) cell.f(false);
 779         }
 780         if (cell.out(L3)!=setup) cell.out(L3, setup);
 781         if (cell.vx(L3)!=setup) cell.v(L3, setup);
 782
 783         Fpslic.SectorWire sw = cell.vwire(L3);
 784         //System.out.println("wire is: " + sw);
 785
 786         if (sw.row > (12 & ~0x3) && sw.north()!=null && sw.north().drives(sw))
 787             sw.north().drives(sw, false);
 788         while(sw.row > (12 & ~0x3) && sw.south() != null) {
 789             //System.out.println(sw + " -> " + sw.south());
 790             if (sw.drives(sw.south())!=setup) sw.drives(sw.south(), setup);
 791             sw = sw.south();
 792         }
 793         if (sw.row < (12 & ~0x3) && sw.south() != null && sw.south().drives(sw))
 794             sw.north().drives(sw, false);
 795         while(sw.row < (12 & ~0x3) && sw.north() != null) {
 796             //System.out.println(sw + " -> " + sw.north());
 797             if (sw.drives(sw.north())!=setup) sw.drives(sw.north(), setup);
 798             sw = sw.north();
 799         }
 800
 801         //cell = dev.cell(19, 15);
 802         cell = dev.cell(cell.col, 15);
 803         /*
 804         System.out.println("cell is " + cell);
 805         cell.xlut(0xff);
 806         cell.ylut(0xff);
 807         cell.b(false);
 808         cell.f(false);
 809         cell.c(XLUT);
 810         cell.out(L3, true);
 811         cell.oe(NONE);
 812         */
 813         if (cell.hx(L3) != setup) cell.h(L3, setup);
 814         if (cell.vx(L3) != setup) cell.v(L3, setup);
 815         sw = cell.hwire(L3);
 816
 817         if (sw.west()!=null && sw.west().drives(sw)) { sw.west().drives(sw, false); }
 818         while(sw.east() != null) {
 819             //System.out.println(sw + " -> " + sw.east());
 820             if (sw.drives(sw.east())!=setup) sw.drives(sw.east(), setup);
 821             sw = sw.east();
 822         }
 823
 824     }
 825
 826         public static void setInput(FlatNetlist fnl, Fpslic fpslic, String prefix, int val) {
 827             for(int i=0; ; i++) {
 828                 FlatNetlist.Node n = fnl.top.get(prefix + "["+i+"]");
 829                 if (n==null && i==0) n = fnl.top.get(prefix);
 830                 if (n==null) return;
 831                 Fpslic.Cell c = n.getPlacement(fpslic);
 832                 c.c(XLUT);
 833                 c.b(false);
 834                 c.xlut((val & 0x1)==0 ? 0x00 : 0xff);
 835                 val = val >> 1;
 836             }
 837         }
 838         public static int getOutput(FlatNetlist fnl, Fpslic fpslic, String prefix) {
 839             int val = 0;
 840             for(int i=0; ; i++) {
 841                 FlatNetlist.Node n = fnl.top.get(prefix+"["+i+"]");
 842                 if (n==null && i==0) n = fnl.top.get(prefix);
 843                 if (n==null) return val;
 844                 Fpslic.Cell c = n.getPlacement(fpslic);
 845                 c.xlut(LUT_SELF);
 846                 c.c(XLUT);
 847                 c.b(false);
 848                 fpslic.flush();
 849                 int scan = scan(fpslic, c);
 850                 val |= ((scan==0 ? 0 : 1) << i);
 851             }
 852         }
 853
 854
 855 }