PlacementTimingInfo.h

Go to the documentation of this file.

 
#ifndef _PlacementTimingInfo
#define _PlacementTimingInfo
 
#include "DesignInfo.h"
#include "DeviceInfo.h"
#include "dumpZip.h"
#include <algorithm>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <map>
#include <mutex>
#include <semaphore.h>
#include <set>
#include <sstream>
#include <string>
#include <thread>
#include <vector>
 
class PlacementTimingInfo
{
  public:
    PlacementTimingInfo(DesignInfo *designInfo, DeviceInfo *deviceInfo, std::map<std::string, std::string> &JSONCfg);
    ~PlacementTimingInfo()
    {
        if (simpleTimingGraph)
            delete simpleTimingGraph;
    }
 
    template <typename nodeType> class TimingGraph
    {
      public:
        TimingGraph(PlacementTimingInfo *timingInfo) : timingInfo(timingInfo)
        {
            nodes.clear();
            edges.clear();
        }
        ~TimingGraph()
        {
            for (auto edge : edges)
                delete edge;
            for (auto node : nodes)
                delete node;
        }
 
        class TimingEdge;
 
        class TimingNode
        {
          public:
            TimingNode(nodeType *designNode, int id) : designNode(designNode), id(id)
            {
                inEdges.clear();
                outEdges.clear();
            };
            ~TimingNode(){};
 
            inline int getId()
            {
                return id;
            }
 
            inline nodeType *getDesignNode()
            {
                return designNode;
            }
 
            inline void setIsRegister()
            {
                isRegister = true;
            }
 
            inline bool checkIsRegister()
            {
                return isRegister;
            }
 
            inline void addInEdge(TimingEdge *tmpEdge)
            {
                inEdges.push_back(tmpEdge);
            }
 
            inline void addOutEdge(TimingEdge *tmpEdge)
            {
                outEdges.push_back(tmpEdge);
            }
 
            inline void setForwardLevel(int _forwardLevel)
            {
                forwardLevel = _forwardLevel;
                destLevel = _forwardLevel;
            }
 
            inline void setBackwardLevel(int _backwardLevel)
            {
                backwardLevel = _backwardLevel;
            }
 
            inline void calcLongestPath()
            {
                longestPathLength = forwardLevel + backwardLevel + 1;
            }
 
            inline int getForwardLevel()
            {
                return forwardLevel;
            }
 
            inline int getBackwardLevel()
            {
                return backwardLevel;
            }
 
            inline int getLongestPathLength()
            {
 
                if (forwardLevel >= 0 && backwardLevel >= 0)
                    return longestPathLength;
                else
                    return -1;
            }
 
            inline void setDestLevel(int _destLevel)
            {
                destLevel = _destLevel;
            }
 
            inline int getDestLevel()
            {
                return destLevel;
            }
 
            inline std::vector<TimingEdge *> &getOutEdges()
            {
                return outEdges;
            }
 
            void sortOutEdgesByBackwardLevel()
            {
                std::sort(outEdges.begin(), outEdges.end(), [](TimingEdge *a, TimingEdge *b) -> bool {
                    return a->getSink()->getBackwardLevel() < b->getSink()->getBackwardLevel();
                });
            }
 
            inline std::vector<TimingEdge *> &getInEdges()
            {
                return inEdges;
            }
 
            void sortInEdgesByForwardLevel()
            {
                std::sort(inEdges.begin(), inEdges.end(), [](TimingEdge *a, TimingEdge *b) -> bool {
                    return a->getSource()->getForwardLevel() < b->getSource()->getForwardLevel();
                });
            }
 
            inline float getLatestInputArrival()
            {
                return latestInputArrival;
            }
 
            inline void setLatestInputArrival(float _latestInputArrival)
            {
                latestInputArrival = _latestInputArrival;
            }
 
            inline void setLatestOutputArrival(float _latestOutputArrival)
            {
                latestOutputArrival = _latestOutputArrival;
            }
 
            inline float getLatestOutputArrival()
            {
                return latestOutputArrival;
            }
 
            inline int getSlowestPredecessorId()
            {
                return slowestPredecessorId;
            }
 
            inline void setSlowestPredecessorId(int _slowestPredecessorId)
            {
                slowestPredecessorId = _slowestPredecessorId;
            }
 
            inline void setInnerDelay(float _innerDelay)
            {
                innerDelay = _innerDelay;
            }
 
            inline float getInnerDelay()
            {
                return innerDelay;
            }
 
            inline float getRequiredArrivalTime()
            {
                return requiredArrival;
            }
 
            inline void setRequiredArrivalTime(float _requiredArrival)
            {
                requiredArrival = _requiredArrival;
            }
 
            inline void setInitialRequiredArrivalTime(float _requiredArrival)
            {
                if (clockPeriod > 0)
                    requiredArrival = clockPeriod;
                else
                    requiredArrival = _requiredArrival;
            }
 
            inline int getEarlestSuccessorId()
            {
                return slowestPredecessorId;
            }
 
            inline void setEarlestSuccessorId(int _earliestSuccessorId)
            {
                earliestSuccessorId = _earliestSuccessorId;
            }
 
            inline void setClockPeriod(float _clockPeriod)
            {
                clockPeriod = _clockPeriod;
            }
 
            inline float getClockPeriod()
            {
                return clockPeriod;
            }
 
            inline void setClusterId(int _clusterId)
            {
                clusterId = _clusterId;
            }
 
            inline float getClusterId()
            {
                return clusterId;
            }
 
          private:
            nodeType *designNode = nullptr;
            int id;
            float latestInputArrival = 0.0; // ns
            float latestOutputArrival = 0.0;
            float requiredArrival = 10.0; // ns
            float clockPeriod = -10;
            int slowestPredecessorId = -1;
            int earliestSuccessorId = -1;
            int clusterId = -1;
 
            float innerDelay = 0.1;
            bool isRegister = false;
            std::vector<TimingEdge *> inEdges;
            std::vector<TimingEdge *> outEdges;
 
            int forwardLevel = -1;
 
            int backwardLevel = -1;
            int destLevel = -1;
 
            int longestPathLength = 100000000;
        };
 
        class TimingEdge
        {
          public:
            TimingEdge(TimingNode *srcNode, TimingNode *sinkNode, DesignInfo::DesignPin *srcPin,
                       DesignInfo::DesignPin *sinkPin, DesignInfo::DesignNet *net = nullptr, int id = -1)
                : srcNode(srcNode), sinkNode(sinkNode), srcPin(srcPin), sinkPin(sinkPin), net(net), id(id)
            {
                assert(srcPin);
                assert(sinkPin);
                assert(id >= 0);
            }
            ~TimingEdge(){};
 
            inline int getId()
            {
                return id;
            }
 
            inline void setDelay(float _delay)
            {
                delay = _delay;
            }
 
            inline float getDelay()
            {
                return delay;
            }
 
            inline TimingNode *getSink()
            {
                return sinkNode;
            }
 
            inline TimingNode *getSource()
            {
                return srcNode;
            }
 
            inline DesignInfo::DesignPin *getSinkPin()
            {
                return sinkPin;
            }
 
            inline DesignInfo::DesignPin *getSourcePin()
            {
                return srcPin;
            }
 
          private:
            TimingNode *srcNode = nullptr;
            TimingNode *sinkNode = nullptr;
            DesignInfo::DesignPin *srcPin = nullptr;
            DesignInfo::DesignPin *sinkPin = nullptr;
            DesignInfo::DesignNet *net = nullptr;
            int id;
            float delay = 0; // ns
        };
 
        inline void insertTimingNode(TimingNode *timingNode)
        {
            nodes.push_back(timingNode);
        }
 
        inline std::vector<TimingNode *> &getNodes()
        {
            return nodes;
        }
 
        inline std::vector<TimingEdge *> &getEdges()
        {
            return edges;
        }
 
        inline void addEdgeBetween(int idA, int idB, DesignInfo::DesignPin *srcPin, DesignInfo::DesignPin *sinkPin,
                                   DesignInfo::DesignNet *net = nullptr, float delay = 0.0)
        {
            auto newEdge = new TimingEdge(nodes[idA], nodes[idB], srcPin, sinkPin, net, edges.size());
            newEdge->setDelay(delay);
            edges.push_back(newEdge);
 
            nodes[idB]->addInEdge(newEdge);
            nodes[idA]->addOutEdge(newEdge);
        }
 
        void findALoopFromNode(std::vector<int> &nodeInPath, int startNode, int curNode, int level)
        {
            if (level > 0 && curNode == startNode)
            {
                for (auto nodeId : nodeInPath)
                {
                    std::cout << nodes[nodeId]->getDesignNode()->getName() << "  =>" << nodes[nodeId]->checkIsRegister()
                              << "\n";
                    std::cout << nodes[nodeId]->getDesignNode() << "\n";
                }
                exit(0);
            }
            for (auto outEdge : nodes[curNode]->getOutEdges())
            {
                int nextId = outEdge->getSink()->getId();
 
                if (!nodes[nextId]->checkIsRegister())
                {
 
                    nodeInPath.push_back(nextId);
                    findALoopFromNode(nodeInPath, startNode, nextId, level + 1);
                    nodeInPath.pop_back();
                }
            }
        }
 
        void forwardLevelization();
 
        void backwardLevelization();
 
        void propogateArrivalTime();
 
        void backPropogateRequiredArrivalTime();
 
        void updateCriticalPath()
        {
            maxDelay = 0;
            maxDelayId = -1;
            for (unsigned int i = 0; i < getNodes().size(); i++)
            {
                if (getNodes()[i]->getLatestInputArrival() > maxDelay)
                {
                    maxDelay = getNodes()[i]->getLatestInputArrival();
                    maxDelayId = i;
                }
            }
        }
 
        inline int getCriticalEndPoint()
        {
            return maxDelayId;
        }
 
        inline float getCriticalPathDelay()
        {
            return maxDelay;
        }
 
        std::vector<int> backTraceDelayLongestPathFromNode(int curNodeId);
 
        bool backTraceDelayLongestPathFromNode(int curNodeId, std::vector<int> &isCovered, std::vector<int> &resPath,
                                               int converThr = 30);
 
        void setLongestPathLength()
        {
            for (auto tmpNode : nodes)
            {
                tmpNode->calcLongestPath();
                tmpNode->getDesignNode()->setTimingLength(tmpNode->getLongestPathLength());
            }
 
            pathLenSortedNodes = nodes;
            std::sort(pathLenSortedNodes.begin(), pathLenSortedNodes.end(), [](TimingNode *a, TimingNode *b) -> bool {
                return (a->getLongestPathLength() == b->getLongestPathLength())
                           ? (a->getForwardLevel() < b->getForwardLevel())
                           : (a->getLongestPathLength() > b->getLongestPathLength());
            });
        }
 
        void sortedEndpointByDelay()
        {
            delaySortedTimingEndpointNodes.clear();
            for (auto id : forwardlevel2NodeIds[0])
            {
                if (nodes[id]->getInEdges().size() == 0)
                    continue;
                delaySortedTimingEndpointNodes.push_back(nodes[id]);
            }
            std::sort(delaySortedTimingEndpointNodes.begin(), delaySortedTimingEndpointNodes.end(),
                      [](TimingNode *a, TimingNode *b) -> bool {
                          return (a->getLatestInputArrival() > b->getLatestInputArrival());
                      });
        }
 
        inline std::vector<TimingNode *> &getSortedTimingEndpoints()
        {
            return delaySortedTimingEndpointNodes;
        }
 
        std::vector<int> traceBackFromNode(int targetId);
 
        std::vector<int> traceForwardFromNode(int targetId);
 
        std::vector<int> BFSFromNode(int startNodeId, int pathLenThr, unsigned sizeThr, std::set<int> &exceptionCells);
 
        std::vector<int> DFSFromNode(int startNodeId, int pathLenThr, unsigned sizeThr, std::set<int> &exceptionCells,
                                     int fanoutThr = 10000000);
 
        inline std::vector<TimingNode *> &getPathLenSortedNodes()
        {
            return pathLenSortedNodes;
        }
 
        inline int getLongPathThresholdLevel()
        {
            return longPathThresholdLevel;
        }
 
        inline int getMediumPathThresholdLevel()
        {
            return mediumPathThresholdLevel;
        }
 
        inline void setLongPathThrRatio(float _r)
        {
            longPathThrRatio = _r;
        }
 
        inline float getClockPeriod()
        {
            return clockPeriod;
        }
 
        inline void setClockPeriod(float _clockPeriod)
        {
            clockPeriod = _clockPeriod;
        }
 
      private:
        PlacementTimingInfo *timingInfo = nullptr;
        std::vector<TimingNode *> nodes;
        std::vector<TimingNode *> pathLenSortedNodes;
        std::vector<TimingNode *> delaySortedTimingEndpointNodes;
        std::vector<TimingEdge *> edges;
 
        std::vector<std::vector<int>> forwardlevel2NodeIds;
 
        std::vector<std::vector<int>> backwardlevel2NodeIds;
 
        float longPathThrRatio = 0.95;
        float mediumPathThrRatio = 0.8;
        int longPathThresholdLevel = 1;
        int mediumPathThresholdLevel = 1;
 
        float clockPeriod = 10.0; // ns
 
        float maxDelay = 0;
        int maxDelayId = -1;
    };
 
