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