PaperlayerView exact revision on arXiv

Source-linked AI summary

Layout decomposition for triple patterning lithography

Bei Yu, Kun Yuan, Boyang Zhang, Duo Ding, David Z. Pan

arXiv:1402.2459v1cs.AR

TL;DR

TPL layout decomposition is an underexplored extension of DPL for further pitch scaling, but the three-mask problem is more difficult. The paper introduces an exact ILP formulation with scalability techniques and an SDP approximation for dense layouts. These methods provide scalable decomposition while exposing tradeoffs between runtime, stitches, and conflicts.

  • Problem

    TPL layout decomposition has received very little study for general layouts, while prior approaches have restrictions involving layout type, stitch minimization, or stitch insertion.

  • Method

    The paper combines an ILP formulation minimizing conflict and stitch numbers with three acceleration techniques and a vector-programming formulation solved by SDP approximation.

  • Results

    The proposed methods achieve promising quality-runtime tradeoffs across exact accelerated ILP and SDP-based decomposition approaches.

  • Takeaways & Limitations

    Accelerated ILP preserves optimality, while SDP extends practical scalability to very dense layouts with a stitch-conflict tradeoff.

  • Takeaways & Limitations

    Layout modification used by some prior approaches may create timing-closure and hotspot problems.

Abstract

from arXiv · show

As minimum feature size and pitch spacing further decrease, triple patterning lithography (TPL) is a possible 193nm extension along the paradigm of double patterning lithography (DPL). However, there is very little study on TPL layout decomposition. In this paper, we show that TPL layout decomposition is a more difficult problem than that for DPL. We then propose a general integer linear programming formulation for TPL layout decomposition which can simultaneously minimize conflict and stitch numbers. Since ILP has very poor scalability, we propose three acceleration techniques without sacrificing solution quality: independent component computation, layout graph simplification, and bridge computation. For very dense layouts, even with these speedup techniques, ILP formulation may still be too slow. Therefore, we propose a novel vector programming formulation for TPL decomposition, and solve it through effective semidefinite programming (SDP) approximation. Experimental results show that the ILP with acceleration techniques can reduce 82% runtime compared to the baseline ILP. Using SDP based algorithm, the runtime can be further reduced by 42% with some tradeoff in the stitch number (reduced by 7%) and the conflict (9% more). However, for very dense layouts, SDP based algorithm can achieve 140x speed-up even compared with accelerated ILP.

1. INTRODUCTION

TPL extends DPL to support further pitch scaling, but its layout decomposition is more difficult and has received little study. The paper develops exact ILP and scalable SDP-based approaches for general TPL layouts.

  • TPL extends DPL by decomposing layouts across three masks, enabling further feature-size scaling through pitch-tripling.
  • DPL can contain native three-way conflict cycles that remain unresolved even after stitch insertion, whereas TPL can resolve them.
  • General TPL decomposition research is limited, with prior methods restricted to contact arrays, lacking stitch minimization, or disallowing stitches.
  • The paper formulates TPL decomposition as an ILP that simultaneously minimizes conflict and stitch numbers.
  • Three acceleration techniques improve ILP scalability without sacrificing solution quality, while vector programming with SDP targets very dense layouts.
  • The experiments report promising quality-runtime tradeoffs for the proposed decomposition methods.

2. PROBLEM FORMULATION AND COMPLEXITY

The paper models TPL decomposition with layout and decomposition graphs, then establishes its computational difficulty. The resulting problem assigns decomposition-graph nodes to three masks while minimizing conflicts and stitches.

  • A. Problem Formulation: TPL problem formulation begins with a layout specified by polygonal features and constructs layout and decomposition graphs.
  • A. Problem Formulation: A layout graph contains one node per polygonal shape and a conflict edge exactly when two shapes lie within minimum coloring distance.
  • A. Problem Formulation: A decomposition graph uses nodes associated with polygonal shapes and separates conflict edges from stitch edges.
  • A. Problem Formulation: Node projection identifies legal splitting locations before the decomposition graph is constructed with conflict and stitch edges.
  • A. Problem Formulation: The decomposition objective assigns every decomposition-graph node to one of three masks while minimizing stitch and conflict numbers.
  • B. Problem Complexity: TPL decomposition is more complicated than ordinary graph coloring because stitch edges are introduced into the optimization problem.
  • B. Problem Complexity: Planar 3-colorability is NP-complete, so checking whether a layout graph is 3-colorable cannot generally be done in polynomial time.
  • B. Problem Complexity: The paper concludes that TPL layout decomposition is NP-hard, using a reduction from the 3-Coloring problem.

