An r-DFA-Based Layout Pattern Match Method Supporting Fuzzy Matching

As chip manufacturing approaches physical limits, the probability of defects due to specific chip layout structures has significantly increased. These defect-prone structures are known as lithographic hotspots. Pattern matching method is widely used in hotspot detection algorithms due to its efficiency and accuracy. However, traditional pattern matching algorithms face major challenges in both solution efficiency and flexibility for fuzzy matching. To overcome these limitations, an integer range-based deterministic finite automaton (r-DFA)-based layout pattern matching method supporting parallelization and fuzzy matching is proposed. Manhattan polygons in the layout are represented as multiple path strings, thereby transforming the pattern matching problem into a string regular expression search problem. To simplifies the construction of large integer range elements in fuzzy matching, the r-DFA is employed, enhancing construction efficiency and enabling the algorithm to achieve linear time complexity. Moreover, this approach focuses most of the matching process within each individual layout polygon, enabling parallelized matching across diverse layout polygons. Compared to the state-of-the-art, our approach supports fuzzy matching, and shows an average efficiency improvement of 1.23 times.