src/edu/berkeley/slipway/mpar/MPARDemo.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
  11 // FIXME: sometimes gets stuck in a loop routing the last few nets
  12
  13 // FEATURE: ability to rip up only one branch of a multi-terminal net
  14
  15 // FEATURE: re-placement based on routing congestion
  16 //          note: must assign a cost to "bare wire" -- if not, the
  17 //          placer will fail to recognize moves that put blocks closer
  18 //          together, thereby decreasing the potential for future
  19 //          congestion.
  20
  21 // FEATURE: A* search (chap7 of independence thesis)
  22
  23 // FIXME: distinguish out,xo,yo
  24 // FIXME: y-axis shortcuts
  25 // FEATURE: ability to use a cell for routing purposes
  26 // FEATURE: global two-sector-long wires
  27
  28 public class MPARDemo {
  29
  30     public static final double alphaParameter = 00.9;
  31     public static final double betaParameter  = 02.5;
  32     public static final double gammaParameter =  1.0;
  33
  34     /*
  35       test code for inter-sector switchboxes
  36     public static void main2() throws Exception {
  37         Fpslic fpslic = new FtdiBoard();
  38         // set up scan cell
  39         fpslic.cell(23,15).h(3, true);
  40         fpslic.cell(23,15).yi(L3);
  41         fpslic.cell(23,15).ylut(0xAA);
  42         fpslic.iob_right(15, true).enableOutput(WEST);
  43         fpslic.cell(23,0).ylut(0x00);
  44         fpslic.iob_right(0, true).enableOutput(WEST);
  45         fpslic.flush();
  46         for(int x=0; x<20; x++) {
  47             for(int y=0; y<20; y++) {
  48                 for(int l=0; l<5; l++) {
  49                     for(int v = 0; v <= 1; v++) {
  50                         boolean vert = v==1;
  51                         int newx = vert ? x   : x-1;
  52                         int newy = vert ? y-1 : y;
  53                         if (newx<0 || newy<0) continue;
  54                         if (vert  && (y%4) != 0) continue;
  55                         if (!vert && (x%4) != 0) continue;
  56
  57                         int layer = l;
  58                         if (layer==3) continue;
  59                         Fpslic.Cell c  = fpslic.cell(x, y);
  60                         Fpslic.Cell c2 = fpslic.cell(newx, newy);
  61                         Fpslic.SectorWire sw1 = vert ? c.vwire(layer)  : c.hwire(layer);
  62                         Fpslic.SectorWire sw2 = vert ? c2.vwire(layer) : c2.hwire(layer);
  63                         sw1.drives(sw2, true);
  64
  65                         c.c(YLUT);
  66                         if (vert) c.v(L0 + layer, true);
  67                         else      c.h(L0 + layer, true);
  68                         c.out(L0 + layer, true);
  69                         c.b(false);
  70
  71                         c2.yi(L0 + layer);
  72                         if (vert) c2.v(L0 + layer, true);
  73                         else      c2.h(L0 + layer, true);
  74                         c2.ylut(LUT_SELF);
  75                         c2.c(YLUT);
  76                         c2.b(false);
  77
  78                         System.out.print(x+","+y+","+l+","+(vert?"v":"h")+": ");
  79                         c.ylut(0x00);
  80                         fpslic.flush();
  81                         boolean good = scan(fpslic, c2)==0;
  82                         if (!good) fails++;
  83                         System.out.print(good ? "ok " : "bad ");
  84                         c.ylut(0xff);
  85                         fpslic.flush();
  86                         good = scan(fpslic, c2)!=0;
  87                         if (!good) fails++;
  88                         System.out.print(good ? "ok " : "bad ");
  89                         System.out.println();
  90                         sw1.drives(sw2, false);
  91                         if (vert) c.v(layer, false);
  92                         else      c.h(layer, false);
  93                         c.out(layer, false);
  94                     }
  95                 }
  96             }
  97         }
  98         System.out.println("fails = " + fails);
  99
 100     }
 101     public static int fails = 0;
 102     */
 103
 104     public static void main(String[] s) throws Exception {
 105         EdifEnvironment topEnv = new EdifEnvironment("top");
 106         EdifLibraryManager elm = new EdifLibraryManager(topEnv);
 107         EdifLibrary initLib = new EdifLibrary(elm, "initLib");
 108         EdifEnvironment env = EdifMergeParser.parseAndMerge(s, initLib);
 109         System.out.println("top is " + env.getTopCell());
 110         FlatNetlist fnl = new FlatNetlist();
 111
 112         for(Iterator<EdifCellInstance> it = (Iterator<EdifCellInstance>)env.getTopCell().cellInstanceIterator();
 113             it.hasNext();
 114             ) {
 115             FlatNetlist.Node n = fnl.createNode(it.next(), null);
 116         }
 117
 118         Fpslic fpslic = new FtdiBoard();
 119         PhysicalDevice pd = new PhysicalDevice(fpslic, 20, 20);
 120
 121         int px = 0;
 122         int py = 0;
 123
 124         // crude map
 125         Random rand = new Random();
 126         boolean[][] used = new boolean[pd.width][pd.height];
 127         for(FlatNetlist.Node n : fnl.nodes) {
 128             while(true) {
 129                 px = Math.abs(rand.nextInt()) % pd.width;
 130                 py = Math.abs(rand.nextInt()) % pd.height;
 131                 if (!used[px][py]) {
 132                     used[px][py] = true;
 133                     n.x = px;
 134                     n.y = py;
 135                     n.physicalCell = pd.getCell(px, py);
 136                     System.out.println("placed " + n + " at ("+px+","+py+")");
 137                     n.place(fpslic);
 138                     break;
 139                 }
 140             }
 141         }
 142
 143         int trial = 0;
 144         HashSet<FlatNetlist.Net> needUnroute = new HashSet<FlatNetlist.Net>();
 145         while(true) {
 146             System.out.println();
 147             System.out.println("routing trial " + (++trial));
 148             for(FlatNetlist.Net net : fnl.nets) {
 149                 if (net.getSize() <= 1) continue;
 150                 net.route(fpslic, pd);
 151             }
 152             double congestion = 0;
 153             int overrouted = 0;
 154             needUnroute.clear();
 155             for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets) {
 156                 if (pn.load > 1) {
 157                     //System.out.println("overrouted: " + pn + ", congestion="+pn.congestion + ", load=" + pn.load);
 158                     overrouted++;
 159                     congestion += pn.congestion;
 160                 }
 161                 pn.congestion = pn.congestion * alphaParameter;
 162                 if (pn.load > 1) {
 163                     pn.congestion += betaParameter;
 164                     // don't do this here
 165                     //pn.congestion += betaParameter;
 166                     for(FlatNetlist.Net n : pn.owners)
 167                         needUnroute.add(n);
 168                 }
 169             }
 170             System.out.println("  overrouted="+overrouted+", congestion="+congestion +", ripping up " + needUnroute.size() +" nets of " + fnl.nets.size());
 171             if (overrouted <= 0) break;
 172             //for(FlatNetlist.Net net : fnl.nets)
 173             for(FlatNetlist.Net net : needUnroute)
 174                 net.unroute();
 175             /*
 176             for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets)
 177                 for(PhysicalDevice.PhysicalPip pip : pn) {
 178                     pip.set(false);
 179                 }
 180             */
 181         }
 182
 183         // set up scan cell
 184         fpslic.cell(23,15).h(3, true);
 185         fpslic.cell(23,15).yi(L3);
 186         fpslic.cell(23,15).ylut(0xAA);
 187         fpslic.iob_right(15, true).enableOutput(WEST);
 188         fpslic.cell(23,0).ylut(0x00);
 189         fpslic.iob_right(0, true).enableOutput(WEST);
 190         fpslic.flush();
 191
 192         int width = 8;
 193         while(true) {
 194             int a = Math.abs(rand.nextInt()) % (1 << width);
 195             int b = Math.abs(rand.nextInt()) % (1 << width);
 196             setInput(fnl, fpslic, "a",  a);
 197             setInput(fnl, fpslic, "b",  b);
 198             setInput(fnl, fpslic, "ci", 0);
 199             int result = getOutput(fnl, fpslic, "out");
 200             System.out.println(Integer.toString(a,16) + " + " +
 201                                Integer.toString(b,16) + " = " +
 202                                Integer.toString(result,16) +
 203                                " [ " + (a+b==result ? "ok" : "bad" ) + " ] ");
 204         }
 205     }
 206
 207
 208     private static int ret;
 209     public static synchronized int scan(final Fpslic device, final Fpslic.Cell cell) {
 210         try {
 211             scan(device, cell, YLUT, true);
 212             ((FtdiBoard)device).readBus(new FtdiBoard.ByteCallback() {
 213                     public void call(byte b) throws Exception {
 214                         ret = b;
 215                         synchronized(device) {
 216                             device.notifyAll();
 217                         }
 218                     }
 219                 });
 220             synchronized(device) {
 221                 try {
 222                     device.wait();
 223                 } catch (Exception e) { throw new RuntimeException(e); }
 224             }
 225             scan(device, cell, YLUT, false);
 226             return ret;
 227         } catch (Exception e) { throw new RuntimeException(e); }
 228     }
 229
 230     public static void scan(Fpslic dev, Fpslic.Cell cell, int source, boolean setup) {
 231         if (setup) {
 232             //if (source != NONE) cell.c(source);
 233             if (cell.b()) cell.b(false);
 234             if (cell.f()) cell.f(false);
 235         }
 236         if (cell.out(L3)!=setup) cell.out(L3, setup);
 237         if (cell.vx(L3)!=setup) cell.v(L3, setup);
 238
 239         Fpslic.SectorWire sw = cell.vwire(L3);
 240         //System.out.println("wire is: " + sw);
 241
 242         if (sw.row > (12 & ~0x3) && sw.north()!=null && sw.north().drives(sw))
 243             sw.north().drives(sw, false);
 244         while(sw.row > (12 & ~0x3) && sw.south() != null) {
 245             //System.out.println(sw + " -> " + sw.south());
 246             if (sw.drives(sw.south())!=setup) sw.drives(sw.south(), setup);
 247             sw = sw.south();
 248         }
 249         if (sw.row < (12 & ~0x3) && sw.south() != null && sw.south().drives(sw))
 250             sw.north().drives(sw, false);
 251         while(sw.row < (12 & ~0x3) && sw.north() != null) {
 252             //System.out.println(sw + " -> " + sw.north());
 253             if (sw.drives(sw.north())!=setup) sw.drives(sw.north(), setup);
 254             sw = sw.north();
 255         }
 256
 257         //cell = dev.cell(19, 15);
 258         cell = dev.cell(cell.col, 15);
 259         /*
 260         System.out.println("cell is " + cell);
 261         cell.xlut(0xff);
 262         cell.ylut(0xff);
 263         cell.b(false);
 264         cell.f(false);
 265         cell.c(XLUT);
 266         cell.out(L3, true);
 267         cell.oe(NONE);
 268         */
 269         if (cell.hx(L3) != setup) cell.h(L3, setup);
 270         if (cell.vx(L3) != setup) cell.v(L3, setup);
 271         sw = cell.hwire(L3);
 272
 273         if (sw.west()!=null && sw.west().drives(sw)) { sw.west().drives(sw, false); }
 274         while(sw.east() != null) {
 275             //System.out.println(sw + " -> " + sw.east());
 276             if (sw.drives(sw.east())!=setup) sw.drives(sw.east(), setup);
 277             sw = sw.east();
 278         }
 279
 280     }
 281
 282         public static void setInput(FlatNetlist fnl, Fpslic fpslic, String prefix, int val) {
 283             for(int i=0; ; i++) {
 284                 FlatNetlist.Node n = fnl.top.get(prefix + "["+i+"]");
 285                 if (n==null && i==0) n = fnl.top.get(prefix);
 286                 if (n==null) return;
 287                 Fpslic.Cell c = n.getPlacement(fpslic);
 288                 c.c(XLUT);
 289                 c.b(false);
 290                 c.xlut((val & 0x1)==0 ? 0x00 : 0xff);
 291                 val = val >> 1;
 292             }
 293         }
 294         public static int getOutput(FlatNetlist fnl, Fpslic fpslic, String prefix) {
 295             int val = 0;
 296             for(int i=0; ; i++) {
 297                 FlatNetlist.Node n = fnl.top.get(prefix+"["+i+"]");
 298                 if (n==null && i==0) n = fnl.top.get(prefix);
 299                 if (n==null) return val;
 300                 Fpslic.Cell c = n.getPlacement(fpslic);
 301                 c.xlut(LUT_SELF);
 302                 c.c(XLUT);
 303                 c.b(false);
 304                 fpslic.flush();
 305                 int scan = scan(fpslic, c);
 306                 val |= ((scan==0 ? 0 : 1) << i);
 307             }
 308         }
 309
 310
 311 }