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
Mar 18, 2024
If you've already seen Vivarium, or if you watch it as a result of reading this blog, I'd love to hear what you think about it....
Mar 18, 2024
Innovation in the AI and supercomputing domains is proceeding at a rapid pace, with each new advancement heralding a future more tightly interwoven with the threads of intelligence and computation. Cadence, with the release of its Millennium Platform, co-optimized with NVIDIA...
Mar 18, 2024
Cloud-based EDA tools are critical to accelerating AI chip design and verification; see how NeuReality leveraged cloud-based chip emulation for their 7NR1 NAPU.The post NeuReality Accelerates 7nm AI Chip Tape-Out with Cloud-Based Emulation appeared first on Chip Design....

featured video

We are Altera. We are for the innovators.

Sponsored by Intel

Today we embark on an exciting journey as we transition to Altera, an Intel Company. In a world of endless opportunities and challenges, we are here to provide the flexibility needed by our ecosystem of customers and partners to pioneer and accelerate innovation. As we leap into the future, we are committed to providing easy-to-design and deploy leadership programmable solutions to innovators to unlock extraordinary possibilities for everyone on the planet.

To learn more about Altera visit: http://intel.com/altera

featured paper

Reduce 3D IC design complexity with early package assembly verification

Sponsored by Siemens Digital Industries Software

Uncover the unique challenges, along with the latest Calibre verification solutions, for 3D IC design in this new technical paper. As 2.5D and 3D ICs redefine the possibilities of semiconductor design, discover how Siemens is leading the way in verifying complex multi-dimensional systems, while shifting verification left to do so earlier in the design process.

Click here to read more

featured chalk talk

Power Gridlock
The power grid is struggling to meet the growing demands of our electrifying world. In this episode of Chalk Talk, Amelia Dalton and Jake Michels from YAGEO Group discuss the challenges affecting our power grids today, the solutions to help solve these issues and why passive components will be the heroes of grid modernization.
Nov 28, 2023
15,317 views