The Trouble With Triples—Part 2

In my last blog, we started to look at some of the challenges of triple patterning (TP) compared to double patterning (DP). In particular, we looked at the algorithmic complexity of determining if a valid coloring solution exists, and if so, producing a three-mask decomposition. This time, let’s look into the challenges of what to do if a layout is not legally decomposable into three colors.

It wasn’t all that long ago that we started trying to understand design issues that were not legally decomposable using two masks. At least with DP there is a very simple and clear definition of what constitutes a legal design construct and what doesn’t. In DP, any construct of polygons and spacing interactions are legal as long as they don’t form an “odd cycle.” Let’s look at some simple examples in Figure 1 just to refresh your memory.

Figure 1: Even and odd cycles in DP design.

The even cycle shows four polygons in a layout whose spacings require color alternation. This interaction is captured by the equivalent graph representation of the resulting requirements. Each node on the graph represents one of the polygons, and each line on the graph represents the requirement to alternate colors between the two nodes due to their close proximity to each other. This graph forms a cycle of four nodes. This geometry can easily be decomposed using two masks by simply alternating each successive node to the other color. This ease of decomposition extends to any even-length cycle (6, 8, 44, 2642, etc.).

In the odd cycle, the layout has been slightly modified, and two of the polygons have been joined into one. The equivalent graph now shows that this forms a set of three nodes that must alternate color. There is no valid way to meet this coloring requirement. With only two colors, no matter how you try to apply them to the three polygons, two of them will always have the same color with a less-than-minimum space, which is illegal. This situation extends to any odd length cycle (5, 7, 13, 73, 6291, etc.). Figure 2 shows some attempted colorings of the three polygons case.

Figure 2: Attempted colorings of the odd cycle, and the corresponding spacing violations.

The red markers in the picture show where two polygons that have been assigned the same color are too close to each other. You can see that there are many possible ways to color these three polygons, but all of them result in an error. This type of spacing violation marker is one way in which DP errors can be displayed to the designer.

The problem with this type of error marker is deciding which one to show the designer. Since all the coloring choices are incorrect, picking one particular set of invalid colorings is an arbitrary choice. No one is better or worse than the other. By showing a particular one, the designer may be led to believe that the only way to fix the issue with the layout is to increase a single particular space between two specific polygons. This is not true. The one good thing about DP errors like this is that the designer actually has the freedom and flexibility to choose between many different options when fixing the error. There are three minimum spacing errors involved in this layout. Increasing any one of them to the point that they meet the minimum same-mask spacing constraints corrects this design error.

Because of this fact, more useful error markers were developed to help better communicate this information to the designer. Figure 3 shows what is commonly referred to as a ring error marker.

Figure 3: Ring error marker and corresponding possible design fixes.

The ring marker communicates the entire cycle to the designer. The locations where the ring crosses the space between polygons represent the spacing interactions between those two polygons that connect the cycle at that point. The fix options shown in the picture present different spacing changes that would break the cycle and remove the error. Any one of them is equally valid from a coloring standpoint, so designers are free to implement whichever one they prefer or fits their layout the best. This type of error visualization greatly enhances design productivity.

This idea also was extended to visualize issues associated with “anchoring” in DP design. With anchoring, the designer places markers on some polygons representing a preferred coloring of that particular polygon. Paths of interaction between the anchored and unanchored polygons can form situations that cannot be legally colored. These situations are visualized as anchor-path error markers (Figure 4).

Figure 4: DP anchor-path violations.

These innovations in DP error visualization help the designer understand and fix potential decomposition violations without even having to color the layout in the first place. This assistance enabled “colorless” and “partially-colored” tapeout flows, allowing designers to verify that the design could be legally colored, but leaving the actual process of decomposing the layers into two colors to the foundry.

Moving to triple patterning changes the scenario drastically. With TP, you now have the option of three mask colors instead of two. Suddenly, those odd cycle errors may become legal constructs. Figure 5 shows how three colors can be used to color not only simple even and odd cycles, but also many complex combinations of even and odd cycles.

Figure 5: Graph configurations that can be legally decomposed with TP.

So does that mean that any layout construct can be decomposed into three colors? Unfortunately, no. There are still plenty of constructs that cause issues, and they are more complex sets of interactions that cannot be as simply described as they are in DP. The simplest and most common case of shape interactions that cannot be decomposed into three colors involves just four polygons that all interact with each other (Figure 6).

Figure 6: Four-polygon TP error construct.

Because each polygon violates the minimum spacing constraint to the other three polygons, then no matter what color you assign to one polygon, two of the other polygons will be one of the other colors (because there are only three color choices in total). Since the other polygons all have minimum spacing constraints between them, the two with the same color will be in conflict. Figure 7 shows some TP coloring attempts.

