Methods, systems, and articles of manufacture for tessellating and labeling routing space for routing electronic designs

• US 9,165,103 B1
• Filed: 06/27/2014
• Issued: 10/20/2015
• Est. Priority Date: 06/28/2013
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Salowe, Jeffrey S.
• Primary Examiner(s): NGUYEN, NHA T
• Application Number:
  US14/318,507
• Time in Patent Office: 480 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Various aspects described herein create tessellated regions by identifying tessellation lines in one or more directions based at least on fixed shape(s) or route(s). New cells or shapes are added to the design by aligning at least some of the boundary segments of the new cells or shapes with existing tessellation lines. Tessellation lines are dynamically adjustable. At least some tessellated regions are associated with initial or tentative track pattern labels some of which are iteratively updated during implementation of the design. Multiple candidate track patterns may be ranked based on consistency costs to determine a tentative track pattern. Designs may be implemented with a trackless approach in trackless region(s) followed by a tracked approach based at least in part upon the initial or tentative labels that are dynamically adjusted during implementation. Capacities and demands are assessed at boundary segments of cells by using the tracked or trackless approach.

Claims

1. A computer implemented method for tessellating and labeling routing space for routing electronic designs, comprising:

using a computing system having at least one processor or at least one processor core to perform a process, the process comprising;

creating, at a tessellation mechanism including or functioning in tandem with the at least one processor, routing grids that define multiple tessellated regions for at least a portion of a layer of an electronic design;

determining, at a region labeling mechanism coupled with the tessellation mechanism, a tentative track pattern label by identifying the tentative track pattern label from multiple track pattern labels for at least one tessellated region of the multiple tessellated regions based in part or in whole upon one or more criteria, wherein the tentative track pattern label indicates which track pattern comprising an arrangement of tracks in a permissible order is to be used for physical implementation of the at least one tessellated region; and

performing, at one or more routing mechanisms including or function in tandem with the at least one processor and coupled with the region labeling mechanism, routing for the portion of the layer by referencing the tentative track pattern label for the at least one tessellated region to interconnect circuit component designs in the layer of the electronic design.

2. The computer implemented method of claim 1, wherein the act of creating the routing grids comprises:

identifying a first shape or route in the at least the portion of the layer, wherein the first shape or route comprises a fixed shape, a detail shape, a global route, a channel route, a conduit route, or a detail route;

identifying at least two tessellation lines from a set of tessellation lines for the tessellation lines based at least in part upon one or more first boundary segments of the first shape; and

aligning one or more second boundary segments of a second shape or a cell with corresponding one or more tessellation lines defining the routing grids.

3. The computer implemented method of claim 1, wherein the act of creating the routing grids comprises:

identifying first tessellation lines from a first set of tessellation lines for the at least the portion of the layer;

identifying a first direction for the layer; and

subdividing the at least the portion of the layer by using at least the tessellation lines for creating the routing grids in the first direction.

4. The computer implemented method of claim 3, wherein the act of creating the routing grids further comprises:

identifying second tessellation lines from a second set of tessellation lines for one or more neighboring layers of the layer;

identifying a second direction for the layer; and

subdividing the at least the portion of the layer by using at least the second tessellation lines for creating the routing grids in the second direction.

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

identifying a first cell for routing in the at least the portion of the layer;

identifying one or more boundary segments a first cell for routing in the at least the portion of the layer; and

aligning the one or more boundary segments of the first cell with one or more corresponding grid lines of the routing grids.

6. The computer implemented method of claim 1, the process further comprising at least one of:

determining the tentative track pattern label from an initial track pattern label for the at least the portion of the layer; and

adjusting the routing grids by adding or removing one or more tessellation lines defining the routing grids.

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

identifying multiple candidate track patterns and multiple labels corresponding to the multiple candidate track patterns;

determining rankings or consistency costs of the multiple candidate track patterns; and

identifying the tentative track pattern label from the multiple labels based at least in part upon the rankings or the consistency costs of the multiple candidate track patterns.

8. The computer implemented method of claim 1, the act of performing routing for the portion of the layer comprising:

determining whether or not a tessellated region is tracked or trackless;

determining whether or not the tessellated region is associated with the tentative track pattern label;

identifying capacity of a cell associated with the tessellated region; and

identifying a demand on a cell associated with the tessellated region.

9. The computer implemented method of claim 8, the act of performing routing for the portion of the layer further comprising:

identifying a width of a boundary segment of the cell, wherein the tessellated region is determined to be trackless;

assigning the width of the boundary segment to the capacity of the cell; and

identifying a width for a route to be implemented in the cell and a spacing value for the route.

10. The computer implemented method of claim 9, the act of performing routing for the portion of the layer further comprising:

performing the routing for the portion of the layer by implementing the route in the cell; and

decreasing the capacity of the cell based at least in part upon the width for the route and the spacing value for the route.

