System and method for assigning color pattern

A method includes operations below. A layout of a circuit is converted to a first conflict graph. A first vertex and a second vertex in the first conflict graph are adjusted based on first data indicating a color patterns assignment for the circuit, in order to generate a second conflict graph, in which the first vertex indicates a first pattern in the layout, and the second vertex indicates a second pattern in the layout. According to the second conflict graph, a first color pattern is assigned to both of the first pattern and the second pattern, or the first color pattern is assigned to the first pattern and a second color pattern is assigned to the second pattern, in order to generate second data for fabricating the circuit.

BACKGROUND

Multiple exposure or multi-patterning technology (MPT) involves forming patterns on a single layer of a substrate using two or more different masks in succession. If only two masks are used for patterning a layer, the technique is referred to as double exposure. One form of double exposure is referred to as double patterning technology (DPT). In DPT, first and second masks are used sequentially to pattern the same layer. As long as the patterns within each mask comply with the relevant minimum separation distances for the technology node, the combination of patterns formed using both masks may include smaller separations than the minimum separation distance. MPT allows line segments, and in some cases, more complex shapes to be formed of a vertical segment and a horizontal segment on the same mask. Thus, MPT provides flexibility and generally allows for significant reduction in overall IC layout.

DETAILED DESCRIPTION

In order to facilitate the illustration of various embodiments of the present disclosure, various terms or components regarding fabrications of semiconductor devices are introduced herein. In some embodiments, integrated circuits (IC) are fabricated by photolithographic techniques, including, for example, forming conductive lines and shapes. For example, copper lines in an interconnect layer of an IC are formed by photolithographic techniques, or a diffusion region in an active device layer of the IC is formed by the photolithographic techniques. These conductive lines and shapes are generally referred to as patterns or polygons in a layout of the IC. Using photolithography to form these patterns is also referred to as “patterning.” Methods in which a single layer of an IC is exposed with two or more photomasks are referred to as multi-patterning.

For ease of visualization, patterns assigned to respectively different masks used to expose the same layer are often drawn in respectively different color patterns. Thus, the set of patterns, which are assigned to be exposed in the photoresist using a given mask, is referred to as being assigned the same “color pattern.” In some embodiments, a display device is configured to display the layout of the IC, in which all circuit patterns assigned to a single photomask using the same color pattern.

In some cases, a proposed division of the patterns among three different masks results in one mask having two patterns closer to each other than a minimum separation distance, a situation referred to as a conflict. Some conflicts are able to be solved by re-assigning a pattern to a different photomask. If, however, there is no way to divide the patterns of that layer among three different masks without having two patterns in a single mask closer to each other than the minimum separation distance, there is a patterning conflict. Some conflicts are able to be resolved by a design (layout) change, or an advanced technique, including, for example, splitting a single circuit pattern into two abutting parts, each to be patterned by a respective mask, and stitched together.

Reference is now made toFIG. 1.FIG. 1is a schematic diagram of a system100, in accordance with some embodiments of the present disclosure.

As illustratively shown inFIG. 1, the system100includes a processor110, a memory120, Input/Output (I/O) interfaces130, and at least one manufacturing tool140. The processor110is coupled to the memory120and the I/O interfaces130. In various embodiments, the processor110is a central processing unit (CPU), an application specific integrated circuit (ASIC), a multi-processor, a distributed processing system, or a suitable processing unit. Various circuits or units to implement the processor110are within the contemplated scope of the present disclosure.

The memory120is configured to store one or more program codes for aiding design of integrating circuits. For illustration, the memory120stores a program code encoded with a set of instructions for assigning color patterns of the multi-patterning to patterns in a layout of a circuit (not shown). The processor110is able to execute the program codes stored in the memory120, and the operations of assigning the color patterns are able to be automatically performed.

In some embodiments, the memory120is a non-transitory computer readable storage medium encoded with, i.e., storing, a set of executable instructions for assigning the color patterns. For illustration, the memory120stores executable instructions for performing operations including, for example, operations S310-S330illustrated inFIG. 3. In some embodiments, the computer readable storage medium is an electronic, magnetic, optical, electromagnetic, infrared, and/or a semiconductor system (or apparatus or device). For example, the computer readable storage medium includes a semiconductor or solid-state memory, a magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk, and/or an optical disk. In one or more embodiments using optical disks, the computer readable storage medium includes a compact disk-read only memory (CD-ROM), a compact disk-read/write (CD-R/W), and/or a digital video disc (DVD).

