# Katabatic Documentation

# Katabatic - Routing Toolbox

GCell.h
1 // -*- C++ -*-
2 //
3 // This file is part of the Coriolis Software.
4 // Copyright (c) UPMC 2008-2018, All Rights Reserved
5 //
6 // +-----------------------------------------------------------------+
7 // | C O R I O L I S |
8 // | K a t a b a t i c - Routing Toolbox |
9 // | |
10 // | Author : Jean-Paul CHAPUT |
11 // | E-mail : Jean-Paul.Chaput@lip6.fr |
12 // | =============================================================== |
13 // | C++ Header : "./katabatic/GCell.h" |
14 // +-----------------------------------------------------------------+
15
16
17 #ifndef KATABATIC_GCELL_H
18 #define KATABATIC_GCELL_H
19
20 #include <set>
21 #include <vector>
22 #include <iostream>
23 #include <functional>
24
25 #include "hurricane/DbU.h"
26 #include "hurricane/Point.h"
27 #include "hurricane/Box.h"
28 #include "hurricane/Interval.h"
29 #include "hurricane/ExtensionGo.h"
30 namespace Hurricane {
31 class Name;
32 class RoutingPad;
33 }
34
35 #include "crlcore/RoutingLayerGauge.h"
36 #include "katabatic/Constants.h"
37 #include "katabatic/AutoSegments.h"
38
39
40 namespace Katabatic {
41
42
43 using std::set;
44 using std::vector;
45 using std::ostream;
46 using std::binary_function;
47 using Hurricane::_TName;
48 using Hurricane::Record;
49 using Hurricane::Name;
50 using Hurricane::DbU;
51 using Hurricane::Point;
52 using Hurricane::Box;
53 using Hurricane::Interval;
54 using Hurricane::ExtensionGo;
55 using Hurricane::RoutingPad;
56
57 class GCellGrid;
58 class AutoContact;
59 class AutoSegment;
60
61
62 enum GCellFunctionFlags { NoUpdate = 0x00000001 };
63
64
65 // -------------------------------------------------------------------
66 // Class : "Katabatic::GCell".
67
68 enum GCellFlag { GCellInvalidated = 0x00000001
69 , GCellSaturated = 0x00000002
70 , GCellUnderIoPad = 0x00000004
71 };
72
73
74 class GCell : public ExtensionGo {
75
76 public:
77 class CompareByIndex : public binary_function<const GCell*,const GCell*,bool> {
78 public:
79 bool operator() ( const GCell* lhs, const GCell* rhs );
80 };
81 class CompareByDensity : public binary_function<GCell*,GCell*,bool> {
82 public:
83 CompareByDensity ( unsigned int depth );
84 bool operator() ( GCell* lhs, GCell* rhs );
85 private:
86 unsigned int _depth;
87 };
88 class CompareByKey : public binary_function<const GCell*,const GCell*,bool> {
89 public:
90 bool operator() ( const GCell* lhs, const GCell* rhs );
91 };
92
93 class Key {
94 private:
95 GCell* _gcell;
96 float _density;
97 public:
98 inline Key ( GCell*, unsigned int depth );
99 inline float getDensity () const;
100 inline GCell* getGCell () const;
101 inline void update ( unsigned int depth );
102 friend bool operator< ( const Key&, const Key& );
103 };
104 public:
105 typedef set<GCell*,CompareByIndex> SetIndex;
106
107 public:
108 // Static Utilities.
109 static bool areDensityConnex ( GCell* a, GCell* b );
110 // Static Accessors.
111 static size_t getAllocateds ();
112 static DbU::Unit getTopRightShrink ();
113 static const Name& getStaticName ();
114 virtual const Name& getName () const;
115 // Accessors.
116 inline bool isSaturated () const;
117 bool isSaturated ( unsigned int depth ) const;
118 inline bool isValid () const;
119 inline bool isUnderIoPad () const;
120 bool isAboveDensity ( float threshold ) const;
121 bool hasFreeTrack ( size_t depth, float reserve ) const;
122 inline GCellGrid* getGCellGrid () const;
123 inline unsigned int getDepth () const;
124 inline unsigned int getIndex () const;
125 unsigned int getRow () const;
126 unsigned int getColumn () const;
127 GCell* getLeft () const;
128 GCell* getRight () const;
129 GCell* getUp () const;
130 GCell* getDown () const;
131 void getDensities ( float* ) const;
132 virtual void translate ( const DbU::Unit&, const DbU::Unit& );
133 virtual Box getBoundingBox () const;
134 inline Point getCenter () const;
135 inline DbU::Unit getX () const;
136 inline DbU::Unit getY () const;
137 inline DbU::Unit getXMax () const;
138 inline DbU::Unit getYMax () const;
139 Interval getSide ( unsigned int ) const;
140 float getHCapacity () const;
141 float getVCapacity () const;
142 float getDensity ( unsigned int flags=0 ) const;
143 float getAverageHVDensity () const;
144 float getMaxHVDensity () const;
145 inline float getCDensity ( unsigned int flags=0 ) const;
146 inline float getWDensity ( unsigned int depth, unsigned int flags=0 ) const;
147 inline DbU::Unit getBlockage ( unsigned int depth ) const;
148 inline float getFragmentation ( unsigned int depth ) const;
149 inline float getFeedthroughs ( unsigned int depth ) const;
150 inline float getGlobalsCount ( unsigned int depth ) const;
151 inline const vector<AutoSegment*>& getHSegments () const;
152 inline const vector<AutoSegment*>& getVSegments () const;
153 inline const vector<AutoContact*>& getContacts () const;
154 AutoSegments getHStartSegments ();
155 AutoSegments getVStartSegments ();
156 AutoSegments getHStopSegments ();
157 AutoSegments getVStopSegments ();
158 inline AutoSegments getStartSegments ( unsigned int direction );
159 inline AutoSegments getStopSegments ( unsigned int direction );
160 size_t getRoutingPads ( set<RoutingPad*>& );
161 inline const Key& getKey () const;
162 size_t checkDensity () const;
163 bool checkEdgeSaturation ( size_t hreserved, size_t vreserved) const;
164 // Modifiers.
165 void addBlockage ( unsigned int depth, DbU::Unit );
166 inline void addHSegment ( AutoSegment* );
167 inline void addVSegment ( AutoSegment* );
168 inline void addContact ( AutoContact* );
169 void removeVSegment ( AutoSegment* );
170 void removeHSegment ( AutoSegment* );
171 void removeContact ( AutoContact* );
172 void updateContacts ();
173 size_t updateDensity ();
174 inline void updateKey ( unsigned int depth );
175 bool stepBalance ( unsigned int depth, SetIndex& invalidateds );
176 void rpDesaturate ( set<Net*>& );
177 bool stepDesaturate ( unsigned int depth
178 , set<Net*>&, AutoSegment*& moved
179 , unsigned int flags=0 );
180 bool stepNetDesaturate ( unsigned int depth
181 , set<Net*>& globalNets
182 , SetIndex& invalidateds );
183 inline void invalidateCt ();
184 inline void setUnderIoPad ();
185 void truncDensities ();
186 // Inspector Management.
187 Record* _getRecord () const;
188 string _getString () const;
189 inline string _getTypeName () const;
190 void _xmlWrite ( ostream& o ) const;
191
192 private:
193 // Static Attributes.
194 static const Name _goName;
195 static size_t _allocateds;
196 static DbU::Unit _topRightShrink;
197 // Attributes.
198 GCellGrid* _gcellGrid;
199 unsigned int _index;
200 vector<AutoSegment*> _vsegments;
201 vector<AutoSegment*> _hsegments;
202 vector<AutoContact*> _contacts;
203 Box _box;
204 size_t _depth;
205 size_t _pinDepth;
206 DbU::Unit* _blockages;
207 float _cDensity;
208 float* _densities;
209 float* _feedthroughs;
210 float* _fragmentations;
211 float* _globalsCount;
212 unsigned int _flags;
213 Key _key;
214
215 protected:
216 // Constructors & Destructors.
217 GCell ( GCellGrid* gcellGrid
218 , unsigned int index
219 , const Box& box
220 );
221 inline ~GCell ();
222 inline void _postCreate ();
223 inline void _preDestroy ();
224 static GCell* create ( GCellGrid* gcellGrid
225 , unsigned int index
226 , Box box
227 );
228 private:
229 GCell ( const GCell& );
230 GCell& operator= ( const GCell& );
231
232 friend class GCellGrid;
233 };
234
235
236 // GCell Inline Functions.
237 inline bool GCell::isSaturated () const { return _flags&GCellSaturated; }
238 inline bool GCell::isValid () const { return not (_flags&GCellInvalidated); }
239 inline bool GCell::isUnderIoPad () const { return _flags&GCellUnderIoPad; }
240 inline GCellGrid* GCell::getGCellGrid () const { return _gcellGrid; }
241 inline unsigned int GCell::getDepth () const { return _depth; }
242 inline unsigned int GCell::getIndex () const { return _index; }
243 inline Point GCell::getCenter () const { return _box.getCenter(); }
244 inline DbU::Unit GCell::getX () const { return _box.getXMin(); }
245 inline DbU::Unit GCell::getY () const { return _box.getYMin(); }
246 inline DbU::Unit GCell::getXMax () const { return _box.getXMax(); }
247 inline DbU::Unit GCell::getYMax () const { return _box.getYMax(); }
248 inline const vector<AutoSegment*>& GCell::getVSegments () const { return _vsegments; }
249 inline const vector<AutoSegment*>& GCell::getHSegments () const { return _hsegments; }
250 inline const vector<AutoContact*>& GCell::getContacts () const { return _contacts; }
251 inline string GCell::_getTypeName () const { return _TName("GCell"); }
252 inline void GCell::invalidateCt () { _flags |= GCellInvalidated; }
253 inline void GCell::setUnderIoPad() { _flags |= GCellUnderIoPad; }
254 inline const GCell::Key& GCell::getKey () const { return _key; }
255 inline void GCell::updateKey ( unsigned int depth ) { _key.update(depth); }
256
257 inline AutoSegments GCell::getStartSegments ( unsigned int direction )
258 { return (direction&KbHorizontal) ? getHStartSegments() : getVStartSegments(); }
259
260 inline AutoSegments GCell::getStopSegments ( unsigned int direction )
261 { return (direction&KbHorizontal) ? getHStopSegments() : getVStopSegments(); }
262
263 inline float GCell::getCDensity ( unsigned int flags ) const
264 { if (not isValid() and not(flags & NoUpdate)) const_cast< GCell*>(this)->updateDensity(); return _cDensity; }
265
266 inline float GCell::getWDensity ( unsigned int depth, unsigned int flags ) const
267 { if (not isValid() and not(flags & NoUpdate)) const_cast< GCell*>(this)->updateDensity(); return _densities[depth]; }
268
269 inline float GCell::getFragmentation ( unsigned int depth ) const
270 { if (not isValid()) const_cast< GCell*>(this)->updateDensity(); return _fragmentations[depth]; }
271
272 inline float GCell::getFeedthroughs ( unsigned int depth ) const
273 { if (not isValid()) const_cast< GCell*>(this)->updateDensity(); return _feedthroughs[depth]; }
274
275 inline float GCell::getGlobalsCount ( unsigned int depth ) const
276 { if (not isValid()) const_cast< GCell*>(this)->updateDensity(); return _globalsCount[depth]; }
277
278 inline DbU::Unit GCell::getBlockage ( unsigned int depth ) const
279 { return (depth<_depth) ? _blockages[depth] : 0; }
280
281 inline void GCell::addVSegment ( AutoSegment* segment )
282 { invalidateCt(); _vsegments.push_back(segment); }
283
284 inline void GCell::addHSegment ( AutoSegment* segment )
285 { invalidateCt(); _hsegments.push_back(segment); }
286
287 inline void GCell::addContact ( AutoContact* contact )
288 { invalidateCt(); _contacts.push_back(contact); }
289
290
291 // GCell::CompareByIndex Inline Functions.
292 inline bool GCell::CompareByIndex::operator() ( const GCell* lhs, const GCell* rhs )
293 { return ( lhs->getIndex() < rhs->getIndex() ); }
294
295
296 // GCell::Key Inline Functions.
297 inline GCell::Key::Key ( GCell* owner, unsigned int depth ) : _gcell(owner), _density(owner->getWDensity(depth,NoUpdate)) {}
298 inline float GCell::Key::getDensity () const { return _density; }
299 inline GCell* GCell::Key::getGCell () const { return _gcell; }
300 inline void GCell::Key::update ( unsigned int depth ) { _density=_gcell->getWDensity(depth); }
301
302 inline bool operator< ( const GCell::Key& lhs, const GCell::Key& rhs )
303 {
304 //float difference = Hurricane::roundfp ( lhs._density - rhs._density );
305 float difference = lhs._density - rhs._density;
306 if (difference != 0.0) return (difference > 0.0);
307
308 return lhs._gcell->getIndex() < rhs._gcell->getIndex();
309 }
310
311
312 // -------------------------------------------------------------------
313 // Class : "GCellDensitySet".
314
315 class GCellDensitySet {
316 public:
317 GCellDensitySet ( unsigned int depth );
318 GCellDensitySet ( unsigned int depth, const std::vector<GCell*>& );
319 ~GCellDensitySet ();
320 inline bool empty () const;
321 inline size_t size () const;
322 inline const std::set<GCell*,GCell::CompareByKey>&
323 getGCells () const;
324 inline void insert ( GCell* );
325 inline void erase ( GCell* );
326 inline void unqueue ( GCell* );
327 void requeue ();
328 private:
329 unsigned int _depth;
330 std::set<GCell*,GCell::CompareByKey> _set;
331 GCell::SetIndex _requests;
332 };
333
334
335 inline bool GCellDensitySet::empty () const { return _set.empty(); }
336 inline size_t GCellDensitySet::size () const { return _set.size(); }
337 inline void GCellDensitySet::insert ( GCell* gcell ) { _requests.insert( gcell ); }
338 inline void GCellDensitySet::erase ( GCell* gcell ) { if (not _set.empty()) _set.erase( gcell ); }
339 inline void GCellDensitySet::unqueue ( GCell* gcell ) { insert( gcell ); }
340 inline const std::set<GCell*,GCell::CompareByKey>& GCellDensitySet::getGCells () const { return _set; }
341
342
343 // -------------------------------------------------------------------
344 // Utilities.
345
346
347 string getVectorString ( float*, size_t );
348
349
350 typedef std::vector<GCell*> GCellVector;
351
352
353 } // End of Katabatic namespace.
354
355
356 INSPECTOR_P_SUPPORT(Katabatic::GCell);
357
358
359 #endif // KATABATIC_GCELL_H
Katabatic::GCell::getY
DbU::Unit getY() const
Definition: GCell.h:245
Katabatic::GCell::CompareByDensity
GCell Density Comparison Functor.
Definition: GCell.h:81
Katabatic::GCell::addContact
void addContact(AutoContact *)
Definition: GCell.h:287
Katabatic::GCellDensitySet::insert
void insert(GCell *)
Definition: GCell.h:337
Hurricane::Box::getXMax
const DbU::Unit & getXMax() const
Katabatic::GCell::getRow
unsigned int getRow() const
Definition: GCell.cpp:461
Katabatic::GCell::translate
virtual void translate(const DbU::Unit &, const DbU::Unit &)
Definition: GCell.cpp:1272
Katabatic::GCell::getColumn
unsigned int getColumn() const
Definition: GCell.cpp:465
Katabatic::GCell::getContacts
const vector< AutoContact * > & getContacts() const
Definition: GCell.h:250
Katabatic::GCell::getHStartSegments
AutoSegments getHStartSegments()
Definition: GCell.cpp:497
Katabatic::GCell::getVSegments
const vector< AutoSegment * > & getVSegments() const
Definition: GCell.h:248
Katabatic::GCell::getVCapacity
float getVCapacity() const
Definition: GCell.cpp:539
Katabatic::GCell::CompareByDensity::CompareByDensity
CompareByDensity(unsigned int depth)
Definition: GCell.cpp:271
Katabatic::GCell::updateContacts
void updateContacts()
Definition: GCell.cpp:742
Katabatic::GCell::getVStopSegments
AutoSegments getVStopSegments()
Definition: GCell.cpp:515
Katabatic::GCellDensitySet::empty
bool empty() const
Definition: GCell.h:335
Katabatic::GCell::getTopRightShrink
static DbU::Unit getTopRightShrink()
Definition: GCell.cpp:453
Hurricane::Box::getYMax
const DbU::Unit & getYMax() const
Katabatic::GCell::getDensity
float getDensity(unsigned int flags=0) const
Definition: GCell.cpp:572
Katabatic::GCell::getStopSegments
AutoSegments getStopSegments(unsigned int direction)
Definition: GCell.h:260
Katabatic::GCell::isAboveDensity
bool isAboveDensity(float threshold) const
Definition: GCell.cpp:400
Katabatic::GCell::removeVSegment
void removeVSegment(AutoSegment *)
Definition: GCell.cpp:715
Hurricane::Name
Katabatic::GCell::getName
virtual const Name & getName() const
Definition: GCell.cpp:457
Katabatic::GCell::Key::getGCell
GCell * getGCell() const
Definition: GCell.h:299
Katabatic::GCell::updateDensity
size_t updateDensity()
Definition: GCell.cpp:750
Hurricane::DbU::Unit
std::int64_t Unit
Katabatic::GCell::getDepth
unsigned int getDepth() const
Definition: GCell.h:241
Katabatic::GCell::getSide
Interval getSide(unsigned int) const
Definition: GCell.cpp:485
Katabatic::GCell::hasFreeTrack
bool hasFreeTrack(size_t depth, float reserve) const
Definition: GCell.cpp:984
Katabatic::GCellDensitySet::getGCells
const std::set< GCell *, GCell::CompareByKey > & getGCells() const
Definition: GCell.h:340
Hurricane::Point
Katabatic::GCellDensitySet::erase
void erase(GCell *)
Definition: GCell.h:338
Katabatic::GCell::rpDesaturate
void rpDesaturate(set< Net *> &)
Definition: GCell.cpp:1102
Hurricane::Box::getXMin
const DbU::Unit & getXMin() const
Katabatic::GCell::checkDensity
size_t checkDensity() const
Definition: GCell.cpp:938
Katabatic::GCell::getDown
GCell * getDown() const
Definition: GCell.cpp:481
Hurricane::Interval
Katabatic::GCellGrid
GCell Grid.
Definition: GCellGrid.h:42
Katabatic::GCell::getFeedthroughs
float getFeedthroughs(unsigned int depth) const
Definition: GCell.h:272
Katabatic::GCell::CompareByIndex
GCell Index Comparison Functor.
Definition: GCell.h:77
Katabatic::GCell::removeContact
void removeContact(AutoContact *)
Definition: GCell.cpp:657
Katabatic::GCell::getStartSegments
AutoSegments getStartSegments(unsigned int direction)
Definition: GCell.h:257
Katabatic::GCell
Routing Global Cell.
Definition: GCell.h:74
Katabatic::GCell::getRoutingPads
size_t getRoutingPads(set< RoutingPad *> &)
Definition: GCell.cpp:521
Katabatic::AutoSegment
Abstract base class for AutoSegment.
Definition: AutoSegment.h:104
Hurricane::GenericCollection
Katabatic::GCell::SetIndex
set< GCell *, CompareByIndex > SetIndex
Definition: GCell.h:105
Katabatic::GCell::isSaturated
bool isSaturated() const
Definition: GCell.h:237
Katabatic
The namespace dedicated to Katabatic.
Definition: Katabatic.dox:13
Katabatic::GCell::stepDesaturate
bool stepDesaturate(unsigned int depth, set< Net *> &, AutoSegment *&moved, unsigned int flags=0)
Definition: GCell.cpp:1130
Katabatic::GCell::getHSegments
const vector< AutoSegment * > & getHSegments() const
Definition: GCell.h:249
Hurricane::Box::getCenter
Point getCenter() const
Katabatic::GCell::getGCellGrid
GCellGrid * getGCellGrid() const
Definition: GCell.h:240
Hurricane::Box
Katabatic::GCell::getStaticName
static const Name & getStaticName()
Definition: GCell.cpp:445
Katabatic::GCell::getIndex
unsigned int getIndex() const
Definition: GCell.h:242
Katabatic::GCell::getHStopSegments
AutoSegments getHStopSegments()
Definition: GCell.cpp:509
Katabatic::GCell::getXMax
DbU::Unit getXMax() const
Definition: GCell.h:246
Katabatic::GCell::Key::update
void update(unsigned int depth)
Definition: GCell.h:300
Hurricane::DbU
Katabatic::GCell::stepNetDesaturate
bool stepNetDesaturate(unsigned int depth, set< Net *> &globalNets, SetIndex &invalidateds)
Definition: GCell.cpp:1226
Katabatic::GCellDensitySet::size
size_t size() const
Definition: GCell.h:336
Katabatic::GCell::getAllocateds
static size_t getAllocateds()
Definition: GCell.cpp:449
Katabatic::GCell::getBlockage
DbU::Unit getBlockage(unsigned int depth) const
Definition: GCell.h:278
Katabatic::GCell::getUp
GCell * getUp() const
Definition: GCell.cpp:477
Katabatic::GCell::getFragmentation
float getFragmentation(unsigned int depth) const
Definition: GCell.h:269
Katabatic::KbHorizontal
Definition: Constants.h:27
Katabatic::GCell::Key::getDensity
float getDensity() const
Definition: GCell.h:298
Katabatic::GCell::getYMax
DbU::Unit getYMax() const
Definition: GCell.h:247
Katabatic::GCell::Key::Key
Key(GCell *, unsigned int depth)
Definition: GCell.h:297
Katabatic::GCell::checkEdgeSaturation
bool checkEdgeSaturation(size_t hreserved, size_t vreserved) const
Definition: GCell.cpp:1034
Katabatic::GCell::updateKey
void updateKey(unsigned int depth)
Definition: GCell.h:255
Hurricane
Katabatic::GCellDensitySet
GCell Set, sorted by density.
Definition: GCell.h:315
Katabatic::GCell::Key
GCell Key - Density Cache.
Definition: GCell.h:93
Katabatic::AutoContact
Abstract base class for AutoContact.
Definition: AutoContact.h:70
Katabatic::GCell::getLeft
GCell * getLeft() const
Definition: GCell.cpp:469
Katabatic::GCell::getWDensity
float getWDensity(unsigned int depth, unsigned int flags=0) const
Definition: GCell.h:266
Katabatic::GCell::isValid
bool isValid() const
Definition: GCell.h:238
Katabatic::GCell::getX
DbU::Unit getX() const
Definition: GCell.h:244
Katabatic::GCell::getKey
const Key & getKey() const
Definition: GCell.h:254
Katabatic::GCell::getGlobalsCount
float getGlobalsCount(unsigned int depth) const
Definition: GCell.h:275
Katabatic::GCellDensitySet::unqueue
void unqueue(GCell *)
Definition: GCell.h:339
Katabatic::GCell::getRight
GCell * getRight() const
Definition: GCell.cpp:473
Katabatic::GCell::addVSegment
void addVSegment(AutoSegment *)
Definition: GCell.h:281
Hurricane::Box::getYMin
const DbU::Unit & getYMin() const
Katabatic::GCell::getCDensity
float getCDensity(unsigned int flags=0) const
Definition: GCell.h:263
Katabatic::GCell::addBlockage
void addBlockage(unsigned int depth, DbU::Unit)
Definition: GCell.cpp:631
Katabatic::GCell::getHCapacity
float getHCapacity() const
Definition: GCell.cpp:533
Hurricane::RoutingPad
Katabatic::GCell::getVStartSegments
AutoSegments getVStartSegments()
Definition: GCell.cpp:503
Katabatic::GCell::removeHSegment
void removeHSegment(AutoSegment *)
Definition: GCell.cpp:688
Katabatic::GCell::addHSegment
void addHSegment(AutoSegment *)
Definition: GCell.h:284
Katabatic::GCell::getBoundingBox
virtual Box getBoundingBox() const
Definition: GCell.cpp:1266