Multithreaded Test Synthesis for Deadlock Detection

Designing and implementing thread-safe multithreaded libraries can be a daunting task as developers of these libraries need to ensure that their implementations are free from concurrency bugs, including deadlocks. The usual practice involves employing software testing and/or dynamic analysis to detect. deadlocks. Their effectiveness is dependent on well-designed multithreaded test cases. Unsurprisingly, developing multithreaded tests is significantly harder than developing sequential tests for obvious reasons. In this paper, we address the problem of automatically synthesizing multithreaded tests that can induce deadlocks. The key insight to our approach is that a subset of the properties observed when a deadlock manifests in a concurrent execution can also be observed in a single threaded execution. We design a novel, automatic, scalable and directed approach that identifies these properties and synthesizes a deadlock revealing multithreaded test. The input to our approach is the library implementation under consideration and the output is a set of deadlock revealing multithreaded tests. We have implemented our approach as part of a tool, named OMEN1. OMEN is able to synthesize multithreaded tests on many multithreaded Java libraries. Applying a dynamic deadlock detector on the execution of the synthesized tests results in the detection of a number of deadlocks, including 35 real deadlocks in classes documented as thread-safe. Moreover, our experimental results show that dynamic analysis on multithreaded tests that are either synthesized randomly or developed by third-party programmers are ineffective in detecting the deadlocks.

Trace Driven Dynamic Deadlock Detection and Reproduction

Dynamic analysis techniques have been proposed to detect potential deadlocks. Analyzing and comprehending each potential deadlock to determine whether the deadlock is feasible in a real execution requires significant programmer effort. Moreover, empirical evidence shows that existing analyses are quite imprecise. This imprecision of the analyses further void the manual effort invested in reasoning about non-existent defects. In this paper, we address the problems of imprecision of existing analyses and the subsequent manual effort necessary to reason about deadlocks. We propose a novel approach for deadlock detection by designing a dynamic analysis that intelligently leverages execution traces. To reduce the manual effort, we replay the program by making the execution follow a schedule derived based on the observed trace. For a real deadlock, its feasibility is automatically verified if the replay causes the execution to deadlock. We have implemented our approach as part of WOLF and have analyzed many large (upto 160KLoC) Java programs. Our experimental results show that we are able to identify 74% of the reported defects as true (or false) positives automatically leaving very few defects for manual analysis. The overhead of our approach is negligible making it a compelling tool for practical adoption.

Long way to go: how outflows from large galaxies propagate through the hot halo gas

