com.xilinx.rapidwright.timing

Class TimingGraph

Object

org.jgrapht.graph.AbstractGraph<V,E>

org.jgrapht.graph.AbstractBaseGraph<V,E>

org.jgrapht.graph.DefaultDirectedGraph<V,E>

org.jgrapht.graph.DefaultDirectedWeightedGraph<TimingVertex,TimingEdge>

com.xilinx.rapidwright.timing.TimingGraph

All Implemented Interfaces:

Serializable, Cloneable, org.jgrapht.Graph<TimingVertex,TimingEdge>

public class TimingGraph
extends org.jgrapht.graph.DefaultDirectedWeightedGraph<TimingVertex,TimingEdge>

A TimingGraph is an acyclic weighted-directed graph representing logic delays and physical net delays based on analyzing the circuits within Design objects.

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
boolean	debug
boolean	overwriteBUGCEDelay
TimingVertex	superSink
TimingVertex	superSource The superSource and superSink are used to consolidate all timing start and end points, respectively.
boolean	verbose

Fields inherited from interface org.jgrapht.Graph

DEFAULT_EDGE_WEIGHT

Constructor Summary

Constructors

Constructor and Description
TimingGraph(Design design) Creates a TimingGraph for the purpose of report_timing based on analyzing nets within a Design object.
TimingGraph(Design design, RuntimeTrackerTree timer, ClkRouteTiming clkTiming, String dspTimingDataFolder)

Method Summary

Modifier and Type	Method and Description
int	addNetDelayEdges(Net net)
boolean	addTimingPath(org.jgrapht.GraphPath<TimingVertex,TimingEdge> path) Inserts a GraphPath into the TimingGraph.
void	build(boolean isPartialRouting, Collection<Net> targetNets) Builds the TimingGraph based on analyzing nets within a Design object.
List<org.jgrapht.GraphPath<TimingVertex,TimingEdge>>	buildGraphPaths() Builds and returns a set of GraphPaths.
void	buildSuperGraphPaths() Connects the sources and sinks of timing paths to a superSource and a superSink, respectively
void	computeArrivalTimes() Computes/recomputes the arrival times stored at the vertices of the graph based on the edges
void	computeArrivalTimesTopologicalOrder() Computes/recomputes the arrival time stored at each vertex of the graph using TopologicalOrderIterator
void	computeSlacks() Computes/recomputes the slack stored at vertices of the graph based on comparing required times and arrival times.
void	generateGraphvizDotVisualization(String dotFileName) This creates a GraphViz library dot file representation of the TimingGraph.
EDIFHierNet	getClockNet(org.jgrapht.GraphPath<TimingVertex,TimingEdge> path) Gets the parent clock net of the launching synchronizer of the path (usually a flip flop).
static String	getClockRegionOfCellPin(String cellPinName, Design design) Get the clock region that the cell pin resides in
List<TimingEdge>	getCriticalTimingEdgesInOrder(TimingVertex maxV) Get a list of timing edges consisting of the critical path
float	getDelay(org.jgrapht.GraphPath<TimingVertex,TimingEdge> graphPath) Gets the delay/weight of a GraphPath
HashSet<org.jgrapht.GraphPath<TimingVertex,TimingEdge>>	getGraphPaths() Returns a set of built GraphPaths.
DelayModel	getintraSiteAndLogicDelayModel()
Pair<Float,TimingVertex>	getMaxDelay() Get the maximum delay, i.e., the maximum arrival time, and corresponding timing path sink of the design
org.jgrapht.GraphPath<TimingVertex,TimingEdge>	getMaxDelayPath() Finds and returns the path from the TimingGraph having maximum delay.
Float	getPathDelay(org.jgrapht.GraphPath<TimingVertex,TimingEdge> path) Gets the total timing delay of the provided path.
float	getRequiredTime(org.jgrapht.GraphPath<TimingVertex,TimingEdge> graphPath) Gets the required time from a specified GraphPath at its source.
Float	getSlack(org.jgrapht.GraphPath<TimingVertex,TimingEdge> graphPath) Gets the slack from a specified GraphPath at its source.
Map<TimingEdge,Connection>	getTimingEdgeConnectionMap()
List<TimingEdge>	getTimingEdgeOfPath(List<String> verticesNames) Finds the given critical path in the timing graph and reports the delay detail
TimingManager	getTimingManager() Returns a reference to the associated TimingManager.
TimingModel	getTimingModel() Returns a reference to the associated TimingModel.
org.jgrapht.GraphPath<TimingVertex,TimingEdge>	getTimingPath(EDIFHierPortInst src, EDIFHierPortInst snk) Gets the longest timing path between two hierarchical pins in the netlist.
org.jgrapht.GraphPath<TimingVertex,TimingEdge>	getTimingPath(String src, String snk) Gets the longest timing path between two hierarchical pins in the netlist.
Float	getWorstSlack() Finds and returns the value of the worst slack from the TimingGraph.
void	populateHierCellInstMap()
void	prettyPrintPathDelays(org.jgrapht.GraphPath<TimingVertex,TimingEdge> path)
boolean	removeTimingPath(org.jgrapht.GraphPath<TimingVertex,TimingEdge> path) Removes a GraphPath from the TimingGraph.
void	resetRequiredAndArrivalTime() Reset the required and arrival time to be null
void	setOrderedTimingVertexLists() Creates and Sets the lists of ordered TimingVertices
void	setTimingEdgesOfConnections(List<Connection> connections) Assigns TimingEdge instances to each connection in the list.
void	setTimingManager(TimingManager tManager) If a TimingMangager is used to create the TimingGraph indirectly from the user, the TimingManager will call this method.
void	setTimingModel(TimingModel tModel) If a TimingMangager is used to create the TimingGraph indirectly from the user, the TimingManager will call this method to set the TimingModel.
void	setTimingRequirement(float requirement) Sets the same specified timing requirement on the TimingGraph on GraphPaths that have been predetermined.
void	setTimingRequirement(float requirement, org.jgrapht.GraphPath<TimingVertex,TimingEdge> graphPath) Sets the same specified timing requirement on a specified GraphPath.
void	setTimingRequirementTopologicalOrder(float requirement) Set the required time of each timing vertex in the graph

