AMF-Placer  2.0
An Open-Source Timing-driven Analytical Mixed-size FPGA Placer
Classes | Public Member Functions | Private Attributes | List of all members
PlacementTimingInfo::TimingGraph< nodeType > Class Template Reference

a directed graph for timing analysis More...

#include <PlacementTimingInfo.h>

Collaboration diagram for PlacementTimingInfo::TimingGraph< nodeType >:
Collaboration graph
[legend]

Classes

class  TimingEdge
 TimingEdge records a directed interconnection relationship between two TimingNode. It is a point-to-point information instead of HyperEdge. More...
 
class  TimingNode
 TimingNode is the node in TimingGraph, which could be pin or cell in the design netlist. More...
 

Public Member Functions

 TimingGraph (PlacementTimingInfo *timingInfo)
 Construct a new empty Timing Graph object. More...
 
 ~TimingGraph ()
 
void insertTimingNode (TimingNode *timingNode)
 insert a TimingNode into this TimingGraph More...
 
std::vector< TimingNode * > & getNodes ()
 
std::vector< TimingEdge * > & getEdges ()
 
void addEdgeBetween (int idA, int idB, DesignInfo::DesignPin *srcPin, DesignInfo::DesignPin *sinkPin, DesignInfo::DesignNet *net=nullptr, float delay=0.0)
 add a TimingEdge into TimingGraph based on some related information More...
 
void findALoopFromNode (std::vector< int > &nodeInPath, int startNode, int curNode, int level)
 find loop from a node in timing graph (for debug) More...
 
void forwardLevelization ()
 propogate the forward level of each TimingNode forward level of a TimingNode is the distance toward the farthest predecessor register based on the path length (instead of delay) More...
 
void backwardLevelization ()
 propogate the backward level of each TimingNode backward level of a TimingNode is the distance toward the farthest successor register based on the path length (instead of delay) More...
 
void propogateArrivalTime ()
 propogate the timing delay along the TimingEdge More...
 
void backPropogateRequiredArrivalTime ()
 back propogate the required arrival time More...
 
void updateCriticalPath ()
 
int getCriticalEndPoint ()
 
float getCriticalPathDelay ()
 
std::vector< int > backTraceDelayLongestPathFromNode (int curNodeId)
 backtrace the longest delay path from the node More...
 
bool backTraceDelayLongestPathFromNode (int curNodeId, std::vector< int > &isCovered, std::vector< int > &resPath, int converThr=30)
 
void setLongestPathLength ()
 Set the Longest Path Length for each TimingNode in the TimingGraph and get a sorted vector of TimingNodes. More...
 
void sortedEndpointByDelay ()
 
std::vector< TimingNode * > & getSortedTimingEndpoints ()
 
std::vector< int > traceBackFromNode (int targetId)
 find the longest path from a register to the target node (id) More...
 
std::vector< int > traceForwardFromNode (int targetId)
 find the longest path from the target node (id) to a register More...
 
std::vector< int > BFSFromNode (int startNodeId, int pathLenThr, unsigned sizeThr, std::set< int > &exceptionCells)
 BFS the sucessors(predecessors) of a node in the long paths. More...
 
std::vector< int > DFSFromNode (int startNodeId, int pathLenThr, unsigned sizeThr, std::set< int > &exceptionCells, int fanoutThr=10000000)
 DFS the sucessors(predecessors) of a node in the long paths. More...
 
std::vector< TimingNode * > & getPathLenSortedNodes ()
 
int getLongPathThresholdLevel ()
 Get the long path threshold level. More...
 
int getMediumPathThresholdLevel ()
 Get the medium path threshold level. More...
 
void setLongPathThrRatio (float _r)
 
float getClockPeriod ()
 Get the clock period. More...
 
void setClockPeriod (float _clockPeriod)
 Set the clock period. More...
 

Private Attributes

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
 levelized nodes in difference forward level More...
 
std::vector< std::vector< int > > backwardlevel2NodeIds
 levelized nodes in difference backward level More...
 
float longPathThrRatio = 0.95
 
float mediumPathThrRatio = 0.8
 
int longPathThresholdLevel = 1
 
int mediumPathThresholdLevel = 1
 
float clockPeriod = 10.0
 
float maxDelay = 0
 
int maxDelayId = -1
 

Detailed Description

template<typename nodeType>
class PlacementTimingInfo::TimingGraph< nodeType >

a directed graph for timing analysis

Template Parameters
nodeTypeindicate the type of a node in the graph, usually it is a DesignCell* or DesignPin*

Definition at line 70 of file PlacementTimingInfo.h.

