Parallel strategies for nonlinear mask optimization in semiconductor lithography

We develop a parallel branch-and-bound method for a nonconvex optimization problem arising in semiconductor lithography. After describing the lithography printing problem and its physical background, we motivate the posing of the optimization problem as a search over the surface of a sphere in high dimension. Previous work on this problem and similar challenges is surveyed. We explore several naive methods for parallel optimization as well as a mixed-integer quadratic program. As an original contribution, we develop a serial branch-and-bound implementation that achieves five orders of magnitude performance improvement over commercial solvers. We then describe an implementation of a parallel branch-and-bound method using novel bounding and branching strategies and provide computational results on the IBM BlueGene/P supercomputer architecture, showing strong scaling to 80% efficiency on up to 4096 processors.