Comprehensive Path-sensitive Data-flow Analysis

Data-flow analysis is an integral part of any aggressive optimizing compiler. We propose a framework for improving the precision of data-flow analysis in the presence of complex control-flow. W initially perform data-flow analysis to determine those control-flow merges which cause the loss in data-flow analysis precision. The control-flow graph of the program is then restructured such that performing data-flow analysis on the resulting restructured graph gives more precise results. The proposed framework is both simple, involving the familiar notion of product automata, and also general, since it is applicable to any forward data-flow analysis. Apart from proving that our restructuring process is correct, we also show that restructuring is effective in that it necessarily leads to more optimization opportunities. Furthermore, the framework handles the trade-off between the increase in data-flow precision and the code size increase inherent in the restructuring. We show that determining an optimal restructuring is NP-hard, and propose and evaluate a greedy strategy. The framework has been implemented in the Scale research compiler, and instantiated for the specific problem of Constant Propagation. On the SPECINT 2000 benchmark suite we observe an average speedup of 4% in the running times over Wegman-Zadeck conditional constant propagation algorithm and 2% over a purely path profile guided approach.

A shortest path tree based algorithm for relay placement in a wireless sensor network and its performance analysis

In this paper, we study a problem of designing a multi-hop wireless network for interconnecting sensors (hereafter called source nodes) to a Base Station (BS), by deploying a minimum number of relay nodes at a subset of given potential locations, while meeting a quality of service (QoS) objective specified as a hop count bound for paths from the sources to the BS. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard. For this problem, we propose a polynomial time approximation algorithm based on iteratively constructing shortest path trees and heuristically pruning away the relay nodes used until the hop count bound is violated. Results show that the algorithm performs efficiently in various randomly generated network scenarios; in over 90% of the tested scenarios, it gave solutions that were either optimal or were worse than optimal by just one relay. We then use random graph techniques to obtain, under a certain stochastic setting, an upper bound on the average case approximation ratio of a class of algorithms (including the proposed algorithm) for this problem as a function of the number of source nodes, and the hop count bound. To the best of our knowledge, the average case analysis is the first of its kind in the relay placement literature. Since the design is based on a light traffic model, we also provide simulation results (using models for the IEEE 802.15.4 physical layer and medium access control) to assess the traffic levels up to which the QoS objectives continue to be met. (C) 2014 Elsevier B.V. All rights reserved.

Path Sensitive Cache Analysis Using Cache Miss Paths

Cache analysis plays a very important role in obtaining precise Worst Case Execution Time (WCET) estimates of programs for real-time systems. While Abstract Interpretation based approaches are almost universally used for cache analysis, they fail to take advantage of its unique requirement: it is not necessary to find the guaranteed cache behavior that holds across all executions of a program. We only need the cache behavior along one particular program path, which is the path with the maximum execution time. In this work, we introduce the concept of cache miss paths, which allows us to use the worst-case path information to improve the precision of AI-based cache analysis. We use Abstract Interpretation to determine the cache miss paths, and then integrate them in the IPET formulation. An added advantage is that this further allows us to use infeasible path information for cache analysis. Experimentally, our approach gives more precise WCETs as compared to AI-based cache analysis, and we also provide techniques to trade-off analysis time with precision to provide scalability.

A critical analysis of the shear difference method

The shear difference method which is commonly used for the separation of normal stresses using photoelastic techniques depends on the step-by-step integration of one of the differential equations of equilibrium. It is assumed that the isoclinic and the isochromatic parameters measured by the conventional methods pertain to the state of stress at the midpoint of the light path. In practice, a slice thin enough for the above assumption to be true and at the same time thick enough to give differences in the shear-stress values over the thickness is necessary. The paper discusses the errors introduced in the isoclinic and isochromatic values by the conventional methods neglecting the variation of stresses along the light path. It is shown that while the error introduced in the measurement of the isochromatic parameter may not be serious, the error caused in the isoclinic measurement may lead to serious errors. Since the shear-difference method involves step-by-step integration the error introduced will be of a cumulative nature.

Sustainable bioenergy for India: Technical, economic and policy analysis