Constructor & Destructor Documentation

◆ TimingGraph()

template<typename nodeType >
PlacementTimingInfo::TimingGraph< nodeType >::TimingGraph ( PlacementTimingInfo *  timingInfo)
inline

Construct a new empty Timing Graph object.

Definition at line 77 of file PlacementTimingInfo.h.

◆ ~TimingGraph()

template<typename nodeType >
PlacementTimingInfo::TimingGraph< nodeType >::~TimingGraph ( )
inline

Definition at line 82 of file PlacementTimingInfo.h.

Member Function Documentation

◆ addEdgeBetween()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::addEdgeBetween ( int  idA,
int  idB,
DesignInfo::DesignPin *  srcPin,
DesignInfo::DesignPin *  sinkPin,
DesignInfo::DesignNet *  net = nullptr,
float  delay = 0.0 
)
inline

add a TimingEdge into TimingGraph based on some related information

Parameters
idATimingNode A id
idBTimingNode B id
srcPinsource DesignPin
sinkPinsink DesignPin
netrelated DesignNet
delaythe delay of this interconnection

Definition at line 557 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::buildSimpleTimingGraph().

Here is the caller graph for this function:

◆ backPropogateRequiredArrivalTime()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::backPropogateRequiredArrivalTime ( )

back propogate the required arrival time

Definition at line 650 of file PlacementTimingInfo.cc.

◆ backTraceDelayLongestPathFromNode() [1/2]

template<typename nodeType >
std::vector< int > PlacementTimingInfo::TimingGraph< nodeType >::backTraceDelayLongestPathFromNode ( int  curNodeId)

backtrace the longest delay path from the node

Parameters
curNodeId
Returns
std::vector<int>

Definition at line 685 of file PlacementTimingInfo.cc.

◆ backTraceDelayLongestPathFromNode() [2/2]

template<typename nodeType >
bool PlacementTimingInfo::TimingGraph< nodeType >::backTraceDelayLongestPathFromNode ( int  curNodeId,
std::vector< int > &  isCovered,
std::vector< int > &  resPath,
int  converThr = 30 
)

Definition at line 703 of file PlacementTimingInfo.cc.

◆ backwardLevelization()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::backwardLevelization ( )

propogate the backward level of each TimingNode backward level of a TimingNode is the distance toward the farthest successor register based on the path length (instead of delay)

Definition at line 309 of file PlacementTimingInfo.cc.

Referenced by PlacementTimingInfo::buildSimpleTimingGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ BFSFromNode()

template<typename nodeType >
std::vector< int > PlacementTimingInfo::TimingGraph< nodeType >::BFSFromNode ( int  startNodeId,
int  pathLenThr,
unsigned  sizeThr,
std::set< int > &  exceptionCells 
)

BFS the sucessors(predecessors) of a node in the long paths.

Parameters
startNodeIdstart node Id
sizeThrthe number limitation to avoid huge cluster
Returns
std::vector<int>

Definition at line 519 of file PlacementTimingInfo.cc.

◆ DFSFromNode()

template<typename nodeType >
std::vector< int > PlacementTimingInfo::TimingGraph< nodeType >::DFSFromNode ( int  startNodeId,
int  pathLenThr,
unsigned  sizeThr,
std::set< int > &  exceptionCells,
int  fanoutThr = 10000000 
)

DFS the sucessors(predecessors) of a node in the long paths.

Parameters
startNodeIdstart node Id
sizeThrthe number limitation to avoid huge cluster
fanoutThrlimit the node fanout during DFS
Returns
std::vector<int>

Definition at line 460 of file PlacementTimingInfo.cc.

◆ findALoopFromNode()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::findALoopFromNode ( std::vector< int > &  nodeInPath,
int  startNode,
int  curNode,
int  level 
)
inline

find loop from a node in timing graph (for debug)

Parameters
nodeInPath
startNode
curNode
level

Definition at line 576 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::findALoopFromNode().

Here is the caller graph for this function:

◆ forwardLevelization()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::forwardLevelization ( )

propogate the forward level of each TimingNode forward level of a TimingNode is the distance toward the farthest predecessor register based on the path length (instead of delay)

Definition at line 186 of file PlacementTimingInfo.cc.

Referenced by PlacementTimingInfo::buildSimpleTimingGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ getClockPeriod()

template<typename nodeType >
float PlacementTimingInfo::TimingGraph< nodeType >::getClockPeriod ( )
inline

Get the clock period.

TODO: enable multiple clock

Returns
float

Definition at line 777 of file PlacementTimingInfo.h.

