Removing user specified false paths from timing graphs

ABSTRACT

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.

REFERENCES

• 1: J. R Fishburn, et.al. "TILOS: A posynomial programming approach to transistor sizing," ICCAD, Nov 1985.
• 2: D. H. Du , S. H. Yen , S. Ghanta, On the general false path problem in timing analysis, Proceedings of the 26th ACM/IEEE conference on Design automation, p.555-560, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74475]
• 3: P. C. McGeer , R. K. Brayton, Efficient algorithms for computing the longest viable path in a combinational network, Proceedings of the 26th ACM/IEEE conference on Design automation, p.561-567, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74476]
• 4: S. Devadas, et. al. "Computation of Floating Mode Delay in Combinational Circuits: Theory and Algorithms", IEEE Trans. on Computer Aided Design, Dec. 1993.
• 5: Hakan Yalcin , John P. Hayes , Karem A. Sakallah, An approximate timing analysis method for datapath circuits, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.114-118, November 10-14, 1996, San Jose, California, United States
• 6: Yuji Kukimoto , Wilsin Gosti , Alexander Saldanha , Robert K. Brayton, Approximate timing analysis of combinational circuits under the XBD0 model, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.176-181, November 09-13, 1997, San Jose, California, United States
• 7: 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]
• 8: Krishna P. Belkhale , Alexander J. Suess, Timing analysis with known false sub graphs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.736-740, November 05-09, 1995, San Jose, California, United States
• 9: E. Goldberg, et. al. "Timing Analysis with Implicitly Specified False Path", Int. Workshop on Timing Issues in the Specification and Synthesis of Digital Designs, T99, 1999.
• 10: K. Keutzer, et. al. "Is Redundancy Necesssary to Reduce Delay", IEEE Trans. on CAD, April 1991.
• 11: A. Saldanha , R. K. Brayton , A. L. Sangiovanni-Vincentelli, Circuit structure relations to redundancy and delay: the KMS algorithm revisited, Proceedings of the 29th ACM/IEEE conference on Design automation, p.245-248, June 08-12, 1992, Anaheim, California, United States
• 12: D. Blaauw, et. al. "Generation of false path free tming graphs for circuit optimization", Int. Workshop on Timing Issues in the Specification and Synthesis of Digital Designs, 1999.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory, Verification