Multiple Patterning Layout Decomposition for Ease of Conflict Removal

A mechanism is provided for multiple patterning lithography with conflict removal aware coloring. The mechanism makes multiple patterning coloring aware of the conflict removal overhead. The coloring solution explicitly considers ease of conflict removal as one of the coloring objectives. The mechanism pre-computes how much shapes can move in each direction. The mechanism generates a conflict graph where nodes represent shapes in the layout and edges represent conflicts between shapes. The mechanism assigns weights to edges based on available spatial slack between conflicting features. The mechanism then uses the weights to guide multiple patterning coloring. The mechanism prioritizes conflicting features with higher weights to be assigned different colors.