torc::router::PathFinderNetRouterHeuristic Class Reference

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

#include <PathFinderNetRouterHeuristic.hpp>

Inheritance diagram for torc::router::PathFinderNetRouterHeuristic:

Collaboration diagram for torc::router::PathFinderNetRouterHeuristic:

Public Member Functions
	PathFinderNetRouterHeuristic (DDB &inDB)
	Public Constructor. More...
	~PathFinderNetRouterHeuristic ()
	Destructor. More...
void	processParameters ()
void	setSink (const Tilewire &inSink)
	Set the current routing target. More...
void	nodeCost (RouteNode &inNode)
	Calculate the node cost based on distance to the sink and path length. More...
void	nodeCostInitial (RouteNode &inNode)
virtual void	reorderSinks (const Tilewire &inSource, TilewireVector &inSinks)
	Reorder the Sinks based on this heuristic. More...
void	expandSegmentSinks (const Tilewire &inTilewire, ArcVector &outArcs)
	Heuristic handling of expansion of a node. More...
boost::any	getParameter (boost::uint32_t index)
	Get a parameter. More...
void	setParameter (boost::uint32_t index, boost::any inParameter)
	Set a parameter. More...

Protected Member Functions
virtual boost::int32_t	distanceToSink (const Tilewire &inTilewire)
virtual boost::int32_t	clkDistanceToSink (const Tilewire &inTilewire)

Protected Attributes
ArcUsage &	mArcUsage
	ArcUsage reference. More...
const Tiles &	mTiles
	Tiles reference. More...
Tilewire	mTargetSink
	Target sink tilewire. More...
const TileInfo *	mSinkTileInfo
	Target sink tile information. More...
boost::int32_t	mRow
	Target row coordinate. More...
boost::int32_t	mCol
	Target column coordinate. More...
TilewireVector	mSegmentBuf
	Segment tilewire buffer. More...
ArcVector	mArcsBuf
	Arc buffer. More...
PathFinderSharingMap *	mConflictMap
	PathFinder sharing information. More...
DDB &	mDB
	Database reference. More...
ParameterMap	mParameters
	Parameter map. More...

Private Types
typedef architecture::DDB	DDB
	Imported type names. More...
typedef architecture::Tiles	Tiles
typedef architecture::ArcUsage	ArcUsage
typedef architecture::WireUsage	WireUsage
typedef architecture::Tilewire	Tilewire
typedef architecture::TileInfo	TileInfo
typedef architecture::Arc	Arc
typedef architecture::TilewireVector	TilewireVector
typedef architecture::ArcVector	ArcVector
typedef architecture::xilinx::TileRow	TileRow
typedef architecture::xilinx::TileCol	TileCol
typedef boost::unordered_map < Tilewire, TilewireData >	PathFinderSharingMap

Detailed Description

Provides net routing based on the Nillson graphsearch algorithm.

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

Definition at line 44 of file PathFinderNetRouterHeuristic.hpp.

Member Typedef Documentation

typedef architecture::Arc torc::router::PathFinderNetRouterHeuristic::Arc

private

Definition at line 53 of file PathFinderNetRouterHeuristic.hpp.

typedef architecture::ArcUsage torc::router::PathFinderNetRouterHeuristic::ArcUsage

private

Definition at line 49 of file PathFinderNetRouterHeuristic.hpp.

typedef architecture::ArcVector torc::router::PathFinderNetRouterHeuristic::ArcVector

private

Definition at line 55 of file PathFinderNetRouterHeuristic.hpp.

typedef architecture::DDB torc::router::PathFinderNetRouterHeuristic::DDB

private

Imported type names.

Definition at line 47 of file PathFinderNetRouterHeuristic.hpp.

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

private

Definition at line 59 of file PathFinderNetRouterHeuristic.hpp.

typedef architecture::xilinx::TileCol torc::router::PathFinderNetRouterHeuristic::TileCol

private

Definition at line 57 of file PathFinderNetRouterHeuristic.hpp.