Referenced by WirelengthOptimizer::addPseudoNet_SlackBased(), ParallelCLBPacker::PackingCLBSite::checkDirectLUTFFConnect_slack(), ParallelCLBPacker::PackingCLBSite::finalMapToSlotsForCarrySite(), ParallelCLBPacker::PackingCLBSite::finalMapToSlotsForCommonLUTFFInSite(), ParallelCLBPacker::PackingCLBSite::greedyMapMuxForCommonLUTFFInSite(), and WirelengthOptimizer::LUTLUTPairing_TimingDriven().

Here is the caller graph for this function:

◆ getCriticalEndPoint()

template<typename nodeType >
int PlacementTimingInfo::TimingGraph< nodeType >::getCriticalEndPoint ( )
inline

Definition at line 642 of file PlacementTimingInfo.h.

◆ getCriticalPathDelay()

template<typename nodeType >
float PlacementTimingInfo::TimingGraph< nodeType >::getCriticalPathDelay ( )
inline

Definition at line 647 of file PlacementTimingInfo.h.

◆ getEdges()

template<typename nodeType >
std::vector<TimingEdge *>& PlacementTimingInfo::TimingGraph< nodeType >::getEdges ( )
inline

Definition at line 542 of file PlacementTimingInfo.h.

◆ getLongPathThresholdLevel()

template<typename nodeType >
int PlacementTimingInfo::TimingGraph< nodeType >::getLongPathThresholdLevel ( )
inline

Get the long path threshold level.

Returns
int

Definition at line 750 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::getLongPathThresholdLevel().

Here is the caller graph for this function:

◆ getMediumPathThresholdLevel()

template<typename nodeType >
int PlacementTimingInfo::TimingGraph< nodeType >::getMediumPathThresholdLevel ( )
inline

Get the medium path threshold level.

Returns
int

Definition at line 760 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::getMediumPathThresholdLevel().

Here is the caller graph for this function:

◆ getNodes()

template<typename nodeType >
std::vector<TimingNode *>& PlacementTimingInfo::TimingGraph< nodeType >::getNodes ( )
inline

Definition at line 537 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::buildSimpleTimingGraph(), PlacementTimingOptimizer::findCriticalPath(), PlacementTimingInfo::getSimplePlacementTimingInfo(), PlacementInfo::reloadNets(), PlacementTimingInfo::setDSPInnerDelay(), and PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::updateCriticalPath().

Here is the caller graph for this function:

◆ getPathLenSortedNodes()

template<typename nodeType >
std::vector<TimingNode *>& PlacementTimingInfo::TimingGraph< nodeType >::getPathLenSortedNodes ( )
inline

Definition at line 740 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::getSimplePlacementTimingInfo_PathLenSorted().

Here is the caller graph for this function:

◆ getSortedTimingEndpoints()

template<typename nodeType >
std::vector<TimingNode *>& PlacementTimingInfo::TimingGraph< nodeType >::getSortedTimingEndpoints ( )
inline

Definition at line 699 of file PlacementTimingInfo.h.

◆ insertTimingNode()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::insertTimingNode ( TimingNode *  timingNode)
inline

insert a TimingNode into this TimingGraph

Parameters
timingNodea given TimingNode

Definition at line 532 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::buildSimpleTimingGraph().

Here is the caller graph for this function:

◆ propogateArrivalTime()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::propogateArrivalTime ( )

propogate the timing delay along the TimingEdge

Definition at line 578 of file PlacementTimingInfo.cc.

◆ setClockPeriod()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::setClockPeriod ( float  _clockPeriod)
inline

Set the clock period.

TODO: enable multiple clock

Parameters
_clockPeriod

Definition at line 789 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::buildSimpleTimingGraph().

Here is the caller graph for this function:

◆ setLongestPathLength()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::setLongestPathLength ( )
inline

Set the Longest Path Length for each TimingNode in the TimingGraph and get a sorted vector of TimingNodes.

Definition at line 668 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::buildSimpleTimingGraph().

Here is the caller graph for this function:

◆ setLongPathThrRatio()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::setLongPathThrRatio ( float  _r)
inline

Definition at line 765 of file PlacementTimingInfo.h.

◆ sortedEndpointByDelay()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::sortedEndpointByDelay ( )
inline

Definition at line 684 of file PlacementTimingInfo.h.

Referenced by PlacementTimingOptimizer::findCriticalPaths(), PlacementTimingOptimizer::getSortedTimingNodes(), and PlacementInfo::transferPaintData().

Here is the caller graph for this function:

◆ traceBackFromNode()