Methods inherited from class org.jgrapht.graph.DefaultDirectedWeightedGraph

createBuilder, createBuilder

Methods inherited from class org.jgrapht.graph.AbstractBaseGraph

addEdge, addEdge, addVertex, addVertex, clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getEdgeWeight, getType, getVertexSupplier, incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, setEdgeSupplier, setEdgeWeight, setVertexSupplier, vertexSet

Methods inherited from class org.jgrapht.graph.AbstractGraph

containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllVertices, toString

Methods inherited from class Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.jgrapht.Graph

containsEdge, removeAllEdges, removeAllEdges, removeAllVertices, setEdgeWeight

Field Detail

debug

public boolean debug

verbose

public boolean verbose

superSource

public TimingVertex superSource

The superSource and superSink are used to consolidate all timing start and end points, respectively. They simplify timing computations and data to compute clock skew will be annotated on the edges from superSource and to superSink. For example, a FF will be represented both as a start and end points using two vertices, says source and sink. The superSource will have no input, but fanout to all the start points nodes. The superSink will have fanin from all the end point nodes and have no output.

superSink

public TimingVertex superSink

overwriteBUGCEDelay

public boolean overwriteBUGCEDelay

Constructor Detail

TimingGraph

public TimingGraph(Design design)

Creates a TimingGraph for the purpose of report_timing based on analyzing nets within a Design object.

Parameters:

design - The RW Design object

TimingGraph

public TimingGraph(Design design,
                   RuntimeTrackerTree timer,
                   ClkRouteTiming clkTiming,
                   String dspTimingDataFolder)

Method Detail

build

public void build(boolean isPartialRouting,
                  Collection<Net> targetNets)

Builds the TimingGraph based on analyzing nets within a Design object.

populateHierCellInstMap

public void populateHierCellInstMap()

getDelay

public float getDelay(org.jgrapht.GraphPath<TimingVertex,TimingEdge> graphPath)

Gets the delay/weight of a GraphPath