typedef architecture::TileInfo torc::router::PathFinderNetRouterHeuristic::TileInfo

private

Definition at line 52 of file PathFinderNetRouterHeuristic.hpp.

typedef architecture::xilinx::TileRow torc::router::PathFinderNetRouterHeuristic::TileRow

private

Definition at line 56 of file PathFinderNetRouterHeuristic.hpp.

typedef architecture::Tiles torc::router::PathFinderNetRouterHeuristic::Tiles

private

Definition at line 48 of file PathFinderNetRouterHeuristic.hpp.

typedef architecture::Tilewire torc::router::PathFinderNetRouterHeuristic::Tilewire

private

Definition at line 51 of file PathFinderNetRouterHeuristic.hpp.

typedef architecture::TilewireVector torc::router::PathFinderNetRouterHeuristic::TilewireVector

private

Definition at line 54 of file PathFinderNetRouterHeuristic.hpp.

typedef architecture::WireUsage torc::router::PathFinderNetRouterHeuristic::WireUsage

private

Definition at line 50 of file PathFinderNetRouterHeuristic.hpp.

Constructor & Destructor Documentation

torc::router::PathFinderNetRouterHeuristic::PathFinderNetRouterHeuristic ( DDB &  inDB )

inline

Public Constructor.

Definition at line 88 of file PathFinderNetRouterHeuristic.hpp.

                                                : NetRouterHeuristicBase(inDB), 
            mArcUsage(inDB.getArcUsage()), mTiles(inDB.getTiles()) {}

torc::router::PathFinderNetRouterHeuristic::~PathFinderNetRouterHeuristic ( )

inline

Destructor.

Definition at line 91 of file PathFinderNetRouterHeuristic.hpp.

{}

Member Function Documentation

virtual boost::int32_t torc::router::PathFinderNetRouterHeuristic::clkDistanceToSink ( const Tilewire &  inTilewire )

inlineprotectedvirtual

Definition at line 223 of file PathFinderNetRouterHeuristic.hpp.

                                                                           {
            return -100;
        }

virtual boost::int32_t torc::router::PathFinderNetRouterHeuristic::distanceToSink ( const Tilewire &  inTilewire )

inlineprotectedvirtual

Definition at line 213 of file PathFinderNetRouterHeuristic.hpp.

                                                                        {
            const TileInfo* tileInfo = &mTiles.getTileInfo(inTilewire.getTileIndex());
            boost::int32_t distance = 0;
            boost::int32_t iRow = tileInfo->getRow();
            boost::int32_t iCol = tileInfo->getCol();
            distance += iRow < mRow ? mRow - iRow : iRow - mRow;
            distance += iCol < mCol ? mCol - iCol : iCol - mCol;
            return distance;
        }

Here is the call graph for this function:

Here is the caller graph for this function:

void torc::router::PathFinderNetRouterHeuristic::expandSegmentSinks ( const Tilewire &  inTilewire, ArcVector &  outArcs  )

inlinevirtual

Heuristic handling of expansion of a node.

Reimplemented from torc::router::NetRouterHeuristicBase.

Definition at line 190 of file PathFinderNetRouterHeuristic.hpp.

                                                                                {
            ArcVector tempArcs;
            
            //const architecture::TileInfo& tileInfo = mTiles.getTileInfo(inTilewire.getTileIndex());
            //const architecture::WireInfo& wireInfo = mTiles.getWireInfo(
            //  tileInfo.getTypeIndex(), inTilewire.getWireIndex());
            //if (wireInfo.isInput()) return;
            
            mDB.expandSegmentSinks(inTilewire, tempArcs, DDB::eExpandDirectionNone,
                true, true, true, false);
            
            unsigned int s = tempArcs.size();
            if (s == 0) return;
            unsigned int t = inTilewire.getTileIndex() % s;
            for (unsigned int i = t; i < s; i++) {
                outArcs.push_back(tempArcs[i]);
            }
            for (unsigned int i = 0; i < t; i++) {
                outArcs.push_back(tempArcs[i]);
            }
        }

