Automatic Compilation of MATLAB Programs for Synergistic Execution on Heterogeneous Processors

MATLAB is an array language, initially popular for rapid prototyping, but is now being increasingly used to develop production code for numerical and scientific applications. Typical MATLAB programs have abundant data parallelism. These programs also have control flow dominated scalar regions that have an impact on the program's execution time. Today's computer systems have tremendous computing power in the form of traditional CPU cores and throughput oriented accelerators such as graphics processing units(GPUs). Thus, an approach that maps the control flow dominated regions to the CPU and the data parallel regions to the GPU can significantly improve program performance. In this paper, we present the design and implementation of MEGHA, a compiler that automatically compiles MATLAB programs to enable synergistic execution on heterogeneous processors. Our solution is fully automated and does not require programmer input for identifying data parallel regions. We propose a set of compiler optimizations tailored for MATLAB. Our compiler identifies data parallel regions of the program and composes them into kernels. The problem of combining statements into kernels is formulated as a constrained graph clustering problem. Heuristics are presented to map identified kernels to either the CPU or GPU so that kernel execution on the CPU and the GPU happens synergistically and the amount of data transfer needed is minimized. In order to ensure required data movement for dependencies across basic blocks, we propose a data flow analysis and edge splitting strategy. Thus our compiler automatically handles composition of kernels, mapping of kernels to CPU and GPU, scheduling and insertion of required data transfer. The proposed compiler was implemented and experimental evaluation using a set of MATLAB benchmarks shows that our approach achieves a geometric mean speedup of 19.8X for data parallel benchmarks over native execution of MATLAB.

A decidable temporal logic with repeating values

Various logical formalisms with the freeze quantifier have been recently considered to model computer systems even though this is a powerful mechanism that often leads to undecidability. In this paper, we study a linear-time temporal logic with past-time operators such that the freeze operator is only used to express that some value from an infinite set is repeated in the future or in the past. Such a restriction has been inspired by a recent work on spatio-temporal logics. We show decidability of finitary and infinitary satisfiability by reduction into the verification of temporal properties in Petri nets. This is a surprising result since the logic is closed under negation, contains future-time and past-time temporal operators and can express the nonce property and its negation. These ingredients are known to lead to undecidability with a more liberal use of the freeze quantifier.

Systems biology of tuberculosis

