US5535145A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Delay model abstraction
Assignee: International Business Machines Corp
•
Filing: 1995-02-03
•
Granted: 1996-07-09
•
Expires: 2015-02-03
Abstract
Abstract An abstracted delay model for a circuit network is generated wherein each internal node and connecting edges of an inputted detailed delay graph are processed. All delay edges in the delay graph which could contribute to an extreme delay path from some primary input of the delay graph are marked as necessary. Unnecessary edges are then removed to produce a partially abstracted delay graph. For each internal node in the partially abstracted delay graph, in-edges and out-edges of the node are then merged, if merging does not cause an increase in the number of edges in the delay graph, thus reducing the total number of edges in the delay abstraction.
Inventors
- 👤 David J. Hathaway
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 07:23
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/33; G06F30/3308; G06F30/3312
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
232 words
A delay abstraction system for a circuit network comprising: a) an input device for inputting an original delay graph of said circuit network; b) a marking device for marking with at least one type of necessary mark all delay edges in said original delay graph which contribute to at least one extreme delay path, each said path having a delay and originating from a primary input of said original delay graph and proceeding through, said circuit network; c) a removing device for removing from said original delay graph all delay edges not marked as necessary by said marking device to produce a partially abstracted delay graph, wherein said partially abstracted delay graph includes at least one internal node having at least one in-edge and at least one out-edge from said marked delay edges; d) a merging device for merging said at least one in-edge with at least one out-edge of said internal node, said out-edge having at least one of the same said type of necessary mark as said in-edge, in said partially abstracted delay graph to form a new edge, if merging by said merging device decreases the number of said delay edges in said partially abstracted delay graph, to produce an abstracted delay graph, wherein said delay of each of said at least one extreme delay path is preserved; and e) an outputting device for outputting said abstracted delay graph.
Claim 2
Dependent Claim
232 words
A delay abstraction system for a circuit network comprising: a) an input device for inputting an original delay graph of said circuit network; b) a marking device for marking with at least one type of necessary mark all delay edges in said original delay graph which contribute to at least one extreme delay path, each said path having a delay and originating from a primary input of said original delay graph and proceeding through, said circuit network; c) a removing device for removing from said original delay graph all delay edges not marked as necessary by said marking device to produce a partially abstracted delay graph, wherein said partially abstracted delay graph includes at least one internal node having at least one in-edge and at least one out-edge from said marked delay edges; d) a merging device for merging said at least one in-edge with at least one out-edge of said internal node, said out-edge having at least one of the same said type of necessary mark as said in-edge, in said partially abstracted delay graph to form a new edge, if merging by said merging device decreases the number of said delay edges in said partially abstracted delay graph, to produce an abstracted delay graph, wherein said delay of each of said at least one extreme delay path is preserved; and e) an outputting device for outputting said abstracted delay graph.
Claim 3
Dependent Claim
35 words
A system according to claim 1 wherein said original delay graph comprises test-edges which merge with said in-edges, and said merging device further comprises a test-edge merging device for merging said in-edges with said test-edges.
Claim 4
Dependent Claim
54 words
A system according to claim 1 wherein said merging device further comprises an edge device for creating a new edge for an in-edge/out-edge pair at each said internal node, and a connecting device for connecting said new edge from a source of said in-edge being merged to a sink of said out-edge being merged.
Claim 5
Dependent Claim
24 words
A system according to claim 3 wherein a delay associated with said new edge is a sum of delays for all edges being merged.
Claim 6
Dependent Claim
83 words
A system according to claim 1 wherein said marking device further comprises an arrival propagating device for propagating arrival times forward from each said primary input, a potential marking device for marking as potentially necessary said in-edges to a node which cause an extreme arrival time at said node, and a necessary marking device for marking as necessary edges which are included in a path to a primary output, said path to said primary output being composed only of edges marked potentially necessary.
Claim 7
Dependent Claim
92 words
A system according to claim 5 wherein said marking device further comprises an applying device for applying separate necessary marks to edges necessary for a maximum delay path and to edges necessary for a minimum delay path; and said merging device further comprises an edge device for creating a new edge for an in-edge/out-edge pair at each said internal node which both have same said necessary marks, and a connecting device for connecting said new edge from a source of said in-edge being merged to a sink of said out-edge being merged.
Claim 8
Dependent Claim
88 words
A system according to claim 5 wherein said marking device further comprises an applying device for applying separate necessary marks to edges necessary for said extreme delay path from each said primary input; and said merging device further comprises an edge device for creating a new edge for an in-edge/out-edge pair at each said internal node which both have same said necessary marks, and a connecting device for connecting said new edge from a source of said in-edge being merged to a sink of said out-edge being merged.
Claim 9
Dependent Claim
128 words
A system according to claim 2 wherein said marking device further comprises: an arrival propagating device for propagating arrival times forward from each said primary input; an arrival potential marking device for marking as potentially necessary said in-edges to a node which cause an extreme arrival time at said node; a required propagating device for propagating required times backward from said test-edges; a required potential marking device for marking as potentially necessary said out-edges to a node which cause an extreme required time at said node; and a necessary marking device for marking as necessary edges which are included in a path to a primary output or a primary input, said path to said primary output or said primary input being composed only of edges marked potentially necessary.
Claim 10
Independent Claim
215 words
A method of generating an abstract delay model for a circuit network comprising the steps of: a) inputting an original delay graph of said circuit network; b) marking with at least one type of necessary mark all delay edges in said original delay graph which contribute to an extreme delay path, said path having a delay and originating from a primary input of said original delay graph and proceeding through said circuit network; c) removing from said original delay graph all delay edges not marked as necessary in step b to produce a partially abstracted delay graph; said partially abstracted delay graph including at least one internal node having at least one in-edge and at least one out-edge from said marked delay edges; d) merging said at least one in-edge with at least one out-edge of said internal node, said out-edge having at least one of the same said type of necessary mark as said in-edge in said partially abstracted delay graph to form a new edge, if said merging decreases or does not change the number of said delay edges in said partially abstracted delay graph, to produce an abstracted delay graph wherein said delay of each of said at least one extreme delay path is preserved; and e) outputting said abstracted delay graph.
Claim 11
Independent Claim
215 words
A method of generating an abstract delay model for a circuit network comprising the steps of: a) inputting an original delay graph of said circuit network; b) marking with at least one type of necessary mark all delay edges in said original delay graph which contribute to an extreme delay path, said path having a delay and originating from a primary input of said original delay graph and proceeding through said circuit network; c) removing from said original delay graph all delay edges not marked as necessary in step b to produce a partially abstracted delay graph; said partially abstracted delay graph including at least one internal node having at least one in-edge and at least one out-edge from said marked delay edges; d) merging said at least one in-edge with at least one out-edge of said internal node, said out-edge having at least one of the same said type of necessary mark as said in-edge in said partially abstracted delay graph to form a new edge, if said merging decreases or does not change the number of said delay edges in said partially abstracted delay graph, to produce an abstracted delay graph wherein said delay of each of said at least one extreme delay path is preserved; and e) outputting said abstracted delay graph.
Claim 12
Dependent Claim
30 words
A method according to claim 9 wherein said original delay graph comprises test-edges, and said merging in step d further comprises the step of merging said in-edges with said test-edges.
Claim 13
Dependent Claim
55 words
A method according to claim 9 where said merging in step d further comprises the steps of: creating a new edge for an in-edge/out-edge pair at each said internal node; and connecting said new edge from a source of an in-edge in said in-edge/out-edge pair to a sink of an out-edge in said in-edge/out-edge pair.
Claim 14
Dependent Claim
24 words
A method according to claim 11 wherein a delay associated with said new edge is a sum of delays for all edges being merged.
Claim 15
Dependent Claim
73 words
A method according to claim 9 wherein said marking in step b further comprises the step of propagating arrival times forward from each said primary input, marking as potentially necessary said in-edges to a node which cause an extreme arrival time at said node, and marking as necessary edges which are included in a path to a primary output, said path to said primary output being composed only of edges marked potentially necessary.
Claim 16
Dependent Claim
94 words
A method according to claim 13 wherein said marking in step b further comprises the step of applying separate necessary marks to edges necessary for a maximum delay path and to edges necessary for a minimum delay path; and said merging in step d further comprises the steps of creating a new edge for an in-edge/out-edge pair at each said internal node which both have same said necessary marks; and connecting said new edge from a source of an in-edge from said in-edge/out-edge pair to a sink of an out-edge from said in-edge/out-edge pair.
Claim 17
Dependent Claim
90 words
A method according to claim 13 wherein said marking in step b further comprises the step of applying separate necessary marks to edges necessary for said extreme delay path from each said primary input; and said merging in step d further comprises the steps of creating a new edge for an in-edge/out-edge pair at each said internal node which both have same said necessary marks; and connecting said new edge from a source of an in-edge from said in-edge/out-edge pair to a sink of an out-edge from said in-edge/out-edge pair.
Claim 18
Dependent Claim
114 words
A method according to claim 10 wherein said marking in step b further comprises the steps of: b1) propagating arrival times forward from each said primary input; b2) marking as potentially necessary said in-edges to a node which cause an extreme arrival time at said node; b3) propagating required times backward from said test-edges; b4) marking as potentially necessary said out-edges to a node which cause an extreme required time at said node; and b5) marking as necessary, edges which are included in a path to a primary output or a primary input, said path to said primary output and said primary input being composed only of said in-edges and out-edges marked potentially necessary.
Claim 19
Dependent Claim
225 words
A delay abstraction system for a circuit network comprising: a) means for inputting an original delay graph of said circuit network; b) marking means for marking with at least one type of necessary mark all delay edges in said original gruel delay graph which contribute to at least one extreme delay path, each said path having a delay and originating from a primary input of said original delay graph and proceeding through said circuit network; c) removing means for removing from said original delay graph all delay edges not marked as necessary by said marking means to produce a partially abstracted delay graph; said partially abstracted delay graph including at least one internal node having at least one in-edge and at least one out-edge from said marked delay edges; d) merging means for merging said at least one in-edge with at least one out-edge of said internal node, said out-edge having at least one of the same said type of necessary mark as said in-edge, in said partially abstracted delay graph to form a new edge, if merging by said merging means decreases the number of said delay edges in said partially abstracted delay graph, to produce an abstracted delay graph wherein said delay of each of said at least one extreme delay path is preserved; and e) means for outputting said abstracted delay graph.
Claim 20
Dependent Claim
225 words
A delay abstraction system for a circuit network comprising: a) means for inputting an original delay graph of said circuit network; b) marking means for marking with at least one type of necessary mark all delay edges in said original gruel delay graph which contribute to at least one extreme delay path, each said path having a delay and originating from a primary input of said original delay graph and proceeding through said circuit network; c) removing means for removing from said original delay graph all delay edges not marked as necessary by said marking means to produce a partially abstracted delay graph; said partially abstracted delay graph including at least one internal node having at least one in-edge and at least one out-edge from said marked delay edges; d) merging means for merging said at least one in-edge with at least one out-edge of said internal node, said out-edge having at least one of the same said type of necessary mark as said in-edge, in said partially abstracted delay graph to form a new edge, if merging by said merging means decreases the number of said delay edges in said partially abstracted delay graph, to produce an abstracted delay graph wherein said delay of each of said at least one extreme delay path is preserved; and e) means for outputting said abstracted delay graph.
References Cited (Backward Citations)
US5029102A
Cited
US4916627A
Cited
US4924430A
Cited
US5003487A
Cited
US5047969A
Cited
US5251147A
Cited
US5253161A
Cited
US5163016A
Cited
US5235521A
Cited
US5262959A
Cited
US5163068A
Cited
US5392221A
Cited
US5339253A
Cited
US5282147A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-09 | 2000-01-08 | 2000-07-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-09 | 2004-01-08 | 2004-07-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-09 | 2008-01-08 | 2008-07-09 | $7700.00 | Window Closed / Lapsed |