template<typename nodeType >
std::vector< int > PlacementTimingInfo::TimingGraph< nodeType >::traceBackFromNode ( int  targetId)

find the longest path from a register to the target node (id)

Parameters
targetId
Returns
std::vector<int>

Definition at line 399 of file PlacementTimingInfo.cc.

◆ traceForwardFromNode()

template<typename nodeType >
std::vector< int > PlacementTimingInfo::TimingGraph< nodeType >::traceForwardFromNode ( int  targetId)

find the longest path from the target node (id) to a register

Parameters
targetId
Returns
std::vector<int>

Definition at line 429 of file PlacementTimingInfo.cc.

◆ updateCriticalPath()

template<typename nodeType >
void PlacementTimingInfo::TimingGraph< nodeType >::updateCriticalPath ( )
inline

Definition at line 628 of file PlacementTimingInfo.h.

Member Data Documentation

◆ backwardlevel2NodeIds

template<typename nodeType >
std::vector<std::vector<int> > PlacementTimingInfo::TimingGraph< nodeType >::backwardlevel2NodeIds
private

levelized nodes in difference backward level

Definition at line 811 of file PlacementTimingInfo.h.

◆ clockPeriod

template<typename nodeType >
float PlacementTimingInfo::TimingGraph< nodeType >::clockPeriod = 10.0
private

Definition at line 818 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::getClockPeriod(), and PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::setClockPeriod().

◆ delaySortedTimingEndpointNodes

template<typename nodeType >
std::vector<TimingNode *> PlacementTimingInfo::TimingGraph< nodeType >::delaySortedTimingEndpointNodes
private

Definition at line 798 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::getSortedTimingEndpoints(), and PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::sortedEndpointByDelay().

◆ edges

template<typename nodeType >
std::vector<TimingEdge *> PlacementTimingInfo::TimingGraph< nodeType >::edges
private

Definition at line 799 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::addEdgeBetween(), PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::getEdges(), PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::TimingGraph(), and PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::~TimingGraph().

◆ forwardlevel2NodeIds

template<typename nodeType >
std::vector<std::vector<int> > PlacementTimingInfo::TimingGraph< nodeType >::forwardlevel2NodeIds
private

levelized nodes in difference forward level

Definition at line 805 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::sortedEndpointByDelay().

◆ longPathThresholdLevel

template<typename nodeType >
int PlacementTimingInfo::TimingGraph< nodeType >::longPathThresholdLevel = 1
private

Definition at line 815 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::getLongPathThresholdLevel().

◆ longPathThrRatio

template<typename nodeType >
float PlacementTimingInfo::TimingGraph< nodeType >::longPathThrRatio = 0.95
private

Definition at line 813 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::setLongPathThrRatio().

◆ maxDelay

template<typename nodeType >
float PlacementTimingInfo::TimingGraph< nodeType >::maxDelay = 0
private

Definition at line 820 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::getCriticalPathDelay(), and PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::updateCriticalPath().

◆ maxDelayId

template<typename nodeType >
int PlacementTimingInfo::TimingGraph< nodeType >::maxDelayId = -1
private

Definition at line 821 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::getCriticalEndPoint(), and PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::updateCriticalPath().

◆ mediumPathThresholdLevel

template<typename nodeType >
int PlacementTimingInfo::TimingGraph< nodeType >::mediumPathThresholdLevel = 1
private

Definition at line 816 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::getMediumPathThresholdLevel().

◆ mediumPathThrRatio

template<typename nodeType >
float PlacementTimingInfo::TimingGraph< nodeType >::mediumPathThrRatio = 0.8
private

Definition at line 814 of file PlacementTimingInfo.h.

◆ nodes

template<typename nodeType >
std::vector<TimingNode *> PlacementTimingInfo::TimingGraph< nodeType >::nodes
private

Definition at line 796 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::addEdgeBetween(), PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::findALoopFromNode(), PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::getNodes(), PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::insertTimingNode(), PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::setLongestPathLength(), PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::sortedEndpointByDelay(), PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::TimingGraph(), and PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::~TimingGraph().

◆ pathLenSortedNodes

template<typename nodeType >
std::vector<TimingNode *> PlacementTimingInfo::TimingGraph< nodeType >::pathLenSortedNodes
private

Definition at line 797 of file PlacementTimingInfo.h.

Referenced by PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::getPathLenSortedNodes(), and PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::setLongestPathLength().

◆ timingInfo

template<typename nodeType >
PlacementTimingInfo* PlacementTimingInfo::TimingGraph< nodeType >::timingInfo = nullptr
private

Definition at line 795 of file PlacementTimingInfo.h.

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