The implementations of the memory120are given for illustrative purposes only. Various devices to implement the memory120are within the contemplated scope of the present disclosure.

In some embodiments, data D1indicating a layout of a circuit and data D2indicating a conflict graph (e.g., conflict graphs inFIGS. 4B, 5B, 6B, 7B, and 8Bbelow) associated with the data D1are stored in the memory120. In some embodiments, the data D2is generated from operations (e.g., operations S310-S330discussed inFIG. 3below) performed by the processor110.

In some embodiments, the at least one manufacturing tool140is configured to retrieve the data D1and the data D2from the memory120, in order to perform one or more semiconductor manufacturing processes to form structures of the circuit corresponding to the layout indicated by the data D1. In some embodiments, the semiconductor manufacturing processes includes a multiple patterning lithography process and normal processes. In some embodiments, the multiple patterning lithography process includes operations of constructing a pattern on a substrate by dividing the pattern into two or more interleaved patterns. In some embodiments, the operations of the multiple patterning lithography process include two or more exposures by using photomasks as assigned based on the data D2, forming spacers adjacent features and removing the features to provide a pattern of spacers, resist freezing, and/or other suitable processes. In some embodiments, the normal processes include various operations including deposition, removal, patterning (which performed based on the data D2), modification of electrical properties, etc.

The operations of the semiconductor manufacturing processes are given for illustrative purposes only. Various suitable operations to perform the semiconductor manufacturing processes are within the contemplated scope of the present disclosure.

The I/O interfaces130receive data or commands from various control devices which, for example, are operated by a circuit designer and/or a layout designer. Accordingly, the system100is able to be manipulated with the inputs or commands received by the I/O interfaces130. For example, in some embodiments, the data D1is transmitted from the I/O interfaces130to the memory120. In some embodiments, the I/O interfaces130include a display device configured to display the status of executing the program code. In some further embodiments, the display device is configured to display patterns in a layout, and/or color patterns assignments in the patterns. In some embodiments, the I/O interfaces130include a graphical user interface (GUI). In some other embodiments, the I/O interfaces130include a keyboard, keypad, mouse, trackball, track-pad, touch screen, cursor direction keys, or the combination thereof, for communicating information and commands to processor110.

The implementations of the I/O interfaces130are given for illustrative purposes only. Various devices to implement the I/O interfaces130are within the contemplated scope of the present disclosure.

Reference is now made toFIG. 2A.FIG. 2Ais a schematic diagram of a layout200of a circuit, in accordance with some embodiments of the present disclosure. In some embodiments, the layout200is generated by receiving the data D1, indicating the layout of a circuit (not shown), from the I/O interfaces130inFIG. 1. In some other embodiments, the layout200is generated by an electronic design automation (EDA) tool carried in the memory120inFIG. 1.

The implementations of the layout200are given for illustrative purposes. Various implementations of the layout200are within the contemplated scope of the present disclosure. In order to facilitate the illustration of a method300ofFIG. 3below, various terms or components regarding layout and patterns thereof are introduced with reference toFIG. 2A.

As illustratively shown inFIG. 2A, in some embodiments, the layout200includes patterns201,202,203, and204. In some embodiments, the patterns201-204are arranged to define a circuit pattern in an IC. In some cases, double patterning lithography is employed in embodiments ofFIG. 2A. In other words, in the example ofFIG. 2A, only two masks are employed to form the patterns201-204in the layout200during the multi-patterning. In some embodiments, for ease of visualization, the processor110inFIG. 1assigns two colors patterns (not shown), corresponding to the two masks, to the patterns201-204. In other words, two of the patterns201-204are expected to be assigned with a first color pattern (not shown) of double patterning, and another two of the patterns201-204are expected to be assigned with a second color pattern (not shown) of double patterning.

