Detailed routing becomes the most complicated and runtime consuming stage in the physical design flow as technology nodes advance. Due to the inaccessibility of advanced routing rules and industrial designs, it is hard to conduct detailed routing academic researches using the modern real-world designs. ISPD18 hosts the first detailed routing contest [1] and releases a set of benchmarks synthesized by industrial tools with practical routing rules. ISPD18 contest spurs detailed routing researches and provides students the opportunity to become familiar with the industrial designs and rules. On top of ISPD18 detailed routing contest, we host another detailed routing contest in ISPD19 [2] to consider several advanced routing rules and make the contest problem one step closer to the real-world routing challenges in advanced technology nodes. ISPD19 detailed routing contest encourages participants to use double-cut vias to improve yield and result quality. In addition, in order to drive the development of efficient routing frameworks, the deterministic multithreading feature is encouraged but optional in this contest.

In advanced technology nodes, detailed routing becomes the most complicated and runtime consuming stage. To spur detailed routing research, ISPD 2018 initial detailed routing contest is hosted and it is the first ISPD contest on detailed routing problem. In this contest, the benchmarks synthesized by industrial tool and library are released, which consider the design rules like spacing table, cut spacing, end-of-line spacing, and min-area rules. In addition, the global routing guide is provided associated to each benchmark, and detailed routers are required to honor the routing guides as much as possible meanwhile minimize design-rule-checking (DRC) violations. The biggest benchmark released in this contest has near-millions of nets, so the runtime and memory scalability for detailed routers need to be well addressed. To reduce routers' runtime, the deterministic multithreading framework is encouraged but optional in this contest.

In 10nm technology node, self-aligned double patterning (SADP) and triple patterning lithography (TPL) allow us to achieve minimum wiring pitch of around 45nm. While metal layers can be printed by SADP, via layer manufacturing requires TPL to maintain design rules. SADP-aware detailed routing is proposed to ensure decomposability of metal layer patterns. However, its routing solution does not automatically guarantee TPL decomposable via layers. Vias have an inherently low reliability and via failure causes a great yield loss. Double via insertion (DVI) is an effective means to increase yield by reducing via failures. With the restriction of SADP design rules and consideration of TPL decomposability for via layers, DVI becomes a more challenging problem. In this paper, we consider DVI and via layer TPL manufacturability simultaneously in SADP-aware detailed routing. Both spacer-is-metal and spacer-is-dielectric types of SADP are considered. Furthermore, we tackle the TPL-aware DVI in postrouting stage. Both ILP and high-performance heuristic solutions are proposed. The experimental results demonstrate our router can obtain 100% routability and TPL decomposable via layers with reduced dead via count. Meanwhile, compared with the ILP approach to solve TPL-aware DVI problem, the heuristic approach can achieve similar solution quality and significant speedup.

The significantly increased number of routing design rules at sub-20nm nodes has made pin access one of the most critical challenges in detailed routing. Resolving pin access issues in detailed routing stage may be too late due to the fixed pin locations, especially in the area with high pin density. In placement stage when cell movement is allowed, the consideration of pin access has more flexibility. We propose a refinement stage after detailed placement to improve pin access. To respect the given placement solution, the refinement techniques are restricted to cell flipping, same-row adjacent cell swap, and cell shifting. A cost function is presented to model pin access for each pin-to-pin connection. Based on the cost function, two phases are proposed to improve pin access for all the connections simultaneously. In the first phase, we refine the placement by cell flipping and same-row adjacent cell swap. The problem is solved by dynamic programming row by row. In the second phase, only cell shifting is used, and a linear program is formulated to further refine the placement. Experimental results demonstrate that the proposed detailed placement refinement can improve pin access and reduce unroutable nets by about 33% in the detailed routing stage.

