src/edu/berkeley/slipway/mpar/PhysicalDevice.java

   1 package edu.berkeley.slipway.mpar;
   2 import com.atmel.fpslic.*;
   3 import byucc.edif.tools.merge.*;
   4 import byucc.edif.*;
   5 import java.io.*;
   6 import java.util.*;
   7 import edu.berkeley.slipway.*;
   8 import com.atmel.fpslic.*;
   9 import static com.atmel.fpslic.FpslicConstants.*;
  10 import static edu.berkeley.slipway.mpar.MPARDemo.*;
  11
  12 public class PhysicalDevice {
  13     private final Fpslic fpslic;
  14
  15     public final int width;
  16     public final int height;
  17     private final PhysicalNet[][][][] sectorWires;
  18     private final PhysicalCell[][] cells;
  19
  20     public PhysicalCell getCell(int col, int row) {
  21         if (col<0) return null;
  22         if (row<0) return null;
  23         if (col>=width) return null;
  24         if (row>=height) return null;
  25         return cells[col][row];
  26     }
  27
  28     public PhysicalDevice(final Fpslic fpslic, int width, int height) {
  29         this.fpslic = fpslic;
  30         this.width = width;
  31         this.height = height;
  32         sectorWires = new PhysicalNet[width][height][5][2];
  33         for(int x=0; x<width; x+=4)
  34             for(int y=0; y<height; y+=4)
  35                 for(int p=0; p<5; p++) {
  36                     for(int xc=x; xc<x+4; xc++) {
  37                         PhysicalNet vwire = new PhysicalNet("("+xc+","+y+"-"+(y+3)+")");
  38                         for(int yc=y; yc<y+4; yc++)
  39                             sectorWires[xc][yc][p][0] = vwire;
  40                     }
  41                     for(int yc=y; yc<y+4; yc++) {
  42                         PhysicalNet hwire = new PhysicalNet("("+x+"-"+(x+3)+","+yc+")");
  43                         for(int xc=x; xc<x+4; xc++)
  44                             sectorWires[xc][yc][p][1] = hwire;
  45                     }
  46                 }
  47
  48         for(int x=4; x<width; x+=4) {
  49             for(int y=0; y<height; y++) {
  50                 for(int p=0; p<5; p++) {
  51                     final int xc = x;
  52                     final int yc = y;
  53                     final int pc = p;
  54                     new PhysicalPip("xxx",
  55                                     sectorWires[x-1][y][p][1],
  56                                     new PhysicalNet[] { sectorWires[x][y][p][1] },
  57                                     5) {
  58                         public void set(boolean connected) {
  59                             fpslic.cell(xc-1, yc).hwire(pc).drives(fpslic.cell(xc, yc).hwire(pc), connected);
  60                         }
  61                     };
  62                     new PhysicalPip("xxx",
  63                                     sectorWires[x][y][p][1],
  64                                     new PhysicalNet[] { sectorWires[x-1][y][p][1] },
  65                                     5) {
  66                         public void set(boolean connected) {
  67                             fpslic.cell(xc, yc).hwire(pc).drives(fpslic.cell(xc-1, yc).hwire(pc), connected);
  68                         }
  69                     };
  70                 }
  71             }
  72         }
  73
  74         for(int x=0; x<width; x++) {
  75             for(int y=4; y<height; y+=4) {
  76                 for(int p=0; p<5; p++) {
  77                     final int xc = x;
  78                     final int yc = y;
  79                     final int pc = p;
  80                     new PhysicalPip("xxx",
  81                                     sectorWires[x][y-1][p][0],
  82                                     new PhysicalNet[] { sectorWires[x][y][p][0] },
  83                                     5) {
  84                         public void set(boolean connected) {
  85                             fpslic.cell(xc, yc-1).vwire(pc).drives(fpslic.cell(xc, yc).vwire(pc), connected);
  86                         }
  87                     };
  88                     new PhysicalPip("xxx",
  89                                     sectorWires[x][y][p][0],
  90                                     new PhysicalNet[] { sectorWires[x][y-1][p][0] },
  91                                     5) {
  92                         public void set(boolean connected) {
  93                             fpslic.cell(xc, yc).vwire(pc).drives(fpslic.cell(xc, yc-1).vwire(pc), connected);
  94                         }
  95                     };
  96                 }
  97             }
  98         }
  99
 100         cells = new PhysicalCell[width][height];
 101         for(int x=0; x<width; x++)
 102             for(int y=0; y<height; y++) {
 103                 cells[x][y] = new PhysicalCell(x, y);
 104             }
 105         for(int x=0; x<width; x++)
 106             for(int y=0; y<height; y++)
 107                 cells[x][y].link();
 108     }
 109
 110     private PhysicalNet getSectorWire(int col, int row, int plane, boolean horizontal) {
 111         return sectorWires[col][row][plane][horizontal ? 1 : 0];
 112     }
 113
 114     public class PhysicalCell {
 115
 116         public PhysicalNet getNet(String name) {
 117             if (name.equals("out")) return outputNet;
 118             if (name.equals("xi"))  return xin;
 119             if (name.equals("yi"))  return yin;
 120             throw new RuntimeException("unknown");
 121         }
 122
 123         private int col;
 124         private int row;
 125         private PhysicalNet   outputNet;
 126         private PhysicalNet   xin;
 127         private PhysicalNet   yin;
 128         private PhysicalNet[] local = new PhysicalNet[5];
 129
 130         private Fpslic.Cell cell() { return fpslic.cell(col, row); }
 131
 132         public void setFunction(String type) {
 133             Fpslic.Cell cell = cell();
 134             cell.c(XLUT);
 135             cell.xo(false);
 136             cell.b(false);
 137             cell.f(false);
 138             if      (type.equals("and2"))    cell.xlut(LUT_SELF & LUT_OTHER);
 139             else if (type.equals("or2"))     cell.xlut(LUT_SELF | LUT_OTHER);
 140             else if (type.equals("xor2"))    cell.xlut(LUT_SELF ^ LUT_OTHER);
 141             else if (type.equals("buf"))     cell.xlut(LUT_SELF);
 142             else if (type.equals("inv"))     cell.xlut(~LUT_SELF);
 143         }
 144
 145         public void link() {
 146             // FIXME wow, this is a horrendous hack!
 147             if (getCell(col-1, row+1) != null)
 148                 new PhysicalPip(this+".xiNW", getCell(col-1, row+1).getNet("out"), new PhysicalNet[] { xin }, 5) {
 149                     public void set(boolean connected) { cell().xi(connected ? NW : NONE); }
 150                 };
 151             if (getCell(col-1, row-1) != null)
 152                 new PhysicalPip(this+".xiSW", getCell(col-1, row-1).getNet("out"), new PhysicalNet[] { xin }, 5) {
 153                     public void set(boolean connected) { cell().xi(connected ? SW : NONE); }
 154                 };
 155             if (getCell(col+1, row+1) != null)
 156                 new PhysicalPip(this+".xiNE", getCell(col+1, row+1).getNet("out"), new PhysicalNet[] { xin }, 5) {
 157                     public void set(boolean connected) { cell().xi(connected ? NE : NONE); }
 158                 };
 159             if (getCell(col+1, row-1) != null)
 160                 new PhysicalPip(this+".xiSE", getCell(col+1, row-1).getNet("out"), new PhysicalNet[] { xin }, 5) {
 161                     public void set(boolean connected) { cell().xi(connected ? SE : NONE); }
 162                 };
 163         }
 164
 165         private PhysicalCell(int col, int row) {
 166             this.row = row;
 167             this.col = col;
 168             outputNet = new PhysicalNet(this.toString()+".out");
 169             xin       = new PhysicalNet(this.toString()+".xi");
 170             yin       = new PhysicalNet(this.toString()+".yi");
 171             for(int j=0; j<5; j++) {
 172
 173                 // plane 3 is reserved for debugging
 174                 if (j==3) continue;
 175
 176                 final int i = j;
 177                 local[i] = new PhysicalNet(this.toString()+".L"+i);
 178                 new PhysicalPip(this+".h"+i,  null,      new PhysicalNet[] { local[i], getSectorWire(col, row, i, true) }) {
 179                     public void set(boolean connected) { cell().h(i, connected); }
 180                 };
 181                 new PhysicalPip(this+".v"+i,  null,      new PhysicalNet[] { local[i], getSectorWire(col, row, i, false) }) {
 182                     public void set(boolean connected) { cell().v(i, connected); }
 183                 };
 184                 new PhysicalPip(this+".xi"+i, local[i],  new PhysicalNet[] { xin }) {
 185                     public void set(boolean connected) { cell().xi(connected ? i : NONE); }
 186                 };
 187                 new PhysicalPip(this+".yi"+i, local[i],  new PhysicalNet[] { yin }) {
 188                     public void set(boolean connected) { cell().yi(connected ? i : NONE); }
 189                 };
 190                 new PhysicalPip(this+".o"+i,  outputNet, new PhysicalNet[] { local[i] }) {
 191                     public void set(boolean connected) { cell().out(i, connected); }
 192                 };
 193             }
 194         }
 195         public  String toString() { return "cell@("+col+","+row+")"; }
 196
 197     }
 198
 199     public void route(PhysicalNet source, PhysicalNet[] dests, FlatNetlist.Net owner) {
 200         HashSet<PhysicalNet> remainingDests = new HashSet<PhysicalNet>();
 201         for(PhysicalNet dest : dests) remainingDests.add(dest);
 202
 203         HashSet<PhysicalNet> needsReset = new HashSet<PhysicalNet>();
 204         PriorityQueue<PhysicalNet> pq = new PriorityQueue<PhysicalNet>();
 205         needsReset.add(source);
 206         source.distance = 0;
 207         pq.add(source);
 208
 209         OUTER: while(true) {
 210             PhysicalNet pn = pq.poll();
 211             if (pn==null) throw new Error("unroutable! " + source + " -> " + dests[0]);
 212             double frontier = pn.distance;
 213             for(PhysicalPip pip : pn)
 214                 for(PhysicalNet net : pip.getDrivenNets()) {
 215                     double newfrontier = frontier + 0.05 + net.congestion;
 216
 217                     // penalty for using any net already routed in this iteration (makes routing order-sensitive)
 218                     if (net.load >= 1) newfrontier = newfrontier + 20;
 219
 220                     if (net.distance <= newfrontier) continue;
 221                     pq.remove(net);  // if already in there
 222                     net.distance = newfrontier;
 223                     pq.add(net);
 224                     needsReset.add(net);
 225                     net.backpointer = pn;
 226                     if (remainingDests.contains(net)) {
 227                         remainingDests.remove(net);
 228                         if (remainingDests.size()==0) break OUTER;
 229
 230                         // Vaughn Betz style multiterminal routing: once we reach one sink, make every node on the path
 231                         // "distance zero" from the source.
 232                         for(PhysicalNet pnx = net; pnx != null; pnx = pnx.backpointer) {
 233                             //pnx.distance = 0;
 234                             pq.add(pnx);
 235                         }
 236                         break;
 237                     }
 238                 }
 239         }
 240
 241         for(PhysicalNet dest : dests) {
 242             PhysicalNet pn = dest;
 243             while(pn != null && pn.backpointer != null) {
 244                 pn.owners.add(owner);
 245                 owner.pns.add(pn);
 246                 if (pn.distance != Double.MAX_VALUE) {
 247                     pn.distance = Double.MAX_VALUE;
 248                     pn.load++;
 249                     if (pn.load>=2) pn.congestion += betaParameter;
 250                 }
 251                 PhysicalPip pip = pn.getPipFrom(pn.backpointer);
 252                 pip.set(true);
 253                 owner.pips.add(pip);
 254                 pn = pn.backpointer;
 255             }
 256             // FIXME: check pn==source at this point
 257         }
 258
 259         for(PhysicalNet pn : needsReset) {
 260             pn.distance    = Double.MAX_VALUE;
 261             pn.backpointer = null;
 262         }
 263     }
 264     public HashSet<PhysicalNet> allPhysicalNets = new HashSet<PhysicalNet>();
 265     public class PhysicalNet implements Iterable<PhysicalPip>, Comparable<PhysicalNet> {
 266         public double      congestion = 0;
 267         public int         load = 0;
 268         public double      distance = Double.MAX_VALUE;
 269         public PhysicalNet backpointer = null;
 270
 271         public int compareTo(PhysicalNet pn) {
 272             double x = distance - pn.distance;
 273             return distance > pn.distance
 274                 ? 1
 275                 : distance < pn.distance
 276                 ? -1
 277                 : 0;
 278         }
 279
 280         private final HashSet<PhysicalPip> pips = new HashSet<PhysicalPip>();
 281         public Iterator<PhysicalPip> iterator() { return pips.iterator(); }
 282         private String name;
 283         public PhysicalNet(String name) {
 284             this.name = name;
 285             allPhysicalNets.add(this);
 286         }
 287         public String toString() { return name; }
 288         private void addPip(PhysicalPip pip) { pips.add(pip); }
 289         public PhysicalPip getPipFrom(PhysicalNet pn) {
 290             for(PhysicalPip pip : pn)
 291                 for(PhysicalNet pn2 : pip.getDrivenNets())
 292                     if (pn2==this)
 293                         return pip;
 294             return null;
 295         }
 296         public HashSet<FlatNetlist.Net> owners = new HashSet<FlatNetlist.Net>();
 297     }
 298
 299     public abstract class PhysicalPip {
 300         private PhysicalNet   driver;
 301         private PhysicalNet[] driven;
 302         private String name;
 303         private int defaultCost;
 304         public String toString() { return name; }
 305         public PhysicalNet   getDriverNet()  { return driver; }
 306         public PhysicalNet[] getDrivenNets() { return driven; }
 307         public int           getCost(PhysicalNet in, PhysicalNet out) { return defaultCost; }
 308         public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven) { this(name, driver, driven, 100); }
 309         public PhysicalPip(String name, PhysicalNet driver, PhysicalNet[] driven, int defaultCost) {
 310             this.name = name;
 311             this.driver = driver;
 312             this.driven = driven;
 313             this.defaultCost = defaultCost;
 314             if (driver != null) driver.addPip(this);
 315             for(PhysicalNet pn : driven) pn.addPip(this);
 316         }
 317         public abstract void set(boolean connected);
 318     }
 319
 320 }