NetRouterHeuristic.hpp

Go to the documentation of this file.

// Torc - Copyright 2011-2013 University of Southern California.  All Rights Reserved.
// $HeadURL$
// $Id$

// This program is free software: you can redistribute it and/or modify it under the terms of the 
// GNU General Public License as published by the Free Software Foundation, either version 3 of the 
// License, or (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
// without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See 
// the GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License along with this program.  If 
// not, see <http://www.gnu.org/licenses/>.

/// \file
/// \brief Header for the Heuristic class.

#ifndef TORC_ROUTER_NETROUTERHEURISTIC_HPP
#define TORC_ROUTER_NETROUTERHEURISTIC_HPP

#include "torc/architecture/DDB.hpp"
#include "torc/router/RouteNode.hpp"
#include "torc/router/NetRouterHeuristicBase.hpp"
#include "torc/architecture/OutputStreamHelpers.hpp"
#include "torc/architecture/XilinxDatabaseTypes.hpp"
#include <set>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <boost/cstdint.hpp>
#include <boost/timer.hpp>
#include <boost/unordered_map.hpp>
#include <boost/functional/hash.hpp>
#include <boost/integer_traits.hpp>

namespace torc {
namespace router {

    /// \brief Provides net routing based on the Nillson graphsearch algorithm.
    /// \details The router can either return a vector of nodes or directly populate DDB usage.
    class NetRouterHeuristic : public NetRouterHeuristicBase {
    // types
        /// \brief Imported type names
        typedef architecture::DDB DDB;
        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;
                
    protected:
    // members
        /// \brief ArcUsage reference.
        ArcUsage& mArcUsage;
        /// \brief Tiles reference.
        const Tiles& mTiles;
        /// \brief Target sink tilewire.
        Tilewire mTargetSink;       
        /// \brief Target sink tile information.
        const TileInfo* mSinkTileInfo;
        /// \brief Target row coordinate
        boost::int32_t mRow;
        /// \brief Target column coordinate
        boost::int32_t mCol;
        
        /// \brief Segment tilewire buffer.
        TilewireVector mSegmentBuf;
        /// \brief Arc buffer.
        ArcVector mArcsBuf;
        
        
        
    public:
    // constructor
        /// \brief Public Constructor
        NetRouterHeuristic(DDB& inDB) : NetRouterHeuristicBase(inDB), 
            mArcUsage(inDB.getArcUsage()), mTiles(inDB.getTiles()) {}
        /// \brief Destructor.
        ~NetRouterHeuristic() {}

        /// \brief Set the current routing target
        virtual void setSink(const Tilewire& inSink) {
            mSinkTileInfo = &mTiles.getTileInfo(inSink.getTileIndex());
            mTargetSink = inSink;
            mRow = mSinkTileInfo->getRow();
            mCol = mSinkTileInfo->getCol();
        }
        /// \brief Calculate the node cost based on distance to the sink and path length
        virtual void nodeCost(RouteNode& inNode) {
            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);
            
        }
        /// \brief 
        virtual void nodeCostInitial(RouteNode& inNode) {
            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);   
        }
        /// \brief Reorder the Sinks based on this heuristic.
        virtual void reorderSinks(const Tilewire& inSource, TilewireVector& inSinks) {
            // do nothing for now
        }
        /// \brief Heuristic handling of expansion of a node.
        virtual void expandSegmentSinks(const Tilewire& inTilewire, ArcVector& outArcs) {
            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]);
            }
        }

    protected:
        virtual boost::int32_t distanceToSink(const Tilewire& inTilewire) {
            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;
        }
        
        virtual boost::int32_t clkDistanceToSink(const Tilewire& inTilewire) {
            return -100;
        }
        
        boost::int32_t distanceFromParent(const Tilewire& inParent, const Tilewire& inCurrent) {
            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;
        }
    }; // class Heuristic
    

} // namespace router
} // namespace torc

#endif // TORC_ROUTER_NETROUTERHEURISTIC_HPP