The Trouble With Triples—Part 1

If you’re a true geek like me, you may remember the Star Trek episode “The Trouble with Tribbles,” about the cute furry little aliens that purr when you pet them. They seemed so nice and friendly on the surface, but in the end, they became an exponentially growing mass of ravenous monsters that almost broke down the ship and consumed the storehouse of grain that was meant to provide humanitarian relief for a planet.

Triple patterning (TP) is, unfortunately, a little like the Tribbles. Those of you currently working on 20nm or 16/14nm designs who have some experience with double patterning (DP) might think to yourself, “We figured out how to use two masks, how hard could three masks be?” Like the Tribble, it looks innocuous from the outside, but potential chaos lies just within. The issue I’ll focus on in this article has to do with the complexity of trying to build an EDA software algorithm for automating the decomposition (coloring) and checking of a layer using TP.
To understand this TP issue, let’s first take another quick look at DP decomposition and checking. We’ve talked about it many times in my past articles, but this time, let’s look at the problem from the perspective of an EDA software algorithm trying to decide how to color a layout.

The first thing any software solution needs is a way to translate the polygons in a layout and the rules for colors into something an algorithm can process. Figure 1 demonstrates the typical approach to this requirement.

Figure 1: Sample translation of a DP layout and design rules into an algorithmic graph.

The first picture shows a layout of polygons on a layer that must be decomposed into two colors. The second picture shows the result of running spacing checks on this set of polygons. The spacing checks are configured based on the DP design rules that define how far polygons must be separated from each other to be allowed to be on the same mask (minimum same mask spacing). Wherever this spacing is violated, you see blue markers. The two polygons creating these spacing violations must be assigned opposite colors to be “DP legal.” The third picture shows how this very specific physical construct is abstracted into a virtual representation (known as a “graph”) that can be processed in an algorithm. The polygons in the layout are represented as “nodes” in the graph. The spacing constraints in the layout are represented as “edges” in the graph. These nodes and edges do not capture any spatial information (coordinates, size, distance, etc.). They only represent how things are “connected” to each other in terms of their requirement to alternate color.

So now that we have a computer representation of the layout and rules, let’s walk through the process of trying to decompose this graph into two colors. Figure 2 gives an example of this process.

Figure 2: Example of automated DP decomposition algorithm.

Let’s begin with the first node in the left graph. It doesn’t matter which node you start with; the results will be essentially the same. Likewise, the choice of which color/mask to assign the initial node is completely arbitrary. There are only two choices. In this example, we chose blue. Since the first node is blue, and there is an edge connected to the second node, then the second node must be green. The edge tells us that it must be a different color than the first node, and the only other choice in DP coloring is green. This process continues through the rest of the nodes until you end up with the final full coloring result in the right picture. You can see that the final two shapes are forced to be blue, but they also have an edge connecting them that requires them to be different colors. This conflict results in an error. Our example algorithm would report that this layout is not legally colorable by highlighting the violated edge (edge connecting two nodes of the same color) in the graph.

Would a different first choice have changed the outcome? If you had made the first node green, then the right-most two nodes would have also been green, and you would have the same issue. If you try to change the top node to green to solve the conflict, you simply move the conflict to between the top node and the one directly down and to the left of it. No level of “backtracking” or “recoloring” will find a legal coloring. The only difference that changing the choice of color on a particular node makes is where the violation edge happens. The point is that no coloring solution exists, and you can know this for sure using a single pass look through the graph.

This layout contained an “odd cycle,” which by definition is not colorable in DP. If a separation edge had not existed between the last two nodes, then the layout would have been legally colorable, and this “algorithm” would have found a legal solution. If we extrapolate from this simple example, you can imagine that the run time for such an approach increases as the number of nodes increases, on the order of

The value of x is essentially 1 for DP, so the computational effort required to solve the DP problem increases linearly with the number of elements involved. This is good news if you want to build an EDA solution for DP, and if you are a designer that wants to run that solution with the hope that it will complete in a reasonable amount of time with a dependable result.
Now let’s move back to TP and look at it in the same way. Let’s take another simple layout and walk through a conceptual “algorithm” attempting to find a coloring solution. Figure 3 shows the example of the virtual mapping of the physical layout and TP rules.

Figure 3: Sample translation of a TP layout and design rules into an algorithmic graph.

So far things look essentially identical to our DP example. The polygons are represented as nodes in a graph, and the spacing constraints that require certain polygons to have different colors are represented as edges in the graph. As with DP, you pick a node and a coloring choice, both of which are essentially arbitrary. The big difference in TP is that, as you move to the next nodes in the graph by tracing each edge, you now have two color options to pick from for a particular node, instead of only two. The specific choice of that next node color is also somewhat arbitrary. Figure 4 demonstrates the difference.

Figure 4: Example of automated TP decomposition algorithm.

