With the continued feature-size shrinking in modern circuit designs, the layout performance estimation and parasitic import calculation based on the extracted centerline result play an important role in mask verification. Most previous works on layout centerline extraction focus on identifying the connectivity among the devices in a mask layout, with few ones collecting accurate centerline information for mask verification while considering design constraints. In this paper, we first formulate the centerline extraction problem as a Voronoi diagram to collect centerline points. Then, we present a graph-based invalid centerline removal algorithm to generate an initial centerline result. Finally, a complexity-driven centerline optimization method is proposed to further optimize the centerline while considering design constraints. Compared with the commercial 3D-RC parasitic parameter extraction tool RCExplorer and the 1st place in the 2019 EDA Elite Challenge Contest, experimental results show that our algorithm achieves the highest average precision ratio of 99.8% on centerline extraction while satisfying all design constraints in the shortest runtime.

A parallel simulation that partitions a large circuit into sub-circuits is widely used to reduce simulation runtime. To achieve higher simulation throughput, we shall consider signal directions, and thus the final partitioning solution must be acyclic. In this paper, we model a circuit as a directed graph and consider acyclic graph partitioning to minimize edge cuts. This problem differs from the traditional partitioning problem because of the additional acyclicity constraint. Unlike traditional heuristics that tend to be trapped in local minima, especially for large graphs, we present a novel discrete dynamic filled function algorithm for the acyclic graph partitioning problem. Our algorithm can guarantee convergence and effectively move from one discrete local minimizer to another better one. Experimental results show that our algorithm achieves 8% average cutsize reduction over the state-of-the-art works in a comparable runtime.