# US 2019/0171789 A1 · Method of determining colorability of a semiconductor device and system for implementing the same > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0171789 A1 - Document ID: US20190171789A1 - Status: Published application - Kind: A1 - Application number: 16/272,391 - Filed: 2019-02-11 - Published: 2019-06-06 - Earliest claimed: 2016-01-07 - Assignees: Taiwan Semiconductor Manufacturing Company, Ltd. - Applicants: Taiwan Semiconductor Manufacturing Company, Ltd. - Inventors: Chung-Yun CHENG; Chin-Chang HSU; Hsien-Hsin Sean LEE; Jian-Yi LI; Li-Sheng KE; Wen-Ju YANG - Web page: https://patentgrep.com/patent/US20190171789A1 ## CPC - 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) - G03F 1/70: Adapting basic layout or design of masks to lithographic process requirements, e.g., second iteration correction of mask patterns for imaging - G06F 30/392: Floor-planning or layout, e.g. partitioning or placement - G06F 2119/18: Manufacturability analysis or optimisation for manufacturability - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G03F: PHOTOMECHANICAL PRODUCTION OF TEXTURED OR PATTERNED SURFACES, e.g. FOR PRINTING, FOR PROCESSING OF SEMICONDUCTOR DEVICES; MATERIALS THEREFOR; ORIGINALS THEREFOR; APPARATUS SPECIALLY ADAPTED THEREFOR; (phototypographic composing devices B41B; photosensitive materials or processes for photographic purposes G03C; electrophotography, sensitive layers or processes therefor G03G) ## Abstract A method of determining colorability of a layer of a semiconductor device includes iteratively decomposing a conflict graph to remove all nodes having fewer links than a threshold number of links. The method further includes determining whether the decomposed conflict graph is a simplified graph based on a comparison between the decomposed conflict graph and a stored conflict graph. The method further includes determining whether the decomposed conflict graph is colorable based on a number of masks used to pattern the layer of the semiconductor device. The method further includes flagging violations in response to a determination that the decomposed conflict graph is not colorable. ## Claims ### Claim 1 A method of determining colorability of a layer of a semiconductor device, the method comprising: iteratively decomposing a conflict graph to remove all nodes having fewer links than a threshold number of links; determining whether the decomposed conflict graph is a simplified graph based on a comparison between the decomposed conflict graph and a stored conflict graph; determining whether the decomposed conflict graph is colorable based on a number of masks used to pattern the layer of the semiconductor device; and flagging violations in response to a determination that the decomposed conflict graph is not colorable. ### Claim 2 (depends on 1) The method of claim 1, further comprising: manufacturing at least one mask in response to a determination that the decomposed conflict graph is colorable. ### Claim 3 (depends on 1) The method of claim 1, further comprising selecting the threshold number of links based on the number of masks used to pattern the layer. ### Claim 4 (depends on 1) The method of claim 1, further comprising reporting the conflict graph as colorable in response to a determination that decomposed conflict graph is colorable. ### Claim 5 (depends on 4) The method of claim 4, wherein the reporting of the conflict graph as colorable comprises suggesting a color for each node of the conflict graph. ### Claim 6 (depends on 1) The method of claim 1, wherein the flagging the violations comprises recommending at least one solution to the flagged violations. ### Claim 7 (depends on 1) The method of claim 1, further comprising partitioning a partially decomposed conflict graph between iterations of decomposing the conflict graph. ### Claim 8 (depends on 1) The method of claim 1, further comprising modifying the conflict graph in response to the flagging the violations. ### Claim 9 A system for determining colorability of a layer of a semiconductor device, the system comprising: a non-transitory computer readable medium configured to store instructions thereon; and a processor connected to the non-transitory computer readable medium, wherein the processor is configured to execute the instructions for: receiving a conflict graph; iteratively decomposing the conflict graph to remove all nodes having fewer links than a threshold number of links; comparing the decomposed conflict graph with a stored conflict graph; determining whether the decomposed conflict graph is colorable based on the comparison; and flagging violations in response to a determination that the decomposed conflict graph is not colorable. ### Claim 10 (depends on 9) The system of claim 9, wherein the processor is configured to execute the instructions for determining whether the decomposed conflict graph is colorable based on a number of masks used to pattern the layer of the semiconductor device. ### Claim 11 (depends on 9) The system of claim 9, wherein the processor is configured to execute the instructions for interfacing with at least one machine for manufacturing the layer of the semiconductor device in response to a determination that the decomposed conflict graph is colorable. ### Claim 12 (depends on 9) The system of claim 9, wherein the processor is configured to execute the instructions for recommending at least one solution to the flagged violations. ### Claim 13 (depends on 12) The system of claim 12, wherein the processor is configured to modify the conflict graph based on the recommended at least on solution. ### Claim 14 (depends on 9) The system of claim 9, wherein the processor is configured to partition a partially decomposed conflict graph between iterations of decomposing the conflict graph. ### Claim 15 (depends on 9) The system of claim 9, wherein the processor is configured to modify the conflict graph based on an input received from a user. ### Claim 16 (depends on 9) The system of claim 9, wherein the processor is configured to instruct a display to display the flagged violations. ### Claim 17 A method of determining colorability of a layer of a semiconductor device, the method comprising: determining a number of masks used to pattern the layer of the semiconductor device; determining a threshold number of links based on the determined number of masks; iteratively decomposing a conflict graph to remove all nodes having fewer links than the threshold number of links; comparing the decomposed conflict graph and a stored conflict graph; determining whether the conflict graph is colorable based on the comparison; and flagging violations in response to a determination that the decomposed conflict graph is not colorable. ### Claim 18 (depends on 17) The method of claim 17, further comprising: manufacturing at least one mask in response to a determination that the conflict graph is colorable. ### Claim 19 (depends on 17) The method of claim 17, further comprising partitioning a partially decomposed conflict graph between iterations of decomposing the conflict graph. ### Claim 20 (depends on 17) The method of claim 17, wherein the determining the threshold number of links comprises setting the threshold number of links to be equal to the determined number of masks.