torc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
torc::router::NetRouter Class Reference

Provides net routing based on the Nilsson graphsearch algorithm. More...

#include <NetRouter.hpp>

+ Inheritance diagram for torc::router::NetRouter:
+ Collaboration diagram for torc::router::NetRouter:

Public Member Functions

 NetRouter (DDB &inDB, NetRouterHeuristicBase *inHeuristic)
 Public Constructor. More...
 
 ~NetRouter ()
 Destructor. More...
 
void routeNet (RouteNet &net)
 Route a net. More...
 
void resetStats ()
 
void printStats (std::ostream &out)
 
void route (RouteNet &inNet)
 Primary route call. More...
 
double getTotalRouteTime ()
 Get total route time. More...
 
NetRouterHeuristicBasegetHeuristic ()
 Get the current heuristic. More...
 
void setHeuristic (NetRouterHeuristicBase *inHeuristic)
 Set the current heuristic. More...
 

Protected Member Functions

void graphSearch (const Tilewire &inSource, TilewireVector &inSinks, RouteNodePtrVector &outRoute)
 Internal top level route function. More...
 
void graphSearchLoop (const Tilewire &inSource, const Tilewire &inSink, RouteNodePtrVector &outRoute)
 Routing loop function. More...
 
void graphSearchFilter (RouteNode *inParent, const Arc &inArc, RouteNodePtrVector &outRoute)
 Create a new node and put it into the appropriate structure. More...
 
void recordPath (RouteNode *node, Tilewire key, Tilewire inSource, RouteNodePtrVector &outRoute)
 Add the newly found route to the outRoute vector. More...
 
void clearContainers ()
 Delete nodes in containers and clear them. More...
 
bool expandNetTerminals (Tilewire &inSource, TilewireVector &inSinks, RouteNodePtrVector &outRoute)
 Move net terminals out into the INT tiles. More...
 
bool testDedicatedPath (Tilewire inSource, Tilewire inSink, RouteNodePtrVector &outRoute)
 Test for a dedicated routing path. More...
 
Tilewire expandSourceTerminal (Tilewire inSource, RouteNodePtrVector &outRoute)
 Move the source terminal of a net in the sinkwards direction. More...
 
Tilewire expandSinkTerminal (Tilewire inSink, RouteNodePtrVector &outRoute)
 Move the sink terminal of a net in the sourcewards direction. More...
 

Protected Attributes

ArcUsagemArcUsage
 Database reference. More...
 
WireUsagemWireUsage
 WireUsage reference. More...
 
RouteNodePtrQueue mOrder
 Pointer to the heuristic for making routing decisions. More...
 
RouteNodePtrMap mOpen
 Collection of candidate nodes the router can expand. More...
 
RouteNodePtrMap mClosed
 Collection of nodes that have been expanded. More...
 
RouteNodePtrMap mSkipped
 Collection of nodes skipped due to heuristic constraints. More...
 
RouteNodePtrVector mPreRoute
 Vector of nodes created during pre-routing. More...
 
TilewireSet mAuxClosed
 Set of Closed Tilewires to avoid issues with bidir resources. More...
 
TilewireVector mSegmentBuf
 Scratch segment storage. More...
 
ArcVector mArcsBuf
 Scratch arc storage. More...
 
boost::uint32_t mSearchLimit
 Maximum number of nodes to explore before failing. More...
 
boost::uint32_t mStatNets
 Number of nets routed since construction. More...
 
boost::uint32_t mStatLoopPasses
 Number of passes through the main loop since construction. More...
 
boost::uint32_t mStatExpanded
 Number of nodes created from expansion. More...
 
boost::uint32_t mStatSources
 Number of net sources seen since construction. More...
 
boost::uint32_t mStatSinks
 Number of net sinks seen since construction. More...
 
DDBmDB
 Database reference. More...
 
NetRouterHeuristicBasemHeuristic
 Pointer to the heuristic for making routing decisions. More...
 
boost::timer mRouteTimer
 Timer object for performance analysis. More...
 
double mTotalRouteTime
 Total routing time since construction. More...
 

Private Types

typedef architecture::DDB DDB
 Imported type names. More...
 
typedef architecture::ArcUsage ArcUsage
 
typedef architecture::WireUsage WireUsage
 
typedef architecture::Tilewire Tilewire
 
typedef architecture::Arc Arc
 
typedef
architecture::TilewireVector 
TilewireVector
 
typedef architecture::ArcVector ArcVector
 
typedef std::priority_queue
< RouteNode *, std::vector
< RouteNode * >
, RouteNodePtrCostCompare
RouteNodePtrQueue
 
typedef boost::unordered_map
< Tilewire, RouteNode
*, boost::hash
< architecture::Tilewire > > 
RouteNodePtrMap
 
typedef boost::unordered_set
< Tilewire, boost::hash
< architecture::Tilewire > > 
TilewireSet
 

