1 package edu.berkeley.slipway.mpar;
2 import com.atmel.fpslic.*;
4 import byucc.edif.tools.merge.*;
8 import edu.berkeley.slipway.*;
9 import edu.berkeley.abits.*;
10 import com.atmel.fpslic.*;
11 import static com.atmel.fpslic.FpslicConstants.*;
12 import static edu.berkeley.slipway.mpar.PhysicalFpslic.*;
14 // FIXME: sometimes gets stuck in a loop routing the last few nets
16 // FEATURE: ability to rip up only one branch of a multi-terminal net
18 // FEATURE: re-placement based on routing congestion
19 // note: must assign a cost to "bare wire" -- if not, the
20 // placer will fail to recognize moves that put blocks closer
21 // together, thereby decreasing the potential for future
24 // FEATURE: A* search (chap7 of independence thesis)
26 // FIXME: distinguish out,xo,yo
27 // FIXME: y-axis shortcuts
28 // FEATURE: ability to use a cell for routing purposes
29 // FEATURE: global two-sector-long wires
31 public class MPARDemo {
34 public static final double alphaParameter = 0.9;
35 public static final double betaParameter = 0.5;
36 public static final double wireCost = 0.005;
37 public static final double wireCostPlacement = 0.01; // cost of an uncongested net (cost of congested net is 1)
38 //public static final double gammaParameter = 1.0;
39 public static final double lambda = 0.7;
41 public static double temperature = 300.0;
42 public static double congestion = 0;
43 public static double timingpenalty = 0;
45 public static void main(String[] s) throws Exception {
47 NetList fnl = new NetList(s[0]);
51 //SlipwayBoard slipway = new SlipwayBoard();
52 Board slipway = new FakeBoard(24, 24);
54 FpslicDevice fpslic = (FpslicDevice)slipway.getDevice();
56 PhysicalDevice pd = new PhysicalFpslic(fpslic, width, height);
58 Placement placement = new Placement(fnl, pd);
59 Routing routing = new Routing(placement);
60 Random rand = new Random();
61 placement.random(rand);
65 int num_moves = width*height;
67 Visualization vis = new Visualization((PhysicalFpslic)pd);
69 boolean alldone = false;
70 long lastDraw = System.currentTimeMillis();
73 double max_swap_dist = 3 * Math.max(width,height) * Math.exp(-1 / temperature);
74 System.out.println("round " + (++trial) + " (temp="+temperature+", maxdist="+max_swap_dist+")");
78 congestion = routing.measureCongestion();
79 timingpenalty = routing.measureTimingpenalty();
80 double wirecost = routing.measureWireCost();
84 for(int i=0; i<num_moves; i++) {
85 System.out.print("\r [place: " + i + "/" + num_moves + " congestion="+congestion+"]");
86 NetList.Node node1 = fnl.randomNode(rand);
87 PhysicalDevice.PhysicalCell cell1 = placement.nodeToCell(node1);
88 PhysicalDevice.PhysicalCell cell2 = cell1.randomCellWithin(rand, max_swap_dist);
89 NetList.Node node2 = placement.cellToNode(cell2);
91 // FIXME: cache and reuse "newrouting"
92 // also: fold down newrouting to collapse parentage
94 routing.unroute(node1);
95 routing.unroute(node2);
96 placement.unplace(cell1);
97 placement.unplace(cell2);
98 placement.place(node1, cell2);
99 placement.place(node2, cell1);
102 double newcongestion = routing.measureCongestion();
103 double newwirecost = routing.measureWireCost();
104 double newtimingpenalty = routing.measureTimingpenalty();
107 lam * ((newcongestion - congestion) / Math.max(0.001, congestion))
109 //(1-lam) * ((newwirecost - wirecost) / wirecost)
111 (1-lam) * ((newtimingpenalty - timingpenalty) / Math.max(0.001, timingpenalty))
113 double swapProbability = Math.exp((-1 * deltaCost) / temperature);
114 //double dist = Math.sqrt( (5-p2x)*(5-p2x) + (5-p2y)*(5-p2y) );
118 swapProbability = Math.max(0, Math.min(swapProbability, dist / Math.sqrt(rad+rad)));
120 boolean doSwap = Math.random() < swapProbability;
123 congestion = newcongestion;
124 wirecost = newwirecost;
125 timingpenalty = newtimingpenalty;
127 placement.unplace(cell1);
128 placement.unplace(cell2);
129 placement.place(node1, cell1);
130 placement.place(node2, cell2);
134 double acceptance = ((double)swaps) / num_moves;
136 if (acceptance > 0.96) gamma = 0.5;
137 else if (acceptance > 0.8) gamma = 0.9;
138 else if (acceptance > 0.15) gamma = 0.95;
141 System.out.println(" acceptance="+acceptance);
142 temperature = temperature * gamma;
143 int num_routes = num_moves - swaps;
145 for(int i=0; i<num_routes; i++) {
146 int overrouted = routing.measureOverloaded();
147 routing.unrouteOverloaded();
148 routing.reRouteAll();
149 System.out.print("\r [route "+i+"/"+num_routes+"] overrouted="+overrouted+" congestion="+routing.measureCongestion()+" penalty="+timingpenalty);
150 routing.updateCongestion(alphaParameter, betaParameter);
151 if (overrouted==0 && timingpenalty < 1) alldone = true;
153 num_moves = (int)(300 * gamma * gamma);
154 vis.draw(placement, routing, false);
155 System.out.println();
157 vis.draw(placement, routing, true);
158 placement.setPlacement();
159 routing.setPips(true);
160 System.out.println("wire utilization: " + Math.round(routing.measureWireUtilization()*100));
163 fpslic.cell(23,15).h(3, true);
164 fpslic.cell(23,15).yi(L3);
165 fpslic.cell(23,15).ylut(0xAA);
166 fpslic.iob_right(15, true).enableOutput(WEST);
167 fpslic.cell(23,0).ylut(0x00);
168 fpslic.iob_right(0, true).enableOutput(WEST);
173 while(temperature==0) {
174 int a = Math.abs(rand.nextInt()) % (1 << xwidth);
175 int b = Math.abs(rand.nextInt()) % (1 << xwidth);
176 setInput(fnl, fpslic, "a", a, placement);
177 setInput(fnl, fpslic, "b", b, placement);
178 setInput(fnl, fpslic, "ci", 0, placement);
179 int result = getOutput(fnl, fpslic, slipway, "out", placement);
180 int expect = (a+b) & ~(-1 << (xwidth+1));
181 System.out.println(Integer.toString(a,16) + " + " +
182 Integer.toString(b,16) + " = " +
183 Integer.toString(result,16) +
184 " [ " + (expect==result ? "ok" : "bad" ) + " ] " + (Integer.toString((result^(expect)),16)));
191 private static int ret;
192 public static synchronized int scan(final FpslicDevice device, final SlipwayBoard slipway, final FpslicDevice.Cell cell) {
194 scan(device, cell, XLUT, true);
195 slipway.readFpgaData(new SlipwayBoard.ByteCallback() {
196 public void call(byte b) throws Exception {
198 synchronized(device) {
203 synchronized(device) {
206 } catch (Exception e) { throw new RuntimeException(e); }
208 scan(device, cell, XLUT, false);
210 } catch (Exception e) { throw new RuntimeException(e); }
213 public static void scan(FpslicDevice dev, FpslicDevice.Cell cell, int source, boolean setup) {
215 //if (source != NONE) cell.c(source);
216 if (cell.b()) cell.b(false);
217 if (cell.f()) cell.f(false);
219 if (cell.out(L3)!=setup) cell.out(L3, setup);
220 if (cell.vx(L3)!=setup) cell.v(L3, setup);
222 FpslicDevice.SectorWire sw = cell.vwire(L3);
223 //System.out.println("wire is: " + sw);
225 if (sw.row > (12 & ~0x3) && sw.north()!=null && sw.north().drives(sw))
226 sw.north().drives(sw, false);
227 while(sw.row > (12 & ~0x3) && sw.south() != null) {
228 //System.out.println(sw + " -> " + sw.south());
229 if (sw.drives(sw.south())!=setup) sw.drives(sw.south(), setup);
232 if (sw.row < (12 & ~0x3) && sw.south() != null && sw.south().drives(sw))
233 sw.north().drives(sw, false);
234 while(sw.row < (12 & ~0x3) && sw.north() != null) {
235 //System.out.println(sw + " -> " + sw.north());
236 if (sw.drives(sw.north())!=setup) sw.drives(sw.north(), setup);
240 //cell = dev.cell(19, 15);
241 cell = dev.cell(cell.col, 15);
243 System.out.println("cell is " + cell);
252 if (cell.hx(L3) != setup) cell.h(L3, setup);
253 if (cell.vx(L3) != setup) cell.v(L3, setup);
256 if (sw.west()!=null && sw.west().drives(sw)) { sw.west().drives(sw, false); }
257 while(sw.east() != null) {
258 //System.out.println(sw + " -> " + sw.east());
259 if (sw.drives(sw.east())!=setup) sw.drives(sw.east(), setup);
265 public static void setInput(NetList fnl, FpslicDevice fpslic, String prefix, int val, Placement placement) {
266 for(int i=0; ; i++) {
267 NetList.Node n = fnl.top.get(prefix + "["+i+"]");
268 if (n==null && i==0) n = fnl.top.get(prefix);
270 FpslicDevice.Cell c = ((PhysicalFpslic.PhysicalFpslicCell)placement.nodeToCell(n)).cell();
273 c.xlut((val & 0x1)==0 ? 0x00 : 0xff);
277 public static int getOutput(NetList fnl, FpslicDevice fpslic, SlipwayBoard slipway, String prefix, Placement placement) {
279 for(int i=0; ; i++) {
280 NetList.Node n = fnl.top.get(prefix+"["+i+"]");
281 if (n==null && i==0) n = fnl.top.get(prefix);
282 if (n==null) return val;
283 FpslicDevice.Cell c = ((PhysicalFpslic.PhysicalFpslicCell)placement.nodeToCell(n)).cell();
288 int scan = scan(fpslic, slipway, c);
289 val |= ((scan==0 ? 0 : 1) << i);