Consider Timing Critical Path Of Double After Wiring Pattern Photoresist Layer Allocation Algorithm Research

In the past more than half a century, integrated circuit (IC), as a key cornerstone of the third industrial revolution, has improved on both integration and process node as Moore’s law predicted. It still keeps this trend in the21st century because of the constant efforts from researchers. However, the improving speed has been slowed down since the feature size increasingly approaches the physical limits. One of the major signs is the edge resolution of photoresist begins to blur since45nm process node. In order to break through this bottleneck in lithography, extreme ultra-violet exposing light source, high refractive index liquid immersion lithography and double patterning lithography have been invented as the new advance in IC manufacturing process. Correspondingly, double patterning decomposition is the new revolution in design methodology. As long as the design methodology is now transferring to the third generation of DFM-centric (design for manufacturability), it attracts a lot of attentions to improve the double patterning decomposition quality.In double patterning lithography, the layout patterns are divided into two groups and then exposed sequentially. It makes the adjacent patterns onto different masks to reduce the light interference effect between adjacent mask windows, which also increases the density of the exposed layout patterns. The problem that double patterning decomposition focuses on is how to minimize the number of unresolvable double patterning conflicts and stitches by layout pattern slicing and mask distribution. The existing work on double patterning usually focuses on pre-manufacturing well designed layouts. They utilize greedy method, odd cycle elimination, max-cut or other optimization methods to achieve double patterning decomposition. Although all of these methods are heuristics, and double patterning decomposition problem is usually estimated as NP-complete problem, none of the previous work has proved its NP-completeness.On the other hand, post-routing layer assignment in current multi-layer interconnection process, which determines the layout features on each layer, thus having great impact on double patterning decomposition, has not been explored in the merit of double patterning. If it could serve the optimization of double patterning decomposition problem, it is possible to achieve better solutions.In this paper, we formulate post-routing layer assignment for double patterning problem for the first time. Both this problem and traditional single layer double patterning decomposition problem are proved to be NP-complete. An effective algorithm is further proposed to solve it. The algorithm consists of three major phases: multi-layer assignment to minimize double patterning risks, single layer double patterning, and via reduction. Since blind post-routing layer assignment may jeopardize timing critical paths obtained in the routing stage, our algorithm also considers total wire length and coupling capacitance on critical paths as timing metrics. Some numerical experiments are also given in this dissertation to demonstrate all these merits of these proposed algorithms.