Scalable Context-Sensitive Points-To Analysis Using Multi-Dimensional Bloom Filters

Context-sensitive points-to analysis is critical for several program optimizations. However, as the number of contexts grows exponentially, storage requirements for the analysis increase tremendously for large programs, making the analysis non-scalable. We propose a scalable flow-insensitive context-sensitive inclusion-based points-to analysis that uses a specially designed multi-dimensional bloom filter to store the points-to information. Two key observations motivate our proposal: (i) points-to information (between pointer-object and between pointer-pointer) is sparse, and (ii) moving from an exact to an approximate representation of points-to information only leads to reduced precision without affecting correctness of the (may-points-to) analysis. By using an approximate representation a multi-dimensional bloom filter can significantly reduce the memory requirements with a probabilistic bound on loss in precision. Experimental evaluation on SPEC 2000 benchmarks and two large open source programs reveals that with an average storage requirement of 4MB, our approach achieves almost the same precision (98.6%) as the exact implementation. By increasing the average memory to 27MB, it achieves precision upto 99.7% for these benchmarks. Using Mod/Ref analysis as the client, we find that the client analysis is not affected that often even when there is some loss of precision in the points-to representation. We find that the NoModRef percentage is within 2% of the exact analysis while requiring 4MB (maximum 15MB) memory and less than 4 minutes on average for the points-to analysis. Another major advantage of our technique is that it allows to trade off precision for memory usage of the analysis.

Prioritizing constraint evaluation for efficient points-to analysis

Pervasive use of pointers in large-scale real-world applications continues to make points-to analysis an important optimization-enabler. Rapid growth of software systems demands a scalable pointer analysis algorithm. A typical inclusion-based points-to analysis iteratively evaluates constraints and computes a points-to solution until a fixpoint. In each iteration, (i) points-to information is propagated across directed edges in a constraint graph G and (ii) more edges are added by processing the points-to constraints. We observe that prioritizing the order in which the information is processed within each of the above two steps can lead to efficient execution of the points-to analysis. While earlier work in the literature focuses only on the propagation order, we argue that the other dimension, that is, prioritizing the constraint processing, can lead to even higher improvements on how fast the fixpoint of the points-to algorithm is reached. This becomes especially important as we prove that finding an optimal sequence for processing the points-to constraints is NP-Complete. The prioritization scheme proposed in this paper is general enough to be applied to any of the existing points-to analyses. Using the prioritization framework developed in this paper, we implement prioritized versions of Andersen's analysis, Deep Propagation, Hardekopf and Lin's Lazy Cycle Detection and Bloom Filter based points-to analysis. In each case, we report significant improvements in the analysis times (33%, 47%, 44%, 20% respectively) as well as the memory requirements for a large suite of programs, including SPEC 2000 benchmarks and five large open source programs.

Use of 45° pulse pair as a filter for pure-phase two-dimensional NMR spectroscopy

Conventionally two-dimensional NMR spectra are recorded in the absolute-intensity mode (1-4). It has recently been demonstrated that absorption-mode 2D spectra have much higher resolution and are the preferred mode of presentation, especially for 2D spectra of biomolecules (5-7). Indeed, any experimental scheme which yields phasemixed lineshapes is subject to modification to yield pure-phase spectra, even at the expense of intensity and anomalous multiplet structure (8-10). For this purpose two types of filters are already known: the z filter (9, 20) and the purging pulse (8, 10). In this note, we propose a 45” pulse pair as a filter for obtaining pure-phase 2D spectra, mainly for experiments in which the above filters do not yield pure-phase spectra.

A Unique Filter-Preserver Device for Digital Photonic Circuits

We discuss micro ring resonator based optical logic gates using Kerr-type nonlinearity. Resonant wavelength selectivity is one key factor in achieving the desired gate. Based on basic gates like AND gate, OR gate etc. We proceed to propose a 3-bit binary adder circuit.Due to the presence of more than a single wavelength, the system gets complicated as we increase the number of components in the circuit. Hence it has been observed that for efficient designing and functioning of digital circuits in optical domain, we need a device which can give single wavelength output, filtering out all other wavelengths and at the same time preserve the digital characteristics of the output. We propose such filter-preserver device based on micro ring resonator.

