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
28 #include <math.h>
29 #include <unistd.h>
30 #include <string.h>
31 #include <algorithm>
32 using namespace std;
33
34 #include "mut.h"
35 #include "mph.h"
36 #include "mpu.h"
37 #include "mlo.h"
38 #include "mlu.h"
39
40 #include "PMove.h"
41 #include "PConstants.h"
42 #include "PDetPlacement.h"
43
44 #include "PPlacement.h"
45
46 double
DetPlaceDebugNetCost()47 PPlacement::DetPlaceDebugNetCost()
48 {
49 double NetCost = 0.0;
50
51 vector<PONet*>::iterator nfirst = _nets.begin();
52 vector<PONet*>::iterator nlast = _nets.end();
53 while (nfirst != nlast) {
54 PONet& net = **nfirst++;
55 PBBox bbox;
56 vector<PElem*>::iterator ifirst = net.GetElems().begin();
57 vector<PElem*>::iterator ilast = net.GetElems().end();
58 if (ifirst != ilast)
59 {
60 while (ifirst != ilast)
61 bbox.Merge((*ifirst++)->GetPos());
62
63 double width = bbox.GetWidth();
64
65 NetCost += bbox.GetHeight() + width;
66 }
67 }
68 return NetCost;
69 }
70
71 void
PlaceFinal()72 PPlacement::PlaceFinal()
73 {
74 // Detailed Placement
75 if (_verbose) cout << " o Final Optimization in process ..." << endl;
76 FinalInitialize();
77 if (_verbose)
78 {
79 if (FinalOptimize())
80 cout << " o Final Optimization succeeded ..." << endl;
81 else
82 cout << " o No Optimization possible" << endl;
83 }
84 double NewCost = DetPlaceDebugNetCost();
85 if (_verbose)
86 {
87 cout << " o Final Net Cost ..... " << NewCost << endl;
88 cout << " o Final Net Cost Optimization ..... "
89 << 100.0 * (_detInitNetCost - NewCost) / _detInitNetCost << "%" << endl;
90 cout << " o Total Net Optimization .... "
91 << 100.0 * (_initNetCost - NewCost) / _initNetCost << "%" << endl;
92 }
93 }
94
95 void
FinalInitialize()96 PPlacement::FinalInitialize()
97 {
98 // on compte le nombre de subrow
99 // on prend uniquement celle qui ont des instances
100 unsigned nbsubrows = 0;
101 for (PRows::iterator rit = _rows.begin(); rit != _rows.end(); rit++)
102 {
103 for (PRow::PSubRows::iterator srit = (*rit)->GetSubRows().begin();
104 srit != (*rit)->GetSubRows().end();
105 srit++)
106 {
107 if ((*srit)->GetNIns() > 0)
108 ++nbsubrows;
109 }
110 }
111 _detSubRows.reserve(nbsubrows);
112
113 for (PRows::iterator rit = _rows.begin(); rit != _rows.end(); rit++)
114 {
115 for (PRow::PSubRows::iterator srit = (*rit)->GetSubRows().begin();
116 srit != (*rit)->GetSubRows().end();
117 srit++)
118 {
119 if ((*srit)->GetNIns() > 0)
120 _detSubRows.push_back(new PDetSubRow(**srit));
121 }
122 }
123
124 PDetInsMap pdetinsmap;
125
126 for (PDetSubRows::iterator dsrit = _detSubRows.begin();
127 dsrit != _detSubRows.end(); dsrit++)
128 {
129 for (PDetSubRow::PDetInsVector::iterator it = (*dsrit)->GetInssVector().begin();
130 it != (*dsrit)->GetInssVector().end();
131 it++)
132 {
133 pdetinsmap[(*it)->GetInstance()->INSNAME] = *it;
134 (*it)->SetSubRow(*dsrit);
135 }
136 }
137
138 for (PONets::iterator nit = _nets.begin(); nit != _nets.end(); nit++)
139 {
140 for (PONet::PElems::iterator eit = (*nit)->GetElems().begin();
141 eit != (*nit)->GetElems().end();
142 eit++)
143 {
144 PToPlaceIns* ptoplaceins = dynamic_cast<PToPlaceIns*>(*eit);
145 if (ptoplaceins)
146 {
147 PDetInsMap::iterator iit =
148 pdetinsmap.find(ptoplaceins->GetInstance()->INSNAME);
149 if (iit == pdetinsmap.end())
150 {
151 cerr << "det ins " << ptoplaceins->GetInstance()->INSNAME
152 << "is not present in data... " << endl;
153 exit(1);
154 }
155 *eit = iit->second;
156 }
157 }
158 }
159 //verification
160 for (PONets::iterator nit = _nets.begin(); nit != _nets.end(); nit++)
161 {
162 for (PONet::PElems::iterator eit = (*nit)->GetElems().begin();
163 eit != (*nit)->GetElems().end();
164 eit++)
165 {
166 if (dynamic_cast<PToPlaceIns*>(*eit))
167 {
168 cerr << " o INTERNAL ERROR: FinalInitialize" << endl;
169 exit(1);
170 }
171 }
172 }
173 // on efface ce qui ne nous sert plus.
174 //_rows.clear();
175 //_toPlaceInss.clear();
176 //_rowsYMax.clear();
177 //_rowsYMinInv.clear();
178
179 //expanding instances in subrows
180 for (PDetSubRows::iterator dsrit = _detSubRows.begin();
181 dsrit != _detSubRows.end(); dsrit++)
182 {
183 (*dsrit)->ExpandInstances(_eqMargin);
184 }
185
186 // Updating All _nets BBoxs
187 DetPlaceNetCost();
188 }
189
190 // ======================================================================
191 // double DetPlaceNetCost();
192 // ======================================================================
193 double
DetPlaceNetCost()194 PPlacement::DetPlaceNetCost()
195 {
196 double NetCost = 0.0;
197
198 vector<PONet*>::iterator nfirst = _nets.begin();
199 vector<PONet*>::iterator nlast = _nets.end();
200 while (nfirst != nlast) {
201 PONet& net = **nfirst++;
202 PBBox& bbox = net.CurrentBBox();
203 vector<PElem*>::iterator ifirst = net.GetElems().begin();
204 vector<PElem*>::iterator ilast = net.GetElems().end();
205 while (ifirst != ilast)
206 bbox.Merge((*ifirst++)->GetPos());
207
208 NetCost += bbox.GetHeight() + bbox.GetWidth();
209 }
210 return NetCost;
211 }
212
213 // ======================================================================
214 // bool FinalOptimize()
215 // ======================================================================
216 bool
FinalOptimize()217 PPlacement::FinalOptimize()
218 {
219 int Loop = 0;
220 //double NewCost;
221 double InitCost = DetPlaceDebugNetCost();
222 _detInitNetCost = InitCost;
223 if (_verbose)
224 cout << " o Net Cost before Final Optimization... "
225 << InitCost << endl;
226 bool ContinueCondition = true;
227 bool OptimizationResult = false;
228 while (ContinueCondition && (Loop < _maxDetLoop)) {
229 ContinueCondition = false;
230
231 for (PDetSubRows::iterator dsrit = _detSubRows.begin();
232 dsrit != _detSubRows.end(); dsrit++)
233 {
234 if ((*dsrit)->FinalOptimize())
235 {
236 ContinueCondition = true;
237 OptimizationResult = true;
238 }
239 /*NewCost =*/ DetPlaceDebugNetCost();
240 //InitCost = NewCost;
241 }
242 ++Loop;
243 }
244 return OptimizationResult;
245 }
246
247 // ======================================================================
248 // int Save()
249 // ======================================================================
250 int
Save()251 PPlacement::Save() {
252 char* phfigname;
253 struct phfig* physicalfig;
254
255 if (!_prePlaceFig) {
256 physicalfig = addphfig(_fileName);
257 phfigname = _fileName;
258 if (_verbose) cout << "NO PREPLACEMENT GIVEN" << endl;
259 physicalfig->XAB1 =(int)(BBox.GetMinX() * PITCH);
260 physicalfig->XAB2 =(int)(BBox.GetMaxX() * PITCH);
261 physicalfig->YAB1 =(int)(BBox.GetMinY() * PITCH);
262 physicalfig->YAB2 =(int)(BBox.GetMaxY() * PITCH);
263 } else {
264 if (_verbose) cout << "PREPLACEMENT GIVEN" << endl;
265 physicalfig = _prePlaceFig;
266 phfigname = physicalfig->NAME;
267 physicalfig->NAME = _fileName;
268 }
269
270 for (PDetSubRows::iterator dsrit = _detSubRows.begin();
271 dsrit != _detSubRows.end(); dsrit++)
272 {
273 for (PDetSubRow::PDetInsVector::iterator it = (*dsrit)->GetInssVector().begin();
274 it != (*dsrit)->GetInssVector().end(); it++)
275 {
276 (*it)->Save(physicalfig, _dx, _dy);
277 }
278 }
279
280 for (PCons::const_iterator cit = _cons.begin();
281 cit != _cons.end();
282 cit++) {
283 if (_ringPlaceCons) {
284 (*cit)->RingSave(physicalfig, _dx, _dy);
285 } else {
286 (*cit)->Save(physicalfig, _dx, _dy);
287 }
288 }
289
290 int superr = AddRowend(physicalfig);
291
292 savephfig(physicalfig);
293 physicalfig->NAME = phfigname;
294
295 return superr;
296 }
297
298 // ======================================================================
299 // void AddRowend(struct phfig* physicalfig)
300 // ======================================================================
AddRowend(struct phfig * physicalfig)301 int PPlacement::AddRowend(struct phfig* physicalfig)
302 {
303 int superr = 0;
304
305 long xmax = (long) (BBox.GetMaxX());
306 long ymax = (long) (BBox.GetMaxY() / ROWHEIGHT);
307
308 // tab represents the circuit
309 bool tab[xmax][ymax];
310
311 for (long tabx = 0 ; tabx < xmax ; tabx++)
312 for (long taby = 0 ; taby < ymax ; taby++)
313 tab[tabx][taby] = false;
314
315 // look for rowend instances already present
316 // if any, we save the highest number of them
317 // we will then create instances whith a bigger number
318 // this prevents having two instances with the same name
319 int rowendcount = 0;
320 int tiecount = 0;
321 for (struct phins* It = physicalfig->PHINS ; It ; It = It->NEXT)
322 {
323 if ( strncmp(It->INSNAME,"rowendx0_",9) == 0 )
324 {
325 char *nb = strdup(It->INSNAME + 9);
326 if ( atoi(nb) > rowendcount ) rowendcount = atoi(nb);
327 free( nb );
328 }
329
330 if ( strncmp(It->INSNAME,"tiex0_",6) == 0 )
331 {
332 char *nb = strdup(It->INSNAME + 6);
333 if ( atoi(nb) > tiecount ) tiecount = atoi(nb);
334 free( nb );
335 }
336
337 // fill the tab with instances (true = instance is present)
338 struct phfig* insfig = getphfig(It->FIGNAME, '0');
339 long width = (long) ((insfig->XAB2 - insfig->XAB1) / PITCH);
340 long height = (long) ((insfig->YAB2 - insfig->YAB1) / (PITCH * ROWHEIGHT));
341 long posx = (long) ((It->XINS - _dx) / PITCH);
342 long posy = (long)((It->YINS - _dy) / (PITCH * ROWHEIGHT));
343
344 for (long ydecal=0 ; ydecal < height ; ydecal++)
345 {
346 for (long xdecal=0 ; xdecal < width ; xdecal++)
347 {
348 if (tab[posx + xdecal][posy + ydecal] == true)
349 {
350 cerr << "ERROR : instances superposed : " << It->INSNAME << endl;
351 superr = 1;
352 }
353 tab[posx + xdecal][posy + ydecal] = true;
354 }
355 }
356
357 }
358 ++rowendcount;
359 ++tiecount;
360
361 for (long tabx = 0 ; tabx < xmax ; tabx++)
362 {
363 for (long taby = 0 ; taby < ymax ; taby++)
364 {
365 if (tab[tabx][taby] == false)
366 {
367 // add tie cell?
368 if ((tabx + 1 < xmax) && (tab[tabx+1][taby] == false))
369 {
370 char buf[256];
371 char sym;
372 sprintf(buf,"tiex0_%d",rowendcount++);
373
374 if (taby%2 == 0)
375 {
376 if (_rowZeroOrientation) sym = NOSYM;
377 else sym = SYM_Y;
378 }
379 else // taby%2 == 1
380 {
381 if (_rowZeroOrientation) sym = SYM_Y;
382 else sym = NOSYM;
383 }
384
385 addphins(physicalfig,"tie_x0",buf,sym,(long) (tabx * PITCH + _dx),(long) (taby * ROWHEIGHT * PITCH + _dy));
386 tab[tabx][taby]= true;
387 tab[tabx+1][taby]= true;
388 } else
389 // add rowend cell
390 {
391 char buf[256];
392 char sym;
393 sprintf(buf,"rowendx0_%d",rowendcount++);
394
395 if (taby%2 == 0)
396 {
397 if (_rowZeroOrientation) sym = NOSYM;
398 else sym = SYM_Y;
399 }
400 else // taby%2 == 1
401 {
402 if (_rowZeroOrientation) sym = SYM_Y;
403 else sym = NOSYM;
404 }
405
406 addphins(physicalfig,"rowend_x0",buf,sym,(long) (tabx * PITCH + _dx),(long) (taby * ROWHEIGHT * PITCH + _dy));
407 tab[tabx][taby]= true;
408 }
409
410 }
411 }
412 }
413 return superr;
414 }
415