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.

Executable Analysis using Abstract Interpretation with Circular Linear Progressions

We propose a new abstract domain for static analysis of executable code. Concrete states are abstracted using circular linear progressions (CLPs). CLPs model computations using a finite word length as is seen in any real life processor. The finite abstraction allows handling overflow scenarios in a natural and straight-forward manner. Abstract transfer functions have been defined for a wide range of operations which makes this domain easily applicable for analyzing code for a wide range of ISAs. CLPs combine the scalability of interval domains with the discreteness of linear congruence domains. We also present a novel, lightweight method to track linear equality relations between static objects that is used by the analysis to improve precision. The analysis is efficient, the total space and time overhead being quadratic in the number of static objects being tracked.

WCET Estimation for Executables in the Presence of Data Caches

This paper describes techniques to estimate the worst case execution time of executable code on architectures with data caches. The underlying mechanism is Abstract Interpretation, which is used for the dual purposes of tracking address computations and cache behavior. A simultaneous numeric and pointer analysis using an abstraction for discrete sets of values computes safe approximations of access addresses which are then used to predict cache behavior using Must Analysis. A heuristic is also proposed which generates likely worst case estimates. It can be used in soft real time systems and also for reasoning about the tightness of the safe estimate. The analysis methods can handle programs with non-affine access patterns, for which conventional Presburger Arithmetic formulations or Cache Miss Equations do not apply. The precision of the estimates is user-controlled and can be traded off against analysis time. Executables are analyzed directly, which, apart from enhancing precision, renders the method language independent.

Partial Flow Sensitivity

Compiler optimizations need precise and scalable analyses to discover program properties. We propose a partially flow-sensitive framework that tries to draw on the scalability of flow-insensitive algorithms while providing more precision at some specific program points. Provided with a set of critical nodes — basic blocks at which more precise information is desired — our partially flow-sensitive algorithm computes a reduced control-flow graph by collapsing some sets of non-critical nodes. The algorithm is more scalable than a fully flow-sensitive one as, assuming that the number of critical nodes is small, the reduced flow-graph is much smaller than the original flow-graph. At the same time, a much more precise information is obtained at certain program points than would had been obtained from a flow-insensitive algorithm.

0.84 ps Resolution Clock Skew Measurement via Subsampling

An all-digital on-chip clock skew measurement system via subsampling is presented. The clock nodes are sub-sampled with a near-frequency asynchronous sampling clock to result in beat signals which are themselves skewed in the same proportion but on a larger time scale. The beat signals are then suitably masked to extract only the skews of the rising edges of the clock signals. We propose a histogram of the arithmetic difference of the beat signals which decouples the relationship of clock jitter to the minimum measurable skew, and allows skews arbitrarily close to zero to be measured with a precision limited largely by measurement time, unlike the conventional XOR based histogram approach. We also analytically show that the proposed approach leads to an unbiased estimate of skew. The measured results from a 65 nm delay measurement front-end indicate that for an input skew range of +/- 1 fan-out-of-4 (FO4) delay, +/- 3 sigma resolution of 0.84 ps can be obtained with an integral error of 0.65 ps. We also experimentally demonstrate that a frequency modulation on a sampling clock maintains precision, indicating the robustness of the technique to jitter. We also show how FM modulation helps in restoring precision in case of rationally related clocks.

The standard enthalpy and entropy of formation of Rh2O3 - A third-law optimization

The standard Gibbs energy of formation of Rh203 at high temperature has been determined recently with high precision. The new data are significantly different from those given in thermodynamic compilations.Accurate values for enthalpy and entropy of formation at 298.15 K could not be evaluated from the new data,because reliable values for heat capacity of Rh2O3 were not available. In this article, a new measurement of the high temperature heat capacity of Rh2O3 using differential scanning calorimetry (DSC) is presented.The new values for heat capacity also differ significantly from those given in compilations. The information on heat capacity is coupled with standard Gibbs energy of formation to evaluate values for standard enthalpy and entropy of formation at 289.15 K using a multivariate analysis. The results suggest a major revision in thermodynamic data for Rh2O3. For example, it is recommended that the standard entropy of Rh203 at 298.15 K be changed from 106.27 J mol-' K-'given in the compilations of Barin and Knacke et al. to 75.69 J mol-' K". The recommended revision in the standard enthalpy of formation is from -355.64 kJ mol-'to -405.53 kJ mol".

Refinement of thermodynamic properties of ReO2