In some embodiments, a minimum separation distance SPDPLbetween the adjacent patterns is determined from the design rules and technology file for the process being used. The minimum separation distance SPDPLis set to ensure that the adjacent patterns are able to be clearly formed by a single photomask. In other words, two adjacent patterns are assigned different color patterns, which correspond to different masks, on condition that a distance between the two adjacent patterns is less than the minimum separation distance SPDPL.

In the example ofFIG. 2A, the distance between the pattern201and the pattern202is less than the minimum separation distance SPDPL. The distance between the pattern202and the pattern203is less than the minimum separation distance SPDPL. The distance between the pattern203and the pattern204is less than the minimum separation distance SPDPL. Accordingly, in order to prevent from violating the design rules, the pattern201and the pattern202are expected to be assigned with different color patterns. The pattern202and the pattern203are expected to be assigned with different color patterns. The pattern203and the pattern204are expected to be assigned with different color patterns. In some embodiments, the system100inFIG. 1is configured to assign color patterns to the patterns201-204in the layout200according to a conflict graph200A inFIG. 2Bas discussed below.

Reference is now made toFIG. 2AandFIG. 2B.FIG. 2Bis a schematic diagram of a conflict graph200A corresponding to the layout200inFIG. 2Ain accordance with some embodiments of the present disclosure.

In some embodiments, the conflict graph200A is generated by the system100inFIG. 1, in order to assign color patterns to the patterns201-204in the layout200, and to detect whether a conflict is present in the color patterns assignment. In some embodiments, a designer is able to input data indicating the conflict graph200A to the system100inFIG. 1via the I/O interfaces130inFIG. 1. Accordingly, at least one of the EDA tool carried in the memory120inFIG. 1is activated to perform the operations of the color patterns assignment and/or conflict detection according to the conflict graph200A. In some other embodiments, the processor110is configured to perform at least one design-aiding tool to process the data indicating the layout200inFIG. 2A, in order to generate the conflict graph200A. The configurations of the conflict graph200A are given for illustrative purposes. Various configurations of the conflict graph200A are within the contemplated scope of the present disclosure.

In some embodiments, the conflict graph200A is utilized to show the spacing relation among the patterns201-204inFIG. 2A. For illustration, the conflict graph200A includes vertices A, B, C, and D, and edges21-24. The vertices A, B, C, and D correspond to the patterns201-204inFIG. 2A, respectively. The edges21-24are generated based on the arrangements of the patterns201-204inFIG. 2A. For example, inFIG. 2A, the pattern201is disposed adjacent to the patterns202and203. Accordingly, in the conflict graph200A, the vertex A, which corresponds to the pattern201, is coupled to the vertex B which corresponds to the pattern202via the edge21. The vertex A is also coupled to the vertex C which corresponds to the pattern203via the edge22. In the layout200inFIG. 2A, the pattern203is disposed between the pattern201and the pattern204. Accordingly, in the conflict graph200A inFIG. 2B, the vertex A is coupled to the vertex D which corresponds to the pattern204via the edge22, the vertex C, and the edge24. With the same analogy, the rest connections among the vertices B, C, and D inFIG. 2Bare able to be generated based on the layout200inFIG. 2A.

In some embodiments, the processor110inFIG. 1is configured to perform at least one of the EDA tool carried in the memory120inFIG. 1, in order to sequentially assign color patterns to patterns201-204in the layout200inFIG. 2Abased on the vertices A-D in the conflict graph200A. In an example of employing the double patterning, two color patterns are alternately assigned to the patterns201-204based on the vertices A-D. For example, based on the order of the vertices A-D, a first color pattern is assigned to the pattern201corresponding to the vertex A, a second color pattern is assigned to the pattern202corresponding to the vertex B. Then, the first color pattern is assigned to the pattern203corresponding to the vertex C, a second color pattern is assigned to the pattern204corresponding to the vertex D.

In some embodiments, the system100is configured to detect whether a conflict, which violates certain design rules, is presented in the layout200based on the conflict graph200A. As discussed above, in the layout200, the pattern201and the pattern202are expected to be assigned with different color patterns, and the pattern202and the pattern203are expected to be assigned with different color patterns. In the example of employing the double patterning, a conflict is present in the patterns201,202,203, and204. For example, as discussed above, the pattern201is assigned with the first color pattern, and the pattern202is assigned with the second color pattern. As a result, there is no an appropriate color pattern to be assigned to the pattern203since the pattern203is expected to be assigned with a color pattern different from the color patterns assigned to the patterns201and202. In some embodiments, when the conflict is detected, the processor110is configured to send a message via the I/O interfaces130, in order to notify a designer to revise the layout200or revise the color patterns assignment.

