IP Library › Granted Patent US 8,132,141
Granted Patent B2
US 8,132,141 · App. 12/605,272 · Granted Mar 6, 2012

Method and apparatus for generating a centerline connectivity representation

Assignee: Synopsys, Inc.
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 8,132,141
App. No.
12/605,272
Granted
Mar 6, 2012
Kind
B2
Abstract

Some embodiments provide a system for generating a centerline connectivity representation for a set of routing shapes. During operation, the system can represent the set of routing shapes using a set of centerlines with endcap extensions. Note that an intersection between two centerlines represents an electrical connection between the two routing shapes associated with the two centerlines. Next, the system can detect two routing shapes which overlap, but whose centerlines do not intersect. The system can then create a virtual shape whose centerline intersects with the centerlines of the two routing shapes. In some embodiments, the system can modify a dimension of at least one of the two routing shapes. Next, the system can create a new routing shape which overlaps with the two routing shapes, and create virtual shapes which connect the centerline of the new shape with the centerlines of the two routing shapes.

Claims (36)

1. A computer-implemented method to generate a centerline connectivity representation for a set of routing shapes, the method comprising:

representing the set of routing shapes using a set of centerlines with endcap extensions, wherein an intersection between two centerlines represents an electrical connection between two routing shapes associated with the two centerlines;

detecting a first routing shape and a second routing shape which overlap, but whose centerlines do not intersect; and

creating, by computer, a virtual shape whose centerline intersects with the first routing shape's centerline and the second routing shape's centerline.

2. The method of claim 1 , further comprising determining whether the set of routing shapes are electrically connected by traversing centerlines associated with routing shapes and virtual shapes.

3. The method of claim 1 , further comprising using the centerline connectivity representation to determine whether the set of routing shapes satisfy a design rule.

4. The method of claim 1 , wherein a terminal point of a routing shape's centerline is represented using one of: a full representation or a compact representation.

5. The method of claim 1 , wherein a terminal point of a virtual shape's centerline is represented using a full representation.

6. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method to generate a centerline connectivity representation for a set of routing shapes, the method comprising:

representing the set of routing shapes using a set of centerlines with endcap extensions, wherein an intersection between two centerlines represents an electrical connection between two routing shapes associated with the two centerlines;

detecting a first routing shape and a second routing shape which overlap, but whose centerlines do not intersect; and

creating a virtual shape whose centerline intersects with the first routing shape's centerline and the second routing shape's centerline.

7. The computer-readable storage medium of claim 6 , the method further comprising determining whether the set of routing shapes are electrically connected by traversing centerlines associated with routing shapes and virtual shapes.

8. The computer-readable storage medium of claim 6 , the method further comprising using the centerline connectivity representation to determine whether the set of routing shapes satisfy a design rule.

9. The computer-readable storage medium of claim 6 , wherein a terminal point of a routing shape's centerline is represented using one of: a full representation or a compact representation.

10. The computer-readable storage medium of claim 6 , wherein a terminal point of a virtual shape's centerline is represented using a full representation.

11. An apparatus to generate a centerline connectivity representation for a set of routing shapes, comprising:

a representing mechanism configured to represent the set of routing shapes using a set of centerlines with endcap extensions, wherein an intersection between two centerlines represents an electrical connection between two routing shapes associated with the two centerlines;

a detecting mechanism configured to detect a first routing shape and a second routing shape which overlap, but whose centerlines do not intersect; and

a creating mechanism configured to create a virtual shape whose centerline intersects with the first routing shape's centerline and the second routing shape's centerline.

12. The apparatus of claim 11 , further comprising a determining mechanism configured to determine whether the set of routing shapes are electrically connected by traversing centerlines associated with routing shapes and virtual shapes.

13. The apparatus of claim 11 , further comprising a design-rule checking mechanism configured to use the centerline connectivity representation to determine whether the set of routing shapes satisfy a design rule.

14. The apparatus of claim 11 , wherein a terminal point of a routing shape's centerline is represented using one of: a full representation or a compact representation.

15. The apparatus of claim 11 , wherein a terminal point of a virtual shape's centerline is represented using a full representation.

16. A computer-implemented method to generate a centerline connectivity representation for a set of routing shapes, the method comprising:

representing the set of routing shapes using a set of centerlines with endcap extensions, wherein an intersection between two centerlines represents an electrical connection between two routing shapes associated with the two centerlines;

detecting a first routing shape and a second routing shape which overlap, but whose centerlines do not intersect;

modifying a dimension of the first routing shape to reduce an overlap length between the first routing shape and the second routing shape;

creating, by computer, a new routing shape which is represented by a new centerline with an endcap extension, wherein the new routing shape overlaps with the first routing shape and the second routing shape;

creating, by computer, a first virtual shape whose centerline intersects with the first routing shape's centerline and the new centerline; and

creating, by computer, a second virtual shape whose centerline intersects with the second routing shape's centerline and the new centerline.

17. The method of claim 16 , further comprising modifying a dimension of the second routing shape.

18. The method of claim 16 , further comprising determining whether the set of routing shapes are electrically connected by traversing centerlines associated with routing shapes and virtual shapes.

19. The method of claim 16 , further comprising using the centerline connectivity representation to determine whether the set of routing shapes satisfy a design rule.

20. The method of claim 16 , wherein a terminal point of a routing shape's centerline is represented using one of: a full representation or a compact representation.

21. The method of claim 16 , wherein a terminal point of a virtual shape's centerline is represented using a full representation.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 23, 2009
From: KUPPUSWAMY, SHANKAR; GAO, TONG
To: SYNOPSYS, INC.
Reel/Frame 023559/0667 →
Continuity (2)
Provisional Application 61233613 · Aug 13, 2009
Related Publication 20110041112A1 · Feb 17, 2011