3. BASIC ALGORITHM

The basic TPL decomposition algorithm uses ILP to assign masks while jointly minimizing conflicts and stitches. Its objective includes a user-defined weighting between these two quantities.

  • ILP provides the basic algorithm for TPL layout decomposition and motivates three techniques that divide the problem into smaller instances.
  • The formulation minimizes conflict and stitch numbers simultaneously through a weighted objective.
  • α is a user-defined parameter controlling the relative importance of conflict and stitch numbers.
  • Conflict evaluation concerns touching rectangles assigned different colors, while stitches are introduced when connected nodes receive the same color.

B. ILP Formulation for TPL Layout Decomposition

The ILP formulation represents each of TPL’s three colors with two binary variables while forbidding one binary pair. Auxiliary variables encode conflicts and stitches in linear constraints.

  • Three colors are represented using two 0-1 variables per node, with the pair (1, 1) forbidden.
  • The allowed binary pairs are (0, 0), (0, 1), and (1, 0), thereby limiting each node to three colors.
  • Constraints (2b)–(2f) encode conflict indicators that become true when conflict-edge endpoints receive the same color.
  • Constraints (2g)–(2k) encode stitch indicators, which become true when either binary color component differs.

C. Acceleration Techniques

The acceleration pipeline decomposes the graph, simplifies low-degree nodes, and uses stack-based recovery to reduce ILP size while preserving optimality when applicable.

  • The acceleration flow consists of independent component computation, layout graph simplification, and bridges computation.
  • Independent Component Computation: Independent component computation solves isolated decomposition-graph components separately and unions their solutions without affecting global optimality.
  • Layout Graph Simplification: The algorithm constructs the decomposition graph for unsimplified nodes, then pops stored nodes and assigns each a legal color.
  • Layout Graph Simplification: Layout graph simplification repeatedly removes nodes with degree no more than two and temporarily stores them on a stack.
  • Layout Graph Simplification: When every node can be pushed onto the stack, layout graph simplification solves TPL decomposition optimally in linear time.

3) Bridges Computation:

Bridge computation partitions suitable decomposition graphs into smaller ILPs. Color rotation reconnects the independently solved subgraphs without introducing new stitches, and the accelerated ILP retains optimality.

  • Removing a bridge that separates independent components divides one ILP into two independent ILP formulations.
  • Partitioning the decomposition graph by removing bridges does not introduce new stitches.
  • After separate color assignments, rotating all colors in one subgraph can make bridge endpoints compatible.
  • The bridge-finding procedure uses an O(|V| + |E|) algorithm.
  • The three acceleration techniques preserve optimal solutions, although ILP may remain too slow for large layouts that resist simplification.

A. Vector Programming for TPL Layout Decomposition

The vector program represents each TPL layout node with a unit vector, using vector relationships to distinguish conflict edges from stitch edges and encode three masks.

  • Each TPL node receives a unit vector, with conflict-edge endpoints encouraged to be far apart and stitch-edge endpoints encouraged to coincide.The formulation uses vector geometry to encode mask-assignment preferences.
  • Three mask colors correspond to three unit vectors whose same-color angle is 0 and different-color angle is 2π/3.
  • The inner product of two m-dimensional vectors is defined from their corresponding coordinates.
  • The resulting vector program formulates TPL layout decomposition from the inner-product property.
  • The vector program is NP-hard because TPL decomposition is NP-hard, motivating its relaxation to semidefinite programming.

B. Semidefinite Programming Approximation

