Design Rule Checking by Plane Sweep

The idea

A foundry's rules are geometric: the minimum width of a shape, the minimum spacing between shapes, the minimum enclosure of a via by the metal around it, the minimum area, and many conditional variants, such as a spacing that grows with the width of the wires and the length they run side by side. Many rules are written as operations on layers (grow, shrink, intersect, subtract) followed by a measurement.

Checking them means measuring distances between edges. Comparing every pair of shapes is quadratic, hopeless for billions of shapes. The standard remedy is a plane sweep. Sort all edges by coordinate and move a scanline across the layout, keeping only the shapes that currently cross a band around the line. A width or spacing check compares an edge only with its neighbors in that active set, so the work grows with the number of shapes times the local density instead of with the square of the count. Bentley and Ottmann's 1979 sweep for reporting geometric intersections is the classic form of the method, and Baird's work on fast layout artwork analysis (1977) brought such techniques to integrated circuit layout.

Watch it work: a sweep line and its active set

Eight shapes on one metal layer and two rules. The walkthrough sweeps a line across the layout, compares each new shape only with the shapes still near the line, and finds every violation with a fraction of the comparisons that checking every pair needs.

The fine print

A modern process has thousands of rules, many of them conditional, so the rule deck is itself a program. Hierarchical checking, which checks each cell once and then only the places where instances meet, is what makes full-chip runs feasible. Rule decks are written in tool-specific languages and are usually the foundry's intellectual property.

Where you meet it today

KLayout and Magic run open rule decks; OpenROAD's detailed router checks and repairs its own routing rules as it works; and the finishing walkthrough on this site runs the deck on every polygon before tapeout.