Area Efficient Loop Filter Design for Charge Pump Phase Locked Loop

In this paper, two new dual-path based area efficient loop filtercircuits are proposed for Charge Pump Phase Locked Loop (CPPLL). The proposed circuits were designed in 0.25 CSM analog process with 1.8V supply. The proposed circuits achievedup to 85% savings in capacitor area. Simulations showed goodmatch of the new circuits with the conventional circuit. Theproposed circuits are particularly useful in applications thatdemand low die area.

A conditionally linearized Monte Carlo filter in non-linear structural dynamics

State and parameter estimations of non-linear dynamical systems, based on incomplete and noisy measurements, are considered using Monte Carlo simulations. Given the measurements. the proposed method obtains the marginalized posterior distribution of an appropriately chosen (ideally small) subset of the state vector using a particle filter. Samples (particles) of the marginalized states are then used to construct a family of conditionally linearized system of equations and thus obtain the posterior distribution of the states using a bank of Kalman filters. Discrete process equations for the marginalized states are derived through truncated Ito-Taylor expansions. Increased analyticity and reduced dispersion of weights computed over a smaller sample space of marginalized states are the key features of the filter that help achieve smaller sample variance of the estimates. Numerical illustrations are provided for state/parameter estimations of a Duffing oscillator and a 3-DOF non-linear oscillator. Performance of the filter in parameter estimation is also assessed using measurements obtained through experiments on simple models in the laboratory. Despite an added computational cost, the results verify that the proposed filter generally produces estimates with lower sample variance over the standard sequential importance sampling (SIS) filter.

Analysis of a Filter Bag Reactor for gaseous pollution abatement

The conveying zone and the filter bag zone of a Filter Bag Reactor have been analysed as individual reactors. The gas and solid particles flow almost in plug flow through the pneumatic conveying section. In the filter bag the height of the packed column varies with time, a cell model has been used to calculate the concentration of outgoing stream. The total conversion obtained is the sum of conversions in each section of the reactor.

Analysis And Design Of Two Layered Ultra Wide Band Filter

Design of an Ultra Wide Band (UWB) filter over 3.1 GHz to 10.6 GHz using broad side coupled and spur lines in microstrip medium suitable for UWB communications has been presented in this paper. Parameters of broad side coupled lines have been appropriately chosen to achieve ultra wide band response. Spur lines have been incorporated at the input and output feed lines of the filter to improve the stop band rejection characteristics of the filter. Filter has been analyzed based on circuit models and full wave simulations. Experimental results of the filter designed using the proposed structure has been verified against the results obtained from circuit models and full wave simulations. The results match satisfactorily. Stop band rejection of better than 20 dB was obtained over the frequencies of 13 GHz to 18.2 GHz. Overall size of the filter is 40 x 18 x 0.787 mm(3).

A Minimax Filter for Systems with Large Plant Uncertainties Using Measurements Corrupted by Colored Noise

A minimax filter is derived to estimate the state of a system, using observations corrupted by colored noise, when large uncertainties in the plant dynamics and process noise are presen.

Wavefront filter for double-exposure holographic interferometry

Measurements of small phase shifts by double-exposure holographic interferometry are facilitated, and ambiguities in the sign of the phase shift eliminated, by introducing a background pattern of interference fringes. A simple and reliable optical system for this purpose utilizing a rotating wedge is described, with which fringes of any desired orientation and spacing can conveniently be obtained. It is shown how this system can be used under certain conditions for measurements of small mechanical deformations.

Constrained linear minimax filter for systems with large plant uncertainties

This paper presents a method of designing a minimax filter in the presence of large plant uncertainties and constraints on the mean squared values of the estimates. The minimax filtering problem is reformulated in the framework of a deterministic optimal control problem and the method of solution employed, invokes the matrix Minimum Principle. The constrained linear filter and its relation to singular control problems has been illustrated. For the class of problems considered here it is shown that the filter can he constrained separately after carrying out the mini maximization. Numorieal examples are presented to illustrate the results.

