1
2 // This file is part of the Alliance Project.
3 // Copyright (C) Laboratoire LIP6 - Departement ASIM
4 // Universite Pierre et Marie Curie
5 //
6 // The Alliance Project is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU General Public License as
8 // published by the Free Software Foundation; either version 2 of the
9 // License, or (at your option) any later version.
10 //
11 // The Alliance Project is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with the Alliance Project; if not, write to the Free Software
18 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 //
20 //
21 // License-Tag
22 //
23 // Date : 29/01/2004
24 // Author : Christophe Alexandre <Christophe.Alexandre@lip6.fr>
25 //
26 // Authors-Tag
27 #include <stdio.h>
28 #include <math.h>
29 #include <unistd.h>
30 #include <string.h>
31 using namespace std;
32
33 #include "PMove.h"
34 #include "PConstants.h"
35
36 #include "PPlacement.h"
37
38 static double
DoubleRand(void)39 DoubleRand(void)
40 {
41 return (double) rand() / (RAND_MAX + 1.0);
42 }
43
44 static bool
Accept(double Temperature,double DeltaCost)45 Accept(double Temperature, double DeltaCost)
46 {
47 if ((DeltaCost <= 0.0) || ((Temperature != 0.0) && (exp(-DeltaCost / Temperature) > DoubleRand())))
48 return true;
49 else
50 return false;
51 }
52
53 static double
GetStdDev(double Sum,double Square,double n)54 GetStdDev(double Sum, double Square, double n)
55 {
56 if (n <= 1.0)
57 return 0.0;
58
59 double StdDev = (Square - Sum * Sum / n) / (n - 1.0);
60 if (StdDev > 0.0)
61 StdDev = sqrt(StdDev);
62 else
63 StdDev = 0.0;
64
65 return StdDev;
66 }
67
68
69 #ifdef PLACE_DEBUG
70 double
GlobalPlaceDebugNetCost()71 PPlacement::GlobalPlaceDebugNetCost()
72 {
73 double NetCost = 0.0;
74
75 vector<PNet>::iterator nfirst = _nets.begin();
76 vector<PNet>::iterator nlast = _nets.end();
77 while (nfirst != nlast) {
78 PNet& net = *nfirst++;
79 PBBox bbox;
80 vector<PElem*>::iterator ifirst = net.GetElems().begin();
81 vector<PElem*>::iterator ilast = net.GetElems().end();
82 if (ifirst != ilast)
83 {
84 while (ifirst != ilast)
85 bbox.Merge((*ifirst++)->GetPos());
86 double width = bbox.GetWidth();
87 if (width == 0.0)
88 {
89 //toutes les instances dans le meme bin
90 //on prend comme largeur la moitie du bin
91 ifirst = net.GetElems().begin();
92 PToPlaceIns* toplaceins = NULL;
93 while (ifirst != ilast)
94 {
95 toplaceins = dynamic_cast<PToPlaceIns*>(*ifirst++);
96 if (toplaceins)
97 break;
98 }
99 if (!toplaceins)
100 width = 0;
101 else
102 width = toplaceins->GetBin().GetWidth() / 2.0;
103 }
104
105 NetCost += bbox.GetHeight() + width;
106 }
107 }
108 return NetCost;
109 }
110 #endif
111
112
113 #ifndef Abs
114 #define Abs(x) ((x) < 0.0 ? -(x) : (x))
115 #endif
116 double
GetRowCost()117 PPlacement::GetRowCost()
118 {
119 double RowCost = 0.0;
120 for (PRows::iterator rit = _rows.begin(); rit != _rows.end(); rit++)
121 {
122 RowCost += (*rit)->GetSubRowCost();
123 }
124 return RowCost;
125 }
126
127 double
GetBinCost()128 PPlacement::GetBinCost()
129 {
130 double BinCost = 0.0;
131
132 for (PRows::iterator rit = _rows.begin(); rit != _rows.end(); rit++)
133 {
134 BinCost += (*rit)->GetBinCost();
135 }
136 return BinCost;
137 }
138
139 double
GetNetCost()140 PPlacement::GetNetCost()
141 {
142 double NetCost = 0.0;
143
144 vector<PONet*>::iterator nfirst = _nets.begin();
145 vector<PONet*>::iterator nlast = _nets.end();
146 while (nfirst != nlast) {
147 PONet& net = **nfirst++;
148 PBBox& bbox = net.CurrentBBox();
149 vector<PElem*>::iterator ifirst = net.GetElems().begin();
150 vector<PElem*>::iterator ilast = net.GetElems().end();
151 if (ifirst == ilast)
152 {
153 cout << " o Placer Warning : Net " << net << " is not connected..." << endl;
154 }
155 else
156 {
157 while (ifirst != ilast)
158 bbox.Merge((*ifirst++)->GetPos());
159 double width = bbox.GetWidth();
160 if (width == 0.0)
161 {
162 //toutes les instances dans le meme bin
163 //on prend comme largeur la moitie du bin
164 ifirst = net.GetElems().begin();
165 PToPlaceIns* toplaceins = NULL;
166 while (ifirst != ilast)
167 {
168 toplaceins = dynamic_cast<PToPlaceIns*>(*ifirst++);
169 if (toplaceins)
170 break;
171 }
172 if (!toplaceins)
173 width = 0;
174 else
175 width = toplaceins->GetBin().GetWidth() / 2.0;
176 }
177 net.CurrentCost() = bbox.GetHeight() + width;
178 NetCost += net.CurrentCost();
179 }
180 }
181 return NetCost;
182 }
183
184 double
GetCost(double RowCost,double BinCost,double NetCost)185 PPlacement::GetCost(double RowCost, double BinCost, double NetCost)
186 {
187 return RowCost / _initRowCost * RowMult + BinCost / _initBinCost * BinMult + NetCost / _initNetCost * NetMult;
188 }
189
190 void
PlaceGlobal()191 PPlacement::PlaceGlobal()
192 {
193 int Iteration;
194 double Cost, RowCost, BinCost, NetCost;
195 double Temperature = 1e30, OldTemperature = 1e30;
196 int Loop = 0;
197 double StdDev = 0 ;
198 double SumCost = 0, SumCostRow = 0, SumCostBin = 0, SumCostNet = 0;
199 double SumSquare = 0, SumSquareRow = 0, SumSquareBin = 0, SumSquareNet = 0;
200 int Accepted = 0;
201 double SucRatio = 1.0;
202 double Dist = 1.0;
203
204 double maxTemperature = 0;
205 double maxCost = 0;
206 double maxRowCost = 0;
207 double maxBinCost = 0;
208 double maxNetCost = 0;
209 double maxSucRatio = 0;
210 double maxDelta = 0;
211
212 ofstream ofout("alldata.dat");
213 if (_verbose)
214 cout << " o Beginning global placement ...." << endl;
215
216 PMove Move(*this);
217
218 _initRowCost = RowCost = GetRowCost();
219 _initBinCost = BinCost = GetBinCost();
220 _initNetCost = NetCost = GetNetCost();
221
222 Cost = GetCost(RowCost, BinCost, NetCost);
223
224 if (_verbose)
225 {
226 cout << " o Initial RowCost = " << RowCost << endl;
227 cout << " o Initial BinCost = " << BinCost << endl;
228 cout << " o Initial NetCost = " << NetCost << endl;
229 cout << " o Initial Cost = " << Cost << endl;
230 cout << " o Computing Initial Temperature ..." << endl;
231 cout << " o bins size " << GetBinsSize() << endl;
232 cout << " o bins capa " << GetBinsCapa() << endl;
233 cout << " o subrows capa " << GetSubRowsCapa() << endl;
234 }
235 // Calcul de la temperature initiale
236 for (int i = 0; i < GetNInsToPlace(); ++i) {
237 if (!Move.Next(Dist))
238 {
239 cout << " o No More Mouvement Possible ....." << endl;
240 return;
241 }
242
243 double DeltaRowCost = Move.GetDeltaRowCost();
244 double DeltaBinCost = Move.GetDeltaBinCost();
245 double DeltaNetCost = Move.GetDeltaNetCost();
246
247 double DeltaCost = GetCost(DeltaRowCost, DeltaBinCost, DeltaNetCost);
248
249 if (Accept(Temperature, DeltaCost)) {
250 Move.Accept();
251
252 Accepted += 1;
253 RowCost += DeltaRowCost;
254 BinCost += DeltaBinCost;
255 NetCost += DeltaNetCost;
256 Cost += DeltaCost;
257
258 SumCost += Cost; SumSquare += Cost * Cost;
259 SumCostRow += RowCost; SumSquareRow += RowCost * RowCost;
260 SumCostBin += BinCost; SumSquareBin += BinCost * BinCost;
261 SumCostNet += NetCost; SumSquareNet += NetCost * NetCost;
262 } else {
263 Move.Reject();
264 }
265
266 _totalMoves += 1;
267 }
268
269 StdDev = GetStdDev(SumCost, SumSquare, Accepted);
270 GetStdDev(SumCostRow, SumSquareRow, Accepted);
271 GetStdDev(SumCostBin, SumSquareBin, Accepted);
272 GetStdDev(SumCostNet, SumSquareNet, Accepted);
273
274 Temperature = 20.0 * StdDev;
275 Iteration = (int)(5.0 * pow(GetNInsToPlace(), 1.33));
276 #ifdef PLACE_DEBUG
277 double Debug = GlobalPlaceDebugNetCost();
278 cout << "Debug = " << Debug << endl;
279 cout << "NetCost = " << NetCost << endl << endl;
280 //assert((NetCost - 1.0 <= Debug) && (Debug <= NetCost + 1.0));
281 #endif
282
283 // Placement
284
285 double firstTemperature = Temperature;
286 double firstCost = Cost;
287 double firstRowCost = RowCost;
288 double firstBinCost = BinCost;
289 double firstNetCost = NetCost;
290 double firstSucRatio = SucRatio;
291 double firstDist = Dist;
292 bool stucked = false;
293
294 do {
295 Accepted = 0;
296 SumCost = 0, SumCostRow = 0, SumCostBin = 0, SumCostNet = 0;
297 SumSquare = 0, SumSquareRow = 0, SumSquareBin = 0, SumSquareNet = 0;
298
299 for (int i = 0; i < Iteration; ++i) {
300 if (!Move.Next(Dist))
301 {
302 cout << " o No More Mouvement Possible ....." << endl;
303 stucked = true;
304 break;
305 }
306
307 double DeltaRowCost = Move.GetDeltaRowCost();
308 double DeltaBinCost = Move.GetDeltaBinCost();
309 double DeltaNetCost = Move.GetDeltaNetCost();
310
311 double DeltaCost = GetCost(DeltaRowCost, DeltaBinCost, DeltaNetCost);
312
313 if (Accept(Temperature, DeltaCost)) {
314 Move.Accept();
315
316 Accepted += 1;
317 RowCost += DeltaRowCost;
318 BinCost += DeltaBinCost;
319 NetCost += DeltaNetCost;
320 Cost += DeltaCost;
321
322 SumCost += Cost; SumSquare += Cost * Cost;
323 SumCostRow += RowCost; SumSquareRow += RowCost * RowCost;
324 SumCostBin += BinCost; SumSquareBin += BinCost * BinCost;
325 SumCostNet += NetCost; SumSquareNet += NetCost * NetCost;
326 } else {
327 Move.Reject();
328 }
329
330 _totalMoves += 1;
331 }
332 if (stucked)
333 break;
334
335 Loop += 1;
336 OldTemperature = Temperature;
337 StdDev = GetStdDev(SumCost, SumSquare, Accepted);
338 GetStdDev(SumCostRow, SumSquareRow, Accepted);
339 GetStdDev(SumCostBin, SumSquareBin, Accepted);
340 GetStdDev(SumCostNet, SumSquareNet, Accepted);
341
342 if (StdDev == 0.0)
343 Temperature = 0.0;
344 else
345 Temperature = Temperature * max(0.5, exp(-0.7 * Temperature / StdDev));
346 SucRatio = Accepted / (double)Iteration;
347 Dist = max(0.1, min(Dist * (1.0 - 0.44 + SucRatio), 1.0));
348
349 if (_verbose)
350 {
351 cout << "Loop = " << Loop << ", Temperature = " << Temperature << ", Cost = " << Cost << endl;
352 cout << " RowCost = " << RowCost << ", BinCost = " << BinCost << ", NetCost = " << NetCost << endl;
353 cout << " Success Ratio = " << SucRatio * 100.0 << "%, Dist = " << Dist << ", Delta = " << Temperature / OldTemperature << endl;
354
355 unsigned totalImpossibleMovements =
356 _impossibleExchangeMovementNumber
357 + _sourceEqualTargetMovementNumber
358 + _surOccupationTargetMovementNumber;
359 cout << " o Total impossible movements = " << totalImpossibleMovements << endl;
360 cout << " o " << 100.0 * _surOccupationTargetMovementNumber / totalImpossibleMovements
361 << " % suroccupied target" << endl;
362 cout << " o " << 100.0 * _sourceEqualTargetMovementNumber / totalImpossibleMovements
363 << " % source equal target" << endl;
364 cout << " o " << 100.0 * _impossibleExchangeMovementNumber / totalImpossibleMovements
365 << " % impossible exchange" << endl;
366 }
367 else cerr << ".";
368
369 if (_boolPlot)
370 {
371 if (Loop == 1)
372 {
373 maxTemperature = Temperature;
374 maxCost = Cost;
375 maxRowCost = firstRowCost;
376 maxBinCost = BinCost;
377 maxNetCost = NetCost;
378 maxSucRatio = SucRatio*100.0;
379 maxDelta = Temperature / OldTemperature * 2;
380
381 ofout << 0 << " " << log10(((firstTemperature/maxTemperature)+1.0)) << " "
382 << firstCost/maxCost << " "<< firstRowCost/maxRowCost << " "
383 << firstBinCost/maxBinCost << " " << firstNetCost/maxNetCost << " "
384 << (firstSucRatio*100.0)/maxSucRatio << " "
385 << firstDist << " "
386 << 1 << endl;
387 }
388
389 ofout << Loop << " " << log10(Temperature/maxTemperature+1.0) << " "
390 << Cost/maxCost << " " << RowCost/maxRowCost << " "
391 << BinCost/maxBinCost << " " << NetCost/maxNetCost << " "
392 << (SucRatio*100.0)/maxSucRatio << " " << Dist
393 << " " << (Temperature/OldTemperature)/maxDelta << endl;
394 }
395
396
397 #ifdef PLACE_DEBUG
398 double Debug = GlobalPlaceDebugNetCost();
399 cout << "Debug = " << Debug << endl;
400 cout << "NetCost = " << NetCost << endl << endl;
401 // assert ((NetCost - 1.0 <= Debug) && (Debug <= NetCost + 1.0));
402 #endif
403
404 } while (Temperature != 0.0 && StdDev > 0.0001 / Cost);
405
406 if (!_boolPlot)
407 unlink("alldata.dat");
408
409 if (!stucked)
410 {
411 // Freeze out
412
413 Accepted = 0;
414 SumCost = 0, SumCostRow = 0, SumCostBin = 0, SumCostNet = 0;
415 SumSquare = 0, SumSquareRow = 0, SumSquareBin = 0, SumSquareNet = 0;
416
417 for (int i = 0; i < Iteration; ++i) {
418 if (!Move.Next(Dist))
419 {
420 cout << " o No More Mouvement Possible ....." << endl;
421 stucked = true;
422 break;
423 }
424
425 double DeltaRowCost = Move.GetDeltaRowCost();
426 double DeltaBinCost = Move.GetDeltaBinCost();
427 double DeltaNetCost = Move.GetDeltaNetCost();
428
429 double DeltaCost = GetCost(DeltaRowCost, DeltaBinCost, DeltaNetCost);
430
431 if (Accept(Temperature, DeltaCost)) {
432 Move.Accept();
433
434 Accepted += 1;
435 RowCost += DeltaRowCost;
436 BinCost += DeltaBinCost;
437 NetCost += DeltaNetCost;
438 Cost += DeltaCost;
439
440 SumCost += Cost; SumSquare += Cost * Cost;
441 SumCostRow += RowCost; SumSquareRow += RowCost * RowCost;
442 SumCostBin += BinCost; SumSquareBin += BinCost * BinCost;
443 SumCostNet += NetCost; SumSquareNet += NetCost * NetCost;
444 } else {
445 Move.Reject();
446 }
447 _totalMoves += 1;
448 }
449 }
450
451 if (_verbose)
452 {
453 unsigned totalImpossibleMovements =
454 _impossibleExchangeMovementNumber
455 + _sourceEqualTargetMovementNumber
456 + _surOccupationTargetMovementNumber;
457 cout << " o Global Placement finished ....." << endl;
458 cout << " o Gain for RowCost = " << 100.0 * (_initRowCost - RowCost) / _initRowCost << "%" << endl;
459 cout << " o Gain for BinCost = " << 100.0 * (_initBinCost - BinCost) / _initBinCost << "%" << endl;
460 cout << " o Gain for NetCost = " << 100.0 * (_initNetCost - NetCost) / _initNetCost << "%" << endl;
461 cout << " o NetCost Estimated = " << NetCost << endl;
462 cout << " o Movements Stats ?! " << endl;
463 cout << " o " << _totalMoves << " Tried Moves" << endl;
464 cout << " o " << 100.0 * _acceptedMoveNumber / _totalMoves
465 << " % of accepted simple instance move" << endl;
466 cout << " o " << 100.0 * _acceptedExchangeNumber / _totalMoves
467 << " % of accepted instance exchange" << endl;
468 cout << " o " << 100.0 * _rejectedMoveNumber / _totalMoves
469 << " % of rejected simple instance move" << endl;
470 cout << " o " << 100.0 * _rejectedExchangeNumber / _totalMoves
471 << " % of rejected instance exchange" << endl;
472 cout << " o Impossible Movements Stats .... "<< endl;
473 cout << " o If you find these values interesting, call a doctor..." << endl;
474 cout << " o Total impossible movements = " << totalImpossibleMovements << endl;
475 cout << " o " << 100.0 * _surOccupationTargetMovementNumber / totalImpossibleMovements
476 << " % suroccupied target" << endl;
477 cout << " o " << 100.0 * _sourceEqualTargetMovementNumber / totalImpossibleMovements
478 << " % source equal target" << endl;
479 cout << " o " << 100.0 * _impossibleExchangeMovementNumber / totalImpossibleMovements
480 << " % impossible exchange" << endl;
481 }
482 }
483
484 PToPlaceIns&
GetRandIns()485 PPlacement::GetRandIns()
486 {
487 return *_toPlaceInss[(int) ((double)_nInsToPlace * rand() / (RAND_MAX + 1.0))];
488 }
489