Polygon reconstruction is widely used across various fields. Although the current polygon reconstruction algorithms have achieved near-linear time complexity, they still fail to meet the speed demands imposed by the exponential growth in polygon numbers. The development of GPU technology provides a promising solution to this issue. This paper proposes a GPU-based algorithm that leverages hash tables and memory pools to transform the polygon reconstruction problem into an efficiently parallelizable task. Experimental results on Nvidia RTX 2080Ti demonstrate that the new algorithm achieves 17× and 46× speedups on Manhattan and non-Manhattan polygon test sets, respectively. Compared to traditional CPU algorithms, the new algorithm significantly improves processing speeds, especially when handling layouts with complex polygons. It demonstrates strong scalability and performance advantages, providing crucial support for enhancing the overall efficiency of CAD tools.
Polygon Boolean operations are widely used in integrated circuit (IC) layout processing tasks such as design rule checking (DRC) and optical proximity correction (OPC). Single-threaded Boolean algorithms cannot meet the efficiency demand of modern IC layouts, necessitating parallel algorithms for acceleration. However, existing parallel algorithms exhibit unsatisfactory parallel speedups and limited scalability, which typically stem from an inefficient merging phase that uses generic Boolean OR operations and redundantly reprocesses all edges of polygons on grid boundaries. To solve these problems, we proposed Polygon Tailor, a novel parallel algorithm for polygon Boolean operations that employs a data-parallel strategy and a new merging approach performing incremental XOR operations solely on edges along grid boundaries, eliminating redundant computations in previous methods. This innovation drastically reduces the grid-merging time by 1–2 orders of magnitude. Compared with the parallel implementation from a commercial layout processing tool, PolygonTailor is on average 5.08× faster and up to 14.36× faster for OR operations that generate highly complex polygons.
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.