 |
|
|
|
|
|
 Title: |
US6321362:
Method of reformulating static circuit optimization problems for reduced size, degeneracy and redundancy
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Conn, Andrew R.; Mount Vernon, NY
Visweswariah, Chandramouli; Croton-on-Hudson, NY
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
2001-11-20
/ 1999-04-06
|
| Application Number: |
US1999000286758
|
| IPC Code: |
Advanced:
G06F 17/50;
Core:
more...
IPC-7:
G06F 17/50;
|
| ECLA Code: |
G06F17/50D2;
|
| U.S. Class: |
Current:
716/002;
716/006;
Original:
716/002;
716/006;
|
| Field of Search: |
716/2;6
|
| Priority Number: |
| 1999-04-06 |
US1999000286758 |
|
| Abstract: |
A method of pruning an initial timing graph for static optimization of a digital circuit includes examining a first group of nodes, which in turn include at least a first one of the nodes in the initial timing graph, to determine whether every node in the first group is prunable. The method further includes pruning the first group by pruning every node therein, if every node therein is prunable, and if the pruning would be beneficial. Furthermore, the method includes repeating the examining and pruning steps for a substantial number of additional groups of nodes, so as to create a pruned timing graph having enhanced numerical qualities and/or compactness compared to an initial timing graph. The pruning can be conducted on groups of more than one node at a time, or on only individual nodes at one time. Reduced size, and the benefits thereof, can be determined by a comparison of the number of nodes and number of directed edges before pruning, with the number of nodes and the number of directed edges after pruning, by summing the quantities before pruning and comparing the sum to the summed quantities after pruning, with or without weighting. Preferably, multistep pruning can be employed to first perform all pruning operations with a gain of a certain value, and to continue for gains of lower values. In an alternative method, an explicit representation of the problem as a timing graph is not employed, but the circuit optimization problem is restated in an analogous manner by pruning arrival times and manipulating constraints.
|
| Attorney, Agent or Firm: |
Otterstedt, Paul J. ;
|
| Primary / Asst. Examiners: |
Phan, Trong;
|
| INPADOC Legal Status: |
Show legal status actions
|
| Family: |
None
|
First Claim:
Show all 32 claims |
What is claimed is:
1. A method of pruning an initial timing graph for static optimization of a digital circuit, the initial timing graph having a plurality of nodes corresponding to arrival times of signals in the digital circuit and a plurality of directed edges corresponding to propagate segments in the digital circuit, those of the edges directed into a given node being referred to as fan-ins for that node and being connected to associated fan-in nodes, those of the edges directed out of the given node being referred to as fan-outs for that node and being connected to associated fan-out nodes, said method comprising the steps of:
- (a) examining a first group of the nodes including at least a first one of the nodes in the initial timing graph to determine if every node of said first group is pruneable;
- (b) pruning said first group by pruning every node of said first group if every node of said first group is pruneable, and if said pruning would be beneficial; and
- (c) repeating steps (a) and (b) for a substantial number of additional groups including at least additional ones of the nodes to create a pruned timing graph having enhanced qualities with respect to the initial timing graph, said enhanced qualities comprising at least one of numerical qualities and compactness.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 1 U.S. patent(s) that reference this one
|
|