Figure 7: TP coloring attempts of a four-polygon TP error with corresponding error markers.

Like DP, showing these spacing violations is one possible way of visualizing the errors associated with TP. However, also like DP, this display suggests to the designer that the fix is limited to a single spacing issue, when the choice of which spacing violation to show is simply arbitrary. There are many possible ways to fix this kind of TP error. However, unlike DP, all the fix options cannot be described by a simple ring marker. So, we developed a specific error output for this kind of error. Figure 8 shows the new error marker for this four-polygon type of error.

Figure 8: Four-polygon error marker.

This error marker shows the four polygons involved and the spacing constraints between them causing the issue. If any one of the spacings indicated in the marker is widened to meet the minimum same-mask spacing requirements, then the error is resolved. The designer has six choices as to which space to increase to resolve this kind of error.
The next most common error type in TP is a “cycle of equivalence” error induced by interconnected “diamond equivalent” constructs. Don’t let the new terminology throw you too much. Let’s start by explaining a diamond equivalent construct and corresponding graph equivalent description (Figure 9).

Figure 9: Diamond equivalent construct.

Diamond equivalents also involve four polygons, but they don’t all interact with each other, meaning a diamond layout is not a coloring error in and of itself. I call it a diamond for obvious reasons—when you look at the graph equivalent, you see it forms two triangle configurations back to back, creating a diamond shape. Let’s call the nodes on the left and right ends the “tips” of the diamond. For this example, I assigned the left tip to color 1. The diamond interactions require that the next two nodes must be different from this tip, and different from each other, so they must be assigned to the other two colors. The right tip must be different from the two middle nodes, so it must be assigned to color 1. Because this diamond configuration requires the two tips to be the same color, we call it a “diamond equivalent” construct. It doesn’t matter which color you assign to the tips, but they must be the same, and the other nodes in the diamond must be assigned to the other two colors, respectively.

That assertion seems rather insignificant and obvious, until you start seeing multiple minimum spacing interactions with these tips. Let’s look at a minor change to this layout in Figure 10, called a diamond equivalent loop.

Figure 10: Simple diamond equivalent loop construct.

Now the two tips have an additional minimum spacing constraint between them, requiring them to be different colors. However, they can’t be different colors, because of the diamond equivalence construct, so this geometry cannot be legally colored. This diamond equivalent loop, in which the two tips interact with each other, is now equivalent to the four-polygon error type discussed previously. It is just four polygons that all interact with each other. This layout would actually be flagged by the four-polygon error type.

However, this diamond equivalent loop can be extended to any number of polygons, as shown in Figure 11.

Figure 11: Extended diamond equivalent loop construct.

Diamonds can connect to other diamonds to form long chains of diamond equivalences. If the ends of those equivalences ever have a minimum space requirement to each other, then an error condition exists. To display this error to the designer, we developed a specific error format (Figure 12).

Figure 12: Diamond equivalent loop error marker.

This error visualization highlights the polygons that are “forced” to be equivalent. It also displays the diamonds driving the equivalence (shown by the hollow rings) and the spacing interaction between the interacting tips. We like to lovingly refer to this as a “diamond necklace,” in which the tip spacing interaction forms the “clasp” of the necklace. If only I could sell it to a jewelry store!

This same type of equivalence interaction can lead to problems with anchors as well, forming equivalence paths (as opposed to loops), as shown in Figure 13.

Figure 13: Diamond equivalent anchor paths.

In the upper left, the diamonds force equivalent mask assignments on each end, but the user has anchored them to different masks, creating a conflict. In the lower left, the right diamond tip should be pink (due to the pink anchor on the left tip), but it would then be in conflict with the pink anchor on the right polygon. On the right, a more complex situation exists, in which the conflict involves three anchors. If only any two of the anchors were present, then the polygon in the middle could be assigned to the third color, so it wouldn’t conflict with any of the diamond tips. However, with all three anchors forcing constraints on the middle polygon, there is no color left to use.

These are not the only error types that can occur with TP, but they are the most common. By generating error markers that distinguish and help explain the common error types, we hope to enable the designer to more effectively deal with the layout issues that occur. Triple patterning is certainly not a walk in the park, but the challenges can be addressed and made manageable with good software, and partnership between the foundries, designers, and Mentor. Just remember not to feed the tribbles!

In my next blog, I’ll return to DP to clarify a topic that came up in a discussion with a customer. They wanted to know if DP errors needed to be fixed in a particular order. It turns out that there are some important guidelines on that topic that I want to make sure all of you understand. So stay tuned!