In some embodiments, on condition that the double-patterning is employed, the system100is configured to check whether a closed cycle, which is formed with an odd number of vertices, is present in the conflict graph200A, in order to detect the conflict in the layout200. For example, in the conflict graph200A, the three vertices A, B, and C form a closed cycle CC. As discussed above, the patterns201-203, which correspond to three vertices A, B, and C in the closed cycle CC, have the conflict therebetween. Effectively, in the example of employing the double-patterning, the closed cycle CC is able to indicate that the conflict is present in the layout200.

Explained in a different way, in the example of using the double-patterning, patterns corresponding to two adjacent vertices are assigned with different color patterns, in order to prevent from violating the design rules. Therefore, if a closed cycle forming by the odd number of vertices is present in the conflict graph, it indicates that a conflict will be present in the color patterns assignment corresponding to the odd number of vertices.

For illustrative purposes only, the above embodiments are discussed with reference to examples employing double-patterning. Various numbers of patterns used in multi-patterning are within the contemplated scope of the present disclosure. For example, in some other embodiments, on condition that an even number of patterns are employed, the system100is also able to check whether the closed cycle, which is formed with the odd number of vertices, is present in the conflict graph200A, in order to detect the conflict in the layout200.

The following paragraphs describe certain embodiments related to the system100to illustrate functions and applications thereof. However, the present disclosure is not limited to the following embodiments. Various arrangements are able to implement the functions and the operations of the system100inFIG. 1are within the contemplated scope of the present disclosure.

FIG. 3is a flow chart of a method300, in accordance with some embodiments of the present disclosure. In some embodiments, the system100inFIG. 1is configured to perform the method300to assign color patterns to patterns in the layout for a circuit. For ease of understanding, reference is now made toFIGS. 1-3, and the operations of the method300are described with the system100. In some embodiments, the method300includes operations S310, S320, S330, and S340.

In operation S310, the layout of a circuit is converted to a first conflict graph. For illustration, in some embodiments, at least one EDA tool carried in the memory120inFIG. 1is activated by the processor110, to decompose the layout200inFIG. 2Ato generate the conflict graph200A inFIG. 2B. Alternatively, in some other embodiments, the processor110is able to receive data indicating the conflict graph200A via the I/O interfaces130inFIG. 1.

In operation S320, a first vertex and a second vertex in the first conflict graph are adjusted based on first data indicating a color patterns assignment for the circuit, in order to generate a second conflict graph. In some embodiments, the processor110is able to receive the first data via the I/O interfaces130inFIG. 1. In some embodiments, the first data includes information of color patterns assignment. The information of color patterns assignment is configured to specify how color patterns are assigned to the patterns in the layout. The detailed descriptions regarding operation S320will be provided below with reference toFIGS. 4A-4C, 5A-5B, 6A-6B, 7A-7B, and 8A-8Bbelow.

In operation S330, the color patterns are assigned to patterns in the layout based on the second conflict graph, in order to generate second data for fabricating the circuit. In some embodiments, after the second conflict graph in operation S320is generated, the processor110is able to perform at least one EDA tool carried in the memory120inFIG. 1, to assign color patterns to the patterns in the layout, in order to generate the second data (e.g., data D2inFIG. 1) that contains information of arrangements of the patterns and the corresponding designated color patterns. In some embodiments, as discussed above, the second data include information indicating the second conflict graph (e.g., conflict graphs discussed inFIGS. 4C, 5B, 6B, 7B, and 8Bbelow).

In operations S340, patterns corresponding to the circuit are formed based on the data generated in operation S330. For illustration, after the operation S330, the processor110transmits the second data (e.g., data D2inFIG. 1) to the at least one manufacturing tool140inFIG. 1, in order to initiate at least one manufacturing process (e.g., photolithography) to fabricate the circuit.