Detailed Description

Provides net routing based on the Nilsson graphsearch algorithm.

The router can either return a vector of nodes or directly populate DDB usage.

Definition at line 42 of file NetRouter.hpp.

Member Typedef Documentation

Definition at line 49 of file NetRouter.hpp.

Definition at line 46 of file NetRouter.hpp.

Definition at line 51 of file NetRouter.hpp.

Imported type names.

Definition at line 45 of file NetRouter.hpp.

typedef boost::unordered_map<Tilewire, RouteNode*, boost::hash<architecture::Tilewire> > torc::router::NetRouter::RouteNodePtrMap
private

Definition at line 56 of file NetRouter.hpp.

typedef std::priority_queue<RouteNode*, std::vector<RouteNode*>, RouteNodePtrCostCompare> torc::router::NetRouter::RouteNodePtrQueue
private

Definition at line 54 of file NetRouter.hpp.

Definition at line 48 of file NetRouter.hpp.

typedef boost::unordered_set<Tilewire, boost::hash<architecture::Tilewire> > torc::router::NetRouter::TilewireSet
private

Definition at line 57 of file NetRouter.hpp.

Definition at line 47 of file NetRouter.hpp.

Constructor & Destructor Documentation

torc::router::NetRouter::NetRouter ( DDB inDB,
NetRouterHeuristicBase inHeuristic 
)
inline

Public Constructor.

Definition at line 105 of file NetRouter.hpp.

105  :
106  NetRouterBase(inDB, inHeuristic), mArcUsage(inDB.getArcUsage()),
107  mWireUsage(inDB.getWireUsage()) {
108 
109  mSearchLimit = 0x001FFFFF;
110  mStatNets = 0u;
111  mStatLoopPasses = 0u;
112  mStatExpanded = 0u;
113  mStatSources = 0u;
114  mStatSinks = 0u;
115 
116  mTotalRouteTime = 0;
117  }
double mTotalRouteTime
Total routing time since construction.
boost::uint32_t mStatNets
Number of nets routed since construction.
Definition: NetRouter.hpp:92
boost::uint32_t mStatSinks
Number of net sinks seen since construction.
Definition: NetRouter.hpp:100
boost::uint32_t mSearchLimit
Maximum number of nodes to explore before failing.
Definition: NetRouter.hpp:90
boost::uint32_t mStatExpanded
Number of nodes created from expansion.
Definition: NetRouter.hpp:96
WireUsage & mWireUsage
WireUsage reference.
Definition: NetRouter.hpp:66
ArcUsage & mArcUsage
Database reference.
Definition: NetRouter.hpp:64
boost::uint32_t mStatSources
Number of net sources seen since construction.
Definition: NetRouter.hpp:98
boost::uint32_t mStatLoopPasses
Number of passes through the main loop since construction.
Definition: NetRouter.hpp:94
NetRouterBase(DDB &inDB, NetRouterHeuristicBase *inHeuristic)
Public Constructor.
torc::router::NetRouter::~NetRouter ( )
inline

Destructor.

Definition at line 119 of file NetRouter.hpp.

119 {}

Member Function Documentation

void torc::router::NetRouter::clearContainers ( )
inlineprotected

Delete nodes in containers and clear them.

Todo:
Report statistics on nodes deleted?

Definition at line 354 of file NetRouter.hpp.

354  {
355  /// \todo Report statistics on nodes deleted?
356  RouteNodePtrMap::iterator p;
357  RouteNodePtrMap::iterator e = mOpen.end();
358  for (p = mOpen.begin(); p != e; p++) { delete (*p).second; }
359  e = mClosed.end();
360  for (p = mClosed.begin(); p != e; p++) { delete (*p).second; }
361  e = mSkipped.end();
362  for (p = mSkipped.begin(); p != e; p++) { delete (*p).second; }
363  while (!mOrder.empty()) { mOrder.pop(); }
364  mOpen.clear();
365  mClosed.clear();
366  mSkipped.clear();
367  mAuxClosed.clear();
368  }
RouteNodePtrQueue mOrder
Pointer to the heuristic for making routing decisions.
Definition: NetRouter.hpp:72
RouteNodePtrMap mSkipped
Collection of nodes skipped due to heuristic constraints.
Definition: NetRouter.hpp:78
RouteNodePtrMap mOpen
Collection of candidate nodes the router can expand.
Definition: NetRouter.hpp:74
RouteNodePtrMap mClosed
Collection of nodes that have been expanded.
Definition: NetRouter.hpp:76
TilewireSet mAuxClosed
Set of Closed Tilewires to avoid issues with bidir resources.
Definition: NetRouter.hpp:82

+ Here is the caller graph for this function:

bool torc::router::NetRouter::expandNetTerminals ( Tilewire inSource,
TilewireVector inSinks,
RouteNodePtrVector outRoute 
)
inlineprotected