The standard Gibbs energy of formation of ReO2 in the temperature range from 900 to 1200 K has been determined with high precision using a novel apparatus incorporating a buffer electrode between reference and working electrodes. The role of the buffer electrode was to absorb the electrochemical flux of oxygen through the solid electrolyte from the electrode with higher oxygen chemical potential to the electrode with lower oxygen potential. It prevented the polarization of the measuring electrode and ensured accurate data. The Re+ReO2 working electrode was placed in a closed stabilized-zirconia crucible to prevent continuous vaporization of Re2O7 at high temperatures. The standard Gibbs energy of the formation of ReO2 can be represented by the equation View the MathML source Accurate values of low and high temperature heat capacity of ReO2 are available in the literature. The thermal data are coupled with the standard Gibbs energy of formation, obtained in this study, to evaluate the standard enthalpy of formation of ReO2 at 298.15 K by the ‘third law’ method. The value of standard enthalpy of formation at 298.15 K is: View the MathML source(ReO2)/kJ mol−1=−445.1 (±0.2). The uncertainty estimate includes both random (2σ) and systematic errors.

Tip Motion Control and Scanning of a Reorientable Micromanipulator With Axially Located Tip

Two-axis micromanipulators, whose tip orientation and position can be controlled in real time in the scanning plane, enable versatile probing systems for 2.5-D nanometrology. The key to achieve high-precision probing systems is to accurately control the interaction point of the manipulator tip when its orientation is changed. This paper presents the development of a probing system wherein the deviation in the end point due to large orientation changes is controlled to within 10 nm. To achieve this, a novel micromanipulator design is first proposed, wherein the end point of the tip is located on the axis of rotation. Next, the residual tip motion caused by fabrication error and actuation crosstalk is modeled and a systematic method to compensate it is presented. The manipulator is fabricated and the performance of the developed scheme to control tip position during orientation change is experimentally validated. Subsequently, the two-axis probing system is demonstrated to scan the full top surface of a micropipette down to a diameter of 300 nm.

Null Dereference Verification via Over-approximated Weakest Pre-conditions Analysis

Null dereferences are a bane of programming in languages such as Java. In this paper we propose a sound, demand-driven, inter-procedurally context-sensitive dataflow analysis technique to verify a given dereference as safe or potentially unsafe. Our analysis uses an abstract lattice of formulas to find a pre-condition at the entry of the program such that a null-dereference can occur only if the initial state of the program satisfies this pre-condition. We use a simplified domain of formulas, abstracting out integer arithmetic, as well as unbounded access paths due to recursive data structures. For the sake of precision we model aliasing relationships explicitly in our abstract lattice, enable strong updates, and use a limited notion of path sensitivity. For the sake of scalability we prune formulas continually as they get propagated, reducing to true conjuncts that are less likely to be useful in validating or invalidating the formula. We have implemented our approach, and present an evaluation of it on a set of ten real Java programs. Our results show that the set of design features we have incorporated enable the analysis to (a) explore long, inter-procedural paths to verify each dereference, with (b) reasonable accuracy, and (c) very quick response time per dereference, making it suitable for use in desktop development environments.

Passive vibration isolation of reaction wheel disturbances using a low frequency flexible space platform

Reaction wheel assemblies (RWAs) are momentum exchange devices used in fine pointing control of spacecrafts. Even though the spinning rotor of the reaction wheel is precisely balanced to minimize emitted vibration due to static and dynamic imbalances, precision instrument payloads placed in the neighborhood can always be severely impacted by residual vibration forces emitted by reaction wheel assemblies. The reduction of the vibration level at sensitive payloads can be achieved by placing the RWA on appropriate mountings. A low frequency flexible space platform consisting of folded continuous beams has been designed to serve as a mount for isolating a disturbance source in precision payloads equipped spacecrafts. Analytical and experimental investigations have been carried out to test the usefulness of the low frequency flexible platform as a vibration isolator for RWAs. Measurements and tests have been conducted at varying wheel speeds, to quantify and characterize the amount of isolation obtained from the reaction wheel generated vibration. These tests are further extended to other variants of similar design in order to bring out the best isolation for given disturbance loads. Both time and frequency domain analysis of test data show that the flexible beam platform as a mount for reaction wheels is quite effective and can be used in spacecrafts for passive vibration control. (C) 2011 Elsevier Ltd. All rights reserved.

On pattern oriented software architecture for the grid