For example, in some conditions (e.g., embodiments discussed inFIGS. 4C, 5A-5B, and 6A-6Bbelow), patterns in the layout of the circuit are assigned with the same color pattern based on the data D2. Under this condition, the at least one manufacturing tool140utilizes the same photomask, which corresponds to the color pattern, to perform the semiconductor manufacturing processes, in order to form structures corresponding to the patterns (e.g., patterns402-403inFIGS. 4C, 5B, and 6B) in the circuit on a substrate (not shown). In some alternative conditions (e.g., embodiments discussed inFIGS. 7B and 8Bbelow), patterns in the layout of the circuit are assigned with the different color patterns based on the data D2. Under this condition, the at least one manufacturing tool140utilizes different photomasks, which corresponds to the color patterns respectively, to perform one or more operations of the semiconductor manufacturing processes, in order to form structures corresponding to the patterns (e.g., patterns402-403inFIGS. 7B and 8B) in the circuit on a substrate (not shown). In these conditions, the semiconductor manufacturing processes may include the operations of the multiple patterning lithography process, the operations of the normal processes as discussed above, or a combination thereof.

The above description of the method300includes exemplary operations, but the operations of the method300are not necessarily performed in the order described. The order of the operations of the method300disclosed in the present disclosure are able to be changed, or the operations are able to be executed simultaneously or partially simultaneously as appropriate, in accordance with the spirit and scope of various embodiments of the present disclosure.

In some alternative embodiments, the method300is implemented as a design tool carried on a non-transitory computer-readable medium. In other words, the method300is able to be implemented in hardware, software, firmware, and the combination thereof. For illustration, if speed and accuracy are determined to be paramount, a mainly hardware and/or firmware vehicle is selected and utilized. Alternatively, if flexibility is paramount, a mainly software implementation is selected and utilized. Various arrangements to implement the method300are within the contemplated scope of the present disclosure.

Reference is now made toFIG. 4AandFIG. 4B.FIG. 4Ais a schematic diagram of a layout400of a circuit, in accordance with some embodiments of the present disclosure.FIG. 4Bis a schematic diagram illustrating a first conflict graph400A corresponding to the layout400inFIG. 4A, in accordance with some embodiments of the present disclosure. With respect to the embodiments ofFIG. 4A, like elements inFIG. 4Bare designated with the same reference numbers for ease of understanding.

As shown inFIG. 4A, the layout400includes four patterns401,402,403, and404. In some embodiments, the patterns401-404correspond to shapes of elements in the circuit (not shown). In the example ofFIG. 4A, the double-patterning is employed, and the patterns402and403are assigned with the same color pattern, which is illustrated with the color pattern CP, based on the first data as discussed in operation S320.

In some embodiments, with similar operations discussed inFIG. 2B, the processor110generates the first conflict graph400A that includes vertices A1, B1, C1, and D1, based on the layout400. The vertices A1, B1, C1, and D1correspond to the patterns401,402,403, and404inFIG. 4A, respectively. The edges that connect the vertices A1, B1, C1, and D1are also generated based on the arrangements of the patterns401,402,403, and404. For illustration, as the patterns401and402are disposed adjacent to each other, the corresponding vertices A1and B1are coupled to each other via one edge. As the patterns403and404are disposed adjacent to each other, the corresponding vertices C1and D1are coupled to each other via another one edge.

As discussed above, in the example of using the double-patterning, patterns corresponding to two adjacent vertices are assigned with different color patterns. As shown inFIG. 4B, if there is no specific requirements (for example, color patterns assignment specified in the first data), the patterns401and402will be assigned with different color patterns, and the patterns403and404will be assigned with different color patterns. For example, in the example of employing the double-patterning, the pattern401is assigned with a first color pattern, and the pattern402is assigned with a second color pattern. The pattern403is assigned with one of the first color pattern and the second color pattern, and the pattern404is assigned with another one of the first color pattern and the second color pattern. In other words, based on the first conflict graph400A inFIG. 4B, the patterns402and403may be assigned with the same color pattern or different color patterns if there is no specific requirements.

Reference is now made toFIG. 4C.FIG. 4Cis a schematic diagram illustrating a second conflict graph400B generated by operation S320inFIG. 3based on the first conflict graph400A inFIG. 4B, in accordance with some embodiments of the present disclosure. With respect to the embodiments ofFIG. 4B, like elements inFIG. 4Care designated with the same reference numbers for ease of understanding.

