torc::router::PathFinder Class Reference

#include <PathFinder.hpp>

Inheritance diagram for torc::router::PathFinder:

Collaboration diagram for torc::router::PathFinder:

Public Member Functions
	PathFinder (DDB &inDB, NetVectorRouterHeuristicBase *inHeuristic, NetRouterBase *inNetRouter)
	Pathfinder constructor. More...
	~PathFinder ()
	Destructor. More...
void	routeNets (RouteNetVector &nets)
void	unrouteNet (RouteNodePtrVector &routeVector, const string &netname)
void	updateSharing (RouteNodePtrVector &outRoute)
void	updateSharing (const Tilewire &inTilewire)
void	recordResult (std::vector< RouteNodePtrVector > &outRoutes, std::vector< RouteNodePtrVector > &tempRoutes, std::vector< unsigned int > &priorities, unsigned int plevel)
void	recordResult (RouteNodePtrVector &outRoute, RouteNodePtrVector &tempRoute)
bool	testReroute (RouteNodePtrVector &currentRoute)
void	unmarkSourcesAndSinks (RouteNet &net)
void	markSourcesAndSinks (RouteNet &net)
void	route (RouteNetVector &inNets)
	Primary route call. More...
NetVectorRouterHeuristicBase *	getHeuristic ()
	Accessor for the heuristic. More...
void	setHeuristic (NetVectorRouterHeuristicBase *inHeuristic)
	Set method for the heuristic. More...
NetRouterBase *	getNetRouter ()
	Accessor for the underlying Net Router. More...
void	setNetRouter (NetRouterBase *inNetRouter)
	Set method for the net router. More...

Protected Attributes
PathFinderSharingMap	mConflicts
WireUsage	mConflictWireUsage
TilewireVector	mTempWireSources
TilewireVector	mTempWireSinks
boost::timer	routetimer
boost::timer	iterationtimer
boost::timer	totaltimer
boost::timer	updatetimer
long	deleteCount
DDB &	mDB
	Database reference. More...
NetVectorRouterHeuristicBase *	mHeuristic
	Pointer to the heuristic for making routing decisions. More...
NetRouterBase *	mNetRouter
	Pointer to the underlying net router. More...
boost::timer	mRouteTimer
	Timer object for performance analysis. More...
double	mTotalRouteTime
	Total routing time since construction. More...

Private Types
typedef std::string	string
typedef architecture::DDB	DDB
typedef architecture::WireUsage	WireUsage
typedef architecture::Tilewire	Tilewire
typedef architecture::Arc	Arc
typedef architecture::TilewireVector	TilewireVector
typedef TilewireVector::const_iterator	TilewireConstIterator
typedef boost::unordered_map < Tilewire, TilewireData >	PathFinderSharingMap

Detailed Description

Definition at line 50 of file PathFinder.hpp.

Member Typedef Documentation

typedef architecture::Arc torc::router::PathFinder::Arc

private

Definition at line 56 of file PathFinder.hpp.

typedef architecture::DDB torc::router::PathFinder::DDB

private

Definition at line 53 of file PathFinder.hpp.

typedef boost::unordered_map<Tilewire, TilewireData> torc::router::PathFinder::PathFinderSharingMap

private

Definition at line 60 of file PathFinder.hpp.

typedef std::string torc::router::PathFinder::string

private

Definition at line 52 of file PathFinder.hpp.

typedef architecture::Tilewire torc::router::PathFinder::Tilewire

private

Definition at line 55 of file PathFinder.hpp.

typedef TilewireVector::const_iterator torc::router::PathFinder::TilewireConstIterator

private

Definition at line 58 of file PathFinder.hpp.

typedef architecture::TilewireVector torc::router::PathFinder::TilewireVector

private

Definition at line 57 of file PathFinder.hpp.

typedef architecture::WireUsage torc::router::PathFinder::WireUsage

private

