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 NetList fnl = new NetList();
112 for(Iterator<EdifCellInstance> it = (Iterator<EdifCellInstance>)env.getTopCell().cellInstanceIterator();
115 NetList.Node n = fnl.createNode(it.next(), null);
118 Fpslic fpslic = new FtdiBoard();
121 PhysicalDevice pd = new PhysicalFpslic(fpslic, width, height);
127 Random rand = new Random();
128 boolean[][] used = new boolean[width][height];
129 for(NetList.Node n : fnl.nodes) {
131 px = Math.abs(rand.nextInt()) % width;
132 py = Math.abs(rand.nextInt()) % height;
135 System.out.println("placed " + n + " at ("+px+","+py+")");
136 pd.getCell(px, py).place(n);
143 HashSet<NetList.LogicalNet> needUnroute = new HashSet<NetList.LogicalNet>();
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);
151 double congestion = 0;
154 for(PhysicalDevice.PhysicalNet pn : pd) {
155 if (pn.isCongested()) {
157 congestion += pn.getCongestion();
159 pn.updateCongestion();
160 if (pn.isCongested())
161 for(NetList.LogicalNet n : pn.getLogicalNets())
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();
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);
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" ) + " ] ");
195 private static int ret;
196 public static synchronized int scan(final Fpslic device, final Fpslic.Cell cell) {
198 scan(device, cell, YLUT, true);
199 ((FtdiBoard)device).readBus(new FtdiBoard.ByteCallback() {
200 public void call(byte b) throws Exception {
202 synchronized(device) {
207 synchronized(device) {
210 } catch (Exception e) { throw new RuntimeException(e); }
212 scan(device, cell, YLUT, false);
214 } catch (Exception e) { throw new RuntimeException(e); }
217 public static void scan(Fpslic dev, Fpslic.Cell cell, int source, boolean setup) {
219 //if (source != NONE) cell.c(source);
220 if (cell.b()) cell.b(false);
221 if (cell.f()) cell.f(false);
223 if (cell.out(L3)!=setup) cell.out(L3, setup);
224 if (cell.vx(L3)!=setup) cell.v(L3, setup);
226 Fpslic.SectorWire sw = cell.vwire(L3);
227 //System.out.println("wire is: " + sw);
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);
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);
244 //cell = dev.cell(19, 15);
245 cell = dev.cell(cell.col, 15);
247 System.out.println("cell is " + cell);
256 if (cell.hx(L3) != setup) cell.h(L3, setup);
257 if (cell.vx(L3) != setup) cell.v(L3, setup);
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);
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);
274 Fpslic.Cell c = n.getPlacement(fpslic);
277 c.xlut((val & 0x1)==0 ? 0x00 : 0xff);
281 public static int getOutput(NetList fnl, Fpslic fpslic, String prefix) {
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);
292 int scan = scan(fpslic, c);
293 val |= ((scan==0 ? 0 : 1) << i);