As discussed above, based on the first data as discussed in operation S320inFIG. 3, the patterns402and403are expected to be assigned with the same color pattern CP. In some embodiments, the processor110inFIG. 1is configured to activate at least one EDA tool carried in the memory120inFIG. 1, in order to perform operation S320to generate the second conflict graph400B based on the first conflict graph400A.

In some embodiments, on condition that, based on the first data, patterns in a layout are assigned with the same color pattern, the processor110is configured to merge the vertices which correspond to the patterns assigned with the same color pattern, in the first conflict graph as a single vertex, in order to generate the second conflict graph. For illustration, in the example ofFIGS. 4A and 4B, the patterns402and403are assigned with the same color pattern CP. The processor110virtually merges the vertices B1and C1, which respectively correspond to the patterns402and403, as a single vertex BC inFIG. 4C, in order to generate the second conflict graph400B. In some embodiments, the term “virtually” indicates that operations discussed in the present disclosure are performed by a series of data-processing and/or data computations.

As shown inFIG. 4C, there is no conflict present in the second conflict graph400B, and as the patterns402and403correspond to the same vertex BC, the patterns402and403will be assigned with the same color pattern CP inFIG. 4Ain operation S330inFIG. 3based on the second conflict graph400B. In the example of employing the double-patterning, based on the order the vertices A1, BC, and D1, the pattern401corresponding to the vertex A1is assigned with a first color pattern, the patterns402-403corresponding to the vertex BC are assigned with a second color pattern (i.e., color pattern CP), and the pattern404corresponding to the vertex D1is assigned with the first color pattern.

Reference is now made toFIG. 5AandFIG. 5B.FIG. 5Ais a schematic diagram illustrating a first conflict graph500A corresponding to the layout400inFIG. 4A, in accordance with some embodiments of the present disclosure.FIG. 5Bis a schematic diagram illustrating a second conflict graph500B generated by operation S320inFIG. 3based on the first conflict graph500A inFIG. 5A, in accordance with some embodiments of the present disclosure. With respect to the embodiments ofFIGS. 4A-4C, like elements inFIGS. 5A-5Bare designated with the same reference numbers for ease of understanding.

In some embodiments, on condition that patterns in a layout are assigned with the same color pattern, the processor110is configured to add a pseudo vertex that connects between vertices, which correspond to the patterns assigned with the same color pattern, in the first conflict graph, in order to generate the second conflict graph. In some embodiments, the term “pseudo” indicates that there is no physical pattern present in the layout corresponds to this vertex. For illustration, the patterns402and403inFIG. 5Aare expected to be assigned with the same color pattern CP as discussed inFIG. 4Aabove. As shown inFIG. 5A, the processor110virtually adds a pseudo vertex PV between the vertices B1and C1in the first conflict graph500A. Then, as shown inFIG. 5B, the processor110virtually couples the vertex B1to the vertex C1via the pseudo vertex PV and additional edges (illustrated with dashed lines), in order to generate the second conflict graph500B. Effectively, with the pseudo vertex PV, the vertices B1and C1are adjusted to be not adjacent vertices. Accordingly, in the example of using the double-patterning, the patterns402and403will be assigned with the same color pattern based on the second conflict graph500B.

For example, based on the second conflict graph500B, the pattern401and the pattern404, which correspond to the vertex A1and the vertex D1respectively, will be assigned with a first color pattern of the double-patterning. As there is no physical pattern corresponds to the pseudo vertex PV, the color patterns assignment corresponding to the pseudo vertex PV will be omitted. The patterns402and403, which correspond to the vertices B1and C1respectively, will be assigned with a second color pattern (e.g., color pattern CP inFIG. 4A) of the double-patterning.

Reference is now made toFIG. 6AandFIG. 6B.FIG. 6Ais a schematic diagram illustrating a first conflict graph600A corresponding to the layout400inFIG. 4A, in accordance with some embodiments of the present disclosure.FIG. 6Bis a schematic diagram illustrating a second conflict graph600B generated by operation S320inFIG. 3based on the first conflict graph600A inFIG. 6A, in accordance with some embodiments of the present disclosure. With respect to the embodiments ofFIGS. 5A-5B, like elements inFIGS. 6A-6Bare designated with the same reference numbers for ease of understanding.

