feature article
Subscribe Now

Keeping Us in Stitches. Or Out.

Or, Everything I Needed To Know About Double-Patterning I Learned In Kindergarten

Chopping wood may be character building, but it takes time. Each chop takes a bit more of the wood away until you finally break through. When you’ve got a lot of wood to chop, getting it done faster is a good thing, so you increase your pace. But even the burliest lumberjack can go only so fast; if you want to go faster, you get two lumberjacks, one on each side, and have them interleave chops.

Moving from the time domain into the space domain, double-patterning has the same role for getting around pesky resolution limits when trying to expose small features. If things are too close together to resolve, you break them apart more or less into even and odd features and expose the even ones on one mask and the odd ones on the other. In theory, each mask will have double the spacing, making resolution easier, and, assuming your alignment is good when applying the second mask, you end up cheating the limits. Simple. In theory.

The hard part is figuring out the “even” and “odd” parts, since it’s never quite so simple. One approach is to use two different metal layers for horizontal and vertical features, but this approach doesn’t seem to have been widely adopted. Instead, efforts are focused on figuring out how to separate the features on a layer into two groups, one set interleaved between the other set. You’d think this should be easy. You’d be wrong.

Remember all those times when you did coloring in school? Well, even though it may have been intended as a way to keep you busy (and, these days, some middle schools even have things like coloring and word search simply so they can meet parents’ unceasing demands for ever more homework to ensure that their little Einstein will be the first CEO on the block), it may have had relevance in unexpected ways. Similarly if you were a geography buff.

Just in case you thought coloring was only for the idle, it has actually occupied the minds of some rather accomplished mathematicians. As if there were nothing better to do, they’ve tried to figure out how many colors it takes to color a map so that no two bordering countries have the same color. (If they come together at a point, like at Four Corners, that doesn’t count.) Lest you, like I, think that the number of colors required is a function of the tendencies of geographic maps only, it turns out that this also applies to any arbitrary “map” or graph where you have shapes that are to be colored so that no two identically-colored elements touch (except perhaps at a point). In the mid-1800s it was posited that you could do this with only four colors. And it took until 1976 for it to be proved.

In discussions of double patterning, this coloring concept is used to describe the process of splitting a single layer into two. Except that here you are allowed only two colors: shapes are “colored,” and those of one color end up on one mask, and those of the other on the other mask. And you have to be able to do the coloring in a way that doesn’t violate any spacing rules. And that’s the catch.

So… to illustrate this, we’re going to use a traditional didactic tactic and have you do some coloring. So get out your paper and two colors – you get to choose whichever colors you like (just to show that we don’t condone completely tyrannical teaching techniques).

First, draw a big capital T – wait – not yet: do it such that the vertical line doesn’t quite touch the capping horizontal line. OK, go. That gap is critical – let’s assume that gap meets the spacing requirements of a layer that will be double-exposed but is too small to expose on a single mask. That means that the vertical line will have to be on one mask and the horizontal on another. So they need to be different colors. So go ahead and color them differently. There, that looks great.

Now, we’re going to do the same thing again, only this time with two verticals very close together – kind of like a letter ∏ but with the verticals close in the middle. So close that they have to be different colors. Also, both lines have gaps between them and the horizontal, just like we had with the T. Now… go ahead and color them in a way that has everything on either side of a gap as a different color.

Not so easy, eh? As it is, it can’t be done. The two verticals need to be different colors because they’re close together. But the horizontal is also too close to both of the verticals and has to be a different color from both of them – which isn’t possible if you have only two colors.

This is where “stitches” come in. A stitch is a place where a single feature is divided into two and “stitched” back together into one. In our example, the horizontal line is split down the middle, and the left side of the horizontal is colored to be opposite of the left vertical, and the right side of the horizontal is colored to be opposite of the right vertical, which is opposite of the left vertical, so it all works out.