    void buildSimpleTimingGraph();
 
    inline std::vector<TimingGraph<DesignInfo::DesignCell>::TimingNode *> &getSimplePlacementTimingInfo()
    {
        return simpleTimingGraph->getNodes();
    }
 
    inline std::vector<TimingGraph<DesignInfo::DesignCell>::TimingNode *> &getSimplePlacementTimingInfo_PathLenSorted()
    {
        return simpleTimingGraph->getPathLenSortedNodes();
    }
 
    inline TimingGraph<DesignInfo::DesignCell> *getSimplePlacementTimingGraph()
    {
        return simpleTimingGraph;
    }
 
    inline int getLongPathThresholdLevel()
    {
        return simpleTimingGraph->getLongPathThresholdLevel();
    }
 
    inline int getMediumPathThresholdLevel()
    {
        return simpleTimingGraph->getMediumPathThresholdLevel();
    }
 
    inline DeviceInfo *getDeviceInfo()
    {
        return deviceInfo;
    }
 
    void setDSPInnerDelay();
 
  private:
    DesignInfo *designInfo;
    DeviceInfo *deviceInfo;
 
    // settings
    std::map<std::string, std::string> &JSONCfg;
 
    TimingGraph<DesignInfo::DesignCell> *simpleTimingGraph = nullptr;
    bool verbose = false;
 
    float clockPeriod = 10.0; // ns
    bool DSPCritical = false;
 
    std::map<DesignInfo::DesignNet *, float> clockNet2Period;
    std::map<int, float> cellId2Period;
};
 
#endif