Separation and minimum wire length constrained maze routing method and system

• US 10,192,019 B2
• Filed: 09/25/2014
• Issued: 01/29/2019
• Est. Priority Date: 09/25/2013
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Chang, Fong-Yuan, Chen, Sheng-Hsiung, Tsay, Ren-Song, Mak, Wai-Kei
• Primary Examiner(s): Kik, Phallaka
• Application Number:
  US14/496,420
• Publication Number:
  US 20150089465A1
• Time in Patent Office: 1,587 Days
• Field of Search: 716129, 716130, 716131, 716123, 716124
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36

Abstract

A computer implemented method for routing a first path in a circuit design is presented. The method includes iteratively building a multitude of partial-paths to route the first path by adding an incremental length to a selected previously built partial-path when the computer is invoked to route the first path in the circuit design, the adding being performed in accordance with at least a first design rule. The multitude of partial-paths start at a first location. The method further includes comparing each of the multitude of partial-paths to each other when the multitude of partial-paths end on a common second location different from the first location, and saving one of the multitude of partial-paths that leads to a shortest first path. The method further includes eliminating one of the multitude of partial-paths that are not selected to lead to the shortest first path.

Claims

1. A computer implemented method for routing a first path in a circuit design, the method comprising:

iteratively building, using the computer, a plurality of partial-paths to route the first path by adding an incremental length to a selected previously built partial-path when the computer is invoked to route the first path in the circuit design, the adding being performed in accordance with at least a first design rule, wherein the plurality of partial-paths start at a first location, wherein said iteratively building comprises;

comparing, using the computer, the plurality of partial-paths to each other when the plurality of partial-paths end on a common second location different from the first location;

saving, using the computer, one of the plurality of partial-paths that leads to a shortest first path; and

eliminating, using the computer, one of the plurality of partial-paths that is not selected to lead to the shortest first path.

2. The computer implemented method of claim 1, wherein the first design rule is associated with a spacing of the incremental length to a second path.

3. The computer implemented method of claim 1, wherein each of the plurality of partial-paths is a continuous electrical conductor that is unbroken by passive or active components.

4. The computer implemented method of claim 1, wherein the plurality of partial-paths start at a first location, wherein the incremental length is added to a first end of the selected previously built partial-path, the first end being disposed opposite a second end adjacent the first location.

5. The computer implemented method of claim 1 further comprising:

repeating the iterative building to find the first path when a stop criteria is not met, wherein the stop criterion is not met when the selected previously built partial-path does not overlap a target location or the length of the selected previously built partial-path that overlaps the target location is longer than the length of any other one of the plurality of partial-paths.

6. The computer implemented method of claim 1 further comprising:

repeating the iterative building to find the first path when a stop criteria is not met, wherein the stop criterion is not met when the selected previously built partial-path does not overlap a target location or at least one of the plurality of partial-paths in a queue does not include the incremental length.

7. The computer implemented method of claim 1 further comprising:

extending, using the computer, the length of a portion of one of the plurality of partial-paths thereby forming an extended partial-path when the portion violates a second design rule different from the first design rule.

8. The computer implemented method of claim 7, wherein the portion is built from a continuous conductive line on a single conductive layer.

9. The computer implemented method of claim 7, wherein the second design rule is associated with a minimum length of the portion.

10. The computer implemented method of claim 7 further comprising:

saving, using the computer, the extended partial-path when the extended partial-path does not violate a third design rule different than the first and second design rules.

11. The computer implemented method of claim 1, wherein the plurality of partial-paths start at a first location, the method further comprising:

saving, using the computer, a first length and a second length associated with each of a different one of the plurality of partial-paths; and

determining, using the computer, one of the plurality of partial-paths that leads to a shortest first path when the plurality of partial-paths end on a common second location different from the first location, the determining being in accordance with the saved first length and second length.

12. The computer implemented method of claim 11 further comprising:

saving, using the computer, one of the plurality of partial-paths that leads to a shortest first path; and

eliminating, using the computer, one of the plurality of partial-paths that are not selected to lead to the shortest first path.

13. The computer implemented method of claim 11, wherein the selected previously built partial-path plus the added incremental length form an expanded partial-path, wherein the method further includes eliminating either the expanded partial-path or the selected previously built partial-path when the first length of the expanded partial-path is equal to the first length of the selected previously built partial-path and when the second length of the expanded partial-path is equal to the second length of the selected previously built partial-path.

14. The computer implemented method of claim 11, wherein the selected previously built partial-path plus the added incremental length form an expanded partial-path, wherein the method further includes eliminating the selected previously built partial-path when the first length of the selected previously built partial-path is longer than or equal to the second length of the expanded partial-path.

15. The computer implemented method of claim 11, wherein the selected previously built partial-path plus the added incremental length form an expanded partial-path, wherein the method further includes eliminating the expanded partial-path when the first length of the expanded partial-path is longer than or equal to the second length of the selected previously built partial-path.

16. The computer implemented method of claim 15, wherein the first length does not include a length associated with a portion of the expanded partial-path that is expanded so as not to violate a second design rule different from the first design rule.

17. The computer implemented method of claim 15, wherein the second length includes a length associated with a portion of the selected previously built partial-path that is expanded so as not to violate a second design rule different from the first design rule.