torc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
PathFinder.hpp
Go to the documentation of this file.
1 // Torc - Copyright 2011-2013 University of Southern California. All Rights Reserved.
2 // $HeadURL$
3 // $Id$
4 
5 // This program is free software: you can redistribute it and/or modify it under the terms of the
6 // GNU General Public License as published by the Free Software Foundation, either version 3 of the
7 // License, or (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
10 // without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
11 // the GNU General Public License for more details.
12 //
13 // You should have received a copy of the GNU General Public License along with this program. If
14 // not, see <http://www.gnu.org/licenses/>.
15 
16 #ifndef TORC_ROUTER_PATHFINDER_HPP
17 #define TORC_ROUTER_PATHFINDER_HPP
18 
20 #include "NetRouterBase.hpp"
22 #include "RouteNet.hpp"
23 #include "RouteNode.hpp"
24 #include <boost/functional/hash.hpp>
25 
26 
27 #include <iostream>
28 #include <fstream>
29 #include <vector>
30 #include <list>
31 #include <map>
32 #include <algorithm>
33 #include "NetVectorRouterBase.hpp"
34 #include <boost/timer.hpp>
35 #include <boost/unordered_map.hpp>
36 #include <boost/functional/hash.hpp>
37 #include <boost/cstdint.hpp>
38 
40 
41 namespace torc {
42 
43 namespace router {
44  /// \brief Pathfinder annotations for Tilewires.
45  struct TilewireData {
46  boost::uint32_t mPresentSharing;
47  boost::uint32_t mHistorySharing;
48  };
49 
51  {
58  typedef TilewireVector::const_iterator TilewireConstIterator;
59 
60  typedef boost::unordered_map<Tilewire, TilewireData> PathFinderSharingMap;
61 
62  protected:
63 
66 
69 
70  boost::timer routetimer;
71  boost::timer iterationtimer;
72  boost::timer totaltimer;
73  boost::timer updatetimer;
74 
76 
77  public:
78  /// \brief Pathfinder constructor.
80  NetRouterBase* inNetRouter) : NetVectorRouterBase(inDB, inHeuristic, inNetRouter),
81  mConflictWireUsage(mDB.getTiles()) {
82 
83  mTempWireSources.reserve(200);
84  mTempWireSinks.reserve(200);
85  mTempWireSources.clear();
86  mTempWireSinks.clear();
87  deleteCount = 0;
88 
92  }
93 
94  /// \brief Destructor.
96 
97  void routeNets(RouteNetVector& nets) {
98 
99  bool flag_resources = true;
100 
101  unsigned int numNets = nets.size();
102 
103  flag_resources = true;
104 
105  int routingPasses = 0;
106 
107 
108  // Initial Routes
109  totaltimer.restart();
110  double updatetime = 0;
111  iterationtimer.restart();
112  for (unsigned int i = 0; i < numNets; i++) {
113  RouteNet& net = nets[i];
114 
115  //double routetime;
116  if (!(net.hasOneSource() && net.hasAnySinks())) {
117  std::cout << "BAD NET: " << net.getName() << std::endl;
118  continue;
119  }
120  try {
121  //std::cout << "### Routing net " << net.getName() << " "
122  // << " index: " << i << " of " << numNets
123  // << std::endl;
124  routetimer.restart();
126  mNetRouter->route(net);
127  markSourcesAndSinks(net);
128  updateSharing(net.routeNodes());
129  //routetime = routetimer.elapsed();
130  }
131  catch (...) {
132  std::cout << "Failed routing net " << i << ": " << std::endl;
133  throw;
134  }
136  }
137 
138  mConflicts.clear();
139  std::cout << "Initial routes time: " << iterationtimer.elapsed() << std::endl;
140 
141  for (unsigned int i = 0; i < numNets; i++) {
142  for (unsigned int j = 0; j < nets[i].routeNodes().size(); j++) {
143  updateSharing(nets[i].routeNodes()[j]->getSinkTilewire());
144  }
145  }
146 
147  // Main Loop
148  while (flag_resources) { // while shared resources exist
149  iterationtimer.restart();
150  std::cout << "." << std::flush;
151 
152  double avgroutetime = 0;
153  double minroutetime = std::numeric_limits<double>::max();
154  double maxroutetime = std::numeric_limits<double>::min();
155  double routetime;
156  int netsRouted = 0;
157 
158  for (unsigned int n = 0; n < numNets; n++) { //for each net
159  RouteNet& net = nets[n];
160  routetimer.restart();
161  //if (testReroute(nets[n].routeNodes())) {
162  if (true) {
163 
164  unrouteNet(net.routeNodes(), net.getName());
165 
166  try {
168  mNetRouter->route(net);
169  markSourcesAndSinks(net);
170  updateSharing(net.routeNodes());
171  }
172  catch (...) {
173  std::cout << "Failed routing net " << net.getName() << " index: "
174  << n << " of " << nets.size() << std::endl;
175  throw;
176  }
177 
178  routetime = routetimer.elapsed();
179 
180  if (routetime < minroutetime)
181  minroutetime = routetime;
182  if (routetime > maxroutetime)
183  maxroutetime = routetime;
184  avgroutetime += routetime;
185  netsRouted++;
186  }
187  }
188  avgroutetime = avgroutetime / netsRouted;
189 
190  updatetimer.restart();
191  PathFinderSharingMap::iterator p;
192  unsigned int conflicts = 0;
193  unsigned int maxpresent = 0;
194  unsigned int maxhistory = 0;
195  Tilewire maxPresentTilewire;
196  Tilewire maxHistoryTilewire;
197  for (p = mConflicts.begin(); p != mConflicts.end(); p++)
198  {
199  if ((*p).second.mPresentSharing > 1)
200  {
201  (*p).second.mHistorySharing += (*p).second.mPresentSharing;
202  conflicts++;
203  }
204 
205  if ((*p).second.mPresentSharing > maxpresent)
206  {
207  maxpresent = (*p).second.mPresentSharing;
208  maxPresentTilewire = (*p).first;
209  }
210  if ((*p).second.mHistorySharing > maxhistory)
211  {
212  maxhistory = (*p).second.mHistorySharing;
213  maxHistoryTilewire = (*p).first;
214  }
215  }
216  updatetime += updatetimer.elapsed();
217 
218 // std::cout << "Conflicts this iteration: " << conflicts << " max present: "
219 // << maxpresent << " max history: " << maxhistory << std::endl;
220 // std::cout << "Total conflict records: " << mConflicts.size() << std::endl;
221 // std::cout << "Nets rerouted: " << netsRouted << "/" << numNets << std::endl;
222 // std::cout << "Total time: " << totaltimer.elapsed()
223 // << " iteration time: " << iterationtimer.elapsed()
224 // << " average route time: " << avgroutetime
225 // << " total update time: " << updatetime
226 // << std::endl;
227 
228  if (netsRouted == 1) {
229  flag_resources = false;
230  for (unsigned int i = 0; i < numNets; i++) {
231  RouteNet& net = nets[i];
232  if (testReroute(net.routeNodes())) {
233  std::cout << "FOUND SELF CONFLICT NET: " << net.getName() << std::endl;
234  std::cout << mDB;
235  for (unsigned int j = 0; j < net.routeNodes().size(); j++) {
236  std::cout << "\t" << net.routeNodes()[j]->getArc() << std::endl;
237  }
238  }
239  }
240  }
241 
242 // std::cout << "Max Present Tilewire: " << maxPresentTilewire
243 // << " Max History Tilewire: " << maxHistoryTilewire << std::endl;
244 
245  if (conflicts == 0) flag_resources = false;
246  routingPasses++;
247  } // end iteraton while loop
248  std::cout << std::endl;
249  std::cout << "Total time: " << totaltimer.elapsed() << " Update time: " << updatetime
250  << std::endl;
251 
252 // std::cout << "RECORD RESULT" << std::endl;
253  } // end of function
254 
255  void unrouteNet(RouteNodePtrVector& routeVector, const string& netname)
256  {
257  int rVecSize = routeVector.size();
258  for (int x = 0; x < rVecSize; x++)
259  {
260  mTempWireSources.clear();
261  mDB.expandSegment(routeVector[x]->getSinkTilewire(), mTempWireSources);
262  int numWireSources = mTempWireSources.size();
263  for (int i = 0; i < numWireSources; i++)
264  {
265  Tilewire tw = mTempWireSources[i];
266  if (mConflicts.find(tw) != mConflicts.end())
267  {
268  mConflicts[tw].mPresentSharing--;
269  if (mConflicts[tw].mPresentSharing == 0)
270  {
272  }
273  if (mConflicts[tw].mPresentSharing < 0)
274  {
275  std::cout << "ERROR PRESENT: " << tw << " net " << netname << std::endl;
276  throw;
277  }
278  }
279  else
280  {
282  }
283  }
284  delete routeVector[x];
285  deleteCount++;
286  }
287  routeVector.clear();
288  }
290  for (unsigned int i = 0; i < outRoute.size(); i++) {
291  updateSharing(outRoute[i]->getSinkTilewire());
292  }
293  }
294  void updateSharing(const Tilewire& inTilewire) {
295  mTempWireSources.clear();
296  mDB.expandSegment(inTilewire, mTempWireSources);
297  int numWireSources = mTempWireSources.size();
298  for (int i = 0; i < numWireSources; i++) {
299  Tilewire tw = mTempWireSources[i];
300  if (mConflictWireUsage.isUsed(tw)) {
301  if (mConflicts.find(tw) != mConflicts.end()) {
302  mConflicts[tw].mPresentSharing++;
303  } else {
304  mConflicts[tw].mPresentSharing = 2;
305  mConflicts[tw].mHistorySharing = 0;
306  }
307  } else {
308  if (mConflicts.find(tw) != mConflicts.end()) {
309  mConflicts[tw].mPresentSharing++;
310  }
312  }
313  }
314 
315  }
316 
317  void recordResult(std::vector<RouteNodePtrVector>& outRoutes,
318  std::vector<RouteNodePtrVector>& tempRoutes,
319  std::vector<unsigned int>& priorities, unsigned int plevel) {
320  if (outRoutes.size() != tempRoutes.size()) {
321  std::cout << "BAD SIZE: " << outRoutes.size() << " " << tempRoutes.size() << std::endl;
322  return;
323  }
324  for (unsigned int i = 0; i < outRoutes.size(); i++) {
325  recordResult(outRoutes[i], tempRoutes[i]);
326  }
327  }
328  void recordResult(RouteNodePtrVector& outRoute, RouteNodePtrVector& tempRoute) {
329  Arc arc;
330  for (unsigned int i = 0; i < tempRoute.size(); i++) {
331  outRoute.push_back(tempRoute[i]);
332  arc = tempRoute[i]->getArc();
333  mDB.useArc(arc);
334  }
335  }
336 
337  bool testReroute(RouteNodePtrVector& currentRoute) {
338  for (unsigned int i = 0; i < currentRoute.size(); i++) {
339  if (mConflicts.find(currentRoute[i]->getSinkTilewire()) != mConflicts.end()
340  && mConflicts[currentRoute[i]->getSinkTilewire()].mPresentSharing > 1) {
341  return true;
342  }
343  }
344  return false;
345  }
346 
351  for (p = net.sinksBegin(); p != e; p++) {
352  mDB.releaseSegment(*p);
353  }
354  }
356  {
357  mDB.useSegment(*net.sourcesBegin());
360  for (p = net.sinksBegin(); p != e; p++) {
361  mDB.useSegment(*p);
362  }
363  }
364 
365  }; // class PathFinder
366 } // namespace router
367 } // namespace torc
368 #endif // TORC_ROUTER_PATHFINDER_HPP
TilewireVector::const_iterator TilewireConstIterator
Definition: RouteNet.hpp:51
TilewireConstIterator sinksEnd(void) const
Returns the end constant iterator for sink Tilewires.
Definition: RouteNet.hpp:184
Pathfinder annotations for Tilewires.
Definition: PathFinder.hpp:45
TilewireVector mTempWireSinks
Definition: PathFinder.hpp:68
Encapsulation of an arc between two tilewires.
Definition: Arc.hpp:28
void releaseSegment(const Tilewire &inTilewire)
Marks all wires on the segment as unused.
Definition: DDB.hpp:193
std::vector< Tilewire > TilewireVector
Vector of Tilewire objects.
Definition: Tilewire.hpp:101
std::vector< RouteNode * > RouteNodePtrVector
Vector of RouteNode pointers.
Definition: RouteNode.hpp:115
TilewireVector mTempWireSources
Definition: PathFinder.hpp:67
Device database, including complete wiring and logic support.
Definition: DDB.hpp:42
std::vector< RouteNet > RouteNetVector
Vector of RouteNet objects.
Definition: RouteNet.hpp:205
TilewireVector::const_iterator TilewireConstIterator
Definition: PathFinder.hpp:58
const string & getName() const
Returns the name of the net.
Definition: RouteNet.hpp:199
boost::timer updatetimer
Definition: PathFinder.hpp:73
bool testReroute(RouteNodePtrVector &currentRoute)
Definition: PathFinder.hpp:337
NetRouterBase * mNetRouter
Pointer to the underlying net router.
Header for the NetVectorRouterHeuristicBase class.
Encapsulation the design wire usage.
Definition: WireUsage.hpp:35
Header for the RouteNode class.
void unmarkSourcesAndSinks(RouteNet &net)
Definition: PathFinder.hpp:347
TilewireConstIterator sinksBegin(void) const
Returns the begin constant iterator for sink Tilewires.
Definition: RouteNet.hpp:182
Header for the BasicRouter class.
Provides net routing based on the Nillson graphsearch algorithm.
void useArc(const Arc &inArc)
Marks the arc and all of its source and sink segment wires as used.
Definition: DDB.hpp:173
std::string string
RouteNodePtrVector & routeNodes()
Returns a reference to the RouteNodePtrVector.
Definition: RouteNet.hpp:201
void clear(void)
Marks all wires as being unused, without releasing the bitset objects.
Definition: WireUsage.hpp:121
void recordResult(RouteNodePtrVector &outRoute, RouteNodePtrVector &tempRoute)
Definition: PathFinder.hpp:328
Header for the NetVectorRouterBase class.
void setParameter(boost::uint32_t index, boost::any inParameter)
Set a parameter.
Encapsulation of a device tile and wire pair.
Definition: Tilewire.hpp:39
NetRouterHeuristicBase * getHeuristic()
Get the current heuristic.
boost::timer iterationtimer
Definition: PathFinder.hpp:71
void updateSharing(RouteNodePtrVector &outRoute)
Definition: PathFinder.hpp:289
void use(const Tilewire &inTilewire)
Marks the specified tilewire as being used.
Definition: WireUsage.hpp:81
boost::uint32_t mHistorySharing
Definition: PathFinder.hpp:47
TilewireConstIterator sourcesBegin(void) const
Returns the begin constant iterator for source Tilewires.
Definition: RouteNet.hpp:174
void recordResult(std::vector< RouteNodePtrVector > &outRoutes, std::vector< RouteNodePtrVector > &tempRoutes, std::vector< unsigned int > &priorities, unsigned int plevel)
Definition: PathFinder.hpp:317
virtual void processParameters()
Do something with the parameters.
Header for the Tilewire class.
void useSegment(const Tilewire &inTilewire)
Marks all wires on the segment as used.
Definition: DDB.hpp:185
boost::uint32_t mPresentSharing
Definition: PathFinder.hpp:46
PathFinderSharingMap mConflicts
Definition: PathFinder.hpp:64
void routeNets(RouteNetVector &nets)
Definition: PathFinder.hpp:97
bool hasOneSource(void) const
Returns true if the net has exactly one source.
Definition: RouteNet.hpp:151
~PathFinder()
Destructor.
Definition: PathFinder.hpp:95
architecture::TilewireVector TilewireVector
Definition: PathFinder.hpp:57
architecture::Tilewire Tilewire
Definition: PathFinder.hpp:55
void release(const Tilewire &inTilewire)
Marks the specified tilewire as being unused.
Definition: WireUsage.hpp:104
architecture::DDB DDB
Definition: PathFinder.hpp:53
Abstract class for a net router.
Abstract class for a net router.
Header for the DDB class.
void route(RouteNet &inNet)
Primary route call.
PathFinder(DDB &inDB, NetVectorRouterHeuristicBase *inHeuristic, NetRouterBase *inNetRouter)
Pathfinder constructor.
Definition: PathFinder.hpp:79
void unrouteNet(RouteNodePtrVector &routeVector, const string &netname)
Definition: PathFinder.hpp:255
boost::unordered_map< Tilewire, TilewireData > PathFinderSharingMap
Definition: PathFinder.hpp:60
architecture::WireUsage WireUsage
Definition: PathFinder.hpp:54
architecture::Arc Arc
Definition: PathFinder.hpp:56
bool isUsed(const Tilewire &inTilewire)
Determines whether the specified tilewire is in use.
Definition: WireUsage.hpp:138
void markSourcesAndSinks(RouteNet &net)
Definition: PathFinder.hpp:355
bool hasAnySinks(void) const
Returns true if the net has any sinks.
Definition: RouteNet.hpp:157
void autosize(void)
Size the wire usage according to the number of device tiles.
Definition: WireUsage.hpp:68
void expandSegment(const Tilewire &inTilewire, TilewireVector &outTilewires, EExpandDirection inExpandDirection=eExpandDirectionNone)
Expands the given tilewire's segment.
Definition: DDB.cpp:154
Header for the Net class.
void updateSharing(const Tilewire &inTilewire)
Definition: PathFinder.hpp:294