Efficient static timing analysis and applications using edge masks

ABSTRACT

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.

REFERENCES

• 1: Altera Corp. Application Note 123, "Using Timing Analysis in the Quartus II Software", available at http://www.altera.com.
• 2: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 3: David Blaauw , Rajendran Panda , Abhijit Das, Removing user specified false paths from timing graphs, Proceedings of the 37th conference on Design automation, p.270-273, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337417]
• 4: David Blaauw , Vladimir Zolotov , Savithri Sundareswaran , Chanhee Oh , Rajendran Panda, Slope propagation in static timing analysis, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 5: R. Fung , V. Betz , W. Chow, Simultaneous short-path and long-path timing optimization for FPGAs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.838-845, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382691]
• 6: R. Hitchcock, G. Smith and D. Cheng, "Timing Analysis of Computer Hardware", in IBM J. Research and Development, Jan. 1983.
• 7: M. Hutton. "Techniques For Using Edge Masks To Perform Timing Analysis", US Patent Pending 2003.
• 8: Tim (Tianming) Kong, A novel net weighting algorithm for timing-driven placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.172-176, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774597]
• 9: Yuji Kukimoto , Robert K. Brayton, Hierarchical functional timing analysis, Proceedings of the 35th annual conference on Design automation, p.580-585, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277197]
• 10: Jin-fuw Lee , Donald T. Tang, An algorithm for incremental timing analysis, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.696-701, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217613]
• 11: V. Manohararajah, D. Singh, S. Brown and Z. Vranesic, "Post-Placement Functional Decomposition for FPGAs", in Proc. IWLS, 2004.
• 12: Sachin Sapatnekar, Timing, Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 13: Karl Schabas , Stephen D. Brown, Using logic duplication to improve performance in FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611838]
• 14: Synopsys Corp. Primetime documentation, available at www.synopsys.com.
• 15: R.E. Tarjan, "Depth-first Search and Linear Graph Algorithms", SIAM J. Computing 1(2), pp. 146--160, 1972.
• 16: S. H. Yen , D. H. Du , S. Ghanta, Efficient algorithms for extracting the K most critical paths in timing analysis, Proceedings of the 26th ACM/IEEE conference on Design automation, p.649-654, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74497]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Algorithms, Design

Keywords:
FPGA, cut-path, multicycle, placement, thru-x, timing analysis