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.

Comparative Study of Protein Unfolding in Aqueous Urea and Dimethyl Sulfoxide Solutions: Surface Polarity, Solvent Specificity, and Sequence of Secondary Structure Melting

Elucidation of possible pathways between folded (native) and unfolded states of a protein is a challenging task, as the intermediates are often hard to detect. Here, we alter the solvent environment in a controlled manner by choosing two different cosolvents of water, urea, and dimethyl sulfoxide (DMSO) and study unfolding of four different proteins to understand the respective sequence of melting by computer simulation methods. We indeed find interesting differences in the sequence of melting of alpha helices and beta sheets in these two solvents. For example, in 8 M urea solution, beta-sheet parts of a protein are found to unfold preferentially, followed by the unfolding of alpha helices. In contrast, 8 M DMSO solution unfolds alpha helices first, followed by the separation of beta sheets for the majority of proteins. Sequence of unfolding events in four different alpha/beta proteins and also in chicken villin head piece (HP-36) both in urea and DMSO solutions demonstrate that the unfolding pathways are determined jointly by relative exposure of polar and nonpolar residues of a protein and the mode of molecular action of a solvent on that protein.

Divide and Conquer: Efficient Large-Scale Structure from Motion Using Graph Partitioning

Despite significant advances in recent years, structure-from-motion (SfM) pipelines suffer from two important drawbacks. Apart from requiring significant computational power to solve the large-scale computations involved, such pipelines sometimes fail to correctly reconstruct when the accumulated error in incremental reconstruction is large or when the number of 3D to 2D correspondences are insufficient. In this paper we present a novel approach to mitigate the above-mentioned drawbacks. Using an image match graph based on matching features we partition the image data set into smaller sets or components which are reconstructed independently. Following such reconstructions we utilise the available epipolar relationships that connect images across components to correctly align the individual reconstructions in a global frame of reference. This results in both a significant speed up of at least one order of magnitude and also mitigates the problems of reconstruction failures with a marginal loss in accuracy. The effectiveness of our approach is demonstrated on some large-scale real world data sets.

The Uniaxial Tensile Deformation of Ni Nanowire: Atomic-Scale Computer Simulations

The mechanical deformations of nickel nanowire subjected to uniaxial tensile strain at 300 K are simulated by using molecular dynamics with the quantum corrected Sutten-Chen many-body force field. We have used common neighbor analysis method to investigate the structural evolution of Ni nanowire during the elongation process. For the strain rate of 0.1%/ps, the elastic limit is up to about 11% strain with the yield stress of 8.6 GPa. At the elastic stage, the deformation is carried mainly through the uniform elongation of the distances between the layers (perpendicular to the Z-axis) while the atomic structure remains basically unchanged. With further strain, the slips in the {111} planes start to take place in order to accommodate the applied strain to carry the deformation partially, and subsequently the neck forms. The atomic rearrangements in the neck region result in a zigzag change in the stress-strain curve; the atomic structures beyond the region, however, have no significant changes. With the strain close to the point of the breaking, we observe the formation of a one-atom thick necklace in Ni nanowire. The strain rates have no significant effect on the deformation mechanism, but have some influence on the yield stress, the elastic limit, and the fracture strain of the nanowire.

Computer Simulation Of Random Sphere Packing In An Arbitrarily Shaped Container

Most simulations of random sphere packing concern a cubic or cylindric container with periodic boundary, containers of other shapes are rarely studied. In this paper, a new relaxation algorithm with pre-expanding procedure for random sphere packing in an arbitrarily shaped container is presented. Boundaries of the container are simulated by overlapping spheres which covers the boundary surface of the container. We find 0.4 similar to 0.6 of the overlap rate is a proper value for boundary spheres. The algorithm begins with a random distribution of small internal spheres. Then the expansion and relaxation procedures are performed alternately to increase the packing density. The pre-expanding procedure stops when the packing density of internal spheres reaches a preset value. Following the pre-expanding procedure, the relaxation and shrinking iterations are carried out alternately to reduce the overlaps of internal spheres. The pre-expanding procedure avoids the overflow problem and gives a uniform distribution of initial spheres. Efficiency of the algorithm is increased with the cubic cell background system and double link data structure. Examples show the packing results agree well with both computational and experimental results. Packing density about 0.63 is obtained by the algorithm for random sphere packing in containers of various shapes.

