Algorithms, Vol. 19, Pages 145: PolygonTailor: A Parallel Algorithm for Polygon Boolean Operations in IC Layout Processing

Algorithms doi: 10.3390/a19020145

Authors:
Zhirui Niu
Ruian Ji
Guan Wang
Siao Guo
Shijie Ye
Lan Chen

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.

Source link

Zhirui Niu www.mdpi.com