In some embodiments, on condition that patterns in a layout are assigned with the same color pattern, the processor110is configured to add an odd number of pseudo vertices that connect between vertices, which correspond to the patterns assigned with the same color pattern, in the first conflict graph, in order to generate the second conflict graph. For illustration, the patterns402and403inFIG. 6Aare expected to be assigned with the same color pattern CP as discussed inFIG. 4Aabove. As shown inFIG. 6A, the processor110virtually adds an odd number of pseudo vertices PV1, PV2, . . . , P2n+1between the vertices B1and C1in the first conflict graph600A. In some embodiments, n is an integer greater than or equal to 1.

For ease of understanding, an example of using three pseudo vertices PV1, PV2, and PV3(i.e., n is set to be 1) is shown inFIG. 6B. As shown inFIG. 6B, the processor110virtually couples the vertex B1to the vertex C1via the pseudo vertices PV1, PV2, and PV3and additional edges (illustrated with dashed lines), in order to generate the second conflict graph600B. Effectively, with the same analogy discussed inFIG. 5B, the vertices B1and C1are adjusted to be not adjacent vertices. Moreover, with the odd number of pseudo vertices PV1, PV2, . . . , P3, in the example of using the double-patterning, the patterns402and403will be assigned with the same color pattern.

For example, based on the second conflict graph600B, the pattern401, and the pattern404, which correspond to the vertex A1and the vertex D1respectively, will be assigned with a first color pattern of the double-patterning. The pattern402and the pattern403, which correspond to the vertex B1and the vertex C1respectively, will be assigned with a second color pattern (e.g., color pattern CP inFIG. 4A) of the double-patterning. As there is no physical patterns correspond to the pseudo vertices PV1, PV2, and PV3, the color patterns assignment corresponding to these pseudo vertices will be omitted.

Reference is now made toFIG. 7A.FIG. 7Ais a schematic diagram of a layout700of a circuit, in accordance with some embodiments of the present disclosure. With respect to the embodiments ofFIGS. 4A and 4B, like elements inFIG. 7Aare designated with the same reference numbers for ease of understanding.

Compared with the layout400inFIG. 4A, based on the color patterns assignment specified in the first data, the pattern401in the layout700is assigned with a first color pattern CP1of the double-patterning, and the pattern402in the layout700is assigned with a second color pattern CP2of the double-patterning. In other words, in the example ofFIG. 7A, the patterns402and403are expected to be assigned with different color patterns.

Reference is now made toFIG. 7B.FIG. 7Bis a schematic diagram illustrating a second conflict graph700B corresponding to the layout700inFIG. 7A, in accordance with some embodiments of the present disclosure. With respect to the embodiments ofFIGS. 4B and 7A, like elements inFIG. 7Bare designated with the same reference numbers for ease of understanding.

In some embodiments, on condition that patterns in a layout are assigned with different color patterns, the processor110is configured to couple vertices, which correspond to the patterns assigned with different color patterns, in the first conflict graph to each other, in order to generate the second conflict graph. In the example ofFIG. 7B, the processor110virtually adds an additional edge (illustrated with dashed lines) to couple the vertices B1and C1of the first conflict graph400A inFIG. 4B, in order to generate the second conflict graph700B. Compared withFIGS. 5B and 6B, the vertices B1and C1inFIG. 7Bare directly coupled with each other via the additional edge. Effectively, the vertices B1and C1inFIG. 7Bin the second conflict graph700B are now adjacent vertices. Accordingly, in the example of using the double-patterning, the patterns402and403corresponding to the vertices B1and C1will be assigned with different color patterns based on the second conflict graph700B.

For example, based on the second conflict graph700B, the pattern401and the pattern403, which correspond to the vertex A1and the vertex C1respectively, are assigned with a first color pattern of the double-patterning. The pattern402and the pattern404, which correspond to the vertex B1and the vertex D1respectively, are assigned with a second color pattern of the double-patterning.

