Shuo Zhou
ABSTRACT
In this paper, we propose a timing model reduction algorithm for hierarchical timing analysis based on a bicliquestar replacement technique. In hierarchical timing analysis, each functional block is characterized into an abstract timing model. The complexity of analysis is linear to the number of edges in the abstract timing model for timing propagation. We propose a biclique-star replacement technique to minimize the number of edges in the timing model. The experiments on industry test cases show that by allowing acceptable errors, the proposed algorithm can largely reduce the number of edges in the timing model.
- C. Visweswariah and A. R. Conn. Formulation of static circuit optimization with reduced size, degeneracy and redundancy by timing graph manipulation. In Proc. of the Intl. Conf. on Computer-Aided Design, page 244C251, 1999. Google Scholar
Digital Library
- C. W. Moon, H. Kriplani, and K. P. Belkhale. Timing model extraction of hierarchical blocks by graph reduction. In Proc. of the Design Automation Conf., page 152C157, 2002. Google ScholarDigital Library
- S. L. Hakimi and S. S. Yau. Distance matrix of a graph and its realizability. Quart. Appl. Math., 22:305C317, 1964.Google ScholarCross Ref
- F. Chung, M. Garrett, R. Graham, and D. Shallcross. Distance realization problems with applications to internet tomography. http://www.math.ucsd.edu/?fan.Google Scholar
- T. Feder, A. Meyerson, R. Motwani, L. OCallaghan, and R. Panigrahy. Representing graph metrics with fewest edges. In Proc. of Symp. on Theoretical Aspects of Computer Science, pages 355--366, 2003. Google ScholarDigital Library
- T. Feder and R. Motwani. Clique partitions, graph compression and speeding up algorithms. In Proc. of the ACM Symposium on Theory of Computing, pages 123--133, 1991. Google ScholarDigital Library
- J. Orlin. Containment in graph theory: Covering graphs with cliques. Indag. Math., 39:211--218, 1977.Google Scholar
- H. Muller. On edge perfectness and classes of bipartite graphs. Discrete Math., 149:159--187, 1996. Google ScholarDigital Library
Index Terms
- Timing model reduction for hierarchical timing analysis
Recommendations
iTimerM: A Compact and Accurate Timing Macro Model for Efficient Hierarchical Timing Analysis
Special Section on Advances in Physical Design Automation and Regular PapersAs designs continue to grow in size and complexity, EDA paradigm shifts from flat to hierarchical timing analysis. In this article, we present compact and accurate timing macro modeling, which is the key to efficient and accurate hierarchical timing ...
Timing analysis including clock skew
Clock skew is an increasing concern for high-speed circuit designers. Circuit designers use transparent latches and skew-tolerant domino circuits to hide clock skew from the critical path and take advantage of shared portions of the clock network to ...
Fast timing-model independent buffered clock-tree synthesis
DAC '10: Proceedings of the 47th Design Automation ConferenceIn high-performance synchronous chip design, a buffered clock tree with small clock skew is essential for improving clocking speed. Due to the insufficient accuracy of timing models for modern chip design, embedding simulation into a clock-tree ...
Comments