torc::router::NetRouterHeuristic Class Reference

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

#include <NetRouterHeuristic.hpp>

Inheritance diagram for torc::router::NetRouterHeuristic:

Collaboration diagram for torc::router::NetRouterHeuristic:

Public Member Functions
	NetRouterHeuristic (DDB &inDB)
	Public Constructor. More...
	~NetRouterHeuristic ()
	Destructor. More...
virtual void	setSink (const Tilewire &inSink)
	Set the current routing target. More...
virtual void	nodeCost (RouteNode &inNode)
	Calculate the node cost based on distance to the sink and path length. More...
virtual void	nodeCostInitial (RouteNode &inNode)
virtual void	reorderSinks (const Tilewire &inSource, TilewireVector &inSinks)
	Reorder the Sinks based on this heuristic. More...
virtual 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...
virtual void	processParameters ()
	Do something with the parameters. More...

Protected Member Functions
virtual boost::int32_t	distanceToSink (const Tilewire &inTilewire)
virtual boost::int32_t	clkDistanceToSink (const Tilewire &inTilewire)
boost::int32_t	distanceFromParent (const Tilewire &inParent, const Tilewire &inCurrent)

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...
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

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 43 of file NetRouterHeuristic.hpp.

Member Typedef Documentation

typedef architecture::Arc torc::router::NetRouterHeuristic::Arc

private

Definition at line 52 of file NetRouterHeuristic.hpp.

typedef architecture::ArcUsage torc::router::NetRouterHeuristic::ArcUsage

private

Definition at line 48 of file NetRouterHeuristic.hpp.

typedef architecture::ArcVector torc::router::NetRouterHeuristic::ArcVector

private

Definition at line 54 of file NetRouterHeuristic.hpp.

typedef architecture::DDB torc::router::NetRouterHeuristic::DDB

private

Imported type names.

Definition at line 46 of file NetRouterHeuristic.hpp.

typedef architecture::xilinx::TileCol torc::router::NetRouterHeuristic::TileCol

private

Definition at line 56 of file NetRouterHeuristic.hpp.

typedef architecture::TileInfo torc::router::NetRouterHeuristic::TileInfo

private

Definition at line 51 of file NetRouterHeuristic.hpp.

typedef architecture::xilinx::TileRow torc::router::NetRouterHeuristic::TileRow

private

Definition at line 55 of file NetRouterHeuristic.hpp.

typedef architecture::Tiles torc::router::NetRouterHeuristic::Tiles

private

Definition at line 47 of file NetRouterHeuristic.hpp.

typedef architecture::Tilewire torc::router::NetRouterHeuristic::Tilewire

private

Definition at line 50 of file NetRouterHeuristic.hpp.

typedef architecture::TilewireVector torc::router::NetRouterHeuristic::TilewireVector

private

Definition at line 53 of file NetRouterHeuristic.hpp.

typedef architecture::WireUsage torc::router::NetRouterHeuristic::WireUsage

private

Definition at line 49 of file NetRouterHeuristic.hpp.

Constructor & Destructor Documentation

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

inline

Public Constructor.

Definition at line 83 of file NetRouterHeuristic.hpp.

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

torc::router::NetRouterHeuristic::~NetRouterHeuristic ( )

inline

Destructor.

Definition at line 86 of file NetRouterHeuristic.hpp.

{}

Member Function Documentation

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

inlineprotectedvirtual

Definition at line 206 of file NetRouterHeuristic.hpp.

                                                                           {
            return -100;
        }

boost::int32_t torc::router::NetRouterHeuristic::distanceFromParent ( const Tilewire &  inParent, const Tilewire &  inCurrent  )

inlineprotected

Definition at line 210 of file NetRouterHeuristic.hpp.

                                                                                             {
            const TileInfo* parentInfo = &mTiles.getTileInfo(inParent.getTileIndex());
            const TileInfo* currentInfo = &mTiles.getTileInfo(inCurrent.getTileIndex());
            
            boost::int32_t distance = 0;
            boost::int32_t pRow = parentInfo->getRow();
            boost::int32_t pCol = parentInfo->getCol();
            boost::int32_t cRow = currentInfo->getRow();
            boost::int32_t cCol = currentInfo->getCol();
            distance += pRow < cRow ? cRow - pRow : pRow - cRow;
            distance += pCol < cCol ? cCol - pCol : pCol - cCol;
            return distance;
        }

Here is the call graph for this function:

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

inlineprotectedvirtual

Definition at line 196 of file NetRouterHeuristic.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:

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

inlinevirtual

Heuristic handling of expansion of a node.

Reimplemented from torc::router::NetRouterHeuristicBase.

Definition at line 174 of file NetRouterHeuristic.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:

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:

virtual void torc::router::NetRouterHeuristic::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 96 of file NetRouterHeuristic.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();
            mDB.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;
            inNode.setCost(cost);
            
        }

Here is the call graph for this function:

Here is the caller graph for this function:

virtual void torc::router::NetRouterHeuristic::nodeCostInitial ( RouteNode &  inNode )

inlinevirtual

Definition at line 136 of file NetRouterHeuristic.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();
            mDB.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:

Here is the caller graph for this function:

virtual void torc::router::RouterHeuristicBase::processParameters ( )

inlinevirtualinherited

Do something with the parameters.

Reimplemented in torc::router::PathFinderNetRouterHeuristic.

Definition at line 64 of file RouterHeuristicBase.hpp.

{}

Here is the caller graph for this function:

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

inlinevirtual

Reorder the Sinks based on this heuristic.

Reimplemented from torc::router::NetRouterHeuristicBase.

Definition at line 170 of file NetRouterHeuristic.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:

virtual void torc::router::NetRouterHeuristic::setSink ( const Tilewire &  inSink )

inlinevirtual

Set the current routing target.

Implements torc::router::NetRouterHeuristicBase.

Definition at line 89 of file NetRouterHeuristic.hpp.

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

Here is the call graph for this function:

Here is the caller graph for this function:

Field Documentation

ArcVector torc::router::NetRouterHeuristic::mArcsBuf

protected

Arc buffer.

Definition at line 76 of file NetRouterHeuristic.hpp.

ArcUsage& torc::router::NetRouterHeuristic::mArcUsage

protected

ArcUsage reference.

Definition at line 61 of file NetRouterHeuristic.hpp.

boost::int32_t torc::router::NetRouterHeuristic::mCol

protected

Target column coordinate.

Definition at line 71 of file NetRouterHeuristic.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::NetRouterHeuristic::mRow

protected

Target row coordinate.

Definition at line 69 of file NetRouterHeuristic.hpp.

TilewireVector torc::router::NetRouterHeuristic::mSegmentBuf

protected

Segment tilewire buffer.

Definition at line 74 of file NetRouterHeuristic.hpp.

const TileInfo* torc::router::NetRouterHeuristic::mSinkTileInfo

protected

Target sink tile information.

Definition at line 67 of file NetRouterHeuristic.hpp.

Tilewire torc::router::NetRouterHeuristic::mTargetSink

protected

Target sink tilewire.

Definition at line 65 of file NetRouterHeuristic.hpp.

const Tiles& torc::router::NetRouterHeuristic::mTiles

protected

Tiles reference.

Definition at line 63 of file NetRouterHeuristic.hpp.

---

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

• NetRouterHeuristic.hpp