An efficient reduction algorithm for computation of interconnect delay variability for statistical timing analysis in clock tree planning

In this paper, we propose a novel and efficient algorithm for modelling sub-65 nm clock interconnect-networks in the presence of process variation. We develop a method for delay analysis of interconnects considering the impact of Gaussian metal process variations. The resistance and capacitance of a distributed RC line are expressed as correlated Gaussian random variables which are then used to compute the standard deviation of delay Probability Distribution Function (PDF) at all nodes in the interconnect network. Main objective is to find delay PDF at a cheaper cost. Convergence of this approach is in probability distribution but not in mean of delay. We validate our approach against SPICE based Monte Carlo simulations while the current method entails significantly lower computational cost.

Persistence Problem in Two-Dimensional Fluid Turbulence

We present a natural framework for studying the persistence problem in two-dimensional fluid turbulence by using the Okubo-Weiss parameter Lambda to distinguish between vortical and extensional regions. We then use a direct numerical simulation of the two-dimensional, incompressible Navier-Stokes equation with Ekman friction to study probability distribution functions (PDFs) of the persistence times of vortical and extensional regions by employing both Eulerian and Lagrangian measurements. We find that, in the Eulerian case, the persistence-time PDFs have exponential tails; by contrast, this PDF for Lagrangian particles, in vortical regions, has a power-law tail with an exponent theta = 2.9 +/- 0.2.

Systematics of the magnetic-Prandtl-number dependence of homogeneous, isotropic magnetohydrodynamic turbulence

We present the results of our detailed pseudospectral direct numerical simulation (DNS) studies, with up to 1024(3) collocation points, of incompressible, magnetohydrodynamic (MHD) turbulence in three dimensions, without a mean magnetic field. Our study concentrates on the dependence of various statistical properties of both decaying and statistically steady MHD turbulence on the magnetic Prandtl number Pr-M over a large range, namely 0.01 <= Pr-M <= 10. We obtain data for a wide variety of statistical measures, such as probability distribution functions (PDFs) of the moduli of the vorticity and current density, the energy dissipation rates, and velocity and magnetic-field increments, energy and other spectra, velocity and magnetic-field structure functions, which we use to characterize intermittency, isosurfaces of quantities, such as the moduli of the vorticity and current density, and joint PDFs, such as those of fluid and magnetic dissipation rates. Our systematic study uncovers interesting results that have not been noted hitherto. In particular, we find a crossover from a larger intermittency in the magnetic field than in the velocity field, at large Pr-M, to a smaller intermittency in the magnetic field than in the velocity field, at low Pr-M. Furthermore, a comparison of our results for decaying MHD turbulence and its forced, statistically steady analogue suggests that we have strong universality in the sense that, for a fixed value of Pr-M, multiscaling exponent ratios agree, at least within our error bars, for both decaying and statistically steady homogeneous, isotropic MHD turbulence.

Popular mixed matchings

