1 package edu.berkeley.slipway.mpar;
2 import com.atmel.fpslic.*;
3 import byucc.edif.tools.merge.*;
7 import edu.berkeley.slipway.*;
8 import com.atmel.fpslic.*;
9 import static com.atmel.fpslic.FpslicConstants.*;
11 // FIXME: sometimes gets stuck in a loop routing the last few nets
13 // FEATURE: ability to rip up only one branch of a multi-terminal net
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
21 // FEATURE: A* search (chap7 of independence thesis)
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
28 public class MPARDemo {
30 public static final double alphaParameter = 00.9;
31 public static final double betaParameter = 02.5;
32 public static final double gammaParameter = 1.0;
35 test code for inter-sector switchboxes
36 public static void main2() throws Exception {
37 Fpslic fpslic = new FtdiBoard();
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);
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++) {
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;
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);
66 if (vert) c.v(L0 + layer, true);
67 else c.h(L0 + layer, true);
68 c.out(L0 + layer, true);
72 if (vert) c2.v(L0 + layer, true);
73 else c2.h(L0 + layer, true);
78 System.out.print(x+","+y+","+l+","+(vert?"v":"h")+": ");
81 boolean good = scan(fpslic, c2)==0;
83 System.out.print(good ? "ok " : "bad ");
86 good = scan(fpslic, c2)!=0;
88 System.out.print(good ? "ok " : "bad ");
90 sw1.drives(sw2, false);
91 if (vert) c.v(layer, false);
92 else c.h(layer, false);
98 System.out.println("fails = " + fails);
101 public static int fails = 0;
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();
112 for(Iterator<EdifCellInstance> it = (Iterator<EdifCellInstance>)env.getTopCell().cellInstanceIterator();
115 FlatNetlist.Node n = fnl.createNode(it.next(), null);
118 Fpslic fpslic = new FtdiBoard();
119 PhysicalDevice pd = new PhysicalDevice(fpslic, 20, 20);
125 Random rand = new Random();
126 boolean[][] used = new boolean[pd.width][pd.height];
127 for(FlatNetlist.Node n : fnl.nodes) {
129 px = Math.abs(rand.nextInt()) % pd.width;
130 py = Math.abs(rand.nextInt()) % pd.height;
135 n.physicalCell = pd.getCell(px, py);
136 System.out.println("placed " + n + " at ("+px+","+py+")");
144 HashSet<FlatNetlist.Net> needUnroute = new HashSet<FlatNetlist.Net>();
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);
152 double congestion = 0;
155 for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets) {
157 //System.out.println("overrouted: " + pn + ", congestion="+pn.congestion + ", load=" + pn.load);
159 congestion += pn.congestion;
161 pn.congestion = pn.congestion * alphaParameter;
163 pn.congestion += betaParameter;
164 // don't do this here
165 //pn.congestion += betaParameter;
166 for(FlatNetlist.Net n : pn.owners)
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)
176 for(PhysicalDevice.PhysicalNet pn : pd.allPhysicalNets)
177 for(PhysicalDevice.PhysicalPip pip : pn) {
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);
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" ) + " ] ");
208 private static int ret;
209 public static synchronized int scan(final Fpslic device, final Fpslic.Cell cell) {
211 scan(device, cell, YLUT, true);
212 ((FtdiBoard)device).readBus(new FtdiBoard.ByteCallback() {
213 public void call(byte b) throws Exception {
215 synchronized(device) {
220 synchronized(device) {
223 } catch (Exception e) { throw new RuntimeException(e); }
225 scan(device, cell, YLUT, false);
227 } catch (Exception e) { throw new RuntimeException(e); }
230 public static void scan(Fpslic dev, Fpslic.Cell cell, int source, boolean setup) {
232 //if (source != NONE) cell.c(source);
233 if (cell.b()) cell.b(false);
234 if (cell.f()) cell.f(false);
236 if (cell.out(L3)!=setup) cell.out(L3, setup);
237 if (cell.vx(L3)!=setup) cell.v(L3, setup);
239 Fpslic.SectorWire sw = cell.vwire(L3);
240 //System.out.println("wire is: " + sw);
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);
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);
257 //cell = dev.cell(19, 15);
258 cell = dev.cell(cell.col, 15);
260 System.out.println("cell is " + cell);
269 if (cell.hx(L3) != setup) cell.h(L3, setup);
270 if (cell.vx(L3) != setup) cell.v(L3, setup);
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);
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);
287 Fpslic.Cell c = n.getPlacement(fpslic);
290 c.xlut((val & 0x1)==0 ? 0x00 : 0xff);
294 public static int getOutput(FlatNetlist fnl, Fpslic fpslic, String prefix) {
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);
305 int scan = scan(fpslic, c);
306 val |= ((scan==0 ? 0 : 1) << i);