Constrained linear filter and its relation to singular optimal control

This paper presents an analysis of an optimal linear filter in the presence of constraints on the moan squared values of the estimates from the viewpoint of singular optimal control. The singular arc has been shown to satisfy the generalized Legcndrc-Clebseh condition and Jacobson's condition. Both the cases of white measurement noise and coloured measurement noise are considered. The constrained estimate is shown to be a linear transformation of the unconstrained Kalman estimate.

A semi-analytical particle filter for identification of nonlinear oscillators

Particle filters find important applications in the problems of state and parameter estimations of dynamical systems of engineering interest. Since a typical filtering algorithm involves Monte Carlo simulations of the process equations, sample variance of the estimator is inversely proportional to the number of particles. The sample variance may be reduced if one uses a Rao-Blackwell marginalization of states and performs analytical computations as much as possible. In this work, we propose a semi-analytical particle filter, requiring no Rao-Blackwell marginalization, for state and parameter estimations of nonlinear dynamical systems with additively Gaussian process/observation noises. Through local linearizations of the nonlinear drift fields in the process/observation equations via explicit Ito-Taylor expansions, the given nonlinear system is transformed into an ensemble of locally linearized systems. Using the most recent observation, conditionally Gaussian posterior density functions of the linearized systems are analytically obtained through the Kalman filter. This information is further exploited within the particle filter algorithm for obtaining samples from the optimal posterior density of the states. The potential of the method in state/parameter estimations is demonstrated through numerical illustrations for a few nonlinear oscillators. The proposed filter is found to yield estimates with reduced sample variance and improved accuracy vis-a-vis results from a form of sequential importance sampling filter.

A Kalman filter based strategy for linear structural system identification based on multiple static and dynamic test data

The problem of identification of stiffness, mass and damping properties of linear structural systems, based on multiple sets of measurement data originating from static and dynamic tests is considered. A strategy, within the framework of Kalman filter based dynamic state estimation, is proposed to tackle this problem. The static tests consists of measurement of response of the structure to slowly moving loads, and to static loads whose magnitude are varied incrementally; the dynamic tests involve measurement of a few elements of the frequency response function (FRF) matrix. These measurements are taken to be contaminated by additive Gaussian noise. An artificial independent variable τ, that simultaneously parameterizes the point of application of the moving load, the magnitude of the incrementally varied static load and the driving frequency in the FRFs, is introduced. The state vector is taken to consist of system parameters to be identified. The fact that these parameters are independent of the variable τ is taken to constitute the set of ‘process’ equations. The measurement equations are derived based on the mechanics of the problem and, quantities, such as displacements and/or strains, are taken to be measured. A recursive algorithm that employs a linearization strategy based on Neumann’s expansion of structural static and dynamic stiffness matrices, and, which provides posterior estimates of the mean and covariance of the unknown system parameters, is developed. The satisfactory performance of the proposed approach is illustrated by considering the problem of the identification of the dynamic properties of an inhomogeneous beam and the axial rigidities of members of a truss structure.

Learning Feature Trajectories Using Gabor Filter Bank for Human Activity Segmentation and Recognition

We describe a novel method for human activity segmentation and interpretation in surveillance applications based on Gabor filter-bank features. A complex human activity is modeled as a sequence of elementary human actions like walking, running, jogging, boxing, hand-waving etc. Since human silhouette can be modeled by a set of rectangles, the elementary human actions can be modeled as a sequence of a set of rectangles with different orientations and scales. The activity segmentation is based on Gabor filter-bank features and normalized spectral clustering. The feature trajectories of an action category are learnt from training example videos using dynamic time warping. The combined segmentation and the recognition processes are very efficient as both the algorithms share the same framework and Gabor features computed for the former can be used for the later. We have also proposed a simple shadow detection technique to extract good silhouette which is necessary for good accuracy of an action recognition technique.