The paper relaxes the discrete vector program into a continuous semidefinite program and establishes equivalence between the SDP and vector formulations, enabling polynomial-time solution methods.

  • Removing the discrete constraint produces a relaxed formulation whose optimal value is no greater than that of the original vector program.The relaxation is an approximation because feasible vector solutions remain feasible after embedding them in a higher-dimensional space.
  • The relaxed programs are no longer NP-hard, and the paper recasts them as semidefinite programs solvable in polynomial time.SDP uses a linear objective and constraints on a square symmetric positive semidefinite matrix.
  • An SDP solution is represented by a positive semidefinite matrix X rather than a list of vectors.
  • A symmetric matrix X is positive semidefinite exactly when it can be factored as X = V V^T.Cholesky decomposition can recover V from X in O(n^3) time.
  • The semidefinite program (6) and vector program (5) are equivalent through the Gram-matrix construction and matrix factorization.

C. Mapping Algorithm

The mapping algorithm converts continuous SDP relationships into three discrete masks by sorting pairwise matrix entries and applying union/separation operations under compatibility constraints.

  • The algorithm maps continuous SDP solutions into discrete assignments of nodes to three masks.
  • Matrix entries near 1 indicate that two nodes should share a mask, whereas entries near −0.5 indicate different-mask tendencies.
  • Disjoint-set operations group nodes while compatibility checks control unions and separation thresholds control distinct-mask assignments.
  • The mapping algorithm has complexity O(n^2 log n), dominated by sorting n^2 triplets.
  • The procedure labels and sorts all nonzero Xij entries as triplets before iterative union and separation steps.
  • If more than three masks remain, the algorithm repeatedly unions a compatible pair with maximum Xij.

D. An Example of the SDP Based Algorithm

The example applies SDP and the mapping algorithm to a decomposition graph, using matrix relationships to assign seven nodes into three masks despite an odd cycle that prevents two-coloring.

  • The example graph contains 7 conflict edges and 1 stitch edge, is 3-colorable, and is not 2-colorable because it contains odd cycles.
  • Figure 8 contrasts the input decomposition graph with its assignment into 3 different colors using SDP and Algorithm 2.
  • With α = 0.1, the SDP produces a matrix X whose entries encode relationships among nodes.
  • Entries X14 = 1.0 and X35 = 1.0 indicate that nodes 1 and 4, and nodes 3 and 5, should share colors.
  • Because X12, X13, and X15 are near −0.5, nodes 2, 3, and 5 cannot share node 1’s color, yielding masks {1, 4}, {2}, and {3, 5}.

5. EXPERIMENTAL RESULTS

Experiments evaluate the implementations, benchmark setup, accelerated ILP, and SDP-based decomposition on standard and very dense layouts. Acceleration preserves ILP solution quality, while SDP improves runtime with quantified tradeoffs in stitches and conflicts.

  • Experimental setup: The evaluation uses C++ implementations with CBC for ILP and CSDP for semidefinite programming on an Intel Core 3.0GHz Linux machine with 32G RAM.OpenAccess2.2 interfaces directly with GDSII.
  • Experimental setup: ISCAS-85 & 89 benchmarks are modified for 16nm technology using the metal one layer, with 25nm minimum width and 30nm spacing.The minimum colorable distance is 85nm, the stitch-overlap margin is 10nm, and α is 0.1.
  • Acceleration results: The Accelerated ILP reaches the same conflict and stitch results as Normal ILP in around 18% of the runtime.The accelerated version uses all three techniques, while Normal ILP uses only independent component computation; the formulations achieve optimal solutions.
  • Acceleration results: The accelerated graph representation reduces stitch edge number by 90% and conflict edge number by 93%.These reductions result from layout graph simplification and bridges computation.
  • SDP comparison: The SDP-based method reduces runtime by 42% and stitch number by 7%, with 9% more conflicts than Accelerated ILP.Both methods use the same decomposition graph, so their stitch and conflict edge numbers are equal.
  • Very dense layouts: On very dense layouts, SDP achieves 140× speed-up versus Speed-up ILP, reducing stitch number by 10% while introducing 5% more conflicts.The larger speed advantage occurs because dense subproblems contain more nodes, where SDP is much faster than ILP.
Loading 1402.2459v1…