Parameters:

graphPath - A timing path within the timingGraph between a source flop and sink flop.

Returns:

The weight of the GraphPath, which is the delay of the path.

setTimingRequirement

public void setTimingRequirement(float requirement)

Sets the same specified timing requirement on the TimingGraph on GraphPaths that have been predetermined.

Parameters:

requirement - The required time in picoseconds at the sink of the path.

setOrderedTimingVertexLists

public void setOrderedTimingVertexLists()

Creates and Sets the lists of ordered TimingVertices

computeArrivalTimesTopologicalOrder

public void computeArrivalTimesTopologicalOrder()

Computes/recomputes the arrival time stored at each vertex of the graph using TopologicalOrderIterator

getClockRegionOfCellPin

public static String getClockRegionOfCellPin(String cellPinName,
                                             Design design)

Get the clock region that the cell pin resides in

Parameters:

cellPinName, - the name of the cell pin

design -

Returns:

clock region name

setTimingRequirementTopologicalOrder

public void setTimingRequirementTopologicalOrder(float requirement)

Set the required time of each timing vertex in the graph

Parameters:

requirement, - the required time of the design

resetRequiredAndArrivalTime

public void resetRequiredAndArrivalTime()

Reset the required and arrival time to be null

getMaxDelay

public Pair<Float,TimingVertex> getMaxDelay()

Get the maximum delay, i.e., the maximum arrival time, and corresponding timing path sink of the design

getPathDelay

public Float getPathDelay(org.jgrapht.GraphPath<TimingVertex,TimingEdge> path)

Gets the total timing delay of the provided path.

Parameters:

path - The path of interest.

Returns:

The timing delay of the entire path.

getCriticalTimingEdgesInOrder

public List<TimingEdge> getCriticalTimingEdgesInOrder(TimingVertex maxV)

Get a list of timing edges consisting of the critical path

Parameters:

maxV - The timing vertex with the maximum arrival time

Returns:

A list of timing edges consisting of the critical path

getTimingEdgeOfPath

public List<TimingEdge> getTimingEdgeOfPath(List<String> verticesNames)

Finds the given critical path in the timing graph and reports the delay detail

Parameters:

verticesNames, - the given TimingVertices

Returns:

A list of TimingEdges associated with the given TimingVertices

setTimingRequirement

public void setTimingRequirement(float requirement,
                                 org.jgrapht.GraphPath<TimingVertex,TimingEdge> graphPath)

Sets the same specified timing requirement on a specified GraphPath.

Parameters:

requirement - The required time in picoseconds at the sink of the path.

graphPath - The GraphPath receiving this required time in picoseconds at the sink of the path.

getSlack

public Float getSlack(org.jgrapht.GraphPath<TimingVertex,TimingEdge> graphPath)

Gets the slack from a specified GraphPath at its source.

Parameters:

graphPath - The GraphPath that is being checked for the slack.

Returns:

The slack as a Float, which can be null if not yet set.

getRequiredTime

public float getRequiredTime(org.jgrapht.GraphPath<TimingVertex,TimingEdge> graphPath)

Gets the required time from a specified GraphPath at its source.

Parameters:

graphPath - The GraphPath that is being checked for the required time.

Returns:

The required time as a Float, which can be null if not yet set.

addTimingPath

public boolean addTimingPath(org.jgrapht.GraphPath<TimingVertex,TimingEdge> path)

Inserts a GraphPath into the TimingGraph.

Parameters:

path - The GraphPath that is being inserted.

Returns:

Boolean indication of success.

removeTimingPath

public boolean removeTimingPath(org.jgrapht.GraphPath<TimingVertex,TimingEdge> path)

Removes a GraphPath from the TimingGraph.

Parameters:

path - The GraphPath that is being removed.

Returns:

Boolean indication of success.

getWorstSlack

public Float getWorstSlack()

Finds and returns the value of the worst slack from the TimingGraph.

Returns:

The value of the worst slack found in the TimingGraph, which might be null if slack hasn't been pre-computed.

getMaxDelayPath

public org.jgrapht.GraphPath<TimingVertex,TimingEdge> getMaxDelayPath()

