Fast independent checker for extreme ultraviolet (EUV) routing

Patent metadata

Field	Value
Publication number	US-11966682-B2
Application number	US-202117389860-A
Country	US
Kind code	B2
Filing date	Jul 30, 2021
Priority date	Jul 30, 2021
Publication date	Apr 23, 2024
Grant date	Apr 23, 2024

Abstract

A constraint graph for a candidate routing solution is created; each node in the graph represents a position of an end of a metal shape and each arc in the graph represents a design rule constraint between two of the nodes. A solution graph is computed, for at least a portion of the constraint graph, using a shape processing algorithm. The solution graph is checked for design rule violations to generate one or more violation graphs. A constraint window and a selection of one or more arcs for at least one of the violation graphs are generated. The candidate routing solution is revised, based on one or more violated design rules corresponding to at least one of the selected arcs within the constraint window. Optionally, an integrated circuit is fabricated in accordance with the revised solution.

First claim

What is claimed is:

1. A method comprising:
creating, using at least one hardware processor, a constraint graph for a candidate routing solution, wherein each node in the constraint graph represents a position of an end of a metal shape and each arc in the constraint graph represents a design rule constraint between two of the nodes of the constraint graph;
computing, using the at least one hardware processor, a solution graph for at least a portion of the constraint graph using a shape processing algorithm;
checking, using the at least one hardware processor, the solution graph for design rule violations to generate one or more violation graphs, wherein each arc in the violation graph represents a design rule constraint between two of the nodes of the violation graph;
generating, using the at least one hardware processor, a constraint window and a selection of one or more arcs for at least one of the violation graphs; and
revising, using the at least one hardware processor, the candidate routing solution based on one or more violated design rules corresponding to at least one of the selected arcs within the constraint window.

2. The method of claim 1 , further comprising repeating the checking, generating and revising operations.

3. The method of claim 2 , wherein the revising of the candidate routing solution ignores arc types specified by a given iteration of the generating and revising operations.

4. The method of claim 2 , wherein all types of arcs are processed during a first pass and less than all of the arc types are processed during a second pass.

5. The method of claim 1 , wherein a breadth of an area designated for rerouting is limited based on a size of the constraint window.

6. The method of claim 1 , wherein the constraint graph is partitioned into a plurality of sub-graphs to optimize an analysis of the constraint graph and the computation of the solution graph is performed on one of the plurality of sub-graphs.

7. The method of claim 1 , wherein each design rule comprises one of a minimal length, a minimal area, a minimal distance between line ends, and an exclusion zone for a line end.

8. The method of claim 1 , wherein the checking of the solution graph comprises searching for one or more arcs having a design rule that is violated.

9. The method of claim 1 , wherein at least one of the violation graphs contains multiple violation subgraphs containing a disjoint set of metal shapes with design rule violations and wherein an initial constraint window encompasses a plurality of violations.

10. The method of claim 1 , further comprising:
instantiating the revised candidate routing solution as a design structure; and
fabricating a physical integrated circuit in accordance with the design structure.

11. The method of claim 1 , wherein technologies having design rules that are less complex than an extreme ultraviolet technology are checked within a routing task and technologies having design rules that are as complex as the extreme ultraviolet technology are checked external to the routing task.

12. The method of claim 1 , further comprising identifying a region of the candidate routing solution as a block out region and removing one or more metal shapes corresponding to the block out region, wherein the revising of the candidate routing solution refrains from locating metal shapes within the block out region.

13. A non-transitory computer readable medium comprising computer executable instructions which when executed by a computer cause the computer to perform a method comprising:
creating, using at least one hardware processor, a constraint graph for a candidate routing solution, wherein each node in the constraint graph represents a position of an end of a metal shape and each arc in the constraint graph represents a design rule constraint between two of the nodes of the constraint graph;
computing, using the at least one hardware processor, a solution graph for at least a portion of the constraint graph using a shape processing algorithm;
checking, using the at least one hardware processor, the solution graph for design rule violations to generate one or more violation graphs, wherein each arc in the violation graph represents a design rule constraint between two of the nodes of the violation graph;
generating, using the at least one hardware processor, a constraint window and a selection of one or more arcs for at least one of the violation graphs; and
revising, using the at least one hardware processor, the candidate routing solution based on one or more violated design rules corresponding to at least one of the selected arcs within the constraint window.

14. An apparatus, comprising:
a memory; and
at least one processor, coupled to said memory, and operative to perform operations comprising:
creating, using at least one hardware processor, a constraint graph for a candidate routing solution, wherein each node in the constraint graph represents a position of an end of a metal shape and each arc in the constraint graph represents a design rule constraint between two of the nodes of the constraint graph;
computing, using the at least one hardware processor, a solution graph for at least a portion of the constraint graph using a shape processing algorithm;
checking, using the at least one hardware processor, the solution graph for design rule violations to generate one or more violation graphs, wherein each arc in the violation graph represents a design rule constraint between two of the nodes of the violation graph;
generating, using the at least one hardware processor, a constraint window and a selection of one or more arcs for at least one of the violation graphs; and
revising, using the at least one hardware processor, the candidate routing solution based on one or more violated design rules corresponding to at least one of the selected arcs within the constraint window.

15. The apparatus of claim 14 , the operations further comprising repeating the checking, generating and revising operations.

16. The apparatus of claim 15 , wherein the revising of the candidate routing solution ignores arc types specified by a given iteration of the generating and revising operations.

17. The apparatus of claim 14 , wherein a breadth of an area designated for rerouting is limited based on a size of the constraint window.

18. The apparatus of claim 14 , wherein at least one of the violation graphs contains multiple violation subgraphs containing a disjoint set of metal shapes with design rule violations and wherein an initial constraint window encompasses a plurality of violations.

19. The apparatus of claim 14 , the operations further comprising:
instantiating the revised candidate routing solution as a design structure; and
fabricating a physical integrated circuit in accordance with the design structure.

20. The apparatus of claim 14 , the operations further comprising identifying a region of the candidate routing solution as a block out region and removing one or more metal shapes corresponding to the block out region, wherein the revising of the candidate routing solution refrains from locating metal shapes within the block out region.

Assignees

• IBM

Inventors

• Pandey Diwesh
• Tellez Gustavo Enrique
• Leland James

Classifications

• G06F30/398 Primary

  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) · CPC title

• G06F30/394 Primary

  Routing (G06F30/396 takes precedence) · CPC title

• G06F2111/04

  Constraint-based CAD · CPC title