Debugging Double Patterning without Getting Double Vision

By David Abercrombie

Given that my last couple of blogs on double patterning (DP) might have scared you to death, I figured it was time to bring you some good news. It is unavoidably true that double patterning layout constraints at 20nm and below are going to require changes in all aspects of the design flow, but Mentor Graphics (and, I am sure, the rest of the EDA industry) is working very hard to make the change as painless as possible. One of the biggest challenges in DP design is understanding and debugging DP violation loops. Figure 1 helps explain the uniqueness of an odd cycle DP violation loop.

Figure 1: Example of an odd cycle DP violation loop

The arrangement of polygons at top represents an example of an odd cycle of five polygons. The double-sided arrows between them represent the locations where the separation distance between the polygons is too close for the polygons to be the same color. Combining these “separators” with the polygons they touch forms a cycle that requires alternating colors. The two rows of colored polygons below it detail all the possible ways you could attempt to color the cycle. Assuming that no cuts are allowed, the odd cycle of five shown at the top does not have a valid two-color solution. All solutions are equally wrong, each containing a location in which two polygons of the same color are too close to each other.

The simplest form of marking a coloring violation is to highlight the separator between the same color polygons. However, as you can see, there are many possible coloring choices, each producing a different violating separator, and the choice of which one to show is essentially arbitrary. Displaying a single violating separator also does not make it clear to the designer that s/he actually has five different ways to fix this single odd cycle. Increasing the spacing between the polygons (i.e., beyond the minimum separation distance) at any of the separator locations such that the two polygons involved are no longer required to be the same color will fix the cycle. So the first piece of good news about coloring cycle conflicts is that, for each error, you have multiple options for correction.

An alternative way to show the situation is with a loop or ring, as shown at the bottom of Figure 1. These show all the polygons involved in an odd cycle error at one time, so the designer can see the available options for fixing. Of course, the problem with multiple options is that not all options are created equal—some are better choices than others.

Figure 2: Examples of multiple interactions and cycle propagation in DP violations

Figure 2 provides two examples of how attempting to fix an odd cycle violation can actually lead to creating a new odd cycle violation. On the left, three polygons are involved in an odd cycle violation. The designer can increase the spacing between the top and right polygon, the right and bottom polygon, or the bottom and top polygon. The bottom and top polygon have multiple interactions between them, whereas the right polygon only has a single interaction between it and the other two polygons. If the designer attempts to fix the cycle as shown on the bottom, then the odd cycle remains, because only some of the polygon interactions were fixed.

The example on the right shows a case where a simple odd cycle of three abuts an even cycle of six. The odd cycle is an error, while the even cycle does not have an issue. Again, the designer can increase the spacing of any of the three separators involved in the odd cycle in an attempt to fix the violation. However, as demonstrated, if the designer chooses to fix the rightmost separator of the odd cycle, it then forms a new odd cycle of seven including all of the polygons that were part of the original even cycle of six. This kind of “whack a mole” error propagation can be very frustrating to the designer. Luckily, Mentor has been working on finding ways to warn the designer about these types of issues.

Figure 3: Example of “warning rings” that help predict DP error propagation

In Figure 3, the design at top has two odd cycle violations (shown by the red rings). The error on the left has two orange rings that make contact with two of the separators of the red ring. Notice that these orange rings show additional interaction between some of the same polygons involved in the current red odd cycle. These orange rings are warnings that an attempt to fix the error by changing the separator in that location will result in a new error extending to the location shown by the orange ring. The bottom picture shows the result after the designer attempts the indicated fix. Notice that the red ring has grown to match the orange ring. The issue is that the two polygons interacting at that separator also interact in a second location. Breaking the one separator did not completely fix the interactions of these three polygons.

The error on the right has only one orange warning ring. Notice that this orange ring shows interaction between two additional polygons that are not currently part of the red error cycle. This is a case of an even loop adjoining an odd loop. The orange ring warns you that if you attempt to fix this particular separator in the odd loop, your correction will only create a larger loop including additional polygons. In the bottom picture, you can see that the designer fixed one of the separators that did not interact with an orange warning ring, fixing the design without causing an additional error. These types of “hints” greatly aid the designer in making good choices for fixing DP cycle violations.

Another key aspect of improved productivity for fixing DP cycle violations is realtime feedback. Mentor Graphics recently released Calibre RealTime, which runs within the layout editor to display DRC violations as the designer makes changes to the layout. This capability becomes more useful than ever with DP cycle violations. If you watch the demo video, you can see and listen to a live example of how Calibre RealTime guides the user through DP violation correction, providing almost instantaneous feedback as the designer changes the layout.

Demo of Calibre RealTime guiding DP debugging in the SpringSoft Laker editor

Although DP design brings some new challenges to layout debug, I think innovative tool solutions are doing a lot to help reduce the pain and improve productivity. With a little practice, it may become as easy as all those other thousands of DRC checks. Do you think these types of capabilities will help you be more productive when working on DP cycle violations? Do you have any other suggested capabilities that you think would be helpful in this area? Let me know in your comments to this blog.

In my next blog, I will address tools and techniques the designer can use to help control coloring, an important factor in DP design methodology.