Here is the call graph for this function:

Here is the caller graph for this function:

boost::any torc::router::RouterHeuristicBase::getParameter ( boost::uint32_t  index )

inlineinherited

Get a parameter.

Definition at line 52 of file RouterHeuristicBase.hpp.

                                                   {
            ParameterMap::iterator p = mParameters.find(index);
            if (p != mParameters.end()) {
                return p->second;
            }
            return boost::any();
        }

Here is the caller graph for this function:

void torc::router::PathFinderNetRouterHeuristic::nodeCost ( RouteNode &  inNode )

inlinevirtual

Calculate the node cost based on distance to the sink and path length.

Todo:

provide an additional field in RouteNode to store path cost

Implements torc::router::NetRouterHeuristicBase.

Definition at line 107 of file PathFinderNetRouterHeuristic.hpp.

                                         {
            Tilewire sinkTilewire = inNode.getSinkTilewire();
            boost::int32_t bestDistance = boost::integer_traits<boost::int32_t>::max();
            boost::int32_t distance = boost::integer_traits<boost::int32_t>::max();
            boost::int32_t cost = 0;
            if (sinkTilewire == mTargetSink) {
                inNode.setCost(0);
                return;
            }
            mArcsBuf.clear();
            expandSegmentSinks(sinkTilewire, mArcsBuf);
            if (mArcsBuf.size() == 0) {
                inNode.setCost(bestDistance);
                return;
            }
            ArcVector::iterator p;
            ArcVector::iterator e = mArcsBuf.end();
            for (p = mArcsBuf.begin(); p != e; p++) {
                if (mArcUsage.isUsed(*p)) continue;
                if (sinkTilewire == mTargetSink) {
                    inNode.setCost(0);
                    return;
                }
                distance = distanceToSink(p->getSinkTilewire());
                if (distance < bestDistance) bestDistance = distance;
            }
            if (bestDistance == boost::integer_traits<boost::int32_t>::max()) {
                inNode.setCost(bestDistance);
                return;
            }
            cost += bestDistance; // heuristic cost
            /// \todo provide an additional field in RouteNode to store path cost
            if (inNode.getParent() == NULL)
                std::cout << "NULL PARENT" << std::endl;
            else
                cost += inNode.getParent()->getCost(); //add cost to parent;
            
            if (mConflictMap->find(sinkTilewire) != mConflictMap->end()) {
                cost = (cost + (*mConflictMap)[sinkTilewire].mHistorySharing) 
                    * (*mConflictMap)[sinkTilewire].mPresentSharing;
            }
            
            inNode.setCost(cost);   
        }

Here is the call graph for this function:

void torc::router::PathFinderNetRouterHeuristic::nodeCostInitial ( RouteNode &  inNode )

inline

Definition at line 152 of file PathFinderNetRouterHeuristic.hpp.

                                                {
            Tilewire sinkTilewire = inNode.getSinkTilewire();
            boost::int32_t bestDistance = boost::integer_traits<boost::int32_t>::max();
            boost::int32_t distance = boost::integer_traits<boost::int32_t>::max();
            boost::int32_t cost = 0;
            if (sinkTilewire == mTargetSink) {
                inNode.setCost(0);
                return;
            }
            mArcsBuf.clear();
            expandSegmentSinks(sinkTilewire, mArcsBuf);
            if (mArcsBuf.size() == 0) {
                inNode.setCost(bestDistance);
                return;
            }
            ArcVector::iterator p;
            ArcVector::iterator e = mArcsBuf.end();
            for (p = mArcsBuf.begin(); p != e; p++) {
                if (mArcUsage.isUsed(*p)) continue;
                if (sinkTilewire == mTargetSink) {
                    inNode.setCost(0);
                    return;
                }
                distance = distanceToSink(p->getSinkTilewire());
                if (distance < bestDistance) bestDistance = distance;
            }
            if (bestDistance == boost::integer_traits<boost::int32_t>::max()) {
                inNode.setCost(bestDistance);
                return;
            }
            cost += bestDistance; // heuristic cost
            inNode.setCost(cost);   
        }

