An efficient SVM-based hotspot detection method using spectral clustering is proposed in this paper. Firstly, we build graphs to represent both training patterns and test layouts. With spectral clustering, the training patterns and test layouts are adaptively decomposed into a set of small critical patterns. The small critical patterns from the training data sets are used to build the SVM models. The SVM models are then employed to check the decomposed features from the test layouts for hotspot detection. Compared with existing SVM-based hotspot detection methods, the proposed method can achieve higher accuracy with comparable number of false alarms and significant speedup.

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.

Because of the widening sub-wavelength lithography gap in advanced fabrication technology, lithography hotspot detection has become an essential task in design for manufacturability. Unlike current state-of-the-art works, which unite pattern matching and machine-learning engines, we fully exploit the strengths of machine learning using novel techniques. By combing topological classification and critical feature extraction, our hotspot detection framework achieves very high accuracy. Furthermore, to speed-up the evaluation, we verify only possible layout clips instead of full-layout scanning. We utilize feedback learning and present redundant clip removal to reduce the false alarm. Experimental results show that the proposed framework is very accurate and demonstrates a rapid training convergence. Moreover, our framework outperforms the 2012 CAD contest at International Conference on ComputerAided Design (ICCAD) winner on accuracy and false alarm.

This work presents a new signature for 2D spatial configurations that is useful for the optimization of a hotspot detection process. The signature is a string of numbers representing changes along the horizontal and vertical slices of a configuration, which serves as the key of an inverted index that groups layout' windows with the same signature. The method extracts signatures from a compact specification of similar exact patterns with a fixed size. Then, these signatures are used as search keys of the inverted index to retrieve candidate windows that can match the patterns. Experimental results show that this simple type of signature has 100% recall and, in average, over 85% of precision in terms of the area effectively covered by the pattern and the retrieved area of the layout. In addition, the signature shows a good discriminate quality, since around 99% of the extracted signatures match each of them with a single pattern.

To improve the yield in current manufacturing processes, the problematic layout configurations, so-called process-hotspots, should be detected and replaced with yield friendly patterns. A hotspot pattern with edge tolerances and incomplete specifications, where edges may vary in a certain range and any layout configurations may exist in its ambit regions, can sufficiently and generally represent a process-hotspot. This type of hotspots, however, cannot be efficiently or correctly detected by using the state-of-the-art string-matching-based method. In this paper, we present an accurate and efficient DRC-based hotspot detection framework to handle hotspot patterns with edge tolerances and incomplete specifications. Unlike existing DRC-based work, which handles only completely specified patterns, we extract critical design rules to represent all possible topologies of hotspot patterns with edge tolerances and incomplete specifications. We further order these rules to iteratively reduce the search regions of a layout during design rule checking. Then, we apply longest common subsequence and linear scan to locate all hotspots accurately and efficiently. Compared with the state-of-the-art work, experimental results show that our approach can reach promising success rates with significant speedups.

Because of the widening sub-wavelength lithography gap in advanced fabrication technology, lithography hotspot detection has become an essential task in design for manufacturability. Current state-of-the-art works unite pattern matching and machine learning engines. Unlike them, we fully exploit the strengths of machine learning using novel techniques. By combing topological classification and critical feature extraction, our hotspot detection framework achieves very high accuracy. Furthermore, to speed up the evaluation, we verify only possible layout clips instead of full-layout scanning. After detection, we filter hotspots to reduce the false alarm. Experimental results show that the proposed framework is very accurate and demonstrates a rapid training convergence. Moreover, our framework outperforms the 2012 CAD Contest at ICCAD winner on accuracy and false alarm.

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

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.

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, stochastic collocation algorithm combined with sparse grid technique (SSCA) is proposed to deal with the periodic steady-state analysis for nonlinear systems with process variations. Compared to the existing approaches, SSCA has several considerable merits. Firstly, compared with the moment-matching parameterized model order reduction (PMOR), which equally treats the circuit response on process variables and frequency parameter by Taylor approximation, SSCA employs homogeneous chaos to capture the impact of process variations with exponential convergence rate and adopts Fourier series or wavelet bases to model the steady-state behavior in time domain. Secondly, contrary to stochastic Galerkin algorithm (SGA), which is efficient for stochastic linear system analysis, the complexity of SSCA is much smaller than that of SGA for nonlinear case. Thirdly, different from efficient collocation method, the heuristic approach which may results in "rank deficient problem" and "Runge phenomenon", sparse grid technique is developed to select the collocation points in SSCA in order to reduce the complexity while guaranteing the approximation accuracy. Furthermore, though SSCA is proposed for the stochastic nonlinear steady-state analysis, it can be applied for any other kinds of nonlinear system simulation with process variations, such as transient analysis, etc.

