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         NetList fnl = new NetList();
 111
 112         for(Iterator<EdifCellInstance> it = (Iterator<EdifCellInstance>)env.getTopCell().cellInstanceIterator();
 113             it.hasNext();
 114             ) {
 115             NetList.Node n = fnl.createNode(it.next(), null);
 116         }
 117
 118         Fpslic fpslic = new FtdiBoard();
 119         int width = 20;
 120         int height = 20;
 121         PhysicalDevice pd = new PhysicalFpslic(fpslic, width, height);
 122
 123         int px = 0;
 124         int py = 0;
 125
 126         // crude map
 127         Random rand = new Random();
 128         boolean[][] used = new boolean[width][height];
 129         for(NetList.Node n : fnl.nodes) {
 130             while(true) {
 131                 px = Math.abs(rand.nextInt()) % width;
 132                 py = Math.abs(rand.nextInt()) % height;
 133                 if (!used[px][py]) {
 134                     used[px][py] = true;
 135                     System.out.println("placed " + n + " at ("+px+","+py+")");
 136                     pd.getCell(px, py).place(n);
 137                     break;
 138                 }
 139             }
 140         }
 141
 142         int trial = 0;
 143         HashSet<NetList.LogicalNet> needUnroute = new HashSet<NetList.LogicalNet>();
 144         while(true) {
 145             System.out.println();
 146             System.out.println("routing trial " + (++trial));
 147             for(NetList.LogicalNet net : fnl.nets) {
 148                 if (net.getSize() <= 1) continue;
 149                 net.route(fpslic, pd);
 150             }
 151             double congestion = 0;
 152             int overrouted = 0;
 153             needUnroute.clear();
 154             for(PhysicalDevice.PhysicalNet pn : pd) {
 155                 if (pn.isCongested()) {
 156                     overrouted++;
 157                     congestion += pn.getCongestion();
 158                 }
 159                 pn.updateCongestion();
 160                 if (pn.isCongested())
 161                     for(NetList.LogicalNet n : pn.getLogicalNets())
 162                         needUnroute.add(n);
 163             }
 164             System.out.println("  overrouted="+overrouted+", congestion="+congestion +
 165                                ", ripping up " + needUnroute.size() +" nets of " + fnl.nets.size());
 166             if (overrouted <= 0) break;
 167             for(NetList.LogicalNet net : needUnroute) net.unroute();
 168         }
 169
 170         // set up scan cell
 171         fpslic.cell(23,15).h(3, true);
 172         fpslic.cell(23,15).yi(L3);
 173         fpslic.cell(23,15).ylut(0xAA);
 174         fpslic.iob_right(15, true).enableOutput(WEST);
 175         fpslic.cell(23,0).ylut(0x00);
 176         fpslic.iob_right(0, true).enableOutput(WEST);
 177         fpslic.flush();
 178
 179         int xwidth = 8;
 180         while(true) {
 181             int a = Math.abs(rand.nextInt()) % (1 << xwidth);
 182             int b = Math.abs(rand.nextInt()) % (1 << xwidth);
 183             setInput(fnl, fpslic, "a",  a);
 184             setInput(fnl, fpslic, "b",  b);
 185             setInput(fnl, fpslic, "ci", 0);
 186             int result = getOutput(fnl, fpslic, "out");
 187             System.out.println(Integer.toString(a,16) + " + " +
 188                                Integer.toString(b,16) + " = " +
 189                                Integer.toString(result,16) +
 190                                " [ " + (a+b==result ? "ok" : "bad" ) + " ] ");
 191         }
 192     }
 193
 194
 195     private static int ret;
 196     public static synchronized int scan(final Fpslic device, final Fpslic.Cell cell) {
 197         try {
 198             scan(device, cell, YLUT, true);
 199             ((FtdiBoard)device).readBus(new FtdiBoard.ByteCallback() {
 200                     public void call(byte b) throws Exception {
 201                         ret = b;
 202                         synchronized(device) {
 203                             device.notifyAll();
 204                         }
 205                     }
 206                 });
 207             synchronized(device) {
 208                 try {
 209                     device.wait();
 210                 } catch (Exception e) { throw new RuntimeException(e); }
 211             }
 212             scan(device, cell, YLUT, false);
 213             return ret;
 214         } catch (Exception e) { throw new RuntimeException(e); }
 215     }
 216
 217     public static void scan(Fpslic dev, Fpslic.Cell cell, int source, boolean setup) {
 218         if (setup) {
 219             //if (source != NONE) cell.c(source);
 220             if (cell.b()) cell.b(false);
 221             if (cell.f()) cell.f(false);
 222         }
 223         if (cell.out(L3)!=setup) cell.out(L3, setup);
 224         if (cell.vx(L3)!=setup) cell.v(L3, setup);
 225
 226         Fpslic.SectorWire sw = cell.vwire(L3);
 227         //System.out.println("wire is: " + sw);
 228
 229         if (sw.row > (12 & ~0x3) && sw.north()!=null && sw.north().drives(sw))
 230             sw.north().drives(sw, false);
 231         while(sw.row > (12 & ~0x3) && sw.south() != null) {
 232             //System.out.println(sw + " -> " + sw.south());
 233             if (sw.drives(sw.south())!=setup) sw.drives(sw.south(), setup);
 234             sw = sw.south();
 235         }
 236         if (sw.row < (12 & ~0x3) && sw.south() != null && sw.south().drives(sw))
 237             sw.north().drives(sw, false);
 238         while(sw.row < (12 & ~0x3) && sw.north() != null) {
 239             //System.out.println(sw + " -> " + sw.north());
 240             if (sw.drives(sw.north())!=setup) sw.drives(sw.north(), setup);
 241             sw = sw.north();
 242         }
 243
 244         //cell = dev.cell(19, 15);
 245         cell = dev.cell(cell.col, 15);
 246         /*
 247         System.out.println("cell is " + cell);
 248         cell.xlut(0xff);
 249         cell.ylut(0xff);
 250         cell.b(false);
 251         cell.f(false);
 252         cell.c(XLUT);
 253         cell.out(L3, true);
 254         cell.oe(NONE);
 255         */
 256         if (cell.hx(L3) != setup) cell.h(L3, setup);
 257         if (cell.vx(L3) != setup) cell.v(L3, setup);
 258         sw = cell.hwire(L3);
 259
 260         if (sw.west()!=null && sw.west().drives(sw)) { sw.west().drives(sw, false); }
 261         while(sw.east() != null) {
 262             //System.out.println(sw + " -> " + sw.east());
 263             if (sw.drives(sw.east())!=setup) sw.drives(sw.east(), setup);
 264             sw = sw.east();
 265         }
 266
 267     }
 268
 269         public static void setInput(NetList fnl, Fpslic fpslic, String prefix, int val) {
 270             for(int i=0; ; i++) {
 271                 NetList.Node n = fnl.top.get(prefix + "["+i+"]");
 272                 if (n==null && i==0) n = fnl.top.get(prefix);
 273                 if (n==null) return;
 274                 Fpslic.Cell c = n.getPlacement(fpslic);
 275                 c.c(XLUT);
 276                 c.b(false);
 277                 c.xlut((val & 0x1)==0 ? 0x00 : 0xff);
 278                 val = val >> 1;
 279             }
 280         }
 281         public static int getOutput(NetList fnl, Fpslic fpslic, String prefix) {
 282             int val = 0;
 283             for(int i=0; ; i++) {
 284                 NetList.Node n = fnl.top.get(prefix+"["+i+"]");
 285                 if (n==null && i==0) n = fnl.top.get(prefix);
 286                 if (n==null) return val;
 287                 Fpslic.Cell c = n.getPlacement(fpslic);
 288                 c.xlut(LUT_SELF);
 289                 c.c(XLUT);
 290                 c.b(false);
 291                 fpslic.flush();
 292                 int scan = scan(fpslic, c);
 293                 val |= ((scan==0 ? 0 : 1) << i);
 294             }
 295         }
 296
 297
 298 }