Move net terminals out into the INT tiles.

Definition at line 370 of file NetRouter.hpp.

371  {
372 
373  if (inSource == Tilewire::sInvalid) return false;
374  inSource = expandSourceTerminal(inSource, outRoute);
375  TilewireVector::iterator e = inSinks.end();
376  for (TilewireVector::iterator p = inSinks.begin(); p != e; p++) {
377  if (*p == Tilewire::sInvalid) return false;
378  *p = expandSinkTerminal(*p, outRoute);
379  }
380  return true;
381  }
Tilewire expandSourceTerminal(Tilewire inSource, RouteNodePtrVector &outRoute)
Move the source terminal of a net in the sinkwards direction.
Definition: NetRouter.hpp:407
static const Tilewire sInvalid
Definition: Tilewire.hpp:93
Tilewire expandSinkTerminal(Tilewire inSink, RouteNodePtrVector &outRoute)
Move the sink terminal of a net in the sourcewards direction.
Definition: NetRouter.hpp:425

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Tilewire torc::router::NetRouter::expandSinkTerminal ( Tilewire  inSink,
RouteNodePtrVector outRoute 
)
inlineprotected

Move the sink terminal of a net in the sourcewards direction.

Definition at line 425 of file NetRouter.hpp.

425  {
426  ArcVector arcs;
427  //bool movingsink = false;
428  Tilewire tempsink = inSink;
429  mDB.expandSegmentSources(inSink, arcs);
430  while (arcs.size() == 1) {
431  //movingsink = true;
432  RouteNode* node = new RouteNode(arcs[0], 0, 0, 0, 0);
433  outRoute.push_back(node);
434  mDB.useArc(arcs[0]);
435  tempsink = arcs[0].getSourceTilewire();
436  arcs.clear();
437  mDB.expandSegmentSources(tempsink, arcs);
438  }
439  return arcs[0].getSinkTilewire();
440  }
void useArc(const Arc &inArc)
Marks the arc and all of its source and sink segment wires as used.
Definition: DDB.hpp:173
void expandSegmentSources(const Tilewire &inTilewire, ArcVector &outSources, EExpandDirection inExpandDirection=eExpandDirectionNone, bool inUseTied=true, bool inUseRegular=true, bool inUseIrregular=true, bool inUseRoutethrough=true)
Expands all source arcs for the given tilewire's segment.
Definition: DDB.cpp:336
DDB & mDB
Database reference.
architecture::Tilewire Tilewire
Definition: NetRouter.hpp:48
architecture::ArcVector ArcVector
Definition: NetRouter.hpp:51

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Tilewire torc::router::NetRouter::expandSourceTerminal ( Tilewire  inSource,
RouteNodePtrVector outRoute 
)
inlineprotected

Move the source terminal of a net in the sinkwards direction.

Definition at line 407 of file NetRouter.hpp.

407  {
408  ArcVector arcs;
409  //bool movingsource = false;
410  Tilewire tempsource = inSource;
411  mDB.expandSegmentSinks(inSource, arcs);
412  while (arcs.size() == 1) {
413  //movingsource = true;
414  RouteNode* node = new RouteNode(arcs[0], 0, 0, 0, 0);
415  outRoute.push_back(node);
416  mDB.useArc(arcs[0]);
417  tempsource = arcs[0].getSinkTilewire();
418  arcs.clear();
419  mDB.expandSegmentSinks(tempsource, arcs);
420  }
421  return tempsource;
422  //return arcs[0].getSourceTilewire();
423  }
void expandSegmentSinks(const Tilewire &inTilewire, ArcVector &outSinks, EExpandDirection inExpandDirection=eExpandDirectionNone, bool inUseTied=true, bool inUseRegular=true, bool inUseIrregular=true, bool inUseRoutethrough=true)
Expands all sink arcs for the given tilewire's segment.
Definition: DDB.cpp:314
void useArc(const Arc &inArc)
Marks the arc and all of its source and sink segment wires as used.
Definition: DDB.hpp:173
DDB & mDB
Database reference.
architecture::Tilewire Tilewire
Definition: NetRouter.hpp:48
architecture::ArcVector ArcVector
Definition: NetRouter.hpp:51

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

NetRouterHeuristicBase* torc::router::NetRouterBase::getHeuristic ( )
inlineinherited

Get the current heuristic.

Definition at line 83 of file NetRouterBase.hpp.

83 { return mHeuristic; }
NetRouterHeuristicBase * mHeuristic
Pointer to the heuristic for making routing decisions.

+ Here is the caller graph for this function:

double torc::router::NetRouterBase::getTotalRouteTime ( )
inlineinherited

Get total route time.

Definition at line 81 of file NetRouterBase.hpp.