India's energy challenges are multi-pronged. They are manifested through growing demand for modern energy carriers, a fossil fuel dominated energy system facing a severe resource crunch, the need for creating access to quality energy for the large section of deprived population, vulnerable energy security, local and global pollution regimes and the need for sustaining economic development. Renewable energy is considered as one of the most promising alternatives. Recognizing this potential, India has been implementing one of the largest renewable energy programmes in the world. Among the renewable energy technologies. bioenergy has a large diverse portfolio including efficient biomass stoves, biogas, biomass combustion and gasification and process heat and liquid fuels. India has also formulated and implemented a number of innovative policies and programmes to promote bioenergy technologies. However, according to some preliminary studies, the success rate is marginal compared to the potential available. This limited success is a clear indicator of the need for a serious reassessment of the bioenergy programme. Further, a realization of the need for adopting a sustainable energy path to address the above challenges will be the guiding force in this reassessment. In this paper an attempt is made to consider the potential of bioenergy to meet the rural energy needs: (I) biomass combustion and gasification for electricity; (2) biomethanation for cooking energy (gas) and electricity; and (3) efficient wood-burning devices for cooking. The paper focuses on analysing the effectiveness of bioenergy in creating this rural energy access and its sustainability in the long run through assessing: the demand for bioenergy and potential that could be created; technologies, status of commercialization and technology transfer and dissemination in India; economic and environmental performance and impacts: bioenergy policies, regulatory measures and barrier analysis. The whole assessment aims at presenting bioenergy as an integral part of a sustainable energy strategy for India. The results show that bioenergy technology (BET) alternatives compare favourably with the conventional ones. The cost comparisons show that the unit costs of BET alternatives are in the range of 15-187% of the conventional alternatives. The climate change benefits in terms of carbon emission reductions are to the tune of 110 T C per year provided the available potential of BETs are utilized.

Capturability analysis of a geometric guidance law in relative velocity space

In this paper, a relative velocity approach is used to analyze the capturability of a geometric guidance law. Point mass models are assumed for both the missile and the target. The speeds of the missile and target are assumed to remain constant throughout the engagement. Lateral acceleration, obtained from the guidance law, is applied to change the path of the missile. The kinematic equations for engagements in the horizontal plane are derived in the relative velocity space. Some analytical results for the capture region are obtained for non-maneuvering and maneuvering targets. For non-maneuvering targets it is enough for the navigation gain to be a constant to intercept the target, while for maneuvering targets a time varying navigation gain is needed for interception. These results are then verified through numerical simulations.

Design and analysis of rate aware ad hoc 802.11 networks

802.11 WLANs are characterized by high bit error rate and frequent changes in network topology. The key feature that distinguishes WLANs from wired networks is the multi-rate transmission capability, which helps to accommodate a wide range of channel conditions. This has a significant impact on higher layers such as routing and transport levels. While many WLAN products provide rate control at the hardware level to adapt to the channel conditions, some chipsets like Atheros do not have support for automatic rate control. We first present a design and implementation of an FER-based automatic rate control state machine, which utilizes the statistics available at the device driver to find the optimal rate. The results show that the proposed rate switching mechanism adapts quite fast to the channel conditions. The hop count metric used by current routing protocols has proven itself for single rate networks. But it fails to take into account other important factors in a multi-rate network environment. We propose transmission time as a better path quality metric to guide routing decisions. It incorporates the effects of contention for the channel, the air time to send the data and the asymmetry of links. In this paper, we present a new design for a multi-rate mechanism as well as a new routing metric that is responsive to the rate. We address the issues involved in using transmission time as a metric and presents a comparison of the performance of different metrics for dynamic routing.

Communication pathways from the anti-codon region to the aminoacylation site in Methionyl tRNA Synthetase: Molecular dynamics simulations and the structure network analysis

The enzymes of the family of tRNA synthetases perform their functions with high precision by synchronously recognizing the anticodon region and the aminoacylation region, which are separated by ?70 in space. This precision in function is brought about by establishing good communication paths between the two regions. We have modeled the structure of the complex consisting of Escherichia coli methionyl-tRNA synthetase (MetRS), tRNA, and the activated methionine. Molecular dynamics simulations have been performed on the modeled structure to obtain the equilibrated structure of the complex and the cross-correlations between the residues in MetRS have been evaluated. Furthermore, the network analysis on these simulated structures has been carried out to elucidate the paths of communication between the activation site and the anticodon recognition site. This study has provided the detailed paths of communication, which are consistent with experimental results. Similar studies also have been carried out on the complexes (MetRS + activated methonine) and (MetRS + tRNA) along with ligand-free native enzyme. A comparison of the paths derived from the four simulations clearly has shown that the communication path is strongly correlated and unique to the enzyme complex, which is bound to both the tRNA and the activated methionine. The details of the method of our investigation and the biological implications of the results are presented in this article. The method developed here also could be used to investigate any protein system where the function takes place through long-distance communication.

Role of elasto-plastic analysis under cyclic loading in fatigue crack growth studies

Linear Elastic Fracture Mechanics (LEFM) has been widely used in the past for fatigue crack growth studies, but this is acceptable only in situations which are within small scale yielding (SSY). In many practical structural components, conditions of SSY could be violated and one has to look for fracture criteria based on elasto-plastic analysis. Crack closure phenomenon, one of the most striking discoveries based on inelastic deformations during crack growth, has significant effect on fatigue crack growth rate. Numerical simulation of this phenomenon is computationally intensive and involved but has been successfully implemented. Stress intensity factors and strain energy release rates lose their meaning, J-integral (or its incremental) values are applicable only in specific situations, whereas alternate path independent integrals have been proposed in the literature for use with elasto-plastic fracture mechanics (EPFM) based criteria. This paper presents certain salient features of two independent finite element (numerical) studies of relevance to fatigue crack growth, where elasto-plastic analysis becomes significant. These problems can only be handled in the current day computational environment, and would have been only a dream just a few years ago.

