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.
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.
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%.
14636157
Probabilistic interval-valued computation: toward a practical surrogate for statistics inside CAD tools
Interval methods offer a general, fine-grain strategy for modeling correlated range uncertainties in numerical algorithms. We present a new, improved interval algebra that extends the classical affine form to a more rigorous statistical foundation. Range uncertainties now take the form of confidence intervals. In place of pessimistic interval bounds, we minimize the probability of numerical "escape"; this can tighten interval bounds by 10times, while yielding 10-100times speedups over Monte Carlo. The formulation relies on three critical ideas: liberating the affine model from the assumption of symmetric intervals; a unifying optimization formulation; and a concrete probabilistic model. We refer to these as probabilistic intervals, for brevity. Our goal is to understand where we might use these as a surrogate for expensive, explicit statistical computations. Results from sparse matrices and graph delay algorithms demonstrate the utility of the approach, and the remaining challenges
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%.
14453892
A One-Bit-Matching Learning Algorithm for Independent Component Analysis
Independent component analysis (ICA) has many practical applications in the fields of signal and image processing and several ICA learning algorithms have been constructed via the selection of model probability density functions. However, there is still a lack of deep mathematical theory to validate these ICA algorithms, especially for the general case that super- and sub-Gaussian sources coexist. In this paper, according to the one-bit-matching principle and by turning the de-mixing matrix into an orthogonal matrix via certain normalization, we propose a one-bit-matching ICA learning algorithm on the Stiefel manifold. It is shown by the simulated and audio experiments that our proposed learning algorithm works efficiently on the ICA problem with both super- and sub-Gaussian sources and outperforms the extended Infomax and Fast-ICA algorithms.
2342345
Finding diversity in remote code injection exploits
Remote code injection exploits inflict a significant societal cost, and an active underground economy has grown up around these continually evolving attacks. We present a methodology for inferring the phylogeny, or evolutionary tree, of such exploits. We have applied this methodology to traffic captured at several vantage points, and we demonstrate that our methodology is robust to the observed polymorphism. Our techniques revealed non-trivial code sharing among different exploit families, and the resulting phylogenies accurately captured the subtle variations among exploits within each family. Thus, we believe our methodology and results are a helpful step to better understanding the evolution of remote code injection exploits on the Internet.
129063
Learning to cluster web search results
Organizing Web search results into clusters facilitates users' quick browsing through search results. Traditional clustering techniques are inadequate since they don't generate clusters with highly readable names. In this paper, we reformalize the clustering problem as a salient phrase ranking problem. Given a query and the ranked list of documents (typically a list of titles and snippets) returned by a certain Web search engine, our method first extracts and ranks salient phrases as candidate cluster names, based on a regression model learned from human labeled training data. The documents are assigned to relevant salient phrases to form candidate clusters, and the final clusters are generated by merging these candidate clusters. Experimental results verify our method's feasibility and effectiveness.
15970819
A Dangerous Location Aware System for Assisting Kids Safety Care
This system focuses on a location-aware computing application and environment which provide preemptive information on dangerous locations in the kid's surroundings; i.e., the system alerts a kid on the move of the possible dangers whenever he/she is near accident prone areas. Using satellite-based GPS position sensing, this system can gradually learn and remember about the different locations that a kid routinely visits and/or passes by in his daily life, based on space-oriented contexts. The full set of system functionalities, including the map display, requires a graphical user interface. This location based services (LBSs) can compute the serious situations and alert kids to avoid dangerous situations. Our research can simulate the virtual environment as hyperspaces for kids safety care
27040656
Rough Asymptotics of Forward-Backward Stochastic Differential Equations
This note is concerned with the asymptotic behavior of adapted solutions to forward-backward SDEs when the forward diffusion contains small noises. We prove the sample path Large Deviation Principle (LDP) for the adapted solutions to the FBSDEs under appropriate conditions stated in terms of a certain type of convergence of the solutions to the associated quasilinear PDEs. As an application we apply the LDP results to a problem of rare event simulation. We provide a necessary condition for the existence of an asymptotically efficient estimator amongst the class of importance sampling estimators.