2005 · 22 citations · 10 references
EngineeringComputer EngineeringComputer ScienceCompilersComputer ArchitectureHardware-software Co-designControl-flow AnalysisTiming AnalysisTiming ModelingBinary Mask DesignBinary MasksConstraintsIncremental Timing AnalysisMulti-clock DesignPlacementStatic Timing AnalysisTiming Optimization
Static timing analysis (STA) with multiple clock domains and complicated exception conditions is a complex practical problem that can dramatically increase compilation time, both for back-end analysis and during place and route. In FPGA placement, timing analysis with many constraints can dominate placement run-time.In this paper we introduce a simple binary edge-mask data structure on arcs in a timing netlist which allows for efficient timing analysis in the presence of many such constraints. The technique applies to either BFS or DFS-based timing analysis. Preliminary implementations on just the basic concept show a 59% decrease in STA run-time for multi-clock designs, indicating that significant benefit is to be gained from a complete implementation. On a set of heavily constrained designs this benefit improved to 80% run-time decrease.Further applications of the edge-mask concept are shown to efficiently deal with thru-x constraints, enumerating the k-longest paths in a timing graph, and partial/incremental timing analysis aimed at significant improvements in placement time.
10
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations
Removing user specified false paths from timing graphs
David Blaauw, Rajendran Panda, Abhijit Das · 2000 · 29 citations · Full text