The 90nm technology node is a mature process and is currently in full production. It was the first node to challenge the limitations of 193 nm lithography in a significant way. Many creative solutions were devised to circumvent those limitations and a lot was learned in the process. Now 65nm, 45nm, and 32nm are pushing the envelope of every aspect of the design and manufacturing flow; not just lithography but also in device engineering, device modeling, and design methodology. Design for Manufacturability (DFM) and Design for Yield (DFY) dictate that we optimize every step in the design flow. Here we address a plurality of those challenges.

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 this paper, a wavelet based approach is proposed for the model order reduction of linear circuits in time domain. Compared with Chebyshev reduction method, the wavelet reduction approach can achieve smaller reduced order circuits with very high accuracy, especially for those circuits with strong singularities. Furthermore, to compute the basis function coefficient vectors, a fast Sylvester equation solver is proposed, which works more than one or two orders faster than the vector equation solver employed by Chebyshev reduction method. The proposed wavelet method is also compared with the frequency domain model reduction method, which may loose accuracy in time domain. Both theoretical analysis and experiment results have demonstrated the high speed and high accuracy of the proposed method.

In this tutorial we will examine the process issues that are causing yield stability issues and how they will affect design flows for 65nm and below.

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.

With the development of IC technology, it becomes urgent to investigate model reduction method for interconnects with process variations. In this paper, a one-shot projection algorithm (OPM) is proposed to generate a projection matrix that is independent of statistically varying parameters. As a result, construction of the reduced system can be decoupled with the Monte Carlo analysis in either frequency domain or time domain. Therefore, without loss of accuracy, OPM can obtain a reduced system in much less CPU time compared with the previous perturbation scheme. Numerical results have demonstrated the advantages of the proposed OPM

This article focuses on the formulation of the substrate resistive coupling using boundary element methods, specifically for substrates without grounded backplates (floating substrates). An accurate and numerically stable formulation is presented. Numerical results are shown to demonstrate the correctness and the numerical robustness of the formulation.

Recently model order reduction techniques for second-order systems have obtained many research interests for the simulation of RCS interconnect circuits employing susceptance elements. In this paper, we propose a Block SAPOR (Block Second-order Arnoldi method for Passive Order Reduction) for Multi-Input Multi-Output RCS Circuits. The proposed Block SAPOR algorithm can simultaneously guarantee passivity and achieve higher accuracy than the first order reduction technique PRIMA. Most importantly, the reduced system matrices obtained by the proposed method can preserve the structure of the original system matrices. Such a nice property makes it possible to construct an equivalent RCS circuit for the reduced system.

In this paper, a novel wavelet method is proposed for noise analysis of nonlinear circuits. Compared with the existing algorithms capable of accessing circuit performance in the present of noise, the proposed method presents several merits. First, it fully accounts for nonlinearities. Second, it can handle signals with continuous frequency spectra. Third, by taking advantage of the properties of the wavelet bases, such as local compactness and multi-resolution, it holds high simulation speed and high accuracy. Furthermore, an adaptive scheme exists to automatically select the wavelet basis functions for a desired accuracy. All these merits make the novel wavelet method outperforms its previous techniques.

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

Non-uniform routing architecture contains routing channels of different widths. In this paper we propose a design methodology of domain specific non-uniform programmable routing architecture for embedded programmable IP cores. This non-uniform architecture is based on symmetrical FPGA model and consists of connection boxes of full connectivity and rectangular switch boxes. The rectangular switch box is derived from universal switch box module. Area and timing efficiency of the proposed architecture is compared with those of uniform architecture based on placement and routing result over a set of MCNC benchmark circuits. The comparison results show that non-uniform routing architecture gains up to 8% layout area reduction from uniform ones. Besides, by widening some of the routing channels where routing congestions accumulate, the average critical path delay of non-uniform architecture is 8% less than that of uniform one while maintain the same area.

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

In this paper, a layout dependent full-chip electroplating (ECP) topography model is developed based on the additive nature of the physics of the EP process. Two layout attributes: layout density, and feature perimeter sum are used to compute the post-ECP topography. Under a unified mechanism, two output variables representing the final topography: the array height and the step height are modeled simultaneously. Using the proposed model long-range effects of the ECP process can be incorporated easily as well. The simulation results of our model were verified with test structure experimental data published in the literature and are presented in this paper. The results show that the errors are less than 5%. This model is not limited to the regular test structures; it can also be used for any practical design. The results of such partial application are shown here as well. Our proposed ECP model can be used to model systematic variations caused by an ECP process or by a chemical mechanical planarization (CMP) process. The potential applications of this model include: layout design evaluation for catastrophic failure prevention; yield aware design (design for manufacturability), and variation- aware timing analysis.

