Monsters, Inc.: How Do I Fix These Double Patterning Errors Anyway?

By David Abercrombie
Just mention double patterning (DP) to designers, and you can see the fear in their eyes. There is real trepidation about what kind of monster DP design debugging will be. In this article, I hope to alleviate some of that trepidation by educating you on manual correction techniques, automated fixing hints, and automated fixing capabilities you can adopt to help you with DP error resolution.

Quick recap—as you’ll recall from my previous articles, there are two basic types of DP errors that a designer will face, odd cycle and anchor path violations:

• An odd cycle violation identifies a group of polygons spaced such that any neighboring polygons must have opposite colors, but because of the odd number of polygons in the cycle, this color alternation cannot be evenly divided by two colors.
• An anchor path violation indicates that the user has “anchored” (pre-colored) a pair of polygons in the layout to ensure they are placed on certain mask layers, but there is a series, or path, of interacting polygons between the two anchors that cannot be colored in alternating colors to align with the anchor masks.

Figure 1 shows a layout containing both types of errors. The two red conflict rings indicate two separate odd cycle violations. The dark purple anchor path indicates a color alternation violation between the anchored polygon at the top and the anchored polygon at the bottom of the cell.

Figure 1: Example layouts containing odd cycle and anchor path violations.

If you are trying to manually correct an odd cycle or anchor path violation, there is good news and bad news. The good news is that, unlike most traditional DRC errors, these DP errors usually have multiple solutions. Since both error types result from the interaction of multiple polygons simultaneously, fixing any single interaction in the set fixes the error. For instance, if an odd cycle contains three polygons with three spacing interactions, the designer only has to edit any single polygon or spacing to fix the entire set.

The bad news is that most designers’ attempts to fix a DP violation often result in a new DP violation. There are two scenarios in which this tends to happen, which I’ll call extrinsic and intrinsic.

Figure 2 demonstrates the extrinsic scenario, in which attempting to fix the polygons and spaces of a given error produces a new error involving new polygons and spacings that were not in the original error (hence the term “extrinsic”). The original error shows three polygons in the middle of the design that interact to create an odd cycle of three, as highlighted by the red arrows. There are other polygons that interact with these three polygons, but they do not participate in this original error. The illustrations below show various ways in which a designer might try to move one of the original three polygons. In all three examples, the move fixes the original error, but creates a new error involving some of the polygons that were not part of the original error.

In this situation, there are some manual techniques that help you avoid this result. Figure 3 demonstrates two such techniques, each with multiple fix options. The first technique, shown in the top row, is to move single edges of polygons instead of moving entire polygons. The second technique, shown in the bottom row, is to either remove or split a polygon to fix an error. Both correction techniques can dramatically reduce the possibility of introducing new interactions that may lead to new errors.

Figure 3: Example techniques that can be used when fixing an odd cycle to avoid creating new errors.

In the intrinsic error scenario, the new error generated involves the same polygons that were in the original error (hence the term “intrinsic”). Figure 4 illustrates two intrinsic error examples. The left example occurs when any two of the polygons involved in the error have more than one point of spacing interaction. When the designer attempts to fix the violation by increasing the space at one of the points of interaction, the error remains after the modification, because there is still another point of interaction between the same two polygons. Since these multiple points of interaction may not be readily visible in the editing window, the designer is unlikely to notice them until re-running the check after the fix, only to find the same error occurring. The right example shows an odd cycle error that shares one or more separators with a neighboring even cycle that is not part of the original error. However, if the designer tries to fix the odd cycle by increasing the space at one of the separator locations shared by the neighboring even cycle, then a new error occurs that includes all the original polygons plus the polygons that were part of the even cycle.

Figure 4: Example of new “intrinsic” errors that can occur when trying to fix an odd cycle.

For intrinsic errors, automated fix hints can help you avoid creating new errors. Mentor Graphics has patented a new type of warning output that, combined with a slightly modified conflict output, greatly enhances the information available to designers trying to fix these types of issues. These new “warning rings” are shown in Figure 5. The left picture shows three errors containing odd cycles of three, and one odd cycle of five, with the traditional conflict ring output for odd cycle violations. In this traditional error visualization, the designer might logically assume that any of the separator spacings indicated by the rings could be modified with equal chance of success in fixing the error.

However, the combination of modified conflict rings and warning rings shown in the right picture tells a very different story. Any separator location in which both a conflict ring and a warning ring exist between polygons indicates that any attempt to fix the conflict ring by increasing that space will create a new error that expands to include the warning ring. For instance, the upper left odd cycle of three has one of the separators blocked by a warning ring, which tells designers to focus their efforts on the other two separator spacings. In the lower left odd cycle of three, two of the three separators are blocked by warning rings, leaving only one viable fix option.

The other type of information that can be gleaned from this innovative automated fix hinting is demonstrated in the two odd cycle errors on the right. In this case, the two conflict rings that share a separator spacing can both be fixed simultaneously by increasing this space, saving the designer significant time and effort.

Figure 5: Comparison of errors highlighted using only conflict rings versus the same errors highlighted with conflict and warning rings to assist in debug.

The last fix option for odd cycle and anchor path DP violations is what all designers want—automated correction. If the foundry process allows polygons to be “cut” into pieces that are colored separately and then “stitched” together by overlapping them at the point where the two pieces meet, an automated fix solution is possible. A large majority of DP violations can be fixed using this method, and Mentor’s DP checking and decomposition tools can find and insert these stitch locations automatically. Figure 6 shows a layout as originally drawn (without stitches) that contains several odd cycle and anchor path violations, and the same layout after Calibre® Multi-Patterning has automatically introduced stitches. The stitch locations are highlighted by the blue circles. Stitching fixed the majority of the errors automatically, and in the one location that was not fixable, the introduction of a stitch removed one of the warning rings, opening up an additional opportunity for the designer to fix it manually.

Figure 6: Example automated odd cycle and anchor path violation fixing using stitches.

If the thought of dealing with DP-related odd cycle and anchor path violations still gives you nightmares, let me assure you that double patterning is not a monster in the closet. The manual techniques, automated hints, and automated fixing that I’ve described here will make your life much easier. You will find that, with a little practice and patience, along with the right techniques and tools, you’ll very quickly become proficient and productive in DP-based design.

Please let me know what you think about these techniques and tools. Also, let me know if you have any creative DP debugging techniques or ideas of your own to share. Next time, we’ll look at how to deal with the parasitic variability impacts of DP-based design.