Efficient Layout Pattern Matching Based on Augmented Vertex Hashing
Source abstract
Abstract
Pattern matching is a key technique in the physical verification of integrated circuit designs and is widely used in lithographic hotspot detection. Existing pattern-matching algorithms face challenges in effectiveness and robustness, especially when processing complex patterns. We propose a pattern-matching algorithm based on augmented vertex hashing that correctly handles polygons with holes and supports fuzzy matching. For exact matching, our method encodes Manhattan polygons into fixed-length hash values using the augmented vertex representation, enabling fast polygon comparisons. For fuzzy matching, we formulate the problem as a constellation problem over augmented vertices and solve it efficiently using a cache-friendly algorithm based on a Bloom filter. Experiments show that our approach is more than 5× faster than the current state of the art on average.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Network Packet Processing and Optimization · Advancements in Photolithography Techniques · Physical Unclonable Functions (PUFs) and Hardware Security
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Institute of Microelectronics of the Chinese Academy of Sciences, Beijing 100029, China
School of Integrated Circuits, University of Chinese Academy of Sciences, Beijing 100049, China
References (21)
Show source-provided references
1. Simmons, M.C., Kang, J.-H., Kim, Y., Park, J.I., Paek, S.W., and Kim, K. (2011). A state-of-the-art hotspot recognition system for full chip verification with lithographic simulation. Design for Manufacturability Through Design-Process Integration V, SPIE.10.1117/12.881596 ↗
2. Cote, M., and Hurat, P. (2004). Layout printability optimization using a silicon simulation methodology. Proceedings of the International Symposium on Signals, Circuits and Systems (SCS 2003), IEEE.10.1109/ISQED.2004.1283667 ↗
3. Cote, M., and Hurat, P. (2005, January 21–23). Standard cell printability grading and hot spot detection. Proceedings of the Sixth International Symposium on Quality Electronic Design (ISQED’05), San Jose, CA, USA.
4. Schuermeyer, C., Malik, S., and Herrmann, T. (2012, January 17–19). Identifying systematic critical features using silicon diagnosis data. Proceedings of the 2012 SEMI Advanced Semiconductor Manufacturing Conference, Saratoga Springs, NY, USA.10.1109/ASMC.2012.6212858 ↗
5. Ding, D., Wu, X., Ghosh, J., and Pan, D.Z. (2009, January 2–4). Machine learning based lithographic hotspot detection with critical-feature extraction and classification. Proceedings of the 2009 IEEE International Conference on IC Design and Technology, Austin, TX, USA.
6. Ding, D., Torres, A.J., Pikus, F.G., and Pan, D.Z. (2011, January 25–28). High performance lithographic hotspot detection using hierarchically refined machine learning. Proceedings of the 16th Asia and South Pacific Design Automation Conference (ASP-DAC 2011), Yokohama, Japan.10.1109/ASPDAC.2011.5722294 ↗
7. Wu, J., Pikus, F.G., Torres, A.J., and Marek-Sadowska, M. (2011, January 25–28). Rapid layout pattern classification. Proceedings of the 16th Asia and South Pacific Design Automation Conference (ASP-DAC 2011), Yokohama, Japan.
8. A fuzzy pattern matching method based on graph kernel for lithography hotspot detection10.1117/12.2257654 ↗
9. Yao, H., Sinha, S., Chiang, C., Hong, X., and Cai, Y. (2006, January 5–9). Efficient process-hotspot detection using range pattern matching. Proceedings of the 2006 IEEE International Conference on Computer Design, San Jose, CA, USA.10.1109/ICCAD.2006.320026 ↗
10. Fast dual-graph-based hotspot filtering10.1109/TCAD.2008.927765 ↗
11. A novel fast layout encoding method for exact multilayer pattern matching with Prüfer encoding10.1109/TCAD.2014.2364973 ↗
12. Geometric pattern match using edge driven dissected rectangles and vector space10.1109/TCAD.2016.2535908 ↗
13. Yu, Y.-T., Chan, Y.-C., Sinha, S., Jiang, I.H.-R., and Chiang, C. (2012, January 3–7). Accurate process-hotspot detection using critical design rule extraction. Proceedings of the 49th Annual Design Automation Conference (DAC 2012), San Francisco, CA, USA.10.1145/2228360.2228576 ↗
14. Wang, S.-H., Chen, Y.-J., Wang, T.-C., and Chen, O. (2020). An algorithm for rule-based layout pattern matching. Proceedings of the 39th International Conference on Computer-Aided Design (ICCAD ’20), Association for Computing Machinery.10.1145/3400302.3415606 ↗
15. Qiu, Q., Zhang, Y., Ge, W., and Wang, C. (2024). Edge pair-based layout pattern matching using space-filling curve. Proceedings of the 2nd International Symposium on Electronics Design Automation (ISEDA 2024), IEEE.10.1109/ISEDA62518.2024.10617982 ↗
16. A general and accurate pattern search method for various scenarios10.1016/j.vlsi.2024.102281 ↗
17. An r-DFA-Based Layout Pattern Match Method Supporting Fuzzy Matching10.1109/TCAD.2025.3556969 ↗
18. Industrial strength polygon clipping: A novel algorithm with applications in VLSI CAD10.1016/j.cad.2010.06.008 ↗
19. Cardoze, D.E., and Schulman, L.J. (1998). Pattern matching for spatial point sets. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), IEEE.10.1109/SFCS.1998.743439 ↗
20. In-Memory database query10.1002/aisy.202000141 ↗
21. Zavalloni, F., Antolini, A., Lico, A., Franchi Scarselli, E., Torres, M.L., Zurla, R., and Pasotti, M. (2023). A Binary Pattern Matching Task Performed in an ePCM-Based Analog In-Memory Computing Unit. Annual Meeting of the Italian Electronics Society, Springer Nature.10.1007/978-3-031-48711-8_1 ↗