Precision, sophistication and economic factors in many areas of scientific research that demand very high magnitude of compute power is the order of the day. Thus advance research in the area of high performance computing is getting inevitable. The basic principle of sharing and collaborative work by geographically separated computers is known by several names such as metacomputing, scalable computing, cluster computing, internet computing and this has today metamorphosed into a new term known as grid computing. This paper gives an overview of grid computing and compares various grid architectures. We show the role that patterns can play in architecting complex systems, and provide a very pragmatic reference to a set of well-engineered patterns that the practicing developer can apply to crafting his or her own specific applications. We are not aware of pattern-oriented approach being applied to develop and deploy a grid. There are many grid frameworks that are built or are in the process of being functional. All these grids differ in some functionality or the other, though the basic principle over which the grids are built is the same. Despite this there are no standard requirements listed for building a grid. The grid being a very complex system, it is mandatory to have a standard Software Architecture Specification (SAS). We attempt to develop the same for use by any grid user or developer. Specifically, we analyze the grid using an object oriented approach and presenting the architecture using UML. This paper will propose the usage of patterns at all levels (analysis. design and architectural) of the grid development.

Performance of inherently compensated flat pad aerostatic bearings subject to dynamic perturbation forces

The importance of air bearing design is growing in engineering. As the trend to precision and ultra precision manufacture gains pace and the drive to higher quality and more reliable products continues, the advantages which can be gained from applying aerostatic bearings to machine tools, instrumentation and test rigs is becoming more apparent. The inlet restrictor design is significant for air bearings because it affects the static and dynamic performance of the air bearing. For instance pocketed orifice bearings give higher load capacity as compared to inherently compensated orifice type bearings, however inherently compensated orifices, also known as laminar flow restrictors are known to give highly stable air bearing systems (less prone to pneumatic hammer) as compared to pocketed orifice air bearing systems. However, they are not commonly used because of the difficulties encountered in manufacturing and assembly of the orifice designs. This paper aims to analyse the static and dynamic characteristics of inherently compensated orifice based flat pad air bearing system. Based on Reynolds equation and mass conservation equation for incompressible flow, the steady state characteristics are studied while the dynamic state characteristics are performed in a similar manner however, using the above equations for compressible flow. Steady state experiments were also performed for a single orifice air bearing and the results are compared to that obtained from theoretical studies. A technique to ease the assembly of orifices with the air bearing plate has also been discussed so as to make the manufacturing of the inherently compensated bearings more commercially viable. (c) 2012 Elsevier Inc. All rights reserved.

Spacelike pion form factor from analytic continuation and the onset of perturbative QCD

The factorization theorem for exclusive processes in perturbative QCD predicts the behavior of the pion electromagnetic form factor F(t) at asymptotic spacelike momenta t(= -Q(2)) < 0. We address the question of the onset energy using a suitable mathematical framework of analytic continuation, which uses as input the phase of the form factor below the first inelastic threshold, known with great precision through the Fermi-Watson theorem from pi pi elastic scattering, and the modulus measured from threshold up to 3 GeV by the BABAR Collaboration. The method leads to almost model-independent upper and lower bounds on the spacelike form factor. Further inclusion of the value of the charge radius and the experimental value at -2.45 GeV2 measured at JLab considerably increases the strength of the bounds in the region Q(2) less than or similar to 10 GeV2, excluding the onset of the asymptotic perturbative QCD regime for Q(2) < 7 GeV2. We also compare the bounds with available experimental data and with several theoretical models proposed for the low and intermediate spacelike region.

An Accurate Fractional Period Delay Generation System

An all-digital technique is proposed for generating an accurate delay irrespective of the inaccuracies of a controllable delay line. A subsampling technique-based delay measurement unit (DMU) capable of measuring delays accurately for the full period range is used as the feedback element to build accurate fractional period delays based on input digital control bits. The proposed delay generation system periodically measures and corrects the error and maintains it at the minimum value without requiring any special calibration phase. Up to 40x improvement in accuracy is demonstrated for a commercial programmable delay generator chip. The time-precision trade-off feature of the DMU is utilized to reduce the locking time. Loop dynamics are adjusted to stabilize the delay after the minimum error is achieved, thus avoiding additional jitter. Measurement results from a high-end oscilloscope also validate the effectiveness of the proposed system in improving accuracy.

Characterization of structural and free energy properties of promoters associated with Primary and Operon TSS in Helicobacter pylori genome and their orthologs

Promoter regions in the genomes of all domains of life show similar trends in several structural properties such as stability, bendability, curvature, etc. In current study we analysed the stability and bendability of various classes of promoter regions (based on the recent identification of different classes of transcription start sites) of Helicobacter pylori 26695 strain. It is found that primary TSS and operon-associated TSS promoters show significantly strong features in their promoter regions. DNA free-energy-based promoter prediction tool PromPredict was used to annotate promoters of different classes, and very high recall values (similar to 80%) are obtained for primary TSS. Orthologous genes from other strains of H. pylori show conservation of structural properties in promoter regions as well as coding regions. PromPredict annotates promoters of orthologous genes with very high recall and precision.