Finds and returns the path from the TimingGraph having maximum delay.

Returns:

The GraphPath that is the critical path found in the TimingGraph, which might be null if the GraphPaths haven't been pre-computed by calling TimingGraph.buildGraphPaths().

getTimingPath

public org.jgrapht.GraphPath<TimingVertex,TimingEdge> getTimingPath(EDIFHierPortInst src,
                                                                    EDIFHierPortInst snk)

Gets the longest timing path between two hierarchical pins in the netlist.

Parameters:

src - Hierarchical port instance of the source of the path of interest.

snk - Hierarchical port instance of the sink of the path of interest.

Returns:

The longest timing path between src and snk or null if none could be found.

getTimingPath

public org.jgrapht.GraphPath<TimingVertex,TimingEdge> getTimingPath(String src,
                                                                    String snk)

Gets the longest timing path between two hierarchical pins in the netlist.

Parameters:

src - Full hierarchical name of the source of the path of interest.

snk - Full hierarchical name of the sink of the path of interest.

Returns:

The longest timing path between src and snk or null if none could be found.

generateGraphvizDotVisualization

public void generateGraphvizDotVisualization(String dotFileName)

This creates a GraphViz library dot file representation of the TimingGraph. Might be useful for visualizing tiny designs. The resulting digraph() might be too large to render depending on the size of design.

Parameters:

dotFileName - The output filename for the writing the .dot file.

getGraphPaths

public HashSet<org.jgrapht.GraphPath<TimingVertex,TimingEdge>> getGraphPaths()

Returns a set of built GraphPaths.

Returns:

The HashSet of current set of GraphPaths that were prebuilt by running buildGraphPaths()

buildGraphPaths

public List<org.jgrapht.GraphPath<TimingVertex,TimingEdge>> buildGraphPaths()

Builds and returns a set of GraphPaths.

Returns:

A List of GraphPaths that were just built by this command

buildSuperGraphPaths

public void buildSuperGraphPaths()

Connects the sources and sinks of timing paths to a superSource and a superSink, respectively

computeArrivalTimes

public void computeArrivalTimes()

Computes/recomputes the arrival times stored at the vertices of the graph based on the edges

computeSlacks

public void computeSlacks()

Computes/recomputes the slack stored at vertices of the graph based on comparing required times and arrival times.

addNetDelayEdges

public int addNetDelayEdges(Net net)

getintraSiteAndLogicDelayModel

public DelayModel getintraSiteAndLogicDelayModel()

getTimingModel

public TimingModel getTimingModel()

Returns a reference to the associated TimingModel.

Returns:

A reference to the TimingModel created by the TimingManager.

setTimingModel

public void setTimingModel(TimingModel tModel)

If a TimingMangager is used to create the TimingGraph indirectly from the user, the TimingManager will call this method to set the TimingModel.

Parameters:

tModel - The TimingManager will set this to the TimingModel that it creates.

getTimingManager

public TimingManager getTimingManager()

Returns a reference to the associated TimingManager.

Returns:

A reference to the TimingManager that created the TimingGraph.

setTimingManager

public void setTimingManager(TimingManager tManager)

If a TimingMangager is used to create the TimingGraph indirectly from the user, the TimingManager will call this method.

Parameters:

tManager - The TimingManager will set this to itself.

getTimingEdgeConnectionMap

public Map<TimingEdge,Connection> getTimingEdgeConnectionMap()

setTimingEdgesOfConnections

public void setTimingEdgesOfConnections(List<Connection> connections)

Assigns TimingEdge instances to each connection in the list.

Parameters:

connections - A list of connections that should be associated with TimingEdge instances.

prettyPrintPathDelays

public void prettyPrintPathDelays(org.jgrapht.GraphPath<TimingVertex,TimingEdge> path)

getClockNet

public EDIFHierNet getClockNet(org.jgrapht.GraphPath<TimingVertex,TimingEdge> path)

Gets the parent clock net of the launching synchronizer of the path (usually a flip flop).

Parameters:

path - The path to get the clock from.

Returns:

The logical parent clock net of this path.