Exploiting the Structure of the Constraint Graph for Efficient Points-to Analysis

Points-to analysis is a key compiler analysis. Several memory related optimizations use points-to information to improve their effectiveness. Points-to analysis is performed by building a constraint graph of pointer variables and dynamically updating it to propagate more and more points-to information across its subset edges. So far, the structure of the constraint graph has been only trivially exploited for efficient propagation of information, e.g., in identifying cyclic components or to propagate information in topological order. We perform a careful study of its structure and propose a new inclusion-based flow-insensitive context-sensitive points-to analysis algorithm based on the notion of dominant pointers. We also propose a new kind of pointer-equivalence based on dominant pointers which provides significantly more opportunities for reducing the number of pointers tracked during the analysis. Based on this hitherto unexplored form of pointer-equivalence, we develop a new context-sensitive flow-insensitive points-to analysis algorithm which uses incremental dominator update to efficiently compute points-to information. Using a large suite of programs consisting of SPEC 2000 benchmarks and five large open source programs we show that our points-to analysis is 88% faster than BDD-based Lazy Cycle Detection and 2x faster than Deep Propagation. We argue that our approach of detecting dominator-based pointer-equivalence is a key to improve points-to analysis efficiency.

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.

Freezing of the octahedral tilt near ferromagnetic transition and appearance of a glassy phase at low temperature driven by the tilt instabilities in SrRuO3

The emergence of low temperature glassy phase in widely known itinerant ferromagnet SrRuO3 is remotely understood. In order to understand this aspect, we have undertaken a detailed temperature dependent (5-250 K) neutron diffraction study. We observe a freezing of the octahedral tilt near the ferromagnetic transition and an unusual deviation in the octahedral tilt near the onset of low temperature spin glass like phase. A reduction of the ordered magnetic moment and a decline in the total integrated magnetic intensity is observed around the temperature where the glassy behaviour starts to appear. The magnetotransport study also reveals the possibility for an additional magnetic ordering by demonstrating a peak in magnetoresistance at the low temperature side as well. The neutron diffraction study presented here provides useful information to understand the observed unusual low temperature magnetic phenomena in SrRuO3.

DSA image registration using non-uniform MRF model and pivotal control points

In order to reduce the motion artifacts in DSA, non-rigid image registration is commonly used before subtracting the mask from the contrast image. Since DSA registration requires a set of spatially non-uniform control points, a conventional MRF model is not very efficient. In this paper, we introduce the concept of pivotal and non-pivotal control points to address this, and propose a non-uniform MRF for DSA registration. We use quad-trees in a novel way to generate the non-uniform grid of control points. Our MRF formulation produces a smooth displacement field and therefore results in better artifact reduction than that of registering the control points independently. We achieve improved computational performance using pivotal control points without compromising on the artifact reduction. We have tested our approach using several clinical data sets, and have presented the results of quantitative analysis, clinical assessment and performance improvement on a GPU. (C) 2013 Elsevier Ltd. All rights reserved.

Reversible shear-induced crystallization above equilibrium freezing temperature in a lyotropic surfactant system

We demonstrate a unique shear-induced crystallization phenomenon above the equilibrium freezing temperature (T-K(o)) in weakly swollen isotropic (L-i) and lamellar (L-alpha) mesophases with bilayers formed in a cationic-anionic mixed surfactant system. Synchrotron rheological X-ray diffraction study reveals the crystallization transition to be reversible under shear (i.e., on stopping the shear, the nonequilibrium crystalline phase L-c melts back to the equilibrium mesophase). This is different from the shear-driven crystallization below T-K(o), which is irreversible. Rheological optical observations show that the growth of the crystalline phase occurs through a preordering of the L-i phase to an L-alpha phase induced by shear flow, before the nucleation of the Lc phase. Shear diagram of the L-i phase constructed in the parameter space of shear rate ((gamma)) over dot vs. temperature exhibits L-i -> L-c and L-i -> L-alpha transitions above the equilibrium crystallization temperature (T-K(o)), in addition to the irreversible shear-driven nucleation of L-c in the L-i phase below T-K(o). In addition to revealing a unique class of nonequilibrium phase transition, the present study urges a unique approach toward understanding shear-induced phenomena in concentrated mesophases of mixed amphiphilic systems.

Succinate esters: odd-even effects in melting points

Dialkyl succinates show a pattern of alternating behavior in their melting points, as the number of C atoms in the alkane side chain increases, unlike in the dialkyl oxalates Joseph et al. (2011). Acta Cryst. B67, 525-534]. Dialkyl succinates with odd numbers of C atoms in the alkyl side chain show higher melting points than the immediately adjacent analogues with even numbers. The crystal structures and their molecular packing have been analyzed for a series of dialkyl succinates with 1 - 4 C atoms in the alkyl side chain. The energy difference (Delta E) between the optimized and observed molecular conformations, density, Kitaigorodskii packing index (KPI) and C-H center dot center dot center dot O interactions are considered to rationalize this behavior. In contrast to the dialkyl oxalates where a larger number of moderately strong C-H center dot center dot center dot O interactions were characteristic of oxalates with elevated melting points, here the molecular packing and the density play a major role in raising the melting point. On moving from oxalate to succinate esters the introduction of the C2 spacer adds two activated H atoms to the asymmetric unit, resulting in the formation of stronger C-H center dot center dot center dot O hydrogen bonds in all succinates. As a result the crystallinity of long-chain alkyl substituted esters improves enormously in the presence of hydrogen bonds from activated donors.