As the technology nodes scale down to sub-22 nm, double patterning lithography has been considered as a practical solution for layout manufacturing. Compared with litho-etch-litho-etch, self-aligned double patterning (SADP) has better overlay control. To have a better SADP layout decomposability of routing patterns, we consider SADP during detailed routing stage. Two major types of SADP processes are considered: 1) spacer-is-dielectric type and 2) spacer-is-metal type. Different from previous works, the idea of color preassignment is adopted for SADP-aware detailed routing. An elegant graph model is proposed to capture both routing and SADP manufacturing cost. They greatly simplify the problem to maintain SADP design rules in detailed routing. We apply a negotiated congestion based rip-up and reroute scheme to achieve better routability while maintaining SADP design rules. Compared with other state-of-the-art academic works, our approach does not produce any side overlay error and no SADP design rules violation is reported. Meanwhile, a better solution in terms of total wirelength, routability, and runtime is achieved.

In 10nm technology node, self-aligned double patterning (SA DP) and triple patterning lithography (TPL) allow us to achieve minimum wiring pitch of around 45nm. While metal layers can be printed by SADP, via layer manufacturing requires TPL to maintain design rules. SADP-aware detailed routing is proposed to ensure decomposability of metal layer patterns. However, its routing solution does not automatically guarantee TPL decomposable via layers. Vias have an inherently low reliability and via failure causes a great yield loss. Double via insertion (DVI) is an effective means to increase yield by reducing via failures. With the restriction of SADP design rules and consideration of TPL decomposability for via layers, DVI becomes a more challenging problem. In this paper, we consider DVI and via layer TPL manufacturability simultaneously in SADP-aware detailed routing. The experimental results demonstrate our router can obtain 100% routability and TPL decomposable via layers with reduced dead via count.

As the technology nodes scale down to 22nm and beyond, Double Patterning Lithography (DPL) has been considered as a practical solution for manufacturing process. Compared with Litho-Etch-Litho-Etch (LELE), Self-Aligned Double Patterning (SADP) has better overlay tolerance. Two types of SADP process are popularly used for the state-of-the-art lithography patterning: Spacer-Is-Dielectric (SID) and Spacer-Is-Metal (SIM). Meanwhile, Self-Aligned Quadruple Patterning (SAQP), as a natural extension of SADP, is expected to be one of the major solutions for future process requirement after the 16nm/14nm technology node. In order to have better decomposability of layout patterns, we consider SIM type SADP/SAQP during detailed routing stage. The idea of color pre-assignment is adopted and a graph model is proposed which greatly simplifies the problem and reduces design rule violation. Then, the negotiated congestion based scheme is applied for detailed routing based on our proposed graph model. Compared with other state-of-art works, our approach does not produce any side overlay error and no design rule violation is reported. Meanwhile, a better solution in terms of total wirelength, via count, routability, and runtime is achieved.

Lithography simulation is an essential technique to guide the design of inverse lithography technology (ILT) masks. To reduce the complexity in modern lithography simulation, a widely used approach is to first rasterize the ILT masks before they are inputted to the simulation tools. Currently, there is no high performance technology to handle the rasterization of all-angle polygons, which are very common in modern ILT masks. Traditional rasterization technology is very expensive in term of runtime and memory usage. In this paper, we propose an efficient rasterization algorithm for all-angle polygons based on a pre-computed lookup table (LUT). We expect that the convolution for a majority of large pixels can be performed in a single lookup table query, which decreases the overall runtime dramatically. The experimental results demonstrate that our proposed algorithm can speed up rasterization process by almost 500x while maintaining small variations in CD. Meanwhile, the time for pre-computing the lookup table and the size of it can be kept within very reasonable limits.

Due to the resolution limitations of optical lithography equipment, 1D gridded layout design is gaining steam. Self-aligned double patterning (SADP) is a mature technology for printing 1D layouts. However, for 20nm and beyond, SADP using a single trim mask becomes insufficient for printing all 1D layouts. A viable solution is to complement SADP with e-beam lithography. In this paper, in order to increase the throughput of printing a 1D layout, we consider the problem of e-beam shot count minimization subject to bounded line end extension constraints. Two different approaches of utilizing the trim mask and e-beam to print a layout are considered. The first approach is under the assumption that the trim mask and e-beam are used for end cutting. The second is under the assumption that the trim mask and e-beam are used to rid of all unnecessary portions. We propose elegant ILP formulations for both approaches. Experimental results show that both ILP formulations can be solved efficiently. The pros and cons of the two approaches for manufacturing 1D layout are discussed.