Circuit delay abstraction tool

Details Circuit delay abstraction tool Circuit delay abstraction tool

1996-07-31

1998-08-18

Teska, Kevin J.

Boots, shoes, and leggings

364490, 364578, 395500, G06F 1750

Patent

active

057966214

ABSTRACT:
What is provided is a system and method for reducing the storage requirements for delay networks used in performing timing analysis. A circuit delay network is transformed by processing all the possible hubs of the input pairs which are created from a bipartite delay graph of the circuit. A smaller delay network is formed by iteratively selecting the hub with the largest edge-saving and removing the conflicts from the remaining unselected hubs. The selections continues until there are no longer any unselected hubs. Further processing can occur using the selected hubs as inputs to insure that there are no further layers of hubs. The composite of all selected hubs and any inputs and outputs that do not contained hubs is an abstracted delay model for the circuit which can be efficiently stored. These models are subsequently used to reduce the computational requirements for timing analysis performed on delay networks at a higher level.

REFERENCES:
patent: 5257201 (1993-10-01), Berman et al.
patent: 5450535 (1995-09-01), North
patent: 5475607 (1995-12-01), Apte et al.
patent: 5535145 (1996-07-01), Hathaway
Blaquiere et al., "Timing Analysis Speed-up . . . ", IEEE, pp. 244-255, Feb. 1996.
Cimikowski et al., "A Neural Network Algorithm for a Graph Layout Problem", IEEE, pp. 341-345, Apr. 1996.
Kobayashi et al., "Delay Abstraction in Combination Logic Circuits" IEEE, pp. 453-458, 1995.
Ziavras, "Rh: A Versatile Family of Reduced . . . ", IEEE, pp. 1210-1220, Nov. 1994.
Watanabe et al., "Minimum Cost Augmentation . . . ", IEEE, pp. 2311-2314, 1993.
Johnson et al., "Optimal Algorithms for the Vertex . . . ", IEEE, pp. 306-314, 1992.
Lee, "A Parallel Improvement Algorithm for the Bipartite Subgraph Problem", IEEE, pp. 139-145, Jan. 1992.
"Hierarchical Delay Predictor and Corrector" IBM Technical Disclosure Bulleton, vol. 33, No. 2, Jul. 1990.
Frank, "Augmenting Graphs to meet Edge-Connectivity Requirements" IEEE, pp. 708-718, 1990.
Introduction to Algorithms. Cormen. Leiserson and Rivest. Third Printing Q A766 C662, ISBN0-07-013 143-0 (McGraw-Hill), 1991.

Affiliated with

Also associated with

Rating

Circuit delay abstraction tool does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Circuit delay abstraction tool, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit delay abstraction tool will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1121148