11. The computer implemented method of claim 8, the act of performing routing for the portion of the layer further comprising:

identifying a label of a track pattern associated with the tessellated region, wherein the tessellated region is determined to be tracked;

identifying a width for a route to be implemented in the cell; and

identifying a first set of tracks associated with the width in the track pattern and a total number of tracks in the first set.

12. The computer implemented method of claim 11, the act of performing routing for the portion of the layer further comprising:

performing the routing for the portion of the layer by implementing the route in the cell; and

decreasing the capacity of the cell based at least in part upon the total number of tracks in the track pattern and the route.

13. An article of manufacture comprising a non-transitory computer accessible storage medium having stored thereupon a sequence of instructions which, when executed by at least one processor or at least one processor core executing one or more threads, causes the at least one processor or the at least one processor core to perform a method for tessellating and labeling routing space for routing electronic designs, the method comprising:

creating, at a tessellation mechanism including or functioning in tandem with the at least one processor, routing grids that define multiple tessellated regions for at least a portion of a layer of an electronic design;

determining, at a region labeling mechanism coupled with the tessellation mechanism, a tentative track pattern label by identifying the tentative track pattern label from multiple track pattern labels for at least one tessellated region of the multiple tessellated regions based in part or in whole upon one or more criteria, wherein the tentative track pattern label indicates which track pattern comprising an arrangement of tracks in a permissible order is to be used for physical implementation of the at least one tessellated region; and

performing, at one or more routing mechanisms including or function in tandem with the at least one processor and coupled with the region labeling mechanism, routing for the portion of the layer by referencing the tentative track pattern label for the at least one tessellated region to interconnect circuit component designs in the layer of the electronic design.

14. The article of manufacture of claim 13, the process further comprising:

identifying a first cell for routing in the at least the portion of the layer;

identifying one or more boundary segments a first cell for routing in the at least the portion of the layer; and

aligning the one or more boundary segments of the first cell with one or more corresponding grid lines of the routing grids.

15. The article of manufacture of claim 13, the process further comprising:

identifying multiple candidate track patterns and multiple labels corresponding to the multiple candidate track patterns;

determining rankings or consistency costs of the multiple candidate track patterns; and

identifying the tentative track pattern label from the multiple labels based at least in part upon the rankings or the consistency costs of the multiple candidate track patterns.

16. The article of manufacture of claim 13, the act of performing routing for the portion of the layer comprising:

determining whether or not a tessellated region is tracked or trackless;

determining whether or not the tessellated region is associated with the tentative track pattern label;

identifying capacity of a cell associated with the tessellated region; and

identifying a demand on a cell associated with the tessellated region.

17. A system for tessellating and labeling routing space for routing electronic designs, comprising:

non-transitory computer accessible storage medium having stored thereupon program code that comprises a sequence of instructions; and

at least one processor or at least one processor core of a computing system executing the sequence of instructions at least to;

create, at a tessellation mechanism including or functioning in tandem with the at least one processor, routing grids that define multiple tessellated regions for at least a portion of a layer of an electronic design;

determine, at a region labeling mechanism coupled with the tessellation mechanism, a tentative track pattern label by identifying the tentative track pattern label from multiple track pattern labels for at least one tessellated region of the multiple tessellated regions based in part or in whole upon one or more criteria, wherein the tentative track pattern label indicates which track pattern comprising an arrangement of tracks in a permissible order is to be used for physical implementation of the at least one tessellated region; and

perform, at one or more routing mechanisms including or function in tandem with the at least one processor and coupled with the region labeling mechanism, routing for the portion of the layer by referencing the tentative track pattern label for the at least one tessellated region to interconnect circuit component designs in the layer of the electronic design.

18. The system of claim 17, wherein the at least one processor or the at least one processor core further executes the sequence of instructions to:

identify a first cell for routing in the at least the portion of the layer;

identify one or more boundary segments a first cell for routing in the at least the portion of the layer; and

align the one or more boundary segments of the first cell with one or more corresponding grid lines of the routing grids.

19. The system of claim 17, wherein the at least one processor or the at least one processor core further executes the sequence of instructions to:

identify multiple candidate track patterns and multiple labels corresponding to the multiple candidate track patterns;

determine rankings or consistency costs of the multiple candidate track patterns; and

identify the tentative track pattern label from the multiple labels based at least in part upon the rankings or the consistency costs of the multiple candidate track patterns.

20. The system of claim 17, wherein the at least one processor or the at least one processor core that executes the sequence of instructions to perform routing for the portion of the layer further executes the sequence of instructions to:

determine whether or not a tessellated region is tracked or trackless;

determine whether or not the tessellated region is associated with the tentative track pattern label;

identify capacity of a cell associated with the tessellated region; and

identify a demand on a cell associated with the tessellated region.