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.

Influence of system size on spatiotemporal dynamics of a model for plastic instability: Projecting low-dimensional and extensive chaos

This work is a continuation of our efforts to quantify the irregular scalar stress signals from the Ananthakrishna model for the Portevin-Le Chatelier instability observed under constant strain rate deformation conditions. Stress related to the spatial average of the dislocation activity is a dynamical variable that also determines the time evolution of dislocation densities. We carry out detailed investigations on the nature of spatiotemporal patterns of the model realized in the form of different types of dislocation bands seen in the entire instability domain and establish their connection to the nature of stress serrations. We then characterize the spatiotemporal dynamics of the model equations by computing the Lyapunov dimension as a function of the drive parameter. The latter scales with the system size only for low strain rates, where isolated dislocation bands are seen, and at high strain rates, where fully propagating bands are seen. At intermediate applied strain rates corresponding to the partially propagating bands, the Lyapunov dimension exhibits two distinct slopes, one for small system sizes and another for large. This feature is rationalized by demonstrating that the spatiotemporal patterns for small system sizes are altered from the partially propagating band types to isolated burst type. This in turn allows us to reconfirm that low-dimensional chaos is projected from the stress signals as long as there is a one-to-one correspondence between the bursts of dislocation bands and the stress drops. We then show that the stress signals in the regime of partially to fully propagative bands have features of extensive chaos by calculating the correlation dimension density. We also show that the correlation dimension density also depends on the system size. A number of issues related to the system size dependence of the Lyapunov dimension density and the correlation dimension density are discussed.

Projecting low and extensive dimensional chaos from spatio-temporal dynamics

We review the spatio-temporal dynamical features of the Ananthakrishna model for the Portevin-Le Chatelier effect, a kind of plastic instability observed under constant strain rate deformation conditions. We then establish a qualitative correspondence between the spatio-temporal structures that evolve continuously in the instability domain and the nature of the irregularity of the scalar stress signal. Rest of the study is on quantifying the dynamical information contained in the stress signals about the spatio-temporal dynamics of the model. We show that at low applied strain rates, there is a one-to-one correspondence with the randomly nucleated isolated bursts of mobile dislocation density and the stress drops. We then show that the model equations are spatio-temporally chaotic by demonstrating the number of positive Lyapunov exponents and Lyapunov dimension scale with the system size at low and high strain rates. Using a modified algorithm for calculating correlation dimension density, we show that the stress-strain signals at low applied strain rates corresponding to spatially uncorrelated dislocation bands exhibit features of low dimensional chaos. This is made quantitative by demonstrating that the model equations can be approximately reduced to space independent model equations for the average dislocation densities, which is known to be low-dimensionally chaotic. However, the scaling regime for the correlation dimension shrinks with increasing applied strain rate due to increasing propensity for propagation of the dislocation bands. The stress signals in the partially propagating to fully propagating bands turn to have features of extensive chaos.

Modelling the impact of extensive irrigation on the groundwater resources

Drastic groundwater resource depletion due to excessive extraction for irrigation is a major concern in many parts of India. In this study, an attempt was made to simulate the groundwater scenario of the catchment using ArcSWAT. Due to the restriction on the maximum initial storage, the deep aquifer component in ArcSWAT was found to be insufficient to represent the excessive groundwater depletion scenario. Hence, a separate water balance model was used for simulating the deep aquifer water table. This approach is demonstrated through a case study for the Malaprabha catchment in India. Multi-site rainfall data was used to represent the spatial variation in the catchment climatology. Model parameters were calibrated using observed monthly stream flow data. Groundwater table simulation was validated using the qualitative information available from the field. The stream flow was found to be well simulated in the model. The simulated groundwater table fluctuation is also matching reasonably well with the field observations. From the model simulations, deep aquifer water table fluctuation was found very severe in the semi-arid lower parts of the catchment, with some areas showing around 60m depletion over a period of eight years. Copyright (c) 2012 John Wiley & Sons, Ltd.

The two-component signalling networks of Mycobacterium tuberculosis display extensive cross-talk in vitro

Two-component systems (TCSs), which contain paired sensor kinase and response regulator proteins, form the primary apparatus for sensing and responding to environmental cues in bacteria. TCSs are thought to be highly specific, displaying minimal cross-talk, primarily due to the co-evolution of the participating proteins. To assess the level of cross-talk between the TCSs of Mycobacterium tuberculosis, we mapped the complete interactome of the M. tuberculosis TCSs using phosphotransfer profiling. Surprisingly, we found extensive crosstalk among the M. tuberculosis TCSs, significantly more than that in the TCSs in Escherichia coli or Caulobacter crescentus, thereby offering an alternate to specificity paradigm in TCS signalling. Nearly half of the interactions we detected were significant novel cross-interactions, unravelling a potentially complex signalling landscape. We classified the TCSs into specific `one-to-one' and promiscuous `one-to-many' and `many-to-one' circuits. Using mathematical modelling, we deduced that the promiscuous signalling observed can explain several currently confounding observations about M. tuberculosis TCSs. Our findings suggest an alternative paradigm of bacterial signalling with significant cross-talk between TCSs yielding potentially complex signalling landscapes.