Synthesis of path generating flexible-link mechanisms

Flexible-link mechanisms are those linkage mechanisms (or structures) which are capable of motion by virtue of elastic deformation of one or more;links. In such mechanisms a single flexible link; can replace several rigid links and joints resulting in fewer links, fewer pin joints, reduced overall weight and reduced mechanical error. In spite of such clear advantages, contributions toward flexible-link mechanisms remain very scarce. The area of flexible-link mechanisms offers much scope for further exploration. This paper attempts to show the potential of flexible-link mechanisms in accomplishing a kinematic task like path generation. Synthesis of a four-bar mechanism with a flexible rocker for circular and straight line path generation is carried out. Displacement analysis of the structure is carried out using finite element method (FEM) and synthesis is formulated and solved as an optimization problem. Several numerical examples are presented for illustration. Based on the results obtained with these examples, the flexible-link mechanism considered shows good promise for-path generation.

New Concepts for Three-Dimensional Shape Analysis

A new approach to machine representation and analysis of three-dimensional objects is presented. The representation, based on the notion of "skeleton" of an object leads to a scheme for comparing two given object views for shape relations. The objects are composed of long, thin, rectangular prisms joined at their ends. The input picture to the program is the digitized line drawing portraying the three-dimensional object. To compare two object views, two characteristic vertices called "cardinal point" and "end-cardinal point," occurring consistently at the bends and open ends of the object are detected. The skeletons are then obtained as a connected path passing through these points. The shape relationships between the objects are then obtained from the matching characteristics of their skeletons. The method explores the possibility of a more detailed and finer analysis leading to detection of features like symmetry, asymmetry and other shape properties of an object.

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.

Analysis of residual tropical cemented soil behaviour

In -situ soils in gee-material spectrum might arise due to sedimentation or could be non-sedimentary residual formations. The inherent nature and diversity of geological processes involved in the soil formation stage itself are responsible for a wide variability in the in-situ state of the soil. In this paper the possibility of analyses to arrive at engineering parameters of residual soils with varied degrees of residual or acquired cementation by the use of physical and in-situ parameters normally determined in routine investigations, are examined. An Intrinsic State Line,(ISL), with reference to an intrinsic state parameter (e/e(L)) and its variation with effective stress for reconstituted clays has been developed for residual tropical soils of non-sedimentary origin. In relation to the Intrinsic State Line (ISL), the undisturbed state, e, the potential parameter, e(L), along with the overburden pressure data has been analyzed to identify the dominance of cementation or stress history or both in controlling the compressibility and strength behaviour of natural residual soil. The location of yield stress point in relation to the ISL, pre-, and post- yield stress, compression indices along the e- log sigma(v) path provide a simple means to the analysis of the compressibility characteristics of cemented soils for analysis.

Modelling and analysis of new coolstreaming for P2P IPTV

Peer to peer networks are being used extensively nowadays for file sharing, video on demand and live streaming. For IPTV, delay deadlines are more stringent compared to file sharing. Coolstreaming was the first P2P IPTV system. In this paper, we model New Coolstreaming (newer version of Coolstreaming) via a queueing network. We use two time scale decomposition of Markov chains to compute the stationary distribution of number of peers and the expected number of substreams in the overlay which are not being received at the required rate due to parent overloading. We also characterize the end-to-end delay encountered by a video packet received by a user and originated at the server. Three factors contribute towards the delay. The first factor is the mean shortest path length between any two overlay peers in terms of overlay hops of the partnership graph which is shown to be O (log n) where n is the number of peers in the overlay. The second factor is the mean number of routers between any two overlay neighbours which is seen to be at most O (log N-I) where N-I is the number of routers in the internet. Third factor is the mean delay at a router in the internet. We provide an approximation of this mean delay E W]. Thus, the mean end to end delay in New Coolstreaming is shown to be upper bounded by O (log E N]) (log N-I) E (W)] where E N] is the mean number of peers at a channel.

GYROSONICS: SIGNATURE ANALYSIS AND REDUCED-ORDER MODELS

In this paper, the authors study the structure of a novel binaural sound with a certain phase and amplitude modulation and the response to this excitation when it is applied to natural rewarding circuit of human brain through auditory neural pathways. This novel excitation, also referred to as gyrosonic excitation in this work, has been found to have interesting effects such as stabilization effects on the left and right hemispheric brain signaling as captured by Galvanic Skin Resistance (GSR) measurements, control of cardiac rhythms (observed from ECG signals), mitigation of psychosomatic syndrome, and mitigation of migraine pain. Experimental data collected from human subjects are presented, and these data are examined to categorize the extent of systems disorder and reinforcement reward due to the gyrosonic stimulus. A multi-path reduced-order model has been developed to analyze the GSR signals. The filtered results are indicative of complicated reinforcing reward patterns due to the gyrosonic stimulation when it is used as a control input for patients with psychosomatic and cardiac disorders.