Robust tracking with interest points: A sparse representation approach

Visual tracking is an important task in various computer vision applications including visual surveillance, human computer interaction, event detection, video indexing and retrieval. Recent state of the art sparse representation (SR) based trackers show better robustness than many of the other existing trackers. One of the issues with these SR trackers is low execution speed. The particle filter framework is one of the major aspects responsible for slow execution, and is common to most of the existing SR trackers. In this paper,(1) we propose a robust interest point based tracker in l(1) minimization framework that runs at real-time with performance comparable to the state of the art trackers. In the proposed tracker, the target dictionary is obtained from the patches around target interest points. Next, the interest points from the candidate window of the current frame are obtained. The correspondence between target and candidate points is obtained via solving the proposed l(1) minimization problem. In order to prune the noisy matches, a robust matching criterion is proposed, where only the reliable candidate points that mutually match with target and candidate dictionary elements are considered for tracking. The object is localized by measuring the displacement of these interest points. The reliable candidate patches are used for updating the target dictionary. The performance and accuracy of the proposed tracker is benchmarked with several complex video sequences. The tracker is found to be considerably fast as compared to the reported state of the art trackers. The proposed tracker is further evaluated for various local patch sizes, number of interest points and regularization parameters. The performance of the tracker for various challenges including illumination change, occlusion, and background clutter has been quantified with a benchmark dataset containing 50 videos. (C) 2014 Elsevier B.V. All rights reserved.

Digital image analysis around isotropic points for photoelastic pattern recognition

Fringe tracking and fringe order assignment have become the central topics of current research in digital photoelasticity. Isotropic points (IPs) appearing in low fringe order zones are often either overlooked or entirely missed in conventional as well as digital photoelasticity. We aim to highlight image processing for characterizing IPs in an isochromatic fringe field. By resorting to a global analytical solution of a circular disk, sensitivity of IPs to small changes in far-field loading on the disk is highlighted. A local theory supplements the global closed-form solutions of three-, four-, and six-point loading configurations of circular disk. The local theoretical concepts developed in this paper are demonstrated through digital image analysis of isochromatics in circular disks subjected to three-and four-point loads. (C) 2015 Society of Photo-Optical Instrumentation Engineers (SPIE)

Use of polydispersity index as control parameter to study melting/freezing of Lennard-Jones system: Comparison among predictions of bifurcation theory with Lindemann criterion, inherent structure analysis and Hansen-Verlet rule

Using polydispersity index as an additional order parameter we investigate freezing/melting transition of Lennard-Jones polydisperse systems (with Gaussian polydispersity in size), especially to gain insight into the origin of the terminal polydispersity. The average inherent structure (IS) energy and root mean square displacement (RMSD) of the solid before melting both exhibit quite similar polydispersity dependence including a discontinuity at solid-liquid transition point. Lindemann ratio, obtained from RMSD, is found to be dependent on temperature. At a given number density, there exists a value of polydispersity index (delta (P)) above which no crystalline solid is stable. This transition value of polydispersity(termed as transition polydispersity, delta (P) ) is found to depend strongly on temperature, a feature missed in hard sphere model systems. Additionally, for a particular temperature when number density is increased, delta (P) shifts to higher values. This temperature and number density dependent value of delta (P) saturates surprisingly to a value which is found to be nearly the same for all temperatures, known as terminal polydispersity (delta (TP)). This value (delta (TP) similar to 0.11) is in excellent agreement with the experimental value of 0.12, but differs from hard sphere transition where this limiting value is only 0.048. Terminal polydispersity (delta (TP)) thus has a quasiuniversal character. Interestingly, the bifurcation diagram obtained from non-linear integral equation theories of freezing seems to provide an explanation of the existence of unique terminal polydispersity in polydisperse systems. Global bond orientational order parameter is calculated to obtain further insights into mechanism for melting.

Physical constraints, fundamental limits, and optimal locus of operating points for an inverted pendulum based actuated dynamic walker

The inverted pendulum is a popular model for describing bipedal dynamic walking. The operating point of the walker can be specified by the combination of initial mid-stance velocity (v(0)) and step angle (phi(m)) chosen for a given walk. In this paper, using basic mechanics, a framework of physical constraints that limit the choice of operating points is proposed. The constraint lines thus obtained delimit the allowable region of operation of the walker in the v(0)-phi(m) plane. A given average forward velocity v(x,) (avg) can be achieved by several combinations of v(0) and phi(m). Only one of these combinations results in the minimum mechanical power consumption and can be considered the optimum operating point for the given v(x, avg). This paper proposes a method for obtaining this optimal operating point based on tangency of the power and velocity contours. Putting together all such operating points for various v(x, avg,) a family of optimum operating points, called the optimal locus, is obtained. For the energy loss and internal energy models chosen, the optimal locus obtained has a largely constant step angle with increasing speed but tapers off at non-dimensional speeds close to unity.

Combining interest points and edges for content-based image retrieval

This paper presents a novel approach using combined features to retrieve images containing specific objects, scenes or buildings. The content of an image is characterized by two kinds of features: Harris-Laplace interest points described by the SIFT descriptor and edges described by the edge color histogram. Edges and corners contain the maximal amount of information necessary for image retrieval. The feature detection in this work is an integrated process: edges are detected directly based on the Harris function; Harris interest points are detected at several scales and Harris-Laplace interest points are found using the Laplace function. The combination of edges and interest points brings efficient feature detection and high recognition ratio to the image retrieval system. Experimental results show this system has good performance. © 2005 IEEE.