Using hydrodynamic simulations, we study the mass-loss due to supernova-driven outflows from Milky Way type disc galaxies, paying particular attention to the effect of the extended hot halo gas. We find that the total mass-loss at inner radii scales roughly linearly with total mass of stars formed, and that the mass loading factor at the virial radius can be several times its value at inner radii because of the swept up hot halo gas. The temperature distribution of the outflowing material in the inner region (similar to 10 kpc) is bimodal in nature, peaking at 10(5) K and 10(6.5) K, responsible for optical and X-ray emission, respectively. The contribution of cold/warm gas with temperature <= 10(5.5) K to the outflow rate within 10 kpc is approximate to 0.3-0.5. The warm mass loading factor, eta(3e5) (T <= 3 x 10(5) K) is related to the mass loading factor at the virial radius (eta(v)) as eta(v) approximate to 25 eta(3e5) (SFR/M-circle dot yr(-1))(-0.15) for a baryon fraction of 0.1 and a starburst period of 50 Myr. We also discuss the effect of multiple bursts that are separated by both short and long periods. The outflow speed at the virial radius is close to the sound speed in the hot halo, less than or similar to 200 km s(-1). We identify two `sequences' of outflowing cold gas at small scales: a fast (approximate to 500 km s(-1)) sequence, driven by the unshocked free-wind; and a slow sequence (approximate to +/- 100 km s(-1)) at the conical interface of the superwind and the hot halo.

A Suzaku view of IGR J16393-4643

The pulsar IGR J16393-4643 belongs to a class of highly absorbed supergiant high-mass X-ray binaries (HMXBs), characterized by a very high column density of absorbing matter. We present the results of simultaneous broad-band pulsation and spectrum analysis from a 44-ks Suzaku observation of the source. The orbital intensity profile created with the Swift Burst Alert Telescope (Swift-BAT) light curve shows an indication of IGR J16393-4643 being an eclipsing system with a short eclipse semi-angle theta(E) similar to 17 degrees. For a supergiant companion star with a 20-R-circle dot radius, this implies an inclination of the orbital plane in the range 39 degrees-57 degrees, whereas for a main-sequence B star as the companion with a 10-R-circle dot radius, the inclination of the orbital plane is in the range 60 degrees-77 degrees. Pulse profiles created for different energy bands have complex morphology, which shows some energy dependence and increases in pulse fraction with energy. We have also investigated broad-band spectral characteristics, phase-averaged spectra and resolving the pulse phase into peak and trough phases. The phase-averaged spectrum has a very high N-H(similar to 3 x 10(23) cm(-2)) and is described by a power law (Gamma similar to 0.9) with a high-energy cut-off above 20 keV. We find a change in the spectral index in the peak and trough phases, implying an underlying change in the source spectrum.

The cold mode: a phenomenological model for the evolution of density perturbations in the intracluster medium

Cool cluster cores are in global thermal equilibrium but are locally thermally unstable. We study a non-linear phenomenological model for the evolution of density perturbations in the intracluster medium (ICM) due to local thermal instability and gravity. We have analysed and extended a model for the evolution of an overdense blob in the ICM. We find two regimes in which the overdense blobs can cool to thermally stable low temperatures. One for large t(cool)/t(ff) (t(cool) is the cooling time and t(ff) is the free-fall time), where a large initial overdensity is required for thermal runaway to occur; this is the regime which was previously analysed in detail. We discover a second regime for t(cool)/t(ff) less than or similar to 1 (in agreement with Cartesian simulations of local thermal instability in an external gravitational field), where runaway cooling happens for arbitrarily small amplitudes. Numerical simulations have shown that cold gas condenses out more easily in a spherical geometry. We extend the analysis to include geometrical compression in weakly stratified atmospheres such as the ICM. With a single parameter, analogous to the mixing length, we are able to reproduce the results from numerical simulations; namely, small density perturbations lead to the condensation of extended cold filaments only if t(cool)/t(ff) less than or similar to 10.

Role of gas in supporting grand spiral structure

The density wave theory for the grand-design two-armed spiral pattern in galaxies is successful in explaining several observed features. However, the long-term persistence of this spiral structure is a serious problem since the group transport would destroy it within about a billion years as shown in a classic paper by Toomre. In this paper, we include the low-velocity dispersion component, namely gas, on an equal footing with stars in the formulation of the density wave theory, and obtain the dispersion relation for this coupled system. We show that the inclusion of gas makes the group transport slower by a factor of few, thus allowing the pattern to persist longer - for several billion years. Though still less than the Hubble time, this helps in making the spiral structure more long-lived. Further we show that addition of gas is essential to get a stable wave for the observed pattern speed for the Galaxy, which otherwise is not possible for a one-component stellar disc.

Narrow escape: how ionizing photons escape from disc galaxies

In this paper we calculate the escape fraction (f(esc)) of ionizing photons from starburst galaxies. Using 2D axisymmetric hydrodynamic simulations, we study superbubbles created by overlapping supernovae in OB associations. We calculate the escape fraction of ionizing photons from the centre of the disc along different angles through the superbubble and the gas disc. After convolving with the luminosity function of OB associations, we show that the ionizing photons escape within a cone of similar to 40 degrees, consistent with observations of nearby galaxies. The evolution of the escape fraction with time shows that it falls initially as cold gas is accumulated in a dense shell. After the shell crosses a few scaleheights and fragments, the escape fraction through the polar regions rises again. The angle-averaged escape fraction cannot exceed similar to1 - cos (1 rad)] = 0.5 from geometrical considerations (using the emission cone opening angle). We calculate the dependence of the time-and angle-averaged escape fraction on the mid-plane disc gas density (in the range n(0) = 0.15-50 cm(-3)) and the disc scaleheight (between z(0) = 10 and 600 pc). We find that the escape fraction is related to the disc parameters (the mid-plane disc density and scaleheight) roughly so that f(esc)(alpha)n(0)(2)z(0)(3) (with alpha approximate to 2.2) is a constant. For discs with a given warm neutral medium temperature, massive discs have lower escape fraction than low-mass galaxies. For Milky Way ISM parameters, we find f(esc) similar to 5 per cent, and it increases to approximate to 10 per cent for a galaxy 10 times less massive. We discuss the possible effects of clumpiness of the ISM on the estimate of the escape fraction and the implications of our results for the reionization of the Universe.

Synthesizing Racy Tests

Subtle concurrency errors in multithreaded libraries that arise because of incorrect or inadequate synchronization are often difficult to pinpoint precisely using only static techniques. On the other hand, the effectiveness of dynamic race detectors is critically dependent on multithreaded test suites whose execution can be used to identify and trigger races. Usually, such multithreaded tests need to invoke a specific combination of methods with objects involved in the invocations being shared appropriately to expose a race. Without a priori knowledge of the race, construction of such tests can be challenging. In this paper, we present a lightweight and scalable technique for synthesizing precisely these kinds of tests. Given a multithreaded library and a sequential test suite, we describe a fully automated analysis that examines sequential execution traces, and produces as its output a concurrent client program that drives shared objects via library method calls to states conducive for triggering a race. Experimental results on a variety of well-tested Java libraries yield 101 synthesized multithreaded tests in less than four minutes. Analyzing the execution of these tests using an off-the-shelf race detector reveals 187 harmful races, including several previously unreported ones.

Variations in the cyclotron resonant scattering features during 2011 outburst of 4U 0115+63

We study the variations in the Cyclotron Resonant Scattering Feature (CRSF) during 2011 outburst of the high mass X-ray binary 4U 0115+63 using observations performed with Suzaku, RXTE, Swift and INTEGRAL satellites. The wide-band spectral data with low-energy coverage allowed us to characterize the broad-band continuum and detect the CRSFs. We find that the broad-band continuum is adequately described by a combination of a low temperature (kT similar to 0.8 keV) blackbody and a power law with high energy cutoff (E-cut similar to 5.4 keV) without the need for a broad Gaussian at similar to 10 keV as used in some earlier studies. Though winds from the companion can affect the emission from the neutron star at low energies (<3 keV), the blackbody component shows a significant presence in our continuum model. We report evidence for the possible presence of two independent sets of CRSFs with fundamentals at similar to 11 and similar to 15 keV. These two sets of CRSFs could arise from spatially distinct emitting regions. We also find evidence for variations in the line equivalent widths, with the 11 keV CRSF weakening and the 15 keV line strengthening with decreasing luminosity. Finally, we propose that the reason for the earlier observed anticorrelation of line energy with luminosity could be due to modelling of these two independent line sets (similar to 11 and similar to 15 keV) as a single CRSF.

GRMHD formulation of highly super-Chandrasekhar rotating magnetized white dwarfs: stable configurations of non-spherical white dwarfs

Here we extend the exploration of significantly super-Chandrasekhar magnetized white dwarfs by numerically computing axisymmetric stationary equilibria of differentially rotating magnetized polytropic compact stars in general relativity (GR), within the ideal magnetohydrodynamic regime. We use a general relativistic magnetohydrodynamic (GRMHD) framework that describes rotating and magnetized axisymmetric white dwarfs, choosing appropriate rotation laws and magnetic field profiles (toroidal and poloidal). The numerical procedure for finding solutions in this framework uses the 3 + 1 formalism of numerical relativity, implemented in the open source XNS code. We construct equilibrium sequences by varying different physical quantities in turn, and highlight the plausible existence of super-Chandrasekhar white dwarfs, with masses in the range of 2-3 solar mass, with central (deep interior) magnetic fields of the order of 10(14) G and differential rotation with surface time periods of about 1-10 s. We note that such white dwarfs are candidates for the progenitors of peculiar, overluminous Type Ia supernovae, to which observational evidence ascribes mass in the range 2.1-2.8 solar mass. We also present some interesting results related to the structure of such white dwarfs, especially the existence of polar hollows in special cases.

Multiwavelength features of Fermi bubbles as signatures of a Galactic wind

Using hydrodynamical simulations, we show for the first time that an episode of star formation in the centre of the Milky Way, with a star formation rate (SFR) similar to 0.5 M-circle dot yr(-1) for similar to 30 Myr, can produce bubbles that resemble the Fermi bubbles (FBs), when viewed from the solar position. The morphology, extent and multiwavelength observations of FBs, especially X-rays, constrain various physical parameters such as SFR, age, and the circumgalactic medium (CGM) density. We show that the interaction of the CGM with the Galactic wind driven by star formation in the central region can explain the observed surface brightness and morphological features of X-rays associated with the FBs. Furthermore, assuming that cosmic ray electrons are accelerated in situ by shocks and/or turbulence, the brightness and morphology of gamma-ray emission and the microwave haze can be explained. The kinematics of the cold and warm clumps in our model also matches with recent observations of absorption lines through the bubbles.

PLUTO plus : Near-Complete Modeling of Affine Transformations for Parallelism and Locality

Affine transformations have proven to be very powerful for loop restructuring due to their ability to model a very wide range of transformations. A single multi-dimensional affine function can represent a long and complex sequence of simpler transformations. Existing affine transformation frameworks like the Pluto algorithm, that include a cost function for modern multicore architectures where coarse-grained parallelism and locality are crucial, consider only a sub-space of transformations to avoid a combinatorial explosion in finding the transformations. The ensuing practical tradeoffs lead to the exclusion of certain useful transformations, in particular, transformation compositions involving loop reversals and loop skewing by negative factors. In this paper, we propose an approach to address this limitation by modeling a much larger space of affine transformations in conjunction with the Pluto algorithm's cost function. We perform an experimental evaluation of both, the effect on compilation time, and performance of generated codes. The evaluation shows that our new framework, Pluto+, provides no degradation in performance in any of the Polybench benchmarks. For Lattice Boltzmann Method (LBM) codes with periodic boundary conditions, it provides a mean speedup of 1.33x over Pluto. We also show that Pluto+ does not increase compile times significantly. Experimental results on Polybench show that Pluto+ increases overall polyhedral source-to-source optimization time only by 15%. In cases where it improves execution time significantly, it increased polyhedral optimization time only by 2.04x.

Effect of dark matter halo on global spiral modes in galaxies

Low surface brightness (LSB) galaxies form a major class of galaxies, and are characterized by low disc surface density and low star formation rate. These are known to be dominated by dark matter halo from the innermost regions. Here, we study the role of the dark matter halo on the grand-design, m = 2, spiral modes in a galactic disc by carrying out a global mode analysis in the WKB approximation. The Bohr-Sommerfeld quantization rule is used to determine how many discrete global spiral modes are permitted. First, a typical superthin, LSB galaxy UGC 7321 is studied by taking only the galactic disc, modelled as a fluid; and then the disc embedded in a dark matter halo. We find that both cases permit the existence of global spiral modes. This is in contrast to earlier results where the inclusion of dark matter halo was shown to nearly fully suppress local, swing-amplified spiral features. Although technically global modes are permitted in the fluid model as shown here, we argue that due to lack of tidal interactions, these are not triggered in LSB galaxies. For comparison, we carried out a similar analysis for the Galaxy, for which the dark matter halo does not dominate in the inner regions. We show that here too the dark matter halo has little effect, hence the disc embedded in a halo is also able to support global modes. The derived pattern speed of the global mode agrees fairly well with the observed value for the Galaxy.

Photometric metallicity map of the Large Magellanic Cloud

We have estimated a metallicity map of the Large Magellanic Cloud (LMC) using the Magellanic Cloud Photometric Survey (MCPS) and Optical Gravitational Lensing Experiment (OGLE III) photometric data. This is a first of its kind map of metallicity up to a radius of 4 degrees-5 degrees, derived using photometric data and calibrated using spectroscopic data of Red Giant Branch (RGB) stars. We identify the RGB in the V, (V - I) colour-magnitude diagrams of small subregions of varying sizes in both data sets. We use the slope of the RGB as an indicator of the average metallicity of a subregion, and calibrate the RGB slope to metallicity using spectroscopic data for field and cluster red giants in selected subregions. The average metallicity of the LMC is found to be Fe/H] = -0.37 dex (sigmaFe/H] = 0.12) from MCPS data, and Fe/H] = -0.39 dex (sigmaFe/H] = 0.10) from OGLE III data. The bar is found to be the most metal-rich region of the LMC. Both the data sets suggest a shallow radial metallicity gradient up to a radius of 4 kpc (-0.049 +/- 0.002 dex kpc(-1) to -0.066 +/- 0.006 dex kpc(-1)). Subregions in which the mean metallicity differs from the surrounding areas do not appear to correlate with previously known features; spectroscopic studies are required in order to assess their physical significance.

PolyMage: Automatic Optimization for Image Processing Pipelines

This paper presents the design and implementation of PolyMage, a domain-specific language and compiler for image processing pipelines. An image processing pipeline can be viewed as a graph of interconnected stages which process images successively. Each stage typically performs one of point-wise, stencil, reduction or data-dependent operations on image pixels. Individual stages in a pipeline typically exhibit abundant data parallelism that can be exploited with relative ease. However, the stages also require high memory bandwidth preventing effective utilization of parallelism available on modern architectures. For applications that demand high performance, the traditional options are to use optimized libraries like OpenCV or to optimize manually. While using libraries precludes optimization across library routines, manual optimization accounting for both parallelism and locality is very tedious. The focus of our system, PolyMage, is on automatically generating high-performance implementations of image processing pipelines expressed in a high-level declarative language. Our optimization approach primarily relies on the transformation and code generation capabilities of the polyhedral compiler framework. To the best of our knowledge, this is the first model-driven compiler for image processing pipelines that performs complex fusion, tiling, and storage optimization automatically. Experimental results on a modern multicore system show that the performance achieved by our automatic approach is up to 1.81x better than that achieved through manual tuning in Halide, a state-of-the-art language and compiler for image processing pipelines. For a camera raw image processing pipeline, our performance is comparable to that of a hand-tuned implementation.