Why Do My DP Colors Keep Changing?

By David Abercrombie
At 20nm, foundries are using several different double patterning design flows. One of the more common flows does not actually require the design team to decompose their layers into two colors. The designer only has to verify that the design can be decomposed before taping out each single layer. There are certain obvious advantages to this flow. For example, the designer does not have to generate the two extra layers needed for double patterning assignments, and the file size will be smaller without those extra layers.

Even though this methodology does not require the designer to generate two colors, there are situations in which the designer may want to know what the color assignments will be.
The first situation is the case where the designer is purely curious. Curiosity is a common trait in most engineers, so this is to be expected, but it probably doesn’t warrant a change in the design methodology. In the second situation, a designer is trying to debug DP errors, and believes that seeing the colors will enhance the productivity of error resolution. As reasonable as this may sound, seeing the colors will most likely degrade debug productivity, which is a surprise to most people.

Let’s look at two examples to explain why this paradox is so. The most common type of DP error is the odd cycle violation, in which an odd number of polygons require color alternation in a way that cannot be resolved. Figure 1 shows an example of an odd cycle violation among three polygons. As indicated by the black arrows, each pair of shapes in the set of three require opposite color alternation between them. The DP error highlighted by the red ring indicates there is no valid coloring solution for these three shapes, meaning any color solution displayed to the designer would, by definition, be incorrect. Not only that, but the particular colors displayed would be only one option out of many equally incorrect set of colors that could be shown. All of these coloring options cause a DP separator to be violated, as indicated by the red error line, so they are all equally incorrect.

Figure 1: Odd cycle DP violation, with all possible (but incorrect) DP coloring options.

By showing the error as a RING, minus any colors, the designer is not distracted by the selection of one particular coloring. For instance, if the first coloring choice is shown, with the DP separator error between the two blue polygons, the designer may be led to think that increasing the spacing between those two polygons is the correct debug solution. Actually, increasing any of the three spaces separating these three polygons is an equally valid solution, and will fix the odd cycle error. It may be that, due to other layout limitations, the spacing between the two blue polygons is the most difficult to increase, so the designer would end up spending excessive time focused on a less-productive solution. While there are reasons that fixing one particular spacing in an odd cycle error may be more beneficial than another, just seeing colors and separator errors does not make this evident. The idea of the RING is to show the designer the multiple fixing alternatives without implying a particular solution.

Another example of a DP error where seeing colors is not particularly helpful is when an odd cycle error shares a separator error with an adjoining even cycle. Fixing that particular spacing will actually create a new DP error involving the polygon(s) in the even cycle. If the designer were focused solely on the coloring of the odd cycle error, that outcome might be missed, and another round of debugging would be needed. In the Calibre Double Patterning tool, we identify these types of issues using a second ring, called a warning ring, as shown in Figure 2.

Figure 2: Example warning ring output to highlight preferred, less optimal, or unfeasible fix locations.

The orange warning rings in the right diagram identify the adjacent even cycles that will become part of a new error if the designer fixes the separator spacing where the red conflict cycle and the orange warning cycle touch. Additionally, modifying the shape of the red conflict rings helps identify separator locations where a spacing change can fix more than one error. While this obviously will greatly improve debug efficiency, none of this information is obvious from seeing the color output. It is the error and warning rings that provide the necessary input.

The third situation where a designer may to want to know the colors is when there is concern over parametric variability caused by the misalignment between the two masks. Because the single layer will be decomposed by the fab into two separate masks, and each of these masks will be patterned and etched separately during the manufacturing process, neighboring shapes in the layout may change relative spacing to each other from wafer to wafer, due to lithographic misalignment.

Because of this spacing change, the capacitive coupling between adjacent shapes can vary more if they are on opposite masks, rather than the same mask. There are some particularly critical or sensitive circuits, where understanding and potentially controlling this extra source of variation may be important to the designer, including:

• Matching between memory cells
• Sensitive analog circuits
• Differential circuits
• Analog instantiated in digital
• Matching between CPU cores

Figure 3 illustrates the various types of spacing changes and the corresponding effect on capacitive coupling that can occur.

Figure 3: Possible spacing changes and capacitive coupling impact caused by DP mask misalignment.