81 { return mTotalRouteTime; }
double mTotalRouteTime
Total routing time since construction.
void torc::router::NetRouter::graphSearch ( const Tilewire inSource,
TilewireVector inSinks,
RouteNodePtrVector outRoute 
)
inlineprotected

Internal top level route function.

Todo:
Count new RouteNodes?
Todo:
Set initial cost

Definition at line 201 of file NetRouter.hpp.

202  {
203 
204  clearContainers();
205 
206  mWireUsage.release(inSource);
207  TilewireVector::const_iterator p;
208  TilewireVector::const_iterator e = inSinks.end();
209  for (p = inSinks.begin(); p != e; p++) {
210  mWireUsage.release(*p);
211 
212  }
213  mHeuristic->reorderSinks(inSource, inSinks);
214  /// \todo Count new RouteNodes?
215  RouteNode* s = new RouteNode(inSource, inSource, 0, 0, 0, 0);
216 
217  mOpen.insert(std::pair<Tilewire, RouteNode*>(inSource, s));
218  mOrder.push(s);
219  e = inSinks.end();
220  for (p = inSinks.begin(); p != e; p++) {
221 
222  RouteNodePtrVector::iterator q;
223  RouteNodePtrVector::iterator f = outRoute.end();
224  for (q = outRoute.begin(); q != f; q++) {
225  /// \todo Set initial cost
226  mOpen.insert(std::pair<Tilewire, RouteNode*>((*q)->getSinkTilewire(), (*q)));
227  mOrder.push(*q);
228  }
229  mHeuristic->setSink(*p);
230  ////////////////
231  graphSearchLoop(inSource, *p, outRoute);
232  ////////////////
233  f = outRoute.end();
234  for (q = outRoute.begin(); q != f; q++) {
235  Tilewire tw = (*q)->getSinkTilewire();
236  mOpen.erase(tw);
237  mClosed.erase(tw);
238  mSkipped.erase(tw);
239  }
240  clearContainers();
241  }
242 
243  mWireUsage.use(inSource);
244  e = inSinks.end();
245  for (p = inSinks.begin(); p != e; p++) {
246  mWireUsage.use(*p);
247  }
248  }
RouteNodePtrQueue mOrder
Pointer to the heuristic for making routing decisions.
Definition: NetRouter.hpp:72
void clearContainers()
Delete nodes in containers and clear them.
Definition: NetRouter.hpp:354
virtual void reorderSinks(const Tilewire &inSource, TilewireVector &inSinks)
Reorder the Sinks based on this heuristic.
NetRouterHeuristicBase * mHeuristic
Pointer to the heuristic for making routing decisions.
WireUsage & mWireUsage
WireUsage reference.
Definition: NetRouter.hpp:66
RouteNodePtrMap mSkipped
Collection of nodes skipped due to heuristic constraints.
Definition: NetRouter.hpp:78
void use(const Tilewire &inTilewire)
Marks the specified tilewire as being used.
Definition: WireUsage.hpp:81
virtual void setSink(const Tilewire &inSink)=0
Set the current routing target.
architecture::Tilewire Tilewire
Definition: NetRouter.hpp:48
void graphSearchLoop(const Tilewire &inSource, const Tilewire &inSink, RouteNodePtrVector &outRoute)
Routing loop function.
Definition: NetRouter.hpp:250
RouteNodePtrMap mOpen
Collection of candidate nodes the router can expand.
Definition: NetRouter.hpp:74
void release(const Tilewire &inTilewire)
Marks the specified tilewire as being unused.
Definition: WireUsage.hpp:104
RouteNodePtrMap mClosed
Collection of nodes that have been expanded.
Definition: NetRouter.hpp:76

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void torc::router::NetRouter::graphSearchFilter ( RouteNode inParent,
const Arc inArc,
RouteNodePtrVector outRoute 
)
inlineprotected

Create a new node and put it into the appropriate structure.

Todo:
Need to check to see if we should be adjusting pointers in here.
Todo:
Heuristic check if node is filtered
Todo:
Heuristic cost of node
Todo:
Cases for different places the node can go.

Definition at line 305 of file NetRouter.hpp.

