efficient static timing analysis and applications using edge masks
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.
timing analysis fpga placement thru-x cut-path multicycle