Collective evolution characteristics and computer simulation of short fatigue cracks

Fatigue testing was conducted using a kind of triangular isostress specimen to obtain the short-fatigue-crack behaviour of a weld low-carbon steel. The experimental results show that short cracks continuously initiate at slip bands within ferrite grain domains and the crack number per unit area gradually increases with increasing number of fatigue cycles. The dispersed short cracks possess an orientation preference, which is associated with the crystalline orientation of the relevant slip system. Based on the observed collective characteristics, computer modelling was carried out to simulate the evolution process of initiation, propagation and coalescence of short cracks. The simulation provides progressive displays which imitate the appearance of experimental observations. The results of simulation indicate that the crack path possesses a stable value of fractal dimension whereas the critical value of percolation covers a wide datum band, suggesting that the collective evolution process of short cracks is sensitive to the pattern of crack site distribution.

Digitized Processing Track Generation of a Computer Integrated Multi-Functional 5-Axis Laser Processing System

Based on the computer integrated and flexible laser processing system, an intelligent measuring sub-system was developed. A novel model has been built up to compensate the deviations of the main frame-structure, and a new 3-D laser tracker system is applied to adjust the accuracy of the system. To analyze the characteristic of all kind surfaces of automobile outer penal moulds and dies, classification of types of the surface、brim and ridge(or vale) area to be measured and processed has been established, resulting in one of the main processing functions of the laser processing system. According to different type of surfaces, a 2-D adaptive measuring method based on B?zier curve was developed; furthermore a 3-D adaptive measuring method based on Spline curve was also developed. According to the laser materials processing characteristics and data characteristics, necessary methods have been developed to generate processing tracks, they are explained in details. Measuring experiments and laser processing experiments were carried out to testify the above mentioned methods, which have been applied in the computer integrated and flexible laser processing system developed by the Institute of Mechanics, CAS.

TUNPOP: A simulation of the dynamics and structure of the yellowfin tuna stock and surface fishery of the Eastern Pacific Ocean

ENGLISH: Three distinct versions of TUNP0P, an age-structured computer simulation model of the eastern Pacific yellowfin tuna, Thunnus albacores, stock and surface tuna fishery, are used to reveal mechanisms which appear to have a significant effect on the fishery dynamics. Real data on this fishery are used to make deductions on the distribution of the fish and to show how that distribution might influence events in the fishery. The most important result of the paper is that the concept of the eastern Pacific yellowfin tuna stock as a homogeneous unit is inadequate to represent the recent history of the fishery. Inferences are made on the size and distribution of the underlying stock as well as its potential yield to the surface fishery as a result of alterations in the level and distribution of the effort. SPANISH: Se han empleado tres versiones diferentes de TUNP0P, un modelo de simulación de la computadora (basado en la estructura de la edad) de la población y la pesca epipelágica del atún aleta amarilla, Tbunnus albacares, del Pacífico oriental, para revelar los mecanismos que parecen tener un efecto importante en la dinámica pesquera. Se emplean los datos verdaderos de esta pesca para hacer deducciones sobre la distribución de los peces y para mostrar cómo puede influir esta distribución en los eventos de pesca. La conclusión más importante de este estudio es que el concepto de que la población del aleta amarilla del Pacífico oriental es una unidad homogénea, es inadecuado para representar la historia reciente de pesca. Se teoriza sobre la talla y distribución de la población subyacente como también sobre su producción potencial en la pesca epipelágica al cambiar el nivel y distribución del esfuerzo.

Influence of composition on the structure, electric and magnetic properties of Pd-Mn-P and Pd-Co-P amorphous alloys

The influence of composition on the structure and on the electric and magnetic properties of amorphous Pd-Mn-P and Pd-Co-P prepared by rapid quenching techniques were investigated in terms of (1) the 3d band filling of the first transition metal group, (2) the phosphorus concentration effect which acts as an electron donor and (3) the transition metal concentration.

