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 <stdlib.h>
28 #include <limits.h>
29 #include <string.h>
30 using namespace std;
31
32 #include "PBin.h"
33
34 #include "PMove.h"
35
36 #ifndef Abs
37 #define Abs(x) ((x) < 0.0 ? -(x) : (x))
38 #endif
39
40 static double
PositionRand(const double Position,const double Distance,const double Max,const double Min)41 PositionRand(const double Position, const double Distance, const double Max, const double Min)
42 {
43 double BorneInf, BorneSup;
44
45 if ((BorneSup = Position + (double)(int)(Distance * Max + 0.5) ) > Max )
46 BorneSup = Max;
47
48 if ((BorneInf = Position - (double)(int)(Distance * Max + 0.5) ) < Min )
49 BorneInf = Min;
50
51 return BorneInf + (double)(int)((BorneSup - BorneInf) * rand() / (RAND_MAX+1.0));
52 }
53
PMove(PPlacement & placement)54 PMove::PMove(PPlacement& placement)
55 : _placement(placement)
56 , _srcIns (NULL)
57 , _srcBin(NULL)
58 , _srcBinInitCost(0.0)
59 , _srcSubRow(NULL)
60 , _srcRow(NULL)
61 , _srcRowInitCost(0.0)
62 , _srcWidth(0.0)
63 , _dstBin(NULL)
64 , _dstBinInitCost(0.0)
65 , _dstSubRow(NULL)
66 , _dstRow(NULL)
67 , _dstRowInitCost(0.0)
68 , _dstIns(NULL)
69 , _dstWidth(0.0)
70 {}
71
72 double
GetDeltaRowCost()73 PMove::GetDeltaRowCost()
74 {
75 double DeltaRowCost = -_srcRowInitCost;
76 DeltaRowCost -= _dstRowInitCost;
77 DeltaRowCost += Abs(_srcSubRow->GetCapa() - _srcSubRow->GetSize());
78 DeltaRowCost += Abs(_dstSubRow->GetCapa() - _dstSubRow->GetSize());
79 return DeltaRowCost;
80 }
81
82 double
GetDeltaBinCost()83 PMove::GetDeltaBinCost()
84 {
85 double DeltaBinCost = -_srcBinInitCost;
86 DeltaBinCost -= _dstBinInitCost;
87 DeltaBinCost += Abs(_srcBin->GetCapa() - _srcBin->GetSize());
88 DeltaBinCost += Abs(_dstBin->GetCapa() - _dstBin->GetSize());
89 #if 0
90 cerr << "hi" << endl;
91 cerr << _srcBinInitCost << endl;
92 cerr << _dstBinInitCost << endl;
93 cerr << DeltaBinCost << endl;
94 cerr << _srcBin->GetCapa() << endl;
95 cerr << _srcBin->GetSize() << endl;
96 cerr << _srcWidth << endl;
97 cerr << _dstWidth << endl;
98 #endif
99 return DeltaBinCost;
100 }
101
102 static const unsigned PONetSrc = 1;
103 static const unsigned PONetDst = 2;
104 static const unsigned PONetSrcDst = 3;
105
106 double
GetDeltaNetCost()107 PMove::GetDeltaNetCost()
108 {
109 // Find affected nets
110 // ==================
111
112 _affectedNets.clear();
113
114 for (PIns::PNets::const_iterator net = _srcIns->GetNets().begin(); net != _srcIns->GetNets().end(); ++net)
115 _affectedNets[static_cast<PONet*>(*net)] = PONetSrc;
116
117 if (_dstIns != NULL)
118 for (PIns::PNets::const_iterator net = _dstIns->GetNets().begin(); net != _dstIns->GetNets().end(); ++net)
119 {
120 PONet* ponet = static_cast<PONet*>(*net);
121
122 if (_affectedNets.find(ponet) == _affectedNets.end())
123 _affectedNets[ponet] = PONetDst;
124 else
125 _affectedNets[ponet] = PONetSrcDst;
126 }
127
128 // Compute delta
129 // =============
130
131 double Delta = 0;
132
133 for (map<PONet*, unsigned>::iterator it = _affectedNets.begin(); it != _affectedNets.end(); ++it) {
134 PONet* net = (*it).first;
135 unsigned Flag = (*it).second;
136
137 if (Flag == PONetSrc) {
138 net->TempBBox() = net->CurrentBBox();
139 if (net->TempBBox().Update(_srcBin->GetPos(), _dstBin->GetPos()).Empty()) {
140 for (vector<PElem*>::iterator elem = net->GetElems().begin(); elem != net->GetElems().end(); ++elem) {
141 net->TempBBox().Merge((*elem)->GetPos());
142 }
143 }
144
145 double width = net->TempBBox().GetWidth();
146 if (width == 0.0)
147 {
148 width = _srcBin->GetWidth() / 2.0;
149 }
150 net->TempCost() = net->TempBBox().GetHeight() + width;
151
152 Delta += net->TempCost() - net->CurrentCost();
153 #ifdef CHECK_COST
154 PBBox check_bbox;
155 vector<PElem*>::iterator efirst = net->GetElems().begin();
156 vector<PElem*>::iterator elast = net->GetElems().end();
157 while (efirst != elast)
158 check_bbox.Merge((*efirst++)->GetPos());
159
160 if (check_bbox != net->TempBBox()) {
161 cout << "error: mauvaise bbox : PONetSrc" << endl;
162 cout << " check_bbox = " << check_bbox << endl;
163 cout << " TempBBox = " << net->TempBBox() << endl;
164 cout << " CurrentBBox = " << net->CurrentBBox() << endl;
165 cout << " SrcPos = " << _srcBin->GetPos() << endl;
166 cout << " DstPos = " << _dstBin->GetPos() << endl;
167 }
168 #endif
169 } else if (Flag == PONetDst) {
170 net->TempBBox() = net->CurrentBBox();
171 if (net->TempBBox().Update(_dstBin->GetPos(), _srcBin->GetPos()).Empty()) {
172 for (vector<PElem*>::iterator elem = net->GetElems().begin(); elem != net->GetElems().end(); ++elem) {
173 net->TempBBox().Merge((*elem)->GetPos());
174 }
175 }
176 double width = net->TempBBox().GetWidth();
177 if (width == 0.0)
178 {
179 width = _dstBin->GetWidth() / 2.0;
180 }
181 net->TempCost() = net->TempBBox().GetHeight() + width;
182 Delta += net->TempCost() - net->CurrentCost();
183 #ifdef CHECK_COST
184 PBBox check_bbox;
185 vector<PElem*>::iterator efirst = net->GetElems().begin();
186 vector<PElem*>::iterator elast = net->GetElems().end();
187 while (efirst != elast)
188 check_bbox.Merge((*efirst++)->GetPos());
189
190 if (check_bbox != net->TempBBox()) {
191 cout << "error: mauvaise bbox : PONetDst" << endl;
192 cout << " check_bbox = " << check_bbox << endl;
193 cout << " TempBBox = " << net->TempBBox() << endl;
194 cout << " CurrentBBox = " << net->CurrentBBox() << endl;
195 cout << " SrcPos = " << _dstBin->GetPos() << endl;
196 cout << " DstPos = " << _srcBin->GetPos() << endl;
197 }
198 #endif
199 }
200 }
201
202 return Delta;
203 }
204
205 void
Move()206 PMove::Move()
207 {
208 if (_dstIns == NULL) {
209 _srcBin->RemoveIns(_srcIns);
210 _dstBin->AddIns(_srcIns);
211 } else {
212 _srcBin->RemoveIns(_srcIns);
213 _dstBin->AddIns(_srcIns);
214 _dstBin->RemoveFrontIns(_dstIns);
215 _srcBin->AddIns(_dstIns);
216 }
217 }
218
219 bool
Next(double Dist)220 PMove::Next(double Dist)
221 {
222 bool MoveCondition;
223 unsigned nbrefused = 0;
224
225 // Choisi un mouvement
226 // ===================
227
228 do {
229 PPos SrcPos;
230 double DstX;
231 _srcIns = NULL;
232 _dstIns = NULL;
233 MoveCondition = true;
234
235 _srcIns = &_placement.GetRandIns();
236 _srcBin = &(_srcIns->GetBin());
237 _srcSubRow = _srcBin->GetSubRow();
238 _srcRow = _srcSubRow->GetRow();
239 SrcPos = _srcBin->GetPos();
240 _srcWidth = _srcIns->GetWidth();
241 _srcBinInitCost = Abs(_srcBin->GetCapa() - _srcBin->GetSize());
242 _srcRowInitCost = Abs(_srcSubRow->GetCapa() - _srcSubRow->GetSize());
243
244 _dstRow = &_placement.GetRow(_srcRow, Dist);
245 DstX = PositionRand(SrcPos.GetX(), Dist, _dstRow->GetMaxX(), _dstRow->GetMinX());
246
247 _dstSubRow = &(_dstRow->GetSubRow(DstX));
248 _dstBin = &(_dstSubRow->GetBin(DstX));
249
250 _dstBinInitCost = Abs(_dstBin->GetCapa() - _dstBin->GetSize());
251 _dstRowInitCost = Abs(_dstSubRow->GetCapa() - _dstSubRow->GetSize());
252
253 if (_dstBin == _srcBin)
254 {
255 MoveCondition = false;
256 _placement.IncrSourceEqualTargetMovementNumber();
257 }
258
259 if (_dstBin->UnderOccupied(_placement.GetMargin()))
260 {
261 // Le bin destination est sous-occup�
262 // On d�place l'instance
263 if (_dstSubRow->GetMax() - _dstSubRow->GetSize() < _srcWidth)
264 {
265 MoveCondition = false;
266 _placement.IncrSurOccupationTargetMovementNumber();
267 }
268 }
269 else
270 {
271 _dstIns = _dstBin->GetToPlaceInss().front();
272 _dstWidth = _dstIns->GetWidth();
273 if (_srcSubRow->GetMax() - _srcSubRow->GetSize() < _dstWidth - _srcWidth)
274 {
275 MoveCondition = false;
276 _placement.IncrImpossibleExchangeMovementNumber();
277 }
278 if (_dstSubRow->GetMax() - _dstSubRow->GetSize() < _srcWidth - _dstWidth)
279 {
280 MoveCondition = false;
281 _placement.IncrImpossibleExchangeMovementNumber();
282 }
283 }
284 if (!MoveCondition)
285 ++nbrefused;
286 if (nbrefused > (unsigned)(1.5 * _placement.GetNInsToPlace()))
287 return false;
288 } while (!MoveCondition);
289
290 // Deplace les instances
291 // =====================
292 _srcBin->IncrementSourceHits();
293 _dstBin->IncrementTargetHits();
294
295 Move();
296 return true;
297 }
298
299
300 void
Accept()301 PMove::Accept()
302 {
303 if (_dstIns == NULL)
304 _placement.IncrAcceptedMoveNumber();
305 else
306 _placement.IncrAcceptedExchangeNumber();
307 // Sauvegarde des cout des nets
308 for (map<PONet*, unsigned>::iterator it = _affectedNets.begin(); it != _affectedNets.end(); ++it) {
309 PONet* net = (*it).first;
310 unsigned Flag = (*it).second;
311
312 if (Flag == PONetSrc || Flag == PONetDst) {
313 net->SaveTemp();
314 }
315 }
316 }
317
318 void
Reject()319 PMove::Reject()
320 {
321 if (_dstIns == NULL) {
322 _placement.IncrRejectedMoveNumber();
323 _dstBin->RemoveBackIns(_srcIns);
324 _srcBin->AddIns(_srcIns);
325 } else {
326 _placement.IncrRejectedExchangeNumber();
327 _srcBin->RemoveBackIns(_dstIns);
328 _dstBin->RemoveBackIns(_srcIns);
329 _dstBin->AddIns(_dstIns);
330 _srcBin->AddIns(_srcIns);
331 }
332 }
333