18902968
Fast interval-valued statistical interconnect modeling and reduction
Correlated interval representations of range uncertainty offer an attractive solution for approximating computations on statistical quantities. The key idea is to use finite intervals to approximate the essential mass of a pdf as it moves through numerical operators; the resulting compact interval-valued solution can be easily interpreted as a statistical distribution and efficiently sampled. This paper describes improved interval-valued algorithms for AWE/PRIMA model order reduction for tree-structured interconnect with correlated $RLC$ parameter variations. By moving to a faster interval-valued linear solver based on path-tracing ideas, and making more optimal trade-offs between interval- and scalar-valued computations, we can extract delay statistics roughly 10X faster than a classical Monte Carlo simulation loop, with accuracy to within 5%.
1826840
Towards global routing with RLC crosstalk constraints
Conventional global routing minimizes total wire length and congestion. Experiments using large industrial benchmark circuits show that up to 24% of nets in such routing solutions may have RLC crosstalk violations at 3GHz clock. We develop an extremely efficient length-scaled Keff (LSK) model that has a high fidelity for long-range RLC crosstalk. We formulate an extended global routing problem (denoted as GSINO) to consider simultaneous shield insertion and net ordering with RLC crosstalk constraints, then propose an effective three-phase GSINO algorithm. The GSINO algorithm completely eliminates the RLC crosstalk violations, and has small area and wire length overhead compared to conventional routing.
10392733
Pre-routing estimation of shielding for RLC signal integrity
The formula-based K/sub eff/ model is a figure of merit for inductive coupling, and has been used to solve the simultaneous shield insertion and net ordering (SINO) and simultaneous signal and power routing (SPR) problems. The authors first show that the K/sub eff/ model has a high fidelity compared to the SPICE-computed noise under an accurate RLC circuit model. We then develop simple yet accurate formulae to estimate numbers of shields needed by optimal SINO solutions under the K/sub eff/ model. Extensive experiments show that our pre-routing estimation has errors less than 10% compared to solutions given by detailed SINO algorithms. These formulae can be used effectively as a pre-routing congestion estimation for layout planning and synthesis.
61488328
Interval-valued reduced order statistical interconnect modeling
We show how recent advances in the handling of correlated interval representations of range uncertainty can be used to predict the impact of statistical manufacturing variations on linear interconnect. We represent correlated statistical variations in RLC parameters as sets of correlated intervals, and show how classical model order reduction methods - AWE and PRIMA - can be re-targeted to compute interval-valued, rather than scalar-valued reductions. By applying a statistical interpretation and sampling to the resulting compact interval-valued model, we can efficiently estimate the impact of variations on the original circuit. Results show the technique can predict mean delay with errors between 5-10%, for correlated RLC parameter variations up to 35%.
956305
Fast interval-valued statistical modeling of interconnect and effective capacitance
Correlated interval representations of range uncertainty offer an attractive solution to approximating computations on statistical quantities. The key idea is to use finite intervals to approximate the essential mass of a probability density function (pdf) as it moves through numerical operators; the resulting compact interval-valued solution can be easily interpreted as a statistical distribution and efficiently sampled. This paper first describes improved interval-valued algorithms for asymptotic wave evaluation (AWE)/passive reduced-order interconnect macromodeling algorithm (PRIMA) model order reduction for tree-structured interconnect circuits with correlated resistance, inductance, and capacitance (RLC) parameter variations. By moving to a much faster interval-valued linear solver based on path-tracing ideas, and making more optimal tradeoffs between interval- and scalar-valued computations, the delay statistics roughly 10/spl times/ faster than classical Monte Carlo (MC) simulation, with accuracy to within 5% can be extracted. This improved interval analysis strategy is further applied in order to build statistical effective capacitance (C/sub eff/) models for variational interconnect, and show how to extract statistics of C/sub eff/ over 100/spl times/ faster than classical MC simulation, with errors less than 4%.
2749728
Interval-valued statistical modeling of oxide chemical-mechanical polishing
Technology-oriented tools provide the raw data needed to optimize the fabrication process itself, and to predict problematic variational impacts on silicon design. Unfortunately, even in these physics-oriented tools, statistically uncertain quantities appear as crucial inputs. To date, Monte Carlo techniques have been the dominant solution method. We suggest an alternative in which uncertainties are represented as correlated intervals, and interval-valued computations replace the standard scalar operations in the numerical algorithm for the tool. We use an oxide chemical-mechanical polishing tool as an example, and show how to "retrofit" workable statistical models on top of the original algorithm. Accuracies to within /spl sim/1-10% of Monte Carlo simulation, and speedups of /spl sim/10-100X can be achieved, depending on whether we choose a formulation which emphasizes accuracy, or efficiency.
14438515
Asymptotic convergence properties of the EM algorithm with respect to the overlap in the mixture
The EM algorithm is generally considered as a linearly convergent algorithm. However, many empirical results show that it can converge significantly faster than those gradient based first-order iterative algorithms, especially when the overlap of densities in a mixture is small. This paper explores this issue theoretically on mixtures of densities from a class of exponential families. We have proved that as an average overlap measure of densities in the mixture tends to zero, the asymptotic convergence rate of the EM algorithm locally around the true solution is a higher order infinitesimal than a positive order power of this overlap measure. Thus, the large sample local convergence rate for the EM algorithm tends to be asymptotically superlinear when the overlap of densities in the mixture tends to zero. Moreover, this result has been detailed on Gaussian mixtures.
40443248
Non-parametric Statistical Tests for Informative Gene Selection
This paper presents two non-parametric statistical test methods, called Kolmogorov-Smirnov (KS) and U statistic test methods, respectively, for informative gene selection of a tumor from microarray data, with help of the theory of false discovery rate. To test the effectiveness of these non-parametric statistical test methods, we use the support vector machine (SVM) to construct a tumor diagnosis system (i.e., a binary classifier) based on the identified informative genes on the colon and leukemia data. It is shown by the experiments that the constructed tumor diagnosis system with both the KS and U statistic test methods can reach a good prediction accuracy on both the colon and leukemia data sets.
16943304
A Random ID Update Scheme to Protect Location Privacy in RFID-Based Student Administration Systems
Recently the RFID has been received great attentions and gotten wide applications in many different areas including some administration systems for automatically managing students in a campus. However, a RFID tag may infringe on its owner's location privacy because of its traceability. Therefore, location privacy problems in RFID-based student administration systems become a critical issue in applying such systems to the practical. Three representative schemes to solve these problems are explained and analyzed. Moreover, a safe, fast and low cost scheme which offers better privacy protections is proposed. In this scheme, a hash value is generated from a secret ID and a random number in a RFID tag by using a cheap hash circuit, and it is used for an identifier of a user. The secret ID is updated by using the hash circuit when a reader for updating is used. Finally, some comparisons between the proposed scheme and the other three typical schemes are presented in terms of safety, speed and cost
361698
The Mahalanobis Distance Based Rival Penalized Competitive Learning Algorithm
The rival penalized competitive learning (RPCL) algorithm has been developed to make the clustering analysis on a set of sample data in which the number of clusters is unknown, and recent theoretical analysis shows that it can be constructed by minimizing a special kind of cost function on the sample data. In this paper, we use the Mahalanobis distance instead of the Euclidean distance in the cost function computation and propose the Mahalanobis distance based rival penalized competitive learning (MDRPCL) algorithm. It is demonstrated by the experiments that the MDRPCL algorithm can be successful to determine the number of elliptical clusters in a data set and lead to a good classification result.
39637186
Spatial-Temporal Cross-Correlation Analysis: A New Measure and a Case Study in Infectious Disease Informatics
This paper aims to develop a new statistical measure to identify significant correlations among multiple events with spatial and temporal components. This new measure, K(r,t), is defined by adding the temporal dimension to Ripley’s K(r) function. Empirical studies show that the use of K(r,t) can lead to a more discriminating and flexible spatial-temporal data analysis framework. This measure also helps identify the causal events whose occurrences induce those of other events.