Increasing transistor densities, smaller feature sizes, and the aggressive use of RET techniques with each successive process generation have collectively presented new challenges for current fracture tools, which are at the heart of layout data preparation. One main challenge is to reduce the number of small dimension trapezoids (slivers) to improve mask yield since the sliver count reflects the risk of mask critical-dimension errors.
Some commercial tools are available for handling the sliver minimization problem in fracture, such as CATS from Synopsys and Fracturem from Mentor Graphics. However, the number of slivers in the existing fracture solutions can be significantly reduced. The integer linear programming (ILP) method has been previously applied to find the optimal fracture but has not explored potential benefits from additional ray-segments. Unfortunately, the ILP becomes prohibitively slow for polygons with the large number of vertices and heuristic partitioning of large polygons may severely degrade the solution quality.
In this paper, we propose a new ray-segment selection heuristic which can find a near-optimal fracture solution in practical time while being flexible enough to take into account all specified requirements. We fist divide the rectilinear region with all rays from the concave points and formulate the fracture problem as a sequential ray-segment selection problem. Each ray segment is assigned a weight based on its probability to form a sliver. All ray segments to be selected are placed in a candidate pool. An iterative "gain" based process is used for fast and efficient selecting ray segments from the candidate pool and dynamic update of ray segments and their gains. Further reduction of the number of slivers is achieved by auxiliary ray-segments. The resulted runtime overhead is reduced by a rule-based auxiliary ray-segments addition method which achieves a tradeoff between the sliver number reduction and runtime overhead. Compared with state-of-art sliver-driven fracturing tools, the proposed method reduces the number of slivers in the fractures of two industry testcases by 76.7% and 58.6%, respectively, without inflating the runtime and shot count. Similarly, compared with the previous ILP based fracture methods, the new method reduces the number of slivers by 56.1% and 2.2%, respectively, with more than 60X speedup and insignificant shot count overhead. The reduction in the sliver number is primarily due to the introduction of additional ray-segments. The proposed method can also solve the reverse-tone fracture problem in practical time for large industry testcases.