We study the problem of matching applicants to jobs under one-sided preferences; that is, each applicant ranks a non-empty subset of jobs under an order of preference, possibly involving ties. A matching M is said to be more popular than T if the applicants that prefer M to T outnumber those that prefer T to M. A matching is said to be popular if there is no matching more popular than it. Equivalently, a matching M is popular if phi(M, T) >= phi(T, M) for all matchings T, where phi(X, Y) is the number of applicants that prefer X to Y. Previously studied solution concepts based on the popularity criterion are either not guaranteed to exist for every instance (e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by considering mixed matchings. A mixed matching is simply a probability distribution over matchings in the input graph. The function phi that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching P is popular if phi(P, Q) >= phi(Q, P) for all mixed matchings Q. We show that popular mixed matchings always exist and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on the price of anarchy and price of stability of the popular matching problem. (C) 2010 Elsevier B.V. All rights reserved.

A Complete Characterization of an Optimal Timer Based Selection Scheme

Timer-based mechanisms are often used in several wireless systems to help a given (sink) node select the best helper node among many available nodes. Specifically, a node transmits a packet when its timer expires, and the timer value is a function of its local suitability metric. In practice, the best node gets selected successfully only if no other node's timer expires within a `vulnerability' window after its timer expiry. In this paper, we provide a complete closed-form characterization of the optimal metric-to-timer mapping that maximizes the probability of success for any probability distribution function of the metric. The optimal scheme is scalable, distributed, and much better than the popular inverse metric timer mapping. We also develop an asymptotic characterization of the optimal scheme that is elegant and insightful, and accurate even for a small number of nodes.

Particle dynamics in a turbulent particle–gas suspension at high Stokes number. Part 1. Velocity and acceleration distributions

The effect of fluid velocity fluctuations on the dynamics of the particles in a turbulent gas–solid suspension is analysed in the low-Reynolds-number and high Stokes number limits, where the particle relaxation time is long compared with the correlation time for the fluid velocity fluctuations, and the drag force on the particles due to the fluid can be expressed by the modified Stokes law. The direct numerical simulation procedure is used for solving the Navier–Stokes equations for the fluid, the particles are modelled as hard spheres which undergo elastic collisions and a one-way coupling algorithm is used where the force exerted by the fluid on the particles is incorporated, but not the reverse force exerted by the particles on the fluid. The particle mean and root-mean-square (RMS) fluctuating velocities, as well as the probability distribution function for the particle velocity fluctuations and the distribution of acceleration of the particles in the central region of the Couette (where the velocity profile is linear and the RMS velocities are nearly constant), are examined. It is found that the distribution of particle velocities is very different from a Gaussian, especially in the spanwise and wall-normal directions. However, the distribution of the acceleration fluctuation on the particles is found to be close to a Gaussian, though the distribution is highly anisotropic and there is a correlation between the fluctuations in the flow and gradient directions. The non-Gaussian nature of the particle velocity fluctuations is found to be due to inter-particle collisions induced by the large particle velocity fluctuations in the flow direction. It is also found that the acceleration distribution on the particles is in very good agreement with the distribution that is calculated from the velocity fluctuations in the fluid, using the Stokes drag law, indicating that there is very little correlation between the fluid velocity fluctuations and the particle velocity fluctuations in the presence of one-way coupling. All of these results indicate that the effect of the turbulent fluid velocity fluctuations can be accurately represented by an anisotropic Gaussian white noise.

Plume structure in high-Rayleigh-number convection

Near-wall structures in turbulent natural convection at Rayleigh numbers of $10^{10}$ to $10^{11}$ at A Schmidt number of 602 are visualized by a new method of driving the convection across a fine membrane using concentration differences of sodium chloride. The visualizations show the near-wall flow to consist of sheet plumes. A wide variety of large-scale flow cells, scaling with the cross-section dimension, are observed. Multiple large-scale flow cells are seen at aspect ratio (AR)= 0.65, while only a single circulation cell is detected at AR= 0.435. The cells (or the mean wind) are driven by plumes coming together to form columns of rising lighter fluid. The wind in turn aligns the sheet plumes along the direction of shear. the mean wind direction is seen to change with time. The near-wall dynamics show plumes initiated at points, which elongate to form sheets and then merge. Increase in rayleigh number results in a larger number of closely and regularly spaced plumes. The plume spacings show a common log–normal probability distribution function, independent of the rayleigh number and the aspect ratio. We propose that the near-wall structure is made of laminar natural-convection boundary layers, which become unstable to give rise to sheet plumes, and show that the predictions of a model constructed on this hypothesis match the experiments. Based on these findings, we conclude that in the presence of a mean wind, the local near-wall boundary layers associated with each sheet plume in high-rayleigh-number turbulent natural convection are likely to be laminar mixed convection type.

Universality and scaling behavior of injected power in elastic turbulence in wormlike micellar gel

We study the statistical properties of spatially averaged global injected power fluctuations for Taylor-Couette flow of a wormlike micellar gel formed by surfactant cetyltrimethylammonium tosylate. At sufficiently high Weissenberg numbers the shear rate, and hence the injected power p(t), at a constant applied stress shows large irregular fluctuations in time. The nature of the probability distribution function (PDF) of p(t) and the power-law decay of its power spectrum are very similar to that observed in recent studies of elastic turbulence for polymer solutions. Remarkably, these non-Gaussian PDFs can be well described by a universal, large deviation functional form given by the generalized Gumbel distribution observed in the context of spatially averaged global measures in diverse classes of highly correlated systems. We show by in situ rheology and polarized light scattering experiments that in the elastic turbulent regime the flow is spatially smooth but random in time, in agreement with a recent hypothesis for elastic turbulence.

Relay Precoder Optimization in MIMO-Relay Networks With Imperfect CSI

In this paper, we consider robust joint designs of relay precoder and destination receive filters in a nonregenerative multiple-input multiple-output (MIMO) relay network. The network consists of multiple source-destination node pairs assisted by a MIMO-relay node. The channel state information (CSI) available at the relay node is assumed to be imperfect. We consider robust designs for two models of CSI error. The first model is a stochastic error (SE) model, where the probability distribution of the CSI error is Gaussian. This model is applicable when the imperfect CSI is mainly due to errors in channel estimation. For this model, we propose robust minimum sum mean square error (SMSE), MSE-balancing, and relay transmit power minimizing precoder designs. The next model for the CSI error is a norm-bounded error (NBE) model, where the CSI error can be specified by an uncertainty set. This model is applicable when the CSI error is dominated by quantization errors. In this case, we adopt a worst-case design approach. For this model, we propose a robust precoder design that minimizes total relay transmit power under constraints on MSEs at the destination nodes. We show that the proposed robust design problems can be reformulated as convex optimization problems that can be solved efficiently using interior-point methods. We demonstrate the robust performance of the proposed design through simulations.

An Accurate Model for EESM and its Application to Analysis of CQI Feedback Schemes and Scheduling in LTE

The Effective Exponential SNR Mapping (EESM) is an indispensable tool for analyzing and simulating next generation orthogonal frequency division multiplexing (OFDM) based wireless systems. It converts the different gains of multiple subchannels, over which a codeword is transmitted, into a single effective flat-fading gain with the same codeword error rate. It facilitates link adaptation by helping each user to compute an accurate channel quality indicator (CQI), which is fed back to the base station to enable downlink rate adaptation and scheduling. However, the highly non-linear nature of EESM makes a performance analysis of adaptation and scheduling difficult; even the probability distribution of EESM is not known in closed-form. This paper shows that EESM can be accurately modeled as a lognormal random variable when the subchannel gains are Rayleigh distributed. The model is also valid when the subchannel gains are correlated in frequency or space. With some simplifying assumptions, the paper then develops a novel analysis of the performance of LTE's two CQI feedback schemes that use EESM to generate CQI. The comprehensive model and analysis quantify the joint effect of several critical components such as scheduler, multiple antenna mode, CQI feedback scheme, and EESM-based feedback averaging on the overall system throughput.

A nested linear codes approach to distributed function computation over subspaces

In this paper, we consider a distributed function computation setting, where there are m distributed but correlated sources X1,...,Xm and a receiver interested in computing an s-dimensional subspace generated by [X1,...,Xm]Γ for some (m × s) matrix Γ of rank s. We construct a scheme based on nested linear codes and characterize the achievable rates obtained using the scheme. The proposed nested-linear-code approach performs at least as well as the Slepian-Wolf scheme in terms of sum-rate performance for all subspaces and source distributions. In addition, for a large class of distributions and subspaces, the scheme improves upon the Slepian-Wolf approach. The nested-linear-code scheme may be viewed as uniting under a common framework, both the Korner-Marton approach of using a common linear encoder as well as the Slepian-Wolf approach of employing different encoders at each source. Along the way, we prove an interesting and fundamental structural result on the nature of subspaces of an m-dimensional vector space V with respect to a normalized measure of entropy. Here, each element in V corresponds to a distinct linear combination of a set {Xi}im=1 of m random variables whose joint probability distribution function is given.

Inversion of moments to retrieve joint probabilities in quantum sequential measurements

A sequence of moments obtained from statistical trials encodes a classical probability distribution. However, it is well known that an incompatible set of moments arises in the quantum scenario, when correlation outcomes associated with measurements on spatially separated entangled states are considered. This feature, viz., the incompatibility of moments with a joint probability distribution, is reflected in the violation of Bell inequalities. Here, we focus on sequential measurements on a single quantum system and investigate if moments and joint probabilities are compatible with each other. By considering sequential measurement of a dichotomic dynamical observable at three different time intervals, we explicitly demonstrate that the moments and the probabilities are inconsistent with each other. Experimental results using a nuclear magnetic resonance system are reported here to corroborate these theoretical observations, viz., the incompatibility of the three-time joint probabilities with those extracted from the moment sequence when sequential measurements on a single-qubit system are considered.

Optimal design of timer-based, distributed selection with unknown number of nodes

The timer-based selection scheme is a popular, simple, and distributed scheme that is used to select the best node from a set of available nodes. In it, each node sets a timer as a function of a local preference number called a metric, and transmits a packet when its timer expires. The scheme ensures that the timer of the best node, which has the highest metric, expires first. However, it fails to select the best node if another node transmits a packet within Delta s of the transmission by the best node. We derive the optimal timer mapping that maximizes the average success probability for the practical scenario in which the number of nodes in the system is unknown but only its probability distribution is known. We show that it has a special discrete structure, and present a recursive characterization to determine it. We benchmark its performance with ad hoc approaches proposed in the literature, and show that it delivers significant gains. New insights about the optimality of some ad hoc approaches are also developed.

Characterizing drought using the reliability-resilience-vulnerability concept

This study borrows the measures developed for the operation of water resources systems as a means of characterizing droughts in a given region. It is argued that the common approach of assessing drought using a univariate measure (severity or reliability) is inadequate as decision makers need assessment of the other facets considered here. It is proposed that the joint distribution of reliability, resilience, and vulnerability (referred to as RRV in a reservoir operation context), assessed using soil moisture data over the study region, be used to characterize droughts. Use is made of copulas to quantify the joint distribution between these variables. As reliability and resilience vary in a nonlinear but almost deterministic way, the joint probability distribution of only resilience and vulnerability is modeled. Recognizing the negative association between the two variables, a Plackett copula is used to formulate the joint distribution. The developed drought index, referred to as the drought management index (DMI), is able to differentiate the drought proneness of a given area when compared to other areas. An assessment of the sensitivity of the DMI to the length of the data segments used in evaluation indicates relative stability is achieved if the data segments are 5years or longer. The proposed approach is illustrated with reference to the Malaprabha River basin in India, using four adjoining Climate Prediction Center grid cells of soil moisture data that cover an area of approximately 12,000 km(2). (C) 2013 American Society of Civil Engineers.

Probabilistic least squares approach to ordinal regression

This paper proposes a novel approach to solve the ordinal regression problem using Gaussian processes. The proposed approach, probabilistic least squares ordinal regression (PLSOR), obtains the probability distribution over ordinal labels using a particular likelihood function. It performs model selection (hyperparameter optimization) using the leave-one-out cross-validation (LOO-CV) technique. PLSOR has conceptual simplicity and ease of implementation of least squares approach. Unlike the existing Gaussian process ordinal regression (GPOR) approaches, PLSOR does not use any approximation techniques for inference. We compare the proposed approach with the state-of-the-art GPOR approaches on some synthetic and benchmark data sets. Experimental results show the competitiveness of the proposed approach.