US5757653A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for dynamically varying net rules
Assignee: International Business Machines Corp
•
Filing: 1996-05-16
•
Granted: 1998-05-26
•
Expires: 2016-05-16
Abstract
Abstract Permutations of orders of elements such as electrical connection pins, vias and t-junctions at known locations are efficiently tested against at least type and distance criteria by forming a plurality of lists of the elements and screening the elements of each list against respective ones of said type criteria to reduce the length of the lists of elements. Pointers to ones of the distance criteria and remaining members of a list corresponding to respective ones of the distance criteria iteratively form pairs of elements which are checked for separation. When the check fails or a solution is found, the pointer to list members is advanced. The pointer to respective distance criteria is advanced when a check is successful. When a list is exhausted and a check is unsuccessful, the pointer to respective distance criteria is regressed. Advancement and regression of pointers reduces iterations of combinations of pairs of elements which do not lead to a solution in order to accelerate the process. Each new solution is evaluated against a single stored prior solution for optimization of solutions while greatly reducing storage requirements.\!
Inventors
- 👤 Kenneth L. Christian
- 👤 Timothy A. Schell
- 👤 Craig R. Selinger
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 23:16
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/10; G06F30/18; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
117 words
A method of checking an ordering of a plurality of elements against desired criteria, said method including the steps of forming a plurality of lists of said plurality of elements, dividing said desired criteria into a plurality of first criteria and a plurality of second criteria, screening individual elements of said plurality of lists against a respective one of said plurality of first criteria and limiting each said screened individual elements to any of said plurality of elements matching said respective first criteria, and comparing pairs of elements in different said screened lists against a respective one of said plurality of second criteria to determine if said compared pairs meet said respective one of said second criteria.
Claim 2
Independent Claim
117 words
A method of checking an ordering of a plurality of elements against desired criteria, said method including the steps of forming a plurality of lists of said plurality of elements, dividing said desired criteria into a plurality of first criteria and a plurality of second criteria, screening individual elements of said plurality of lists against a respective one of said plurality of first criteria and limiting each said screened individual elements to any of said plurality of elements matching said respective first criteria, and comparing pairs of elements in different said screened lists against a respective one of said plurality of second criteria to determine if said compared pairs meet said respective one of said second criteria.
Claim 3
Dependent Claim
29 words
A method as recited in claim 1, wherein said forming step includes forming a number of said plurality of lists which equals the number of said plurality of elements.
Claim 4
Dependent Claim
39 words
A method as recited in claim 1, wherein said dividing step includes setting said plurality of first criteria such that the number of first criteria in said plurality of first criteria equals the number of said plurality of elements.
Claim 5
Dependent Claim
42 words
A method as recited in claim 1, wherein said dividing step includes setting said plurality of second criteria such that the number of second criteria in said plurality of second criteria is one less than the number of said plurality of elements.
Claim 6
Dependent Claim
30 words
A method as recited in claim 1, wherein individual elements of said plurality of elements includes identity information and criteria of said plurality of first criteria include a type criterion.
Claim 7
Dependent Claim
28 words
A method as recited in claim 1, wherein individual elements of said plurality of elements include location information and criteria of said second criteria include a distance criterion.
Claim 8
Dependent Claim
57 words
A method as recited in claim 1, wherein each of said plurality of elements, said plurality of first criteria and said plurality of second criteria has an order, said method including the further step of advancing through said order of elements in one of said lists when a respective one of said second criteria is not met.
Claim 9
Dependent Claim
82 words
A method as recited in claim 1, wherein each of said plurality of elements, said plurality of first criteria and said plurality of second criteria has an order, said method including the further steps of regressing through said order of said first criteria when one of said lists of said remaining elements of said plurality of elements is exhausted when a respective one of said second criteria is not met, and advancing through said order of elements in one of said lists.
Claim 10
Dependent Claim
50 words
A method as recited in claim 8, including the further steps of recording a pair of said plurality of elements in a respective one of said lists when one of said second criteria is not met, and advancing past said pair of said plurality of elements in said advancing step.
Claim 11
Dependent Claim
70 words
A method as recited in claim 1, wherein each of said plurality of elements, said plurality of first criteria and said plurality of second criteria has an order, said method including the further steps of recording a solution of an order of said plurality of elements when a last of said order of said second criteria is met and advancing through said order of elements in one of said lists.
Claim 12
Dependent Claim
50 words
A method as recited in claim 10, including the further steps of evaluating a further solution of said ordering of elements against said solution recorded in said recording step, and replacing said solution with said further solution in response to a result of said step of evaluating said further solution.
Claim 13
Dependent Claim
51 words
A method as recited in claim 1, wherein said plurality of elements include one of electrical connection pins, vias and t-junctions and wherein individual elements of said plurality of elements includes connection pin, via or t-junction information and criteria of said plurality of first criteria include an electrical node type criterion.
Claim 14
Dependent Claim
34 words
A method as recited in claim 1, wherein individual elements of said plurality of elements include electrical connection pin, via and t-junction location information and criteria of said second criteria include a distance criterion.
Claim 15
Dependent Claim
53 words
A method as recited in claim 1, wherein each of said plurality of elements, said plurality of first criteria and said plurality of second criteria has an order, said method including the further step of advancing through said order of said second criteria when a respective one of said second criteria is met.
Claim 16
Independent Claim
126 words
A system for checking an ordering of a plurality of elements against desired criteria, said system comprising: first storage means for storing a plurality of lists of said plurality of elements, second storage means for storing said desired criteria as a plurality of first criteria and a plurality of second criteria, means for screening individual elements of said plurality of lists against a respective one of said plurality of first criteria and limiting each said screened lists' elements to any of said plurality of elements matching said respective first criteria, and means for comparing pairs of elements in different said screened lists against a respective one of said plurality of second criteria to determine if said compared pairs meet said respective one of said second criteria.
Claim 17
Independent Claim
126 words
A system for checking an ordering of a plurality of elements against desired criteria, said system comprising: first storage means for storing a plurality of lists of said plurality of elements, second storage means for storing said desired criteria as a plurality of first criteria and a plurality of second criteria, means for screening individual elements of said plurality of lists against a respective one of said plurality of first criteria and limiting each said screened lists' elements to any of said plurality of elements matching said respective first criteria, and means for comparing pairs of elements in different said screened lists against a respective one of said plurality of second criteria to determine if said compared pairs meet said respective one of said second criteria.
Claim 18
Dependent Claim
43 words
A system as recited in claim 15, wherein said first storage means is a matrix having an equal number of columns and rows and a column for each one of said first criteria, each said list comprising one said column of said matrix.
Claim 19
Dependent Claim
28 words
A system as recited in claim 15, further including a pointer means for said second storage means, said pointer means selecting a location in said first storage means.
Claim 20
Dependent Claim
22 words
A system as recited in claim 17, further including a further pointer means to select a location in said second storage means.
Claim 21
Dependent Claim
31 words
A system as recited in claim 15, further including a third storage means for storing a pair of said elements which do not meet a respective one of said second criteria.
Claim 22
Dependent Claim
48 words
A system as recited in claim 15, further including means for storing a solution to said ordering of said elements, means for evaluating a further solution in accordance with said solution, and means for replacing said solution with said further solution in said means for storing a solution.
References Cited (Backward Citations)
US4495559A
Cited
US4758947A
Cited
US4700316A
Cited
US4613941A
Cited
US4763288A
Cited
US5212650A
Cited
US5095441A
Cited
US5175696A
Cited
US5267175A
Cited
US4965739A
Cited
US5309372A
Cited
US5359539A
Cited
US5081602A
Cited
US5231589A
Cited
US5218551A
Cited
US5367469A
Cited
US5237514A
Cited
US5392222A
Cited
US5311443A
Cited
US5519630A
Cited
US5648912A
Cited
US5391993A
Cited
US5548747A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |