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
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%.
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%.
16215317
Large-scale placement by grid-warping
Grid-warping is a new placement algorithm based on a strikingly simple idea: rather than move the gates to optimize their location, we elastically deform a model of the 2-D chip surface on which the gates have been roughly placed, "stretching" it until the gates arrange themselves to our liking. Put simply: we move the grid, not the gates. Deforming the elastic grid is a surprisingly simple, low-dimensional nonlinear optimization, and augments a traditional quadratic formulation. A preliminary implementation, WARP1, is already competitive with most recently published placers, e.g., placements that average 4% better wirelength, 40% faster than GORDIAN-L-DOMINO.
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.
2675323
Unexpected means of protocol inference
Network managers are inevitably called upon to associate network traffic with particular applications. Indeed, this operation is critical for a wide range of management functions ranging from debugging and security to analytics and policy support. Traditionally, managers have relied on application adherence to a well established global port mapping: Web traffic on port 80, mail traffic on port 25 and so on. However, a range of factors - including firewall port blocking, tunneling, dynamic port allocation, and a bloom of new distributed applications - has weakened the value of this approach. We analyze three alternative mechanisms using statistical and structural content models for automatically identifying traffic that uses the same application-layer protocol, relying solely on flow content. In this manner, known applications may be identified regardless of port number, while traffic from one unknown application will be identified as distinct from another. We evaluate each mechanism's classification performance using real-world traffic traces from multiple sites.
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.
38376850
A Shopping Negotiation Agent That Adapts to User Preferences
This paper describes a shopping negotiation agent that can adapt user preferences and automatically negotiate with its counter party on behalf of a user it represents. The agent is built on a basis of the proposed negotiation model, the enhanced extended Bazaar model, which is a sequence of decision making model of negotiation with exploiting common knowledge, public information, and game theory. Since different users can have different preferences, it is important for the agent to have adaptation to different user preferences. This can be achieved by acquiring user preferences, tracing user's behavior on Web and mapping the behavior to a set of the preference parameters, creating the negotiation model class, and generating an instance negotiation model object with new/updated preference parameters.
34011902
On the correct convergence of the EM algorithm for Gaussian mixtures
It is well-known that the EM algorithm generally converges to a local maximum likelihood estimate. However, there have been many evidences to show that the EM algorithm can converge correctly to the true parameters as long as the overlap of Gaussians in the sample data is small enough. This paper studies this correct convergence problem asymptotically on the EM algorithm for Gaussian mixtures. It has been proved that the EM algorithm becomes a contraction mapping of the parameters within a neighborhood of the consistent solution of the maximum likelihood when the measure of average overlap among Gaussians in the original mixture is small enough and the number of samples is large enough. That is, if the initial parameters are set within the neighborhood, the EM algorithm will always converge to the consistent solution, i.e., the expected result. Moreover, the simulation results further demonstrate that this correct convergence neighborhood becomes larger as the average overlap becomes smaller.
5457719
Macro University
This paper discusses the technical issues related to the Macro University framework. First we present the characteristics of the Macro University, from which the design principles are derived. Then we describe Macro University's software architecture and networking infrastructure. Since the Macro University is a federation of virtual universities, the format and protocol for open information exchange will be very important. Another often neglected issue is the technical tools to facilitate evaluation and assessment. A third issue is a universal interface for distance learning.