306  {
307 
308  const Tilewire& arcSink = inArc.getSinkTilewire();
309  /// \todo Need to check to see if we should be adjusting pointers in here.
310  if (mWireUsage.isUsed(arcSink)) return; // check if resources used
311  if (mOpen.find(arcSink) != mOpen.end()) return;
312  if (mClosed.find(arcSink) != mClosed.end()) return;
313  if (mSkipped.find(arcSink) != mSkipped.end()) return;
314 
315  if (mAuxClosed.find(arcSink) != mAuxClosed.end()) {
316 // std::cout << "FOUND SPECIAL CASE: " << arcSink << std::endl;
317  return;
318  }
319 
320  RouteNode* node = new RouteNode(inArc, 0, 0, inParent->getDepth() + 1, inParent);
321  /// \todo Heuristic check if node is filtered
322  /// \todo Heuristic cost of node
323  mHeuristic->nodeCost(*node);
324  /// \todo Cases for different places the node can go.
325  mOpen.insert(std::pair<Tilewire, RouteNode*>(arcSink, node));
326  mOrder.push(node);
327  }
RouteNodePtrQueue mOrder
Pointer to the heuristic for making routing decisions.
Definition: NetRouter.hpp:72
NetRouterHeuristicBase * mHeuristic
Pointer to the heuristic for making routing decisions.
WireUsage & mWireUsage
WireUsage reference.
Definition: NetRouter.hpp:66
RouteNodePtrMap mSkipped
Collection of nodes skipped due to heuristic constraints.
Definition: NetRouter.hpp:78
architecture::Tilewire Tilewire
Definition: NetRouter.hpp:48
RouteNodePtrMap mOpen
Collection of candidate nodes the router can expand.
Definition: NetRouter.hpp:74
RouteNodePtrMap mClosed
Collection of nodes that have been expanded.
Definition: NetRouter.hpp:76
bool isUsed(const Tilewire &inTilewire)
Determines whether the specified tilewire is in use.
Definition: WireUsage.hpp:138
TilewireSet mAuxClosed
Set of Closed Tilewires to avoid issues with bidir resources.
Definition: NetRouter.hpp:82
virtual void nodeCost(RouteNode &inNode)=0
Calculate the node cost based on distance to the sink and path length.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void torc::router::NetRouter::graphSearchLoop ( const Tilewire inSource,
const Tilewire inSink,
RouteNodePtrVector outRoute 
)
inlineprotected

Routing loop function.

Todo:
Throw route failed exception.
Todo:
Throw route limited exception.
Todo:
adjust the node cost to be just the path cost?

Definition at line 250 of file NetRouter.hpp.

251  {
252 
253  boost::uint32_t expanded = 0;
254  boost::uint32_t processed = 0;
255  while (true) {
256  mStatLoopPasses++;
257  if (mOrder.size() == 0) {
258  std::cout << "ROUTING FAILED!" << std::endl;
259  clearContainers();
260  /// \todo Throw route failed exception.
261  throw;
262  }
263 
264  if (++processed > mSearchLimit) {
265  std::cout << "ROUTE LIMIT!" << std::endl;
266  /// \todo Throw route limited exception.
267  throw;
268  }
269  RouteNode* n = mOrder.top();
270  Tilewire key = n->getSinkTilewire();
271  RouteNodePtrMap::iterator pk = mOpen.find(key);
272  mClosed.insert(std::pair<Tilewire, RouteNode*>(key, n));
273  mOpen.erase(pk);
274  mOrder.pop();
275 
276 //std::cout << key << " " << mOrder.size() << std::endl;
277  /// \todo adjust the node cost to be just the path cost?
278 
279  mSegmentBuf.clear();
281  TilewireVector::iterator p;
282  TilewireVector::iterator e = mSegmentBuf.end();
283  for (p = mSegmentBuf.begin(); p != e; p++) {
284  if (*p == inSink) {
285  recordPath(n, key, inSource, outRoute);
286  mStatExpanded += expanded;
287  return;
288  }
289  mAuxClosed.insert(*p);
290  }
291 
292  mArcsBuf.clear();
293 
295 //std::cout << "\t" << mArcsBuf.size() << std::endl;
296  ArcVector::iterator q;
297  ArcVector::iterator f = mArcsBuf.end();
298  for (q = mArcsBuf.begin(); q != f; q++) {
299  expanded++;
300  graphSearchFilter(n, *q, outRoute);
301  }
302  }
303  }
RouteNodePtrQueue mOrder
Pointer to the heuristic for making routing decisions.
Definition: NetRouter.hpp:72
void clearContainers()
Delete nodes in containers and clear them.
Definition: NetRouter.hpp:354
boost::uint32_t mSearchLimit
Maximum number of nodes to explore before failing.
Definition: NetRouter.hpp:90
boost::uint32_t mStatExpanded
Number of nodes created from expansion.
Definition: NetRouter.hpp:96
virtual void expandSegmentSinks(const Tilewire &inTilewire, ArcVector &outArcs)
Heuristically expand a segment.
void graphSearchFilter(RouteNode *inParent, const Arc &inArc, RouteNodePtrVector &outRoute)
Create a new node and put it into the appropriate structure.
Definition: NetRouter.hpp:305
NetRouterHeuristicBase * mHeuristic
Pointer to the heuristic for making routing decisions.
void recordPath(RouteNode *node, Tilewire key, Tilewire inSource, RouteNodePtrVector &outRoute)
Add the newly found route to the outRoute vector.
Definition: NetRouter.hpp:329
TilewireVector mSegmentBuf
Scratch segment storage.
Definition: NetRouter.hpp:85
ArcVector mArcsBuf
Scratch arc storage.
Definition: NetRouter.hpp:87
DDB & mDB
Database reference.
architecture::Tilewire Tilewire
Definition: NetRouter.hpp:48
RouteNodePtrMap mOpen
Collection of candidate nodes the router can expand.
Definition: NetRouter.hpp:74
boost::uint32_t mStatLoopPasses
Number of passes through the main loop since construction.
Definition: NetRouter.hpp:94
RouteNodePtrMap mClosed
Collection of nodes that have been expanded.
Definition: NetRouter.hpp:76
void expandSegment(const Tilewire &inTilewire, TilewireVector &outTilewires, EExpandDirection inExpandDirection=eExpandDirectionNone)
Expands the given tilewire's segment.
Definition: DDB.cpp:154
TilewireSet mAuxClosed
Set of Closed Tilewires to avoid issues with bidir resources.
Definition: NetRouter.hpp:82

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void torc::router::NetRouter::printStats ( std::ostream &  out)
inline