If the designer is concerned about a specific net and the variability of capacitive coupling to neighboring nets, then knowing the colors of those neighboring shapes may be useful. Of course, any shapes that are closer than the required color spacing to each other (shown by the separator between them) must be opposite colors. But any shapes whose common space is greater than or equal to same mask spacing requirements can be arbitrarily colored. Figure 4 shows an example of these spacing conditions.

Figure 4: Example coloring options around a polygon from a critical net.

In the original layer, the polygons labeled B and C are close enough to the critical net polygon that they must be the opposite color of the critical net polygon. Because of this, these polygons will have the maximum alignment variability. Knowing this, the designer may wish to move these polygons farther away from the critical net polygon so they can be arbitrarily colored relative to the critical net polygon, like polygons A and D. Given the original layout, the other three diagrams show some of the possible legal colorings. In the first coloring option, the two arbitrary colorable polygons A and D are the same color as the critical net polygon, so they would not misalign relative to the critical net polygon. However, in the second option, they happen to be the opposite color, and would misalign relative to the critical net polygon. In the third option, one is the same color and the other is the opposite, yielding a misalignment variation somewhere in the middle.

So, the critical question would seem to be, which one of these colorings will be the one the foundry generates when it create the masks? Sadly (for the designer), the answer is…there is no way to know. All of these coloring options are equally legal according to the design rules. Most designers believe that if they run the same script that their foundry uses to decompose the masks on their designs, they can expect to see the same colors the foundry will generate.

However, this is not so, and here’s why…All EDA DP decomposition tools use a form of graph processing to find a legal coloring. This technique is very sensitive to the slightest changes in the data that is presented to it, and may vary from run to run, or time to time, for any number of reasons. For example:

• Release-to-release changes in the tool algorithms;
• Changes in initial database construction, which can be affected by running in different configuration modes (e.g., flat, multi-threading, etc.);
• Running on a different number of CPUs;
• Other checks being executed in the deck during that run;
• Any changes to the layout, which will most likely cause different color selections to be made;
• Adding or removing a polygon anywhere in the layout;
• Moving any polygon or edge of any polygon;
• Adding or removing a cell or cell placement;
• Moving a cell to a different hierarchy, and
• Running the decomposition on the cell by itself, which will most likely yield different coloring than when decomposition is run on a cell placed in a larger cell or chip.

Remember, there is no inherent “meaning” in the particular colors shown in these options. They are all equally correct, so there is no intrinsic forcing function that causes the tool to always produce a particular coloring. This behavior is equally true for any vendor decomposition and checking tool, as it is integral to the graphing algorithm techniques by which all DP tools perform decomposition.

On the other hand, don’t get too anxious about this situation, for two reasons. First, the extraction corners provided by the foundry assume worst case, so if a layout passes the timing analysis, the circuit will work, regardless of which coloring happens to occur. Second, the designer does have some ability to control coloring for these special case critical circuits, or at least make sure certain polygons have matched coloring. To enable this control, most foundries provide an alternate DP flow in which the designer is allowed to “anchor” shapes to particular masks.

With anchoring, the designer is allowed to draw markers on important polygons to designate that they should be assigned a certain coloring. The automated decomposition tool recognizes these markers, and will always color those particular polygons those particular colors. For flows in which the designer does not decompose the design layers into two colors before tapeout, anchoring is the only way to be sure that certain polygons will be on certain masks. Figure 5 shows an example of a cell auto-decomposed with and without anchors. Notice that, in the anchored layout, the corresponding polygons in the decomposed layout match the color of the anchors as desired, and that these colors are different than the colors that were produced on the non-anchored version.

Figure 5: Example decomposition without and with anchor markers.

Using anchors guarantees designers that they will get the colors they want for the anchored polygons, but as seen in the example, it is possible to request coloring that will introduce coloring path violations between anchors, as indicated by the brown lines. The designer must still provide legal coloring solutions, even when using anchors.

So, if you have found yourself wanting to see colors during your DP design, first ask yourself, what is my motivation? Then use this article to help you decide if “color vision” is really something you need, or if “color blindness” is, in this case, actually a benefit.