Reference is now made toFIG. 8AandFIG. 8B.FIG. 8Ais a schematic diagram illustrating a first conflict graph800A corresponding to the layout700inFIG. 7A, in accordance with some embodiments of the present disclosure.FIG. 8Bis a schematic diagram illustrating a second conflict graph800B generated by operation S320inFIG. 3based on the first conflict graph800A inFIG. 8A, in accordance with some embodiments of the present disclosure. With respect to the embodiments ofFIGS. 7A and 7B, like elements inFIGS. 8A-8Bare designated with the same reference numbers for ease of understanding.

In some embodiments, on condition that patterns in a layout are assigned with different color patterns, the processor110is configured to add an even number of pseudo vertices that connect between vertices, which correspond to the patterns assigned with different color patterns, in the first conflict graph, in order to generate the second conflict graph. In the example ofFIG. 8B, the processor110virtually adds an even number of pseudo vertices PV1, . . . , PV2nand additional edges (illustrated with dashed lines) to couple the vertices B1and C1inFIG. 8A, in order to generate the second conflict graph800B. In some embodiments, n is an integer greater than or equal to 1. Effectively, the vertices B1and C1in the second conflict graph800B are able to be assigned with different color patterns.

For ease of understanding, an example of using two pseudo vertices PV1and PV2(i.e., n is set to be 1) is shown inFIG. 8B. As shown inFIG. 8B, the processor110virtually couples the vertex B1to the vertex C1via the pseudo vertices PV1and PV2and additional edges (illustrated with dashed lines), in order to generate the second conflict graph800B. Based on the second conflict graph800B, the pattern401and the pattern403, which correspond to the vertex A1and the vertex C1respectively, will be assigned with a first color pattern (e.g., color pattern CP1inFIG. 7A) of the double-patterning. The pattern402and the pattern404, which correspond to the vertex Bland the vertex D1respectively, will be assigned with a second color pattern (e.g., color pattern CP2inFIG. 7A) of the double-patterning. As there is not physical patterns correspond to the pseudo vertices PV1and PV2, the color patterns assignment corresponding these pseudo vertices will be omitted.

As described above, with operation S320inFIG. 3, a specific color patterns assignment for patterns in a layout can be achieved. As a result, the conflict in color patterns assignments can be removed, and the operations of detecting the conflicts in the multi-patterning in further applications are able to be performed more efficiently.

For ease of understanding, the embodiments above are described with double patterning lithography. In various embodiments, multi-patterning, which has two or more color pattern and are able to be employed with the method300inFIG. 3, is within the contemplated scope of the present disclosure.

In this document, the term “coupled” may also be termed as “electrically coupled,” and the term “connected” may be termed as “electrically connected”. “Coupled” and “connected” may also be used to indicate that two or more elements cooperate or interact with each other.

In some embodiments, a method is disclosed that includes operations below. A layout of a circuit is converted to a first conflict graph. A first vertex and a second vertex in the first conflict graph are adjusted based on first data indicating a color patterns assignment for the circuit, in order to generate a second conflict graph, in which the first vertex indicates a first pattern in the layout, and the second vertex indicates a second pattern in the layout. According to the second conflict graph, a first color pattern is assigned to both of the first pattern and the second pattern, or the first color pattern is assigned to the first pattern and a second color pattern is assigned to the second pattern, in order to generate second data for fabricating the circuit.

Also disclosed is a system that includes a memory configured to store computer program codes, and a processor. The memory is configured to store computer program codes. The processor is configured to execute the computer codes in the memory to perform operations below. Vertices in a first conflict graph are adjusted based on a first data indicating a color patterns assignment associated with the vertices, in order to generate a second conflict graph. According to the second conflict graph, the same color pattern or different color patterns are assigned to patterns, which correspond to the vertices, in a circuit, in order to generate second data for fabricating the circuit.

Also disclosed is a system that includes a memory configured to store computer program codes, and a processor. The memory is configured to store computer program codes. The processor is configured to execute the computer codes in the memory to perform operations below. Based on a color patterns assignment for a first pattern and a second pattern in a layout, a first vertex corresponding to the first pattern is coupled to a second vertex corresponding to the second pattern in a first conflict graph, in order to generate a second conflict graph. One or more color patterns are assigned to the first pattern and the second pattern, in order to generate data for fabricating a circuit corresponding to the layout.