Novel algorithms for placement of rectangular covers for mask inspection in advanced lithography and other VLSI design applications

The continuous drive of very large scale integrated (VLSI) chip manufacturers to meet Moore's law has spurred the development of novel resolution enhancement techniques (RETs) and optical proximity correction (OPC) methodologies in optical microlithography. These RET and OPC methods have increased the complexity of mask-manufacturing manifold and have, at the same time, put added emphasis on the mask inspection procedure. A technique to simplify mask inspection is to identify rectangular regions on the mask that do not require inspection. Such a region is referred to as a do not inspect region (DNIR). A novel and practical algorithm to place DNIR rectangles on the mask is presented. It is shown that the most general DNIR placement problem is at least NP-Hard (Garey and Johnson, 1979). However, under certain relaxed criteria, there exists a polynomial-time algorithm for DNIR placement using dynamic programming. However, the optimal algorithm has very-high-degree polynomial bounds on its runtime and space complexities. On the other hand, a very simple greedy algorithm extended by lookahead and randomization, or by simulated annealing, can greatly improve the performance of the DNIR placement and produce near-optimal results. Although the algorithm developed in this work is targeted primarily toward DNIR placement, it has many other VLSI design applications.