iClaire: A Fast and General Layout Pattern Classification Algorithm With Clip Shifting and Centroid Recreation

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 a...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 2020-08, Vol.39 (8), p.1662-1673
Main Authors: Chang, Wei-Chun, Jiang, Iris Hui-Ru
Format: Article
Language:English
Subjects:
Algorithms
Centroids
Classification
Classification algorithms
Clips
Clustering
Clustering algorithms
Data storage
Data structures
Design for manufacturability
Design for manufacturability (DFM)
Layout
layout pattern classification
Layouts
Libraries
lithography hotspot library
Markov clustering
Optimization
Pattern classification
Recreation
Representations
Runtime
Tolerances
Topology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. In this paper, we present a fast and general layout pattern classification algorithm considering clip shifting and centroid recreation. 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. For achieving a small cluster count, our clip clustering is guided by the natural grouping structure of layout clips. The clustering results are further improved by centroid recreation. 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. Moreover, our algorithm with clip shifting and centroid recreation further reduces the cluster count effectively and efficiently. In addition to the good solution quality, the interplay between adopted data structures and our algorithm makes it fast and viable to be incorporated into practical DFM flows.
ISSN:0278-0070
1937-4151
DOI:10.1109/TCAD.2019.2917849