The variational analysis has been employed in for order reduction of weakly nonlinear systems. For a relatively strong nonlinear system, this method will mostly lose efficiency because of the exponentially increased number of inputs in higher order variational equations caused by the individual reduction process of the variational systems. Moreover, the inexact inputs into the higher order variational equations indispensably introduce extra errors in the order reduction process. Inspired by the variational analysis, we propose a direct model order reduction method. The order of the approximate polynomial system of the original nonlinear system is directly reduced by one project space. The proposed direct reduction technique can easily avoid the errors brought by inexact inputs and the exponentially increased inputs. We show theoretically and experimentally that the proposed method can achieve much more accurate reduced system with smaller order size than the conventional variational equation order reduction method.

In this paper, we propose a novel time-domain based method, discrete singular convolution algorithm, for computing steady-state response in nonlinear circuit. Properties and advantages of discrete singular convolution method are discussed, compared with some other approaches. The accuracy and efficiency of this method are tested by the numerical experiments.

The recently-introduced susceptance element exhibits many prominent features in modeling the on-chip magnetic couplings. For an RCS circuit, it is better to be formulated as a second-order system. Therefore, corresponding MOR (model-order reduction) techniques for second-order systems are desired to efficiently deal with the ever-increasing circuit scale and to preserve essential model properties. We first review the existing MOR methods for RCS circuits, such as ENOR and SMOR, and discuss several key issues related to numerical stability and accuracy of the methods. Then, a technique, SAPOR (second-order Arnoldi method for passive order reduction), is proposed to effectively address these issues. Based on an implementation of a generalized second-order Arnoldi method, SAPOR is numerically stable and efficient. Meanwhile, the reduced-order system also guarantees passivity.

We study the octilinear Steiner tree to evaluate the rectilinear Steiner tree based router. First, we give the worst and average case wirelength for rectilinear routing and octilinear routing for two terminals net. Next, we show the octilinear Steiner trees have smaller wirelength reduction for multiterminal net than that of rectilinear Steiner tree. Then, we propose an O(|V|+|E|) algorithm to construct an isomorphic octilinear Steiner tree from a rectilinear Steiner tree G = (V, E) and prove the wirelength of the isomorphic octilinear Steiner tree is the lower bound. In the end, we show two types of experiment of wirelength reduction results by using diagonal wire The octilinear Steiner tree reduces 9.201% and 6.63% of the wirelength over rectilinear Steiner tree on a set of nets generated at random and on 15 VLSI designs, respectively.

We consider the problem of global routing, aiming to simultaneously minimize wire length and density through the regions. Previous global routers have attempted to achieve this goal; however, they minimized one of the two parameters as the main objective and proposed heuristics for minimizing the other parameter. We accomplish this task by introducing the concept of weighted Steiner trees. We propose an efficient and simple algorithm for obtaining a weighted (rectilinear) Steiner tree in the plane. The proposed global router at each step finds a weighted Steiner tree for a net, where weight of a region represents its "complexity". Weights of the regions are dynamically changing. Experimental results on master slice chips and on benchmark examples from the Physical Design Workshop are included, and they verify the effectiveness of the proposed global router and its superiority over related global routers.>

A layout model called vertical-two-overlap is introduced. The following results are established for an arbitrary vertical-two-overlap layout W with area A. 1. A linear time algorithm for obtaining a two-layer wiring of W, if one exists, is devised. Also, by increasing the area to at most 2A a two-layer wirable layout is obtained. 2. To decide three-layer wirability of an arbitrary vertical-two-overlap layout is NP-complete. However, W can be converted into a three-layer wirable layout with area at most 3/2 A. 3. W is always four-layer wirable and a four-layer wiring thereof can be constructed in O(A) time.>

Global routing of multiterminal nets is studied. A novel global router is proposed; each step consists of finding a tree, called a Steiner min-max tree, that is Steiner tree with maximum-weight edge minimized (real vertices represent channels containing terminals of a net, Steiner vertices represent intermediate channels, and weights correspond to densities). An O (min(e loglog e, n/sup 2/)) time algorithm is proposed for obtaining a Steiner min-max tree in a weighted graph with e edges and n vertices. (This result should be contrasted with the NP-completeness of the traditional minimum-length Steiner tree problem). Experimental results on difficult examples, on randomly generated data, on master slice chips, and on benchmark examples from the Physical Design Workshop are included.>

A study is made of the global routing of multiterminal nets. The authors propose a novel global router. Each step consists of finding a tree, called Steiner min-max tree, that is, a Steiner tree with the maximum-weight edge minimized (real vertices represent channels containing terminals of a net, Steiner vertices represent intermediate channels, and weights correspond to densities). An efficient algorithm is presented for obtaining a Steiner min-max tree, in a weighted graph. Experimental results on difficult examples, randomly generated data, master slice chips, and benchmark examples from the physical design workshop are very promising. (In all cases, previous results have been improved.).>