Definition at line 54 of file PathFinder.hpp.

Constructor & Destructor Documentation

torc::router::PathFinder::PathFinder ( DDB &  inDB, NetVectorRouterHeuristicBase *  inHeuristic, NetRouterBase *  inNetRouter  )

inline

Pathfinder constructor.

Definition at line 79 of file PathFinder.hpp.

                                        : NetVectorRouterBase(inDB, inHeuristic, inNetRouter), 
            mConflictWireUsage(mDB.getTiles()) {
            
            mTempWireSources.reserve(200);
            mTempWireSinks.reserve(200);
            mTempWireSources.clear();
            mTempWireSinks.clear();
            deleteCount = 0;
            
            mConflictWireUsage.autosize();
            mNetRouter->getHeuristic()->setParameter(0, &mConflicts);
            mNetRouter->getHeuristic()->processParameters();
        }

Here is the call graph for this function:

torc::router::PathFinder::~PathFinder ( )

inline

Destructor.

Definition at line 95 of file PathFinder.hpp.

{}

Member Function Documentation

NetVectorRouterHeuristicBase* torc::router::NetVectorRouterBase::getHeuristic ( )

inlineinherited

Accessor for the heuristic.

Definition at line 78 of file NetVectorRouterBase.hpp.

{ return mHeuristic; }

NetRouterBase* torc::router::NetVectorRouterBase::getNetRouter ( )

inlineinherited

Accessor for the underlying Net Router.

Definition at line 82 of file NetVectorRouterBase.hpp.

{ return mNetRouter; }

void torc::router::PathFinder::markSourcesAndSinks ( RouteNet &  net )

inline

Definition at line 355 of file PathFinder.hpp.

        {
            mDB.useSegment(*net.sourcesBegin());
            RouteNet::TilewireConstIterator p;
            RouteNet::TilewireConstIterator e = net.sinksEnd();
            for (p = net.sinksBegin(); p != e; p++) {
                mDB.useSegment(*p);
            }
        }

Here is the call graph for this function:

Here is the caller graph for this function:

void torc::router::PathFinder::recordResult ( std::vector< RouteNodePtrVector > &  outRoutes, std::vector< RouteNodePtrVector > &  tempRoutes, std::vector< unsigned int > &  priorities, unsigned int  plevel  )

inline

Definition at line 317 of file PathFinder.hpp.

                                                                      {
            if (outRoutes.size() != tempRoutes.size()) {
                std::cout << "BAD SIZE: " << outRoutes.size() << " " << tempRoutes.size() << std::endl;
                return;
            }
            for (unsigned int i = 0; i < outRoutes.size(); i++) {
                recordResult(outRoutes[i], tempRoutes[i]);
            }
        }

void torc::router::PathFinder::recordResult ( RouteNodePtrVector &  outRoute, RouteNodePtrVector &  tempRoute  )

inline

Definition at line 328 of file PathFinder.hpp.

                                                                                       {
            Arc arc;
            for (unsigned int i = 0; i < tempRoute.size(); i++) {
                outRoute.push_back(tempRoute[i]);
                arc = tempRoute[i]->getArc();
                mDB.useArc(arc);
            }
        }

Here is the call graph for this function:

void torc::router::NetVectorRouterBase::route ( RouteNetVector &  inNets )

inlineinherited

Primary route call.

Definition at line 72 of file NetVectorRouterBase.hpp.

                                           {
            mRouteTimer.restart();
            routeNets(inNets);
            mTotalRouteTime += mRouteTimer.elapsed();
        }

Here is the call graph for this function:

Here is the caller graph for this function:

void torc::router::PathFinder::routeNets ( RouteNetVector &  nets )

inlinevirtual

Implements torc::router::NetVectorRouterBase.