Definition at line 190 of file NetRouter.hpp.

190  {
191  out << "Nets routed: " << mStatNets
192  << " Sources: " << mStatSources
193  << " Sinks : " << mStatSinks
194  << " Arcs expanded: " << mStatExpanded
195  << " Loop passes: " << mStatLoopPasses
196  << " Total routing time: " << mTotalRouteTime
197  << std::endl;
198  }
double mTotalRouteTime
Total routing time since construction.
boost::uint32_t mStatNets
Number of nets routed since construction.
Definition: NetRouter.hpp:92
boost::uint32_t mStatSinks
Number of net sinks seen since construction.
Definition: NetRouter.hpp:100
boost::uint32_t mStatExpanded
Number of nodes created from expansion.
Definition: NetRouter.hpp:96
boost::uint32_t mStatSources
Number of net sources seen since construction.
Definition: NetRouter.hpp:98
boost::uint32_t mStatLoopPasses
Number of passes through the main loop since construction.
Definition: NetRouter.hpp:94
void torc::router::NetRouter::recordPath ( RouteNode node,
Tilewire  key,
Tilewire  inSource,
RouteNodePtrVector outRoute 
)
inlineprotected

Add the newly found route to the outRoute vector.

Definition at line 329 of file NetRouter.hpp.

330  {
331 
332  RouteNodePtrVector::iterator p;
333  RouteNodePtrVector::iterator e;
334  e = mPreRoute.end();
335  // transfer preroute to the outRoute;
336  for (p = mPreRoute.begin(); p != e; p++) {
337  outRoute.push_back(*p);
338  }
339  mPreRoute.clear();
340  while (true) {
341  node->setCost(0); // new wavefront?
342  e = outRoute.end();
343  for (p = outRoute.begin(); p != e; p++) {
344  if ((*p)->getSinkTilewire() == node->getSinkTilewire()) return;
345  }
346  outRoute.push_back(node);
347  if (key == inSource) return; // maybe a redundant check?
348  node = node->getParent();
349  if (node == 0) return;
350  key = node->getSinkTilewire();
351  }
352  }
RouteNodePtrVector mPreRoute
Vector of nodes created during pre-routing.
Definition: NetRouter.hpp:80

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void torc::router::NetRouter::resetStats ( )
inline

Definition at line 183 of file NetRouter.hpp.

183  {
184  mStatNets = 0u;
185  mStatLoopPasses = 0u;
186  mStatExpanded = 0u;
187  mStatSources = 0u;
188  mStatSinks = 0u;
189  }
boost::uint32_t mStatNets
Number of nets routed since construction.
Definition: NetRouter.hpp:92
boost::uint32_t mStatSinks
Number of net sinks seen since construction.
Definition: NetRouter.hpp:100
boost::uint32_t mStatExpanded
Number of nodes created from expansion.
Definition: NetRouter.hpp:96
boost::uint32_t mStatSources
Number of net sources seen since construction.
Definition: NetRouter.hpp:98
boost::uint32_t mStatLoopPasses
Number of passes through the main loop since construction.
Definition: NetRouter.hpp:94
void torc::router::NetRouterBase::route ( RouteNet inNet)
inlineinherited

Primary route call.

Definition at line 72 of file NetRouterBase.hpp.

72  {
73  mRouteTimer.restart();
74  routeNet(inNet);
75  double routeTime = mRouteTimer.elapsed();
76  mTotalRouteTime += routeTime;
77  inNet.mProperties[eRouteTime] = routeTime;
78  }
double mTotalRouteTime
Total routing time since construction.
boost::timer mRouteTimer
Timer object for performance analysis.
virtual void routeNet(RouteNet &inNet)=0
Virtual route call.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void torc::router::NetRouter::routeNet ( RouteNet net)
inlinevirtual