The challenge is that you’ve now got these two horizontal pieces that need to become one again when printed; you’ve now introduced a new yield loss mechanism. If they don’t overlap enough, you might end up with the two not connecting on some dice or some wafers or some lots. If they overlap too much, well, I’m not sure, but you’d have a pile of metal at the join point – and you might end up violating the very spacing you were trying to fix.

In fact, if the two vertical lines are close enough to each other and to the horizontal, then, depending on the spacing rules, it might even be that the left end of the right horizontal half is still too close to the top of the left vertical. (Are you with me here? Keep up!) In which case the problem can’t be solved at all – you either have to move things around or resort to two metal layers.

If this weren’t enough, you also get situations where stitches propagate like sutured rabbits. To see this, let’s take our example one step further: we’re going to add a second horizontal line close above the first one. But – don’t do it yet. Start by drawing two horizontal lines close together. Then color them. Trivially easy. Now add the two verticals (plus small gaps) below the bottom horizontal, just like we had before. Now you have to place a stitch in the bottom horizontal, as we just saw. But now the top horizontal is colored correctly only for half the distance – it too has to be stitched where the bottom horizontal was stitched so that it flips colors when the bottom one does.

What this has created is a general problem to be solved: how do you color a layer such that you minimize the number of stitches (as well as unresolvable conflicts)? It’s a linear programming problem that’s being worked in university settings, with algorithms being proposed to solve the problem in the context of other real-world situations like process migration. Papers dealing with variations on this theme were presented at the last ICCAD by National Taiwan University, Iowa State University, and UC San Diego. Some University of Texas work is also available on the web. It’s still a ways from working its way into your favorite CAD tool.

So if you were expecting easy answers here, sorry, I hate to disappoint. But the good news is, if you’re feeling bored or overwhelmed and need a way to release some steam, try doing some coloring. If anyone challenges you, just tell them you’re doing some advanced double-patterning research.

Leave a Reply

featured blogs
May 30, 2023
Explore our 2022 environmental, social, and governance (ESG) report to explore our sustainable business practices and our progress in building a smart future. The post Synopsys 2022 ESG Report: Building a Smart Future Together appeared first on New Horizons for Chip Design....
May 25, 2023
Register only once to get access to all Cadence on-demand webinars. Unstructured meshing can be automated for much of the mesh generation process, saving significant engineering time and cost. However, controlling numerical errors resulting from the discrete mesh requires ada...
May 8, 2023
If you are planning on traveling to Turkey in the not-so-distant future, then I have a favor to ask....

featured video

Synopsys Solution for RTL to Signoff Power Analysis

Sponsored by Synopsys

Synopsys’ industry-leading power analysis solution built on PrimePower technology that enables early RTL exploration, low power implementation and power signoff for design of energy-efficient SoCs.

Learn more about Synopsys’ Energy-Efficient SoCs Solutions

featured contest

Join the AI Generated Open-Source Silicon Design Challenge

Sponsored by Efabless

Get your AI-generated design manufactured ($9,750 value)! Enter the E-fabless open-source silicon design challenge. Use generative AI to create Verilog from natural language prompts, then implement your design using the Efabless chipIgnite platform - including an SoC template (Caravel) providing rapid chip-level integration, and an open-source RTL-to-GDS digital design flow (OpenLane). The winner gets their design manufactured by eFabless. Hurry, though - deadline is June 2!

Click here to enter!

featured chalk talk

Enable Sustainable Enterprises of the Future
Did you know that buildings are responsible for 40% of global energy consumption and 33% of greenhouse gas emissions? One way we can help both modernize and increase sustainability in our buildings is by adding 10BASE-T1L to our building controllers. In this episode of Chalk Talk, Amelia Dalton chats with Salem Gharbi from Analog Devices about how we can enable sustainable enterprises with ethernet connected building controllers. They examine the10BASE-T1L flexible design solutions that Analog Devices offers, how exiting?building infrastructure can take advantage of 10BASE-T1L and how you can get started on your next sustainable enterprise journey.
Dec 20, 2022
21,044 views