A distance metric of patterns is crucial to hotspot cluster analysis and classification. In this paper, we propose an improved tangent space (ITS)-based distance metric for hotspot cluster analysis and classification. The proposed distance metric is an important extension of the well-developed tangent space method in computer vision. It can handle patterns containing multiple polygons, while the traditional tangent space method can only deal with patterns with a single polygon. It inherits most of the advantages of the traditional tangent space method, e.g., it is easy to compute and is tolerant with small variations or shifts of the shapes. The ITS-based distance metric is a more reliable and accurate metric for hotspot cluster analysis and classification. We also propose a hierarchical density-based clustering method for hotspot clustering. It is more suitable for arbitrary shaped clusters.

A distance metric of patterns is crucial to hotspot cluster analysis and classification. In this paper, we propose an improved tangent space based metric for pattern matching based hotspot cluster analysis and classification. The proposed distance metric is an important extension of the well-developed tangent space method in computer vision. It can handle patterns containing multiple polygons, while the traditional tangent space method can only deal with patterns with a single polygon. It inherits most of the advantages of the traditional tangent space method, e.g., it is easy to compute and is tolerant with small variations or shifts of the shapes. Compared with the existing distance metric based on XOR of hotspot patterns, the improved tangent space based distance metric can achieve up to 37.5% accuracy improvement with at most 4.3x computational cost in the context of cluster analysis. The improved tangent space based distance metric is a more reliable and accurate metric for hotspot cluster analysis and classification. It is more suitable for industry applications.

In advanced fabrication technology, the sub-wavelength lithography gap causes unwanted layout distortions. Even if a layout passes design rule checking (DRC), it still might contain process hotspots, which are sensitive to the lithographic process. Hence, process-hotspot detection has become a crucial issue. In this paper, we propose an accurate process-hotspot detection framework. Unlike existing DRC-based works, we extract only critical design rules to express the topological features of hotspot patterns. We adopt a two-stage filtering process to locate all hotspots accurately and efficiently. Compared with state-of-the-art DRC-based works, our results show that our approach can reach 100% success rate with significant speedups.

This paper introduces a novel distributed algorithm for performing the layout geometry operations usually found in design rule checking, layout verification, and mask synthesis. A large number of machines are typically available to the user during the mask synthesis flow. As multiple machines or cores become more ubiquitous, even designers using layout verification tools will have access to a large set of machines. Therefore, an efficient and scalable distributed algorithm for performing sequences of layout geometry operations will be of great value to both designers and mask synthesis engineers. Given a layout and a sequence of layout geometry operations, the proposed algorithm divides the layout into several partitions. The given sequence of layout geometry operations is executed in parallel on different partitions. New partitions are derived from the original set of partitions and the sequence of geometry operations is repeated on larger partitions with much fewer polygons. This process continues until it produces a partition that covers the entire layout area. A key feature of the proposed algorithm is that it is correct-by-construction, i.e., each partition is guaranteed to generate a subset of the correct results. Complete and correct results are generated for each layout geometry operation for the entire layout when the operation completes execution on all the partitions. The proposed algorithm was implemented in Gearman, an open-source distributed framework. Results on large industrial layouts show good performance and scalability.

This paper introduces a novel distributed algorithm for performing layout geometry operations usually found in design rule checking, layout verification and/or mask synthesis. Typically, during the mask synthesis flow, a large number of machines are available to the user. Also, as multiple machines/cores become more ubiquitous, even designers using layout verification tools will have access to a large set of machines. Having an efficient and scalable distributed algorithm for performing sequences of layout geometry operations will be of great value to both the designer and the mask synthesis engineer.

During the very large scale integration design process, a synthesized design is often required to be modified in order to accommodate different goals. To preserve the engineering effort already invested, designers seek small logic structural transformations to achieve these logic restructuring goals. This paper proposes a systematic methodology to devise such transformations automatically. It first presents a simulation-based formulation to approximate sets of pairs of functions to be distinguished and avoid the memory/time explosion issue inherent with the original representation. Then, it uses this new data structure to devise the required transformations dynamically without the need of a static dictionary model. The methodology is applied to both combinational and sequential designs with transformations at a single or multiple locations. An extensive suite of experiments documents the benefits of the proposed methodology when compared to existing practices.

In this paper, we present a novel algorithm for 3D floorplanning with fixed outline constraints and a particular emphasis on thermal awareness. A computationally efficient thermal model that can be used to guide the thermal-aware floorplanning algorithm to reduce the peak temperature is proposed. We also present a novel white space redistribution algorithm to dissipate hotspot. Thermal through-silicon via (TSV) insertion is performed during the floorplanning process as a means to control the peak temperature. Experimental results are very promising and demonstrate that the proposed floorplanning algorithm has a high success rate at meeting the fixed-outline constraints while effectively limiting the rise in peak temperature.