Route a net.

Todo:
Throw appropriate exception.
Todo:
Throw appropriate exception.

Implements torc::router::NetRouterBase.

Definition at line 122 of file NetRouter.hpp.

122  {
123 //std::cout << "### ROUTING " << net.getName() << " ###" << std::endl;
124  if (!net.hasOneSource()) {
125  std::cout << "NetRouter does not support multiple sources" << std::endl;
126  throw;
127  }
128  Tilewire source = *net.sourcesBegin();
129  TilewireVector sinks;
130  TilewireVector::iterator p;
131  TilewireVector::iterator e = net.sinksEnd();
132  for (p = net.sinksBegin(); p != e; p++) {
133  sinks.push_back(*p);
134  }
135 
136  // test resources in use
137  if (source == Tilewire::sInvalid) {
138  std::cout << net.getName() << ": source is INVALID" << std::endl;
139  return;
140  }
141  if (mWireUsage.isUsed(source)) {
142  /// \todo Throw appropriate exception.
143  std::cout << "!Source already in use! " << source << std::endl;
144  throw;
145  }
146  e = sinks.end();
147  for (p = sinks.begin(); p != e; p++) {
148  if (*p == Tilewire::sInvalid) {
149  std::cout << net.getName() << ": sink is INVALID" << std::endl;
150  return;
151  }
152  if (mWireUsage.isUsed(*p)) {
153  /// \todo Throw appropriate exception.
154  std::cout << "!Sink already in use! " << *p << std::endl;
155  throw;
156  }
157  }
158 
159  // pre-routing
160 
161  if (sinks.size() == 1 && testDedicatedPath(source, sinks[0], mPreRoute)) {
162  RouteNodePtrVector::iterator p;
163  RouteNodePtrVector::iterator e;
164  e = mPreRoute.end();
165  // transfer preroute to the net.
166  for (p = mPreRoute.begin(); p != e; p++) {
167  net.routeNodes().push_back(*p);
168  }
169  mPreRoute.clear();
170  } else {
171  if (!expandNetTerminals(source, sinks, mPreRoute)) {
172  std::cout << "DISCARDED in expand function: " << net.getName() << std::endl;
173  throw;
174  }
175 
176  graphSearch(source, sinks, net.routeNodes());
177  }
178 
179  mStatNets++;
180  mStatSources++;
181  mStatSinks += sinks.size();
182  }
RouteNodePtrVector mPreRoute
Vector of nodes created during pre-routing.
Definition: NetRouter.hpp:80
boost::uint32_t mStatNets
Number of nets routed since construction.
Definition: NetRouter.hpp:92
boost::uint32_t mStatSinks
Number of net sinks seen since construction.
Definition: NetRouter.hpp:100
bool expandNetTerminals(Tilewire &inSource, TilewireVector &inSinks, RouteNodePtrVector &outRoute)
Move net terminals out into the INT tiles.
Definition: NetRouter.hpp:370
WireUsage & mWireUsage
WireUsage reference.
Definition: NetRouter.hpp:66
void graphSearch(const Tilewire &inSource, TilewireVector &inSinks, RouteNodePtrVector &outRoute)
Internal top level route function.
Definition: NetRouter.hpp:201
boost::uint32_t mStatSources
Number of net sources seen since construction.
Definition: NetRouter.hpp:98
architecture::Tilewire Tilewire
Definition: NetRouter.hpp:48
bool testDedicatedPath(Tilewire inSource, Tilewire inSink, RouteNodePtrVector &outRoute)
Test for a dedicated routing path.
Definition: NetRouter.hpp:383
static const Tilewire sInvalid
Definition: Tilewire.hpp:93
architecture::TilewireVector TilewireVector
Definition: NetRouter.hpp:50
bool isUsed(const Tilewire &inTilewire)
Determines whether the specified tilewire is in use.
Definition: WireUsage.hpp:138

+ Here is the call graph for this function:

void torc::router::NetRouterBase::setHeuristic ( NetRouterHeuristicBase inHeuristic)
inlineinherited

Set the current heuristic.

Definition at line 85 of file NetRouterBase.hpp.

85 { mHeuristic = inHeuristic; }
NetRouterHeuristicBase * mHeuristic
Pointer to the heuristic for making routing decisions.
bool torc::router::NetRouter::testDedicatedPath ( Tilewire  inSource,
Tilewire  inSink,
RouteNodePtrVector outRoute 
)
inlineprotected

Test for a dedicated routing path.

Definition at line 383 of file NetRouter.hpp.

