Multi-Patterning and Coloring Checks

Below roughly 20nm, a single lithography exposure can no longer resolve the tight pitch of the lowest metal and via layers. The wavelength of the light (193nm) is far larger than the features, so two shapes too close together blur into one. Multi-patterning splits a single drawn layer across two or more masks so that each mask alone has a relaxed, printable pitch.

Decomposition and coloring

Litho-etch-litho-etch (LELE) double patterning assigns every polygon on the layer to one of two masks, traditionally drawn as two colors. The rule is simple to state: any two shapes closer than the single-mask minimum spacing must be on different masks (different colors). The tool that assigns these colors is the decomposer, and the verification that a legal assignment exists is the coloring check.

The odd-cycle conflict

Model each polygon as a node and draw an edge between any two nodes that are too close to share a mask. A legal two-coloring exists only if this conflict graph has no odd-length cycle. Three shapes mutually too close to each other form a triangle, an odd cycle, and cannot be split across two masks. This unresolvable loop is the classic native conflict, and the decomposer reports it back to the designer as a coloring error.

Stitches and anchored coloring

A long wire can sometimes be split mid-shape so its two halves go on different masks, joined by an overlapping stitch. Stitches relax coloring but add yield risk: any mask-to-mask misalignment at the stitch becomes a resistance bump or an open. Some flows also let designers pre-color critical shapes (anchored coloring) so a matched pair, for example a differential route, lands on the same mask and shares the same process variation.

# Conceptual decomposition / coloring check (pseudo-code, not a real deck)
# A real flow uses a foundry double-patterning deck (e.g. Calibre nmDRC
# with multi-patterning operations); the logic below is what it enforces.

# 1. Decompose drawn metal1 into two masks (two colors)
mask_a, mask_b = decompose(metal1)

# 2. Each mask alone must meet the relaxed single-mask spacing
viol_a = spacing(mask_a, mask_a) < 0.040   # same-color shapes too close
viol_b = spacing(mask_b, mask_b) < 0.040

# 3. Any polygon the decomposer could not legally color = native conflict
uncolored = metal1 - (mask_a + mask_b)     # leftover = odd-cycle error