Distance metrics and clustering algorithms for detection and classification of process sensitive patterns

Detection of process sensitive patterns known as hotspots is critical to maximising yield in integrated circuit layouts. Design rule checking is a common tool in the industry for fast hotspot detection, but it is becoming impractical as we approach smaller technology nodes, due to an exponentially growing rule book which must be manually maintained.A pattern matching based system for hotspot detection is explored in this dissertation which has the advantage of being automatically generated while still performing detection with a runtime comparable to design rule checking. Instead of scanning a design layout for certain combinations of distances found in a library of rules, we use a pattern matching tool to find occurrences in the layout of patterns which match or closely resemble known bad configurations.In order for such a system to detect hotspots effectively, we require a comprehensive catalogue of hotspot patterns for the pattern matcher to use. Of course, it is not feasible to simply store all known hotspots patterns in the catalogue, as the memory requirements and pattern matching runtimes would be enormous. Instead, the catalogue must contain a smaller number of hotspot classes, where each class represents a set of geometrically similar patterns which embody the same type of hotspot. The pattern matching tool is able to find matches to a hotspot class by matching to a particular representative pattern of the class, and allowing for small geometric deviations from this representative.To build such a catalogue, a large diverse set of hotspot clips must be analysed and reduced to a small number of hotspot classes. To perform this reduction meaningfully, a deep understanding of what it means for two hotspots to be the same "type'" of hotspot is required. We perform an in-depth analysis of the process sensitivity of patterns. From this we design a distance metric which quantifies the extent to which the process sensitivities of two hotspots are caused by similar geometry of surrounding features.Equipped with this distance metric, clustering algorithms are used to group a dataset of clips into a small number of clusters containing similar hotspots. Because the number of clips to analyse must be very large in order to build a comprehensive catalogue, it is important to make this process as computationally efficient as possible. To this end, the distance metric and the clustering algorithm are designed and tailored for maximum efficiency.To test our hotspot detection system, we build a catalogue of hotspot classes based on a dataset of clips extracted from a device layout. A pattern matching tool then uses our catalogue to detect hotspots, and the results are presented