Definition at line 97 of file PathFinder.hpp.

                                             {
            
            bool flag_resources = true;
            
            unsigned int numNets = nets.size();
            
            flag_resources = true;

            int routingPasses = 0;


            // Initial Routes
            totaltimer.restart();
            double updatetime = 0;
            iterationtimer.restart();
            for (unsigned int i = 0; i < numNets; i++) {
                RouteNet& net = nets[i];
            
                //double routetime;
                if (!(net.hasOneSource() && net.hasAnySinks())) {
                    std::cout << "BAD NET: " << net.getName() << std::endl;
                    continue;
                }
                try {
                    //std::cout << "### Routing net " << net.getName() << " " 
                    //  << " index: " << i << " of " << numNets 
                    //  << std::endl;
                    routetimer.restart();
                    unmarkSourcesAndSinks(net);
                    mNetRouter->route(net);
                    markSourcesAndSinks(net);
                    updateSharing(net.routeNodes());
                    //routetime = routetimer.elapsed();
                }
                catch (...) {
                        std::cout << "Failed routing net " << i << ": " << std::endl;
                        throw;
                }
                mConflictWireUsage.clear();
            }

            mConflicts.clear();
            std::cout << "Initial routes time: " << iterationtimer.elapsed() << std::endl;

            for (unsigned int i = 0; i < numNets; i++) {
                for (unsigned int j = 0; j < nets[i].routeNodes().size(); j++) {
                    updateSharing(nets[i].routeNodes()[j]->getSinkTilewire());
                }
            }
            
            // Main Loop
            while (flag_resources) { // while shared resources exist
                iterationtimer.restart();
                std::cout << "." << std::flush;
                        
                double avgroutetime = 0;
                double minroutetime = std::numeric_limits<double>::max();
                double maxroutetime = std::numeric_limits<double>::min();
                double routetime;
                int netsRouted = 0;
                
                for (unsigned int n = 0; n < numNets; n++) { //for each net
                    RouteNet& net = nets[n];
                    routetimer.restart();
                    //if (testReroute(nets[n].routeNodes())) {
                    if (true) {
                    
                        unrouteNet(net.routeNodes(), net.getName());
                        
                        try {
                            unmarkSourcesAndSinks(net);
                            mNetRouter->route(net);
                            markSourcesAndSinks(net);
                            updateSharing(net.routeNodes());
                        }
                        catch (...) {
                            std::cout << "Failed routing net " << net.getName() << " index: "
                                << n << " of " << nets.size() << std::endl;
                            throw;
                        }

                        routetime = routetimer.elapsed();

                        if (routetime < minroutetime)
                            minroutetime = routetime;
                        if (routetime > maxroutetime)
                            maxroutetime = routetime;
                        avgroutetime += routetime;
                        netsRouted++;
                    }
                }
                avgroutetime = avgroutetime / netsRouted;
                
                updatetimer.restart();
                PathFinderSharingMap::iterator p;
                unsigned int conflicts = 0;
                unsigned int maxpresent = 0;
                unsigned int maxhistory = 0;
                Tilewire maxPresentTilewire;
                Tilewire maxHistoryTilewire;
                for (p = mConflicts.begin(); p != mConflicts.end(); p++)
                {
                    if ((*p).second.mPresentSharing > 1)
                    {
                        (*p).second.mHistorySharing += (*p).second.mPresentSharing; 
                        conflicts++;
                    }
                    
                    if ((*p).second.mPresentSharing > maxpresent)
                    {
                        maxpresent = (*p).second.mPresentSharing;
                        maxPresentTilewire = (*p).first;
                    }
                    if ((*p).second.mHistorySharing > maxhistory)
                    {
                        maxhistory = (*p).second.mHistorySharing;
                        maxHistoryTilewire = (*p).first;
                    }
                }
                updatetime += updatetimer.elapsed();
                
//              std::cout << "Conflicts this iteration: " << conflicts << " max present: " 
//                  << maxpresent << " max history: " << maxhistory << std::endl;
//              std::cout << "Total conflict records: " << mConflicts.size() << std::endl;
//              std::cout << "Nets rerouted: " << netsRouted << "/" << numNets << std::endl;
//              std::cout << "Total time: " << totaltimer.elapsed() 
//                  << " iteration time: " << iterationtimer.elapsed() 
//                  << " average route time: " << avgroutetime
//                  << " total update time: " << updatetime
//                  << std::endl;
                    
                if (netsRouted == 1) {
                    flag_resources = false;
                    for (unsigned int i = 0; i < numNets; i++) {
                        RouteNet& net = nets[i];
                        if (testReroute(net.routeNodes())) {
                            std::cout << "FOUND SELF CONFLICT NET: " << net.getName() << std::endl;
                            std::cout << mDB;
                            for (unsigned int j = 0; j < net.routeNodes().size(); j++) {
                                std::cout << "\t" << net.routeNodes()[j]->getArc() << std::endl;
                            }
                        }
                    }
                }
                
//              std::cout << "Max Present Tilewire: " << maxPresentTilewire 
//                  << " Max History Tilewire: " << maxHistoryTilewire << std::endl;
                
                if (conflicts == 0) flag_resources = false;
                routingPasses++;
            } // end iteraton while loop
            std::cout << std::endl;
            std::cout << "Total time: " << totaltimer.elapsed() << " Update time: " << updatetime 
                << std::endl;
            
//          std::cout << "RECORD RESULT" << std::endl;
        } // end of function