In this example, we chose to make the node up and to the right of the first one green, and the node down and to the right to be pink. It would have been equally valid to reverse that assignment. You cannot make them both green or both pink, however, because they have an edge between them. In this case, having three colors is advantageous when compared to DP, in that this first “odd cycle” has a valid coloring solution in TP, where it would not in DP. So far, so good.

We continue on to the next set of nodes in the graph. Moving to the right from the upper green node, the next node can be either pink or blue. We don’t have any reason to choose one over the other, so let’s pick pink. Moving right from the previous lower pink node, we can pick blue or green for the next node. Again, we don’t have any reason to prefer one over the other, so let’s pick blue.
Now, moving from the pink and blue nodes we just colored to the two that are left, we encounter an issue. Because of the blue node, neither of the two remaining nodes can be blue, and because of the pink node, neither of them can be pink. That only leaves green, so let’s make them both green. However, they have an edge connecting them, which makes this color choice invalid and produces a violated edge (as shown in the third picture).

Is this the correct answer? Is this graph truly not colorable with three colors? Immediately, you ask yourself, “What if I had made different color decisions at some of the previous nodes where I had more than one choice?” See, this is the major difference in TP vs DP. Because there are more than two choices for the colors, there are many places along the way in which other choices could have been made. Let’s backtrack a few steps and see what happens if we change our choices (Figure 5).

Figure 5: Alternate coloring choice.

Well, look at that! If we just go back one step on the right, and change the choice of the node farthest to the right from pink to blue, we can recolor the remaining nodes for a TP legal layout. Both pink and blue were perfectly valid choices at the time, given that the previous node on top was green, but without foreknowledge of what would happen, we had no reason to pick one color over the other, and arbitrarily chose pink. Now having replaced pink with blue, the last two remaining nodes can be green and pink. The choice of which one is green and which one is pink is arbitrary, as either works. So it turns out this layout was colorable in three colors, and we simply got the “wrong” answer the first time through.

As you might have picked up on by now, the addition of more color choices means you might have to iterate through many different “trials” of coloring to ensure you make the right final decision about whether a layout is colorable and find a valid coloring. Because of this, the run time of a general-purpose algorithm for such a problem is of the form

Notice that the variable “nodes” has moved from the mantissa to the exponent of the expression. The value of “x” is typically <3, as there are at most three color choices for each node. The obvious problem with this expression is that the run time increases exponentially as the number of polygons in the layout increases. Hold on! “Exponential” is a four-letter word when you start talking about software and run time. Just as Tribbles procreate exponentially when you feed them, so does the run time of general purpose TP algorithms when the design size increases.

Now before you go running for the transporter or looking for a phaser, all is not lost. Although this fact of exponential run time is unavoidable for the “general case” of three coloring, the answer to this nightmare lies in avoiding the “general case.” By intelligently restricting the “types” or “variety” of layout constructs that the designer can draw, you can contain the situation to a level of “complexity” for which a customized software heuristic can be developed that can guarantee the discovery of a valid solution or the identification of a real coloring error in a reasonable run time. It all comes down to partnership.

Fortunately, partnership with our customers is something we excel in at Mentor Graphics. Rest assured that we have not spent the last few years hiding on Ceti Alpha V, crying over the fact that TP is inherently “exponential.” We have been working feverishly (and successfully) with the various foundries to find and agree on design rule and design methodology constraints that will make TP work. As a designer, you can expect to see a few extra constraints on the layouts you are allowed to draw for 10nm technologies, but we have worked hard to make these constraints as minimal as possible, while also making sure an effective EDA solution can be provided for you to check and automatically decompose your layouts into three colors.

As you begin to move to 10 nm, and start having discussions with your foundry partners on the design rules and design methodologies associated with layers that use triple patterning, be open-minded to some of the new constraints you might see, and understand that they are ultimately there for your benefit (and sanity). No one wants to push the button on any EDA tool only to have it run “forever.” We in the EDA industry know this, which is why we have worked so hard to find reasonable constraints that will make it all work. Please partner with us and your foundry as we deploy the practical answers to the not-so-practical problems associated to keeping up with Moore’s law.

We’ll look at some of the other challenges associated with triple patterning in my next blog article. First, though, I have a little problem called the Kobayashi Maru to take care of…

p.s., For all the computer science types in the audience, this issue falls into the general class of “P vs. NP” problems. If you want a more scholarly, detailed, and accurate treatment of the issue, you may want to spend some time researching this topic further. Here is a good place to start: P_versus_NP_problem.

p.p.s., In a recent episode of the new Sherlock Homes TV drama “Elementary,” (titled “Solve For X,” which aired October Oct. 3, 2013), several mathematicians were murdered because they were on the verge of finding an equation that would convert all these “NP” problems into “P” problems, and other mathematicians wanted to steal their ideas. Essentially, the new math equation could remove the “exponential” run time issue of such software problems like TP. Needless to say, such an equation would be worth millions or billions of dollars, but to date, no such equation exists. However, if we find one someday, you will certainly wish you had more Mentor Graphics stock!