Here is the call graph for this function:

void torc::router::PathFinderNetRouterHeuristic::processParameters ( )

inlinevirtual

Reimplemented from torc::router::RouterHeuristicBase.

Definition at line 93 of file PathFinderNetRouterHeuristic.hpp.

                                 {
            boost::any map = getParameter(0);
            mConflictMap = boost::any_cast<PathFinderSharingMap*>(map);
            std::cout<< "SETUP CONFLICT MAP" << std::endl;
        }

Here is the call graph for this function:

virtual void torc::router::PathFinderNetRouterHeuristic::reorderSinks ( const Tilewire &  inSource, TilewireVector &  inSinks  )

inlinevirtual

Reorder the Sinks based on this heuristic.

Reimplemented from torc::router::NetRouterHeuristicBase.

Definition at line 186 of file PathFinderNetRouterHeuristic.hpp.

                                                                                     {
            // do nothing for now
        }

void torc::router::RouterHeuristicBase::setParameter ( boost::uint32_t  index, boost::any  inParameter  )

inlineinherited

Set a parameter.

Definition at line 60 of file RouterHeuristicBase.hpp.

                                                                     {
            mParameters[index] = inParameter;
        }

Here is the caller graph for this function:

void torc::router::PathFinderNetRouterHeuristic::setSink ( const Tilewire &  inSink )

inlinevirtual

Set the current routing target.

Implements torc::router::NetRouterHeuristicBase.

Definition at line 100 of file PathFinderNetRouterHeuristic.hpp.

                                             {
            mSinkTileInfo = &mTiles.getTileInfo(inSink.getTileIndex());
            mTargetSink = inSink;
            mRow = mSinkTileInfo->getRow();
            mCol = mSinkTileInfo->getCol();
        }

Here is the call graph for this function:

Field Documentation

ArcVector torc::router::PathFinderNetRouterHeuristic::mArcsBuf

protected

Arc buffer.

Definition at line 79 of file PathFinderNetRouterHeuristic.hpp.

ArcUsage& torc::router::PathFinderNetRouterHeuristic::mArcUsage

protected

ArcUsage reference.

Definition at line 64 of file PathFinderNetRouterHeuristic.hpp.

boost::int32_t torc::router::PathFinderNetRouterHeuristic::mCol

protected

Target column coordinate.

Definition at line 74 of file PathFinderNetRouterHeuristic.hpp.

PathFinderSharingMap* torc::router::PathFinderNetRouterHeuristic::mConflictMap

protected

PathFinder sharing information.

Definition at line 82 of file PathFinderNetRouterHeuristic.hpp.

DDB& torc::router::RouterHeuristicBase::mDB

protectedinherited

Database reference.

Definition at line 40 of file RouterHeuristicBase.hpp.

ParameterMap torc::router::RouterHeuristicBase::mParameters

protectedinherited

Parameter map.

Definition at line 42 of file RouterHeuristicBase.hpp.

boost::int32_t torc::router::PathFinderNetRouterHeuristic::mRow

protected

Target row coordinate.

Definition at line 72 of file PathFinderNetRouterHeuristic.hpp.

TilewireVector torc::router::PathFinderNetRouterHeuristic::mSegmentBuf

protected

Segment tilewire buffer.

Definition at line 77 of file PathFinderNetRouterHeuristic.hpp.

const TileInfo* torc::router::PathFinderNetRouterHeuristic::mSinkTileInfo

protected

Target sink tile information.

Definition at line 70 of file PathFinderNetRouterHeuristic.hpp.

Tilewire torc::router::PathFinderNetRouterHeuristic::mTargetSink

protected

Target sink tilewire.

Definition at line 68 of file PathFinderNetRouterHeuristic.hpp.

const Tiles& torc::router::PathFinderNetRouterHeuristic::mTiles

protected

Tiles reference.

Definition at line 66 of file PathFinderNetRouterHeuristic.hpp.

---

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

• PathFinderNetRouterHeuristic.hpp