Here is the call graph for this function:

void torc::router::NetVectorRouterBase::setHeuristic ( NetVectorRouterHeuristicBase *  inHeuristic )

inlineinherited

Set method for the heuristic.

Definition at line 80 of file NetVectorRouterBase.hpp.

{ mHeuristic = inHeuristic; }

void torc::router::NetVectorRouterBase::setNetRouter ( NetRouterBase *  inNetRouter )

inlineinherited

Set method for the net router.

Definition at line 84 of file NetVectorRouterBase.hpp.

{ mNetRouter = inNetRouter; }

bool torc::router::PathFinder::testReroute ( RouteNodePtrVector &  currentRoute )

inline

Definition at line 337 of file PathFinder.hpp.

                                                           {
            for (unsigned int i = 0; i < currentRoute.size(); i++) {
                if (mConflicts.find(currentRoute[i]->getSinkTilewire()) != mConflicts.end() 
                    && mConflicts[currentRoute[i]->getSinkTilewire()].mPresentSharing > 1) {
                    return true;
                }
            }
            return false;
        }

Here is the caller graph for this function:

void torc::router::PathFinder::unmarkSourcesAndSinks ( RouteNet &  net )

inline

Definition at line 347 of file PathFinder.hpp.

                                                  {
            mDB.releaseSegment(*net.sourcesBegin());
            RouteNet::TilewireConstIterator p;
            RouteNet::TilewireConstIterator e = net.sinksEnd();
            for (p = net.sinksBegin(); p != e; p++) {
                mDB.releaseSegment(*p);
            }
        }

Here is the call graph for this function:

Here is the caller graph for this function:

void torc::router::PathFinder::unrouteNet ( RouteNodePtrVector &  routeVector, const string &  netname  )

inline

Definition at line 255 of file PathFinder.hpp.

        {
            int rVecSize = routeVector.size();
            for (int x = 0; x < rVecSize; x++)
            {
                mTempWireSources.clear();
                mDB.expandSegment(routeVector[x]->getSinkTilewire(), mTempWireSources);
                int numWireSources = mTempWireSources.size();
                for (int i = 0; i < numWireSources; i++)
                {
                    Tilewire tw = mTempWireSources[i];
                    if (mConflicts.find(tw) != mConflicts.end())
                    {
                        mConflicts[tw].mPresentSharing--;
                        if (mConflicts[tw].mPresentSharing == 0)
                        {
                            mConflictWireUsage.release(tw);
                        }
                        if (mConflicts[tw].mPresentSharing < 0)
                        {
                            std::cout << "ERROR PRESENT: " << tw << " net " << netname << std::endl;
                            throw;
                        }
                    }
                    else 
                    {
                        mConflictWireUsage.release(tw);
                    }
                }
                delete routeVector[x];
                deleteCount++;
            }
            routeVector.clear();
        }