Today's SoCs/SIPs face numerous design challenges as increased integration of system components on a single die stretches the limits of technology and design capacity. 3D integration, where multiple dies are stacked and interconnected in the vertical dimension using through-silicon vias (TSVs), is probably the best hope for carrying ICs along (and even beyond) the path of Moore's law in the 21st century. However successful adoption of 3D ICs will require among other things modifications to EDA tools to enable 3D IC design. In this paper, we identify key stages in EDA that need modification to handle 3D ICs, highlight the challenges and review existing solutions, if they exist. Whenever appropriate, at a particular stage, we also provide preferred features of the solutions necessary to enable 3D IC design with the least amount of disruption.

In the digital VLSI cycle, logic transformations are often required to modify the design to meet different synthesis and optimization goals. Logic transformations on sequential circuits are hard to perform due to the vast underlying solution space. This paper proposes an SPFD-based sequential logic transformation methodology to tackle the problem with no sacrifice on performance. It first presents an efficient approach to construct approximate SPFDs (aSPFDs) for sequential circuits. Then, it demonstrates an algorithm using aSPFDs to perform the desirable sequential logic transformations using both combinational and sequential don't cares. Experimental results show the effectiveness and robustness of the approach.

Thickness range, i.e. the difference between the highest point and the lowest point of the chip surface, is a key indicator of chip yield. This paper presents a novel metal filling algorithm that seeks to minimize the thickness range of the chip surface during the copper damascene process. The proposed solution considers the physical mechanisms in the damascene process, namely ECP (which is the process used to deposit Cu in the trenches) and CMP (which is the process used to polish Cu after ECP), that affect thickness range. Key predictors for the final thickness range, which is the thickness range after ECP and CMP, that can be computed efficiently are identified and used to drive the metal filling process. To the best of our knowledge, this is the first metal filling algorithm that uses an ECP model among other things to guide metal filling. Experimental results are very promising and indicate that the proposed method can significantly reduce the thickness range after metal filling. This is in sharp contrast with the density-driven approaches which often increase the thickness range after metal filling, thereby potentially adversely impacting yield. In addition, the proposed method inserts significantly smaller amount of fill when compared to the density-driven approaches. This is desirable as it limits the impact of metal filling on timing.

In this paper, a novel and computationally efficient methodology to accurately estimate key yield factors during the global routing stage is presented. Such an yield factor estimator at the global routing stage is essential since it can used to either get an early estimate of the final yield of the same design (i.e. the yield after applying the required sequence of detailed routing and post-routing yield optimizations) and/or to improve the final yield of the design by making the solution at the end of global routing more amenable to post-routing yield optimizations. The proposed yield factor estimator is inherently flexible and can easily be programmed to estimate during global routing a variety of key yield factors of the same design after a typical sequence of detailed routing and representative post-routing yield optimizations has been applied. Examples are provided to show how the yield factor estimator can be used to predict short and open critical area and metal density after typical yield optimization solutions like wire-spreading, wire-widening and metal filling, respectively. Experimental results presented in the paper show that the proposed yield factor estimator can predict final yield factor hotspots/values with a high degree of accuracy. The proposed estimator is also shown to be more suited for the purpose of yield factor estimation compared with typical metrics at the global routing stage like congestion.

This paper introduces the concept of via range patterns and incompletely specified range patterns to represent new types of process-hotspots. Via range patterns can represent process-hotspots containing vias that are a major source of lithography issues. An incompletely specified range pattern can accurately and succinctly represent a process-hotspot where any configuration of objects (that is unknown to the user apriori) can exist in some of its peripheral regions. These new types of range patterns cannot be accurately represented and/or detected using the concept of range patterns introduced in [7]. A new detection algorithm that can accurately detect these new types of patterns is also proposed. This is necessitated since the range pattern matching algorithm proposed earlier causes mismatches: it either misses true matches or reports false matches for these new kinds of patterns. Theoretical results show that the proposed algorithm prevents the incorrect mis-match issues, while experimental results on fab provided process-hotspots show the algorithm is computationally efficient and practical for use on real industrial designs.

