iClaire: A Fast and General Layout Pattern Classification Algorithm

Abstract

Layout pattern classification, which groups similar layout clips into clusters, underlies a variety of design for manufacturability (DFM) applications such as hotspot library generation, hierarchical data storage, and yield optimization speedup. The key challenges of layout pattern classification are clip representation and clip clustering, while the mutually conflicting concerns are efficiency and solution quality (in terms of cluster count). In this paper, we present a fast and general layout pattern classification algorithm. Our simple but general clip representation captures both topology and density; we can handle not only rigid area match or edge displacement constraints but also variant edge tolerances and don't care regions. On the other hand, for achieving a small cluster count, our clip clustering is guided by the natural grouping structure of layout clips. Our experiments are conducted on 2016 CAD contest at ICCAD benchmark suite; our results show that our algorithm outperforms the reference solution and all contest winning teams, delivering the smallest cluster count, fastest runtime, and 100% validity. In addition to the good solution quality, the interplay between adopted simple and easily manipulated data structures and our algorithm makes it fast and viable to be incorporated into practical DFM flows.