Systems biology seeks to study biological systems as a whole, by adopting an integrated approach to study and understand the function of biological systems, particularly, the response of such systems to various perturbations. In this article, we focus on the Indian efforts towards systems-level studies of Mycobacterium tuberculosis and its interaction with the host. Availability of a variety of genome-scale experimental data, providing first level `omics' descriptions of the pathogen, render it feasible to study it at a systems level. Various aspects of the pathogen, from metabolic pathways to protein-protein interaction networks have been modelled and simulated, while host-pathogen interactions have been studied experimentally using siRNA-based techniques. These studies have been useful in obtaining a global perspective of the pathogen and its interactions with the host in many ways. For example, significant insights have been gained about different aspects such as proteins essential for bacterial survival, proteins that are highly influential in the network, pathways that are highly connected, host factors responsible for maintaining the TB infection and key factors involved in autophagy and pathogenesis. A rational pipeline developed for drug target identification incorporating analyses of the interactome, reactome, genome, pocketome and the transcriptome is discussed. Finally, exploring host factors as drug targets and insights about the emergence of drug resistance are also discussed. (C) 2011 Elsevier Ltd. All rights reserved.

Some studies on a solid state sulphur probe for coal gasification system

Measurements on the solid electrolyte cell(Ar -b H2 ~ H2S/CaS + CaF2 ~- ( P t ) / / C a F 2 / / ( P t )-~- CaF2 ~ CaS/H2S ~- H2 ~- At) show that the emf of the cell is directly related through the Nernst equation to the difference in sulfur potentials established at the two Ar ~- H2 ~ H2S/electrode interfaces. The electrodes are designed to convert the sulfur potential gradient across the calcium fluoride electrolyte into an equivalent fluorine potential gradient with the aid of the reaction, CaF2(s) ~ 1~ S2(g)-e CaS(s) ~- F2(g). The response time of the probe varies from approximately 9 hr at 990~ to 2.5 hr at 1225~ The conversion of calcium sulfide and/or calcium fluoride into calcium oxide should not be a problem in anticipated commercial coal gasification systems. Suggestions are presented for improving the cell for such commercial applications.

Techniques for Analysis of Certain Nonlinear Systems

This paper suggests the use of simple transformations like ÿ=kx, kx2 for second-order nonlinear differential equations to effect rapid plotting of the phase-plane trajectories. The method is particularly helpful in determining quickly the trajectory slopes along simple curves in any desired region of the phase plane. New planes such as the tÿ-x, tÿ2-x are considered for the study of some groups of nonlinear time-varying systems. Suggestions for solving certain higher-order nonlinear systems are also made.

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.

Temporal Logics of Repeating Values

Various logical formalisms with the freeze quantifier have been recently considered to model computer systems even though this is a powerful mechanism that often leads to undecidability. In this article, we study a linear-time temporal logic with past-time operators such that the freeze operator is only used to express that some value from an infinite set is repeated in the future or in the past. Such a restriction has been inspired by a recent work on spatio-temporal logics that suggests such a restricted use of the freeze operator. We show decidability of finitary and infinitary satisfiability by reduction into the verification of temporal properties in Petri nets by proposing a symbolic representation of models. This is a quite surprising result in view of the expressive power of the logic since the logic is closed under negation, contains future-time and past-time temporal operators and can express the nonce property and its negation. These ingredients are known to lead to undecidability with a more liberal use of the freeze quantifier. The article also contains developments about the relationships between temporal logics with the freeze operator and counter automata as well as reductions into first-order logics over data words.

Automatic compilation of MATLAB programs for synergistic execution on heterogeneous processors

MATLAB is an array language, initially popular for rapid prototyping, but is now being increasingly used to develop production code for numerical and scientific applications. Typical MATLAB programs have abundant data parallelism. These programs also have control flow dominated scalar regions that have an impact on the program's execution time. Today's computer systems have tremendous computing power in the form of traditional CPU cores and throughput oriented accelerators such as graphics processing units(GPUs). Thus, an approach that maps the control flow dominated regions to the CPU and the data parallel regions to the GPU can significantly improve program performance. In this paper, we present the design and implementation of MEGHA, a compiler that automatically compiles MATLAB programs to enable synergistic execution on heterogeneous processors. Our solution is fully automated and does not require programmer input for identifying data parallel regions. We propose a set of compiler optimizations tailored for MATLAB. Our compiler identifies data parallel regions of the program and composes them into kernels. The problem of combining statements into kernels is formulated as a constrained graph clustering problem. Heuristics are presented to map identified kernels to either the CPU or GPU so that kernel execution on the CPU and the GPU happens synergistically and the amount of data transfer needed is minimized. In order to ensure required data movement for dependencies across basic blocks, we propose a data flow analysis and edge splitting strategy. Thus our compiler automatically handles composition of kernels, mapping of kernels to CPU and GPU, scheduling and insertion of required data transfer. The proposed compiler was implemented and experimental evaluation using a set of MATLAB benchmarks shows that our approach achieves a geometric mean speedup of 19.8X for data parallel benchmarks over native execution of MATLAB.

Discovering Math APIs by Mining Unit Tests

In today's API-rich world, programmer productivity depends heavily on the programmer's ability to discover the required APIs. In this paper, we present a technique and tool, called MATHFINDER, to discover APIs for mathematical computations by mining unit tests of API methods. Given a math expression, MATHFINDER synthesizes pseudo-code to compute the expression by mapping its subexpressions to API method calls. For each subexpression, MATHFINDER searches for a method such that there is a mapping between method inputs and variables of the subexpression. The subexpression, when evaluated on the test inputs of the method under this mapping, should produce results that match the method output on a large number of tests. We implemented MATHFINDER as an Eclipse plugin for discovery of third-party Java APIs and performed a user study to evaluate its effectiveness. In the study, the use of MATHFINDER resulted in a 2x improvement in programmer productivity. In 96% of the subexpressions queried for in the study, MATHFINDER retrieved the desired API methods as the top-most result. The top-most pseudo-code snippet to implement the entire expression was correct in 93% of the cases. Since the number of methods and unit tests to mine could be large in practice, we also implement MATHFINDER in a MapReduce framework and evaluate its scalability and response time.

TIME VARYING LINEAR PREDICTION USING SPARSITY CONSTRAINTS

Time-varying linear prediction has been studied in the context of speech signals, in which the auto-regressive (AR) coefficients of the system function are modeled as a linear combination of a set of known bases. Traditionally, least squares minimization is used for the estimation of model parameters of the system. Motivated by the sparse nature of the excitation signal for voiced sounds, we explore the time-varying linear prediction modeling of speech signals using sparsity constraints. Parameter estimation is posed as a 0-norm minimization problem. The re-weighted 1-norm minimization technique is used to estimate the model parameters. We show that for sparsely excited time-varying systems, the formulation models the underlying system function better than the least squares error minimization approach. Evaluation with synthetic and real speech examples show that the estimated model parameters track the formant trajectories closer than the least squares approach.

Effect of Pt doping on the gas sensing properties of porous chromium oxide films through a kinetic response analysis approach

The effect of doping trace amounts of noblemetals (Pt) on the gas sensing properties of chromium oxide thin films, is studied. The sensors are fabricated by depositing chromium oxide films on a glass substrate using a modified spray pyrolysis technique and characterized using X-ray diffraction, scanning electron microscopy, transmission electron microscopy and X-ray photoelectron spectroscopy. The films are porous and nanocrystalline with an average crystallite size of similar to 30 nm. The typical p-type conductivity arises due to the presence of Cr vacancies, formed as a result of Cr non-stoichiometry, which is found to vary upon Pt doping. In order to analyze the effect of doping on the gas sensing properties, we have adopted a kinetic response analysis approach, which is based on Langmuir Adsorption isotherm (LA) theory. The sensor response is analyzed with equations obtained from LA theory and time constants as well as energies of adsorption-desorption are evaluated. It is seen that, Pt doping lowers the Schottky barrier height of the metal oxide semiconductor sensor from 222 meV to 172 meV. Subsequently the reduction in adsorption and desorption energies led to enhancement in sensor response and improvement in the kinetics of the sensor response i.e. the response time as well as recovery times of the sensor.

Global Response Sensitivity Analysis of Randomly Excited Dynamic Structures

The response of structural dynamical systems excited by multiple random excitations is considered. Two new procedures for evaluating global response sensitivity measures with respect to the excitation components are proposed. The first procedure is valid for stationary response of linear systems under stationary random excitations and is based on the notion of Hellinger's metric of distance between two power spectral density functions. The second procedure is more generally valid and is based on the l2 norm based distance measure between two probability density functions. Specific cases which admit exact solutions are presented, and solution procedures based on Monte Carlo simulations for more general class of problems are outlined. Illustrations include studies on a parametrically excited linear system and a nonlinear random vibration problem involving moving oscillator-beam system that considers excitations attributable to random support motions and guide-way unevenness. (C) 2015 American Society of Civil Engineers.

Helium Gas Purity Monitor based on Low Frequency Acoustic Resonance

Monitoring gas purity is an important aspect of gas recovery stations where air is usually one of the major impurities. Purity monitors of Katherometric type ate commercially available for this purpose. Alternatively, we discuss here a helium gas purity monitor based on acoustic resonance of a cavity at audio frequencies. It measures the purity by monitoring the resonant frequency of a cylindrical cavity filled with the gas under test and excited by conventional telephone transducers fixed at the ends. The use of the latter simplifies the design considerably. The paper discusses the details of the resonant cavity and the electronic circuit along with temperature compensation. The unit has been calibrated with helium gas of known purities. The unit has a response time of the order of 10 minutes and measures the gas purity to an accuracy of 0.02%. The unit has been installed in our helium recovery system and is found to perform satisfactorily.

High-Throughput Flexible Constraint Length Viterbi Decoders on De Bruijn, Shuffle-Exchange and Butterfly Connected Architectures

Flexible constraint length channel decoders are required for software defined radios. This paper presents a novel scalable scheme for realizing flexible constraint length Viterbi decoders on a de Bruijn interconnection network. Architectures for flexible decoders using the flattened butterfly and shuffle-exchange networks are also described. It is shown that these networks provide favourable substrates for realizing flexible convolutional decoders. Synthesis results for the three networks are provided and a comparison is performed. An architecture based on a 2D-mesh, which is a topology having a nominally lesser silicon area requirement, is also considered as a fourth point for comparison. It is found that of all the networks considered, the de Bruijn network offers the best tradeoff in terms of area versus throughput.

Utilization bounds for RM scheduling on uniform multiprocessors

Utilization bounds for Earliest Deadline First(EDF) and Rate Monotonic(RM) scheduling are known and well understood for uniprocessor systems. In this paper, we derive limits on similar bounds for the multiprocessor case, when the individual processors need not be identical. Tasks are partitioned among the processors and RM scheduling is assumed to be the policy used in individual processors. A minimum limit on the bounds for a 'greedy' class of algorithms is given and proved, since the actual value of the bound depends on the algorithm that allocates the tasks. We also derive the utilization bound of an algorithm which allocates tasks in decreasing order of utilization factors. Knowledge of such bounds allows us to carry out very fast schedulability tests although we are constrained by the fact that the tests are sufficient but not necessary to ensure schedulability.