Alternating-aperture phase shift masking (AAPSM), a form of strong resolution enhancement technology, will be used to image critical features on the polysilicon layer at smaller technology nodes. This technology imposes additional constraints on the layouts beyond traditional design rules. Of particular note is the requirement that all critical features be flanked by opposite-phase shifters while the shifters obey minimum width and spacing requirements. A layout is called phase assignable if it satisfies this requirement. Phase conflicts have to be removed to enable the use of AAPSM for layouts that are not phase assignable. Previous work has sought to detect a suitable set of phase conflicts to be removed as well as correct them. This paper has two key contributions: 1) a new computationally efficient approach to detect a minimal set of phase conflicts, which when corrected will produce a phase-assignable layout, and 2) a novel layout modification scheme for correcting these phase conflicts with small layout area increase. Unlike previous formulations of this problem, the proposed solution for the conflict detection problem does not frame it as a graph bipartization problem. Instead, a simpler and more computationally efficient reduction is proposed. This simplification greatly improves the runtime while maintaining the same improvements in the quality of results obtained in Chiang (Proc. DATE, 2005, p. 908). An average runtime speedup of 5.9times is achieved using the new flow. A new layout modification scheme suited for correcting phase conflicts in large standard-cell blocks is also proposed. The experiments show that the percentage area increase for making standard-cell blocks phase assignable ranges from 1.7% to 9.1%

In deep submicron feature sizes continue to shrink aggressively beyond the natural capabilities of the 193 nm lithography used to produce those features thanks to all the innovations in the field of resolution enhancement techniques (RET). With reduced feature sizes and tighter pitches die level variations become an increasingly dominant factor in determining manufacturing yield. Thus a prediction of design-specific features that impact intra-die variability and correspondingly its yield is extremely valuable as it allows for altering such features in a manner that reduces intra-die variability and improves yield. In this paper, a manufacturing yield model which takes into account both physical layout features and manufacturing fluctuations is proposed. The intra-die systematic variations are evaluated using a physics-based model as a function of a design's physical layout. The random variations and their across-die spatial correlations are obtained from data harvested from manufactured test structures. An efficient algorithm is proposed to reduce the order of the numerical integration in the yield model. The model can be used to (i) predict manufacturing yields at the design stage and (ii) enhance the layout of a design for higher manufacturing yield.

In current manufacturing processes, certain layout configurations are likely to have reduced yield and/or reliability due to increased susceptibility to stress effects or poor tolerance to certain processes like lithography. These problematic layout configurations need to be efficiently detected and eliminated from a design layout to enable better yield. In this paper, such layout configurations are called processhotspots and an efficient and scalable algorithm is proposed to detect such process-hotspots in a given layout.

As feature sizes shrink, it will be necessary to use AAPSM (alternating-aperture phase shift masking) to image critical features, especially on the polysilicon layer. This imposes additional constraints on the layouts beyond traditional design rules. Of particular note is the requirement that all critical features be flanked by opposite-phase shifters, while the shifters obey minimum width and spacing requirements. A layout is called phase-assignable if it satisfies this requirement. If a layout is not phase-assignable, the phase conflicts have to be removed to enable the use of AAPSM for the layout. Previous work has sought to detect a suitable set of phase conflicts to be removed, as well as correct them. The contributions of this paper are the following: (1) a new approach to detect a minimal set of phase conflicts (also referred to as AAPSM conflicts), which when corrected will produce a phase-assignable layout; (2) a novel layout modification scheme for correcting these AAPSM conflicts. The proposed approach for conflict detection shows significant improvements in the quality of results and runtime for real industrial circuits, when compared to previous methods. To the best of our knowledge, this is the first time layout modification results are presented for bright-field AAPSM. Our experiments show that the percentage area increase for making a layout phase-assignable ranges from 0.7-11.8%.

Alternating-aperture phase shift masking (AAPSM), a form of strong resolution enhancement technology (RET) is used to image critical features on the polysilicon layer at smaller technology nodes. This technology imposes additional constraints on the layouts beyond traditional design rules. Of particular note is the requirement that all critical features be flanked by opposite-phase shifters, while the shifters obey minimum width and spacing requirements. A layout is called phase-assignable if it satisfies this requirement. Phase conflicts between shifters have to be removed to enable the use of AAPSM for layouts that air not phase-assignable. Previous work has sought to detect a suitable set of phase conflicts to be removed, as well as correct them as well as correct them. This paper has two key contributions: (1) a new computationally efficient approach to detect a minimal set of phase conflicts, which when corrected produces a phase-assignable layout; (2) a novel layout modification scheme for correcting these phase conflicts in standard-cell blocks. Unlike previous formulations of this problem, the proposed solution for the conflict detection problem does not frame it as a graph bipartization problem. Instead, a simpler and more computationally efficient reduction is proposed. This simplification greatly improves the runtime, while maintaining the same improvements ill the quality of results. An average runtime speedup of 5.9/spl times/ is achieved using the new flow. A new layout modification scheme for correcting phase conflicts in large standard-cell blocks is also proposed. The proposed layout modification scheme can handle all phase conflicts in large standard-cell blocks with small increases in area. Our experiments show that the percentage area increase for making typical standard-cell blocks phase-assignable ranges from 3.4-9.1%.