The structure is essentially characterized by a set of polyhedra subunits essentially inverse to the packing of hard spheres in real space. Examination of computer generated distribution functions using Monte Carlo random statistical distribution of these polyhedra entities demonstrated tile reproducibility of the experimentally calculated atomic distribution function. As a result, several possible "structural parameters" are proposed such as: the number of nearest neighbors, the metal-to-metal distance, the degree of short-range order and the affinity between metal-metal and metal-metalloid. It is shown that the degree of disorder increases from Ni to Mn. Similar behavior is observed with increase in the phosphorus concentration.

The magnetic properties of Pd-Co-P alloys show that they are ferromagnetic with a Curie temperature between 272 and 399°K as the cobalt concentration increases from 15 to 50 at.%. Below 20 at.% Co the short-range exchange interactions which produce the ferromagnetism are unable to establish a long-range magnetic order and a peak in the magnetization shows up at the lowest temperature range . The electric resistivity measurements were performed from liquid helium temperatures up to the vicinity of the melting point (900°K). The thermomagnetic analysis was carried out under an applied field of 6.0 kOe. The electrical resistivity of Pd-Co-P shows the coexistence of a Kondo-like minimum with ferromagnetism. The minimum becomes less important as the transition metal concentration increases and the coefficients of ℓn T and T^2 become smaller and strongly temperature dependent. The negative magnetoresistivity is a strong indication of the existence of localized moment.

The temperature coefficient of resistivity which is positive for Pd- Fe-P, Pd-Ni-P, and Pd-Co-P becomes negative for Pd-Mn-P. It is possible to account for the negative temperature dependence by the localized spin fluctuation model and the high density of states at the Fermi energy which becomes maximum between Mn and Cr. The magnetization curves for Pd-Mn-P are typical of those resulting from the interplay of different exchange forces. The established relationship between susceptibility and resistivity confirms the localized spin fluctuation model. The magnetoresistivity of Pd-Mn-P could be interpreted in tenns of a short-range magnetic ordering that could arise from the Rudennan-Kittel type interactions.

I. The crystal structure of trimesic acid. II. Topics in crystallographic calculations

I. Trimesic acid (1, 3, 5-benzenetricarboxylic acid) crystallizes with a monoclinic unit cell of dimensions a = 26.52 A, b = 16.42 A, c = 26.55 A, and β = 91.53° with 48 molecules /unit cell. Extinctions indicated a space group of Cc or C2/c; a satisfactory structure was obtained in the latter with 6 molecules/asymmetric unit - C₅₄O₃₆H₃₆ with a formula weight of 1261 g. Of approximately 12,000 independent reflections within the CuK_α sphere, intensities of 11,563 were recorded visually from equi-inclination Weissenberg photographs.

The structure was solved by packing considerations aided by molecular transforms and two- and three-dimensional Patterson functions. Hydrogen positions were found on difference maps. A total of 978 parameters were refined by least squares; these included hydrogen parameters and anisotropic temperature factors for the C and O atoms. The final R factor was 0.0675; the final "goodness of fit" was 1.49. All calculations were carried out on the Caltech IBM 7040-7094 computer using the CRYRM Crystallographic Computing System.

The six independent molecules fall into two groups of three nearly parallel molecules. All molecules are connected by carboxylto- carboxyl hydrogen bond pairs to form a continuous array of sixmolecule rings with a chicken-wire appearance. These arrays bend to assume two orientations, forming pleated sheets. Arrays in different orientations interpenetrate - three molecules in one orientation passing through the holes of three parallel arrays in the alternate orientation - to produce a completely interlocking network. One third of the carboxyl hydrogen atoms were found to be disordered.

II. Optical transforms as related to x-ray diffraction patterns are discussed with reference to the theory of Fraunhofer diffraction.

The use of a systems approach in crystallographic computing is discussed with special emphasis on the way in which this has been done at the California Institute of Technology.

An efficient manner of calculating Fourier and Patterson maps on a digital computer is presented. Expressions for the calculation of to-scale maps for standard sections and for general-plane sections are developed; space-group-specific expressions in a form suitable for computers are given for all space groups except the hexagonal ones.

Expressions for the calculation of settings for an Eulerian-cradle diffractometer are developed for both the general triclinic case and the orthogonal case.

Photographic materials on pp. 4, 6, 10, and 20 are essential and will not reproduce clearly on Xerox copies. Photographic copies should be ordered.