2000 · 29 citations · 12 references
ComputingComputer EngineeringComputer ScienceAlgorithmic DesignAlgorithmsComputer ArchitectureAlgorithm AnalysisData-flow AnalysisGraph AlgorithmsTiming AnalysisTiming ModelingWorst-case Execution Time AnalysisCircuit OptimizationCircuit-level OptimizationFalse Path AnalysisHeuristic ApproachSplittingStatic Timing AnalysisTiming OptimizationWorst-case Complexity
We present a new method for removing user-specified false subgraphs from timing analysis and circuit optimization. Given a timing graph and a list of specified false paths, false subpaths, or false subgraphs, we generate a new timing graph in which all specified false paths are removed using a process of node splitting and edge removal. We present the necessary and sufficient condition for splitting a node, and show that the number of nodes that must be added to the timing graph is linear with the size of the false path specification. We also present an algorithm for finding the minimum set of nodes that must be split. Since this algorithm requires exponential run time for false subpaths and false subgraphs, we present a heuristic splitting approach which has linear worst-case run time, and where the number of added nodes is linear with the size of the false path specification. The heuristic approach was implemented and results are given for large industrial circuits.
12
On the general false path problem in timing analysis
Dongsheng Du, S. H. Yen, S. Ghanta · 1989 · 140 citations · Full text
Hierarchical functional timing analysis
Yuji Kukimoto, Robert K. Brayton · 1998 · 21 citations
Engineering, Computer Engineering, Electrical Engineering +16