Maximum Clique Based Method For Optimal Solution Of Pattern Classification

Hotspot clip classification of chip image is a technology classifies a series of chip image into different clusters according to their similarity degree,which reduces the workload of repair.It lays foundation for the design for manufacturability(DFM)application,such as hotspot library generation,hierarchical data storage and systematic yield optimization,etc..The key challenge of hotspot clip classification lies in the similarity quantification and clustering,and the evaluation criteria of the classification effect are mainly about the classification efficiency and quality.In the current research,classification quality is a major problem faced by the industry,most of the existing methods can not obtain the optimal classification results easily,and other methods which can obtain better results have problem with low classification efficiency.Hotspot clip clustering algorithm based on the maximum clique is a fast and general hotspot clip classification algorithm,which uses a concise and low cost clip representation method,and two different similarity constraint modes were supported:area constrained clustering and edge constrained clustering.In order to ensure the classification quality,this paper proves that this method is optimal in terms of classification results.At the same time,the algorithm uses a set of data structure process method of clip images to reduce the data processing time,and provides an accurate calculation method for calculate the distance between two hotspot clips.Experiment of paper adopted the competition benchmarks in the ICCAD 2016 CAD competition.In the test results,the algorithm could find the lower limit of the minimum cluster number with the help of the maximum clique.In the clustering,the algorithm uses the set coverage problem(SCP)algorithm and the maximum clique result to cluster hostspot clips,which can obtain the optimal clipping classification and ensure the running time in a reasonable range.The main work of this paper is as follows:(1)An efficient method for extracting and calculating hot spot clip images is proposed,which covers the process of extracting hotspot polygons,saving as data structure,eliminating redundant clips,etc..The similarity of hotspot clip images can be defined according to two different modes : area constrained clustering and edge constrained clustering.It provides reliable data and information for the subsequent clustering,and ensures high efficiency.(2)A method,which based on maximum clique,to calculates the lower limit of the number of hotspot clip clustering is proposed.The method can calculates the theoretical minimum value of a series of hotspot clip clusters,and provides some guidance for the subsequent clustering and other clustering algorithms.(3)A hotspot clip clustering method is proposed,which initialized by using the maximum clique result and based on set coverage problem.Experiments show that the method obtained better clustering results compared with existing papers.