Here is the call graph for this function:

Here is the caller graph for this function:

void torc::router::PathFinder::updateSharing ( RouteNodePtrVector &  outRoute )

inline

Definition at line 289 of file PathFinder.hpp.

                                                         {
            for (unsigned int i = 0; i < outRoute.size(); i++) {
                updateSharing(outRoute[i]->getSinkTilewire());
            }
        }

Here is the caller graph for this function:

void torc::router::PathFinder::updateSharing ( const Tilewire &  inTilewire )

inline

Definition at line 294 of file PathFinder.hpp.

                                                       {
            mTempWireSources.clear();
            mDB.expandSegment(inTilewire, mTempWireSources);
            int numWireSources = mTempWireSources.size();
            for (int i = 0; i < numWireSources; i++) {
                Tilewire tw = mTempWireSources[i];
                if (mConflictWireUsage.isUsed(tw)) {
                    if (mConflicts.find(tw) != mConflicts.end()) {
                        mConflicts[tw].mPresentSharing++;
                    } else {
                        mConflicts[tw].mPresentSharing = 2;
                        mConflicts[tw].mHistorySharing = 0;
                    }
                } else {
                    if (mConflicts.find(tw) != mConflicts.end()) {
                        mConflicts[tw].mPresentSharing++;
                    }
                    mConflictWireUsage.use(tw);
                }
            }
            
        }

Here is the call graph for this function:

Field Documentation

long torc::router::PathFinder::deleteCount

protected

Definition at line 75 of file PathFinder.hpp.

boost::timer torc::router::PathFinder::iterationtimer

protected

Definition at line 71 of file PathFinder.hpp.

PathFinderSharingMap torc::router::PathFinder::mConflicts

protected

Definition at line 64 of file PathFinder.hpp.

WireUsage torc::router::PathFinder::mConflictWireUsage

protected

Definition at line 65 of file PathFinder.hpp.

DDB& torc::router::NetVectorRouterBase::mDB

protectedinherited

Database reference.

Definition at line 50 of file NetVectorRouterBase.hpp.

NetVectorRouterHeuristicBase* torc::router::NetVectorRouterBase::mHeuristic

protectedinherited

Pointer to the heuristic for making routing decisions.

Definition at line 52 of file NetVectorRouterBase.hpp.

NetRouterBase* torc::router::NetVectorRouterBase::mNetRouter

protectedinherited

Pointer to the underlying net router.

Definition at line 54 of file NetVectorRouterBase.hpp.

boost::timer torc::router::NetVectorRouterBase::mRouteTimer

protectedinherited

Timer object for performance analysis.

Definition at line 56 of file NetVectorRouterBase.hpp.

TilewireVector torc::router::PathFinder::mTempWireSinks

protected

Definition at line 68 of file PathFinder.hpp.

TilewireVector torc::router::PathFinder::mTempWireSources

protected

Definition at line 67 of file PathFinder.hpp.

double torc::router::NetVectorRouterBase::mTotalRouteTime

protectedinherited

Total routing time since construction.

Definition at line 58 of file NetVectorRouterBase.hpp.

boost::timer torc::router::PathFinder::routetimer

protected

Definition at line 70 of file PathFinder.hpp.

boost::timer torc::router::PathFinder::totaltimer

protected

Definition at line 72 of file PathFinder.hpp.

boost::timer torc::router::PathFinder::updatetimer

protected

Definition at line 73 of file PathFinder.hpp.

---

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

• PathFinder.hpp