383  {
384  ArcVector arcs;
385  RouteNodePtrVector tempRoute;
386  Tilewire tempsink = inSink;
387  mDB.expandSegmentSources(inSink, arcs);
388  while (arcs.size() == 1) {
389  RouteNode* node = new RouteNode(arcs[0], 0, 0, 0, 0);
390  tempRoute.push_back(node);
391  mDB.useArc(arcs[0]);
392  tempsink = arcs[0].getSourceTilewire();
393  if (tempsink == inSource) {
394 // std::cout << "FOUND DEDICATED ROUTE!!! " << inSource << " to " << inSink
395 // << std::endl;
396  for (unsigned int i = 0; i < tempRoute.size(); i++) {
397  outRoute.push_back(tempRoute[i]);
398  }
399  return true;
400  }
401  arcs.clear();
402  mDB.expandSegmentSources(tempsink, arcs);
403  }
404  return false;
405  }
std::vector< RouteNode * > RouteNodePtrVector
Vector of RouteNode pointers.
Definition: RouteNode.hpp:115
void useArc(const Arc &inArc)
Marks the arc and all of its source and sink segment wires as used.
Definition: DDB.hpp:173
void expandSegmentSources(const Tilewire &inTilewire, ArcVector &outSources, EExpandDirection inExpandDirection=eExpandDirectionNone, bool inUseTied=true, bool inUseRegular=true, bool inUseIrregular=true, bool inUseRoutethrough=true)
Expands all source arcs for the given tilewire's segment.
Definition: DDB.cpp:336
DDB & mDB
Database reference.
architecture::Tilewire Tilewire
Definition: NetRouter.hpp:48
architecture::ArcVector ArcVector
Definition: NetRouter.hpp:51

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Field Documentation

ArcVector torc::router::NetRouter::mArcsBuf
protected

Scratch arc storage.

Definition at line 87 of file NetRouter.hpp.

ArcUsage& torc::router::NetRouter::mArcUsage
protected

Database reference.

ArcUsage reference.

Definition at line 64 of file NetRouter.hpp.

TilewireSet torc::router::NetRouter::mAuxClosed
protected

Set of Closed Tilewires to avoid issues with bidir resources.

Definition at line 82 of file NetRouter.hpp.

RouteNodePtrMap torc::router::NetRouter::mClosed
protected

Collection of nodes that have been expanded.

Definition at line 76 of file NetRouter.hpp.

DDB& torc::router::NetRouterBase::mDB
protectedinherited

Database reference.

Definition at line 53 of file NetRouterBase.hpp.

NetRouterHeuristicBase* torc::router::NetRouterBase::mHeuristic
protectedinherited

Pointer to the heuristic for making routing decisions.

Definition at line 55 of file NetRouterBase.hpp.

RouteNodePtrMap torc::router::NetRouter::mOpen
protected

Collection of candidate nodes the router can expand.

Definition at line 74 of file NetRouter.hpp.

RouteNodePtrQueue torc::router::NetRouter::mOrder
protected

Pointer to the heuristic for making routing decisions.

Priority queue of nodes to explore during routing, mirrors mOpen.

Definition at line 72 of file NetRouter.hpp.

RouteNodePtrVector torc::router::NetRouter::mPreRoute
protected

Vector of nodes created during pre-routing.

Definition at line 80 of file NetRouter.hpp.

boost::timer torc::router::NetRouterBase::mRouteTimer
protectedinherited

Timer object for performance analysis.

Definition at line 57 of file NetRouterBase.hpp.

boost::uint32_t torc::router::NetRouter::mSearchLimit
protected

Maximum number of nodes to explore before failing.

Definition at line 90 of file NetRouter.hpp.

TilewireVector torc::router::NetRouter::mSegmentBuf
protected

Scratch segment storage.

Definition at line 85 of file NetRouter.hpp.

RouteNodePtrMap torc::router::NetRouter::mSkipped
protected

Collection of nodes skipped due to heuristic constraints.

Definition at line 78 of file NetRouter.hpp.

boost::uint32_t torc::router::NetRouter::mStatExpanded
protected

Number of nodes created from expansion.

Definition at line 96 of file NetRouter.hpp.

boost::uint32_t torc::router::NetRouter::mStatLoopPasses
protected

Number of passes through the main loop since construction.

Definition at line 94 of file NetRouter.hpp.

boost::uint32_t torc::router::NetRouter::mStatNets
protected

Number of nets routed since construction.

Definition at line 92 of file NetRouter.hpp.

boost::uint32_t torc::router::NetRouter::mStatSinks
protected

Number of net sinks seen since construction.

Definition at line 100 of file NetRouter.hpp.

boost::uint32_t torc::router::NetRouter::mStatSources
protected

Number of net sources seen since construction.

Definition at line 98 of file NetRouter.hpp.

double torc::router::NetRouterBase::mTotalRouteTime
protectedinherited

Total routing time since construction.

Definition at line 59 of file NetRouterBase.hpp.

WireUsage& torc::router::NetRouter::mWireUsage
protected

WireUsage reference.

Definition at line 66 of file NetRouter.hpp.


The documentation for this class was generated from the following file: