Edge Pair-Based Layout Pattern Matching using Space-filling Curve
Qingsheng Qiu, Yuqing Zhang, Wuxin Ge, Chao Wang · 2024
DRC-based layout pattern matching is currently the mainstream method in the industry. However, as process nodes shrink and pattern complexity grows, the runtime of DRC-based layout pattern matching methods has increased significantly. The DRC method relies on weakly constrained one-dimensional rule checks, resulting in numerous potential matching regions. In addition, it is difficult to accurately describe patterns with DRC rules, which leads to a complex matching verification process. To address the above issues, we propose a novel edge pair-based approach that reduces the number of potential matching regions while speeding up the search process. Additionally, we employ a hash method for simplified and effective matching verification. Furthermore, as the hash method relies on spatial indexing, we utilize space-filling curves to accelerate index construction and reduce region query time. Experimental results show that compared to the fastest known pattern matching method, our proposed approach achieves a speedup ranging from 7.5× to 28.3× with 100% accuracy.