Generating Efficient Data Movement Code for Heterogeneous Architectures with Distributed-Memory

Programming for parallel architectures that do not have a shared address space is extremely difficult due to the need for explicit communication between memories of different compute devices. A heterogeneous system with CPUs and multiple GPUs, or a distributed-memory cluster are examples of such systems. Past works that try to automate data movement for distributed-memory architectures can lead to excessive redundant communication. In this paper, we propose an automatic data movement scheme that minimizes the volume of communication between compute devices in heterogeneous and distributed-memory systems. We show that by partitioning data dependences in a particular non-trivial way, one can generate data movement code that results in the minimum volume for a vast majority of cases. The techniques are applicable to any sequence of affine loop nests and works on top of any choice of loop transformations, parallelization, and computation placement. The data movement code generated minimizes the volume of communication for a particular configuration of these. We use a combination of powerful static analyses relying on the polyhedral compiler framework and lightweight runtime routines they generate, to build a source-to-source transformation tool that automatically generates communication code. We demonstrate that the tool is scalable and leads to substantial gains in efficiency. On a heterogeneous system, the communication volume is reduced by a factor of 11X to 83X over state-of-the-art, translating into a mean execution time speedup of 1.53X. On a distributed-memory cluster, our scheme reduces the communication volume by a factor of 1.4X to 63.5X over state-of-the-art, resulting in a mean speedup of 1.55X. In addition, our scheme yields a mean speedup of 2.19X over hand-optimized UPC codes.

Determination of Internal Structures of Heterogeneous Nanocrystals Using Variable-Energy Photoemission Spectroscopy

This article describes the determination of the internal structure of heterogeneous nanoparticle systems including inverted core-shell (CdS core and CdSe shell) and alloyed (CdSeS) quantum dots using depth-resolved, variable-energy X-ray photoelectron spectroscopy (XPS). A unique feature of this work is the combination of photoelectron spectroscopy performed at lower X-ray energies (400-700 eV), to achieve surface sensitivity, with bulk sensitive measurements at high photon energies (>2000 eV), thereby providing detailed information about the whole nanoparticle structure with a great accuracy. The use of high photon energies furthermore allows us to investigate nanoparticles much larger than those studied thus far. This capability is a consequence of the much-increased mean free path of the photoelectron achieved at high excitation energies. Our results show that the actual structures of the synthesized nanoparticles are considerably different from the nominal, targeted structures, which can be post facto rationalized in terms of the reactivity of different constituents.

Efficient simulation of unitary operators by combining two numerical algorithms: An NMR simulation of the mirror-inversion propagator of an XY spin chain

Precise experimental implementation of unitary operators is one of the most important tasks for quantum information processing. Numerical optimization techniques are widely used to find optimized control fields to realize a desired unitary operator. However, finding high-fidelity control pulses to realize an arbitrary unitary operator in larger spin systems is still a difficult task. In this work, we demonstrate that a combination of the GRAPE algorithm, which is a numerical pulse optimization technique, and a unitary operator decomposition algorithm Ajoy et al., Phys. Rev. A 85, 030303 (2012)] can realize unitary operators with high experimental fidelity. This is illustrated by simulating the mirror-inversion propagator of an XY spin chain in a five-spin dipolar coupled nuclear spin system. Further, this simulation has been used to demonstrate the transfer of entangled states from one end of the spin chain to the other end.

Lantana camara L. (Verbenaceae) invasion along streams in a heterogeneous landscape

Streams are periodically disturbed due to flooding, act as edges between habitats and also facilitate the dispersal of propagules, thus being potentially more vulnerable to invasions than adjoining regions. We used a landscape-wide transect-based sampling strategy and a mixed effects modelling approach to understand the effects of distance from stream, a rainfall gradient, light availability and fire history on the distribution of the invasive shrub Lantana camara L.(lantana) in the tropical dry forests of Mudumalai in southern India. The area occupied by lantana thickets and lantana stem abundance were both found to be highest closest to streams across this landscape with a rainfall gradient. There was no advantage in terms of increased abundance or area occupied by lantana when it grew closer to streams in drier areas as compared to moister areas. On an average, the area covered by lantana increased with increasing annual rainfall. Areas that experienced greater number of fires during 1989-2010 had lower lantana stem abundance irrespective of distance from streams. In this landscape, total light availability did not affect lantana abundance. Understanding the spatially variable environmental factors in a heterogeneous landscape influencing the distribution of lantana would aid in making informed management decisions at this scale.

Smoothed Functional Algorithms for Stochastic Optimization Using q-Gaussian Distributions

Smoothed functional (SF) schemes for gradient estimation are known to be efficient in stochastic optimization algorithms, especially when the objective is to improve the performance of a stochastic system However, the performance of these methods depends on several parameters, such as the choice of a suitable smoothing kernel. Different kernels have been studied in the literature, which include Gaussian, Cauchy, and uniform distributions, among others. This article studies a new class of kernels based on the q-Gaussian distribution, which has gained popularity in statistical physics over the last decade. Though the importance of this family of distributions is attributed to its ability to generalize the Gaussian distribution, we observe that this class encompasses almost all existing smoothing kernels. This motivates us to study SF schemes for gradient estimation using the q-Gaussian distribution. Using the derived gradient estimates, we propose two-timescale algorithms for optimization of a stochastic objective function in a constrained setting with a projected gradient search approach. We prove the convergence of our algorithms to the set of stationary points of an associated ODE. We also demonstrate their performance numerically through simulations on a queuing model.

Parameterized Algorithms for MAX COLORABLE INDUCED SUBGRAPH Problem on Perfect Graphs

We address the parameterized complexity ofMaxColorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n(O(q)) algorithm on chordal graphs. We first observe that the problem is W2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm runs in time 5.44(l) (n+#alpha(G))(O(1)) where #alpha(G) is the number of maximal independent sets of the input graph. The second algorithm runs in time q(l+o()l())n(O(1))T(alpha) where T-alpha is the time required to find a maximum independent set in any induced subgraph of G. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. The running time of the second algorithm is FPT in l alone (whenever T-alpha is a polynomial in n), since q <= l for all non-trivial situations. Finally, we show that (under standard complexitytheoretic assumptions) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense: (a) On split graphs, we do not expect a polynomial kernel if q is a part of the input. (b) On perfect graphs, we do not expect a polynomial kernel even for fixed values of q >= 2.

Hydrophobic hydration driven self-assembly of curcumin in water: Similarities to nucleation and growth under large metastability, and an analysis of water dynamics at heterogeneous surfaces

As the beneficial effects of curcumin have often been reported to be limited to its small concentrations, we have undertaken a study to find the aggregation properties of curcumin in water by varying the number of monomers. Our molecular dynamics simulation results show that the equilibrated structure is always an aggregated state with remarkable structural rearrangements as we vary the number of curcumin monomers from 4 to 16 monomers. We find that the curcumin monomers form clusters in a very definite pattern where they tend to aggregate both in parallel and anti-parallel orientation of the phenyl rings, often seen in the formation of beta-sheet in proteins. A considerable enhancement in the population of parallel alignments is observed with increasing the system size from 12 to 16 curcumin monomers. Due to the prevalence of such parallel alignment for large system size, a more closely packed cluster is formed with maximum number of hydrophobic contacts. We also follow the pathway of cluster growth, in particular the transition from the initial segregated to the final aggregated state. We find the existence of a metastable structural intermediate involving a number of intermediate-sized clusters dispersed in the solution. We have constructed a free energy landscape of aggregation where the metatsable state has been identified. The course of aggregation bears similarity to nucleation and growth in highly metastable state. The final aggregated form remains stable with the total exclusion of water from its sequestered hydrophobic core. We also investigate water structure near the cluster surface along with their orientation. We find that water molecules form a distorted tetrahedral geometry in the 1st solvation layer of the cluster, interacting rather strongly with the hydrophilic groups at the surface of the curcumin. The dynamics of such quasi-bound water molecules near the surface of curcumin cluster is considerably slower than the bulk signifying a restricted motion as often found in protein hydration layer. (C) 2014 AIP Publishing LLC.

Newton-based stochastic optimization using q-Gaussian smoothed functional algorithms

We present the first q-Gaussian smoothed functional (SF) estimator of the Hessian and the first Newton-based stochastic optimization algorithm that estimates both the Hessian and the gradient of the objective function using q-Gaussian perturbations. Our algorithm requires only two system simulations (regardless of the parameter dimension) and estimates both the gradient and the Hessian at each update epoch using these. We also present a proof of convergence of the proposed algorithm. In a related recent work (Ghoshdastidar, Dukkipati, & Bhatnagar, 2014), we presented gradient SF algorithms based on the q-Gaussian perturbations. Our work extends prior work on SF algorithms by generalizing the class of perturbation distributions as most distributions reported in the literature for which SF algorithms are known to work turn out to be special cases of the q-Gaussian distribution. Besides studying the convergence properties of our algorithm analytically, we also show the results of numerical simulations on a model of a queuing network, that illustrate the significance of the proposed method. In particular, we observe that our algorithm performs better in most cases, over a wide range of q-values, in comparison to Newton SF algorithms with the Gaussian and Cauchy perturbations, as well as the gradient q-Gaussian SF algorithms. (C) 2014 Elsevier Ltd. All rights reserved.

An iterative framework for sparse signal reconstruction algorithms

It has been shown that iterative re-weighted strategies will often improve the performance of many sparse reconstruction algorithms. However, these strategies are algorithm dependent and cannot be easily extended for an arbitrary sparse reconstruction algorithm. In this paper, we propose a general iterative framework and a novel algorithm which iteratively enhance the performance of any given arbitrary sparse reconstruction algorithm. We theoretically analyze the proposed method using restricted isometry property and derive sufficient conditions for convergence and performance improvement. We also evaluate the performance of the proposed method using numerical experiments with both synthetic and real-world data. (C) 2014 Elsevier B.V. All rights reserved.

Simultaneous Perturbation Newton Algorithms for Simulation Optimization

We present a new Hessian estimator based on the simultaneous perturbation procedure, that requires three system simulations regardless of the parameter dimension. We then present two Newton-based simulation optimization algorithms that incorporate this Hessian estimator. The two algorithms differ primarily in the manner in which the Hessian estimate is used. Both our algorithms do not compute the inverse Hessian explicitly, thereby saving on computational effort. While our first algorithm directly obtains the product of the inverse Hessian with the gradient of the objective, our second algorithm makes use of the Sherman-Morrison matrix inversion lemma to recursively estimate the inverse Hessian. We provide proofs of convergence for both our algorithms. Next, we consider an interesting application of our algorithms on a problem of road traffic control. Our algorithms are seen to exhibit better performance than two Newton algorithms from a recent prior work.

Insights on Defect-Mediated Heterogeneous Nucleation of Graphene on Copper

The grain size of monolayer large area graphene is key to its performance. Microstructural design for the desired grain size requires a fundamental understanding of graphene nucleation and growth. The two levers that can be used to control these aspects are the defect density, whose population can be controlled by annealing, and the gas-phase supersaturation for activation of nucleation at the defect sites. We observe that defects on copper surface, namely dislocations, grain boundaries, triple points, and rolling marks, initiate nucleation of graphene. We show that among these defects dislocations are the most potent nucleation sites, as they get activated at lowest supersaturation. As an illustration, we tailor the defect density and supersaturation to change the domain size of graphene from <1 mu m(2) to >100 mu m(2). Growth data reported in the literature has been summarized on a supersaturation plot, and a regime for defect-dominated growth has been identified. In this growth regime, we demonstrate the spatial control over nucleation at intentionally introduced defects, paving the way for patterned growth of graphene. Our results provide a unified framework for understanding the role of defects in graphene nucleation and can be used as a guideline for controlled growth of graphene.

Timing Recovery Algorithms and Architectures for 2-D Magnetic Recording Systems

We investigate the problem of timing recovery for 2-D magnetic recording (TDMR) channels. We develop a timing error model for TDMR channel considering the phase and frequency offsets with noise. We propose a 2-D data-aided phase-locked loop (PLL) architecture for tracking variations in the position and movement of the read head in the down-track and cross-track directions and analyze the convergence of the algorithm under non-separable timing errors. We further develop a 2-D interpolation-based timing recovery scheme that works in conjunction with the 2-D PLL. We quantify the efficiency of our proposed algorithms by simulations over a 2-D magnetic recording channel with timing errors.

A Perspective to Adopt Continuous Dynamic Cognition for Malicious Node Detection in Heterogeneous Networks

The current day networks use Proactive networks for adaption to the dynamic scenarios. The use of cognition technique based on the Observe, Orient, Decide and Act loop (OODA) is proposed to construct proactive networks. The network performance degradation in knowledge acquisition and malicious node presence is a problem that exists. The use of continuous time dynamic neural network is considered to achieve cognition. The variance in service rates of user nodes is used to detect malicious activity in heterogeneous networks. The improved malicious node detection rates are proved through the experimental results presented in this paper. (C) 2015 The Authors. Published by Elsevier B.V.

Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints

The 3-Hitting Set problem involves a family of subsets F of size at most three over an universe U. The goal is to find a subset of U of the smallest possible size that intersects every set in F. The version of the problem with parity constraints asks for a subset S of size at most k that, in addition to being a hitting set, also satisfies certain parity constraints on the sizes of the intersections of S with each set in the family F. In particular, an odd (even) set is a hitting set that hits every set at either one or three (two) elements, and a perfect code is a hitting set that intersects every set at exactly one element. These questions are of fundamental interest in many contexts for general set systems. Just as for Hitting Set, we find these questions to be interesting for the case of families consisting of sets of size at most three. In this work, we initiate an algorithmic study of these problems in this special case, focusing on a parameterized analysis. We show, for each problem, efficient fixed-parameter tractable algorithms using search trees that are tailor-made to the constraints in question, and also polynomial kernels using sunflower-like arguments in a manner that accounts for equivalence under the additional parity constraints.

Modeling of the non-isothermal liquid droplet impact on a heated solid substrate with heterogeneous wettability

A comprehensive numerical investigation on the impingement and spreading of a non-isothermal liquid droplet on a solid substrate with heterogeneous wettability is presented in this work. The time-dependent incompressible Navier-Stokes equations are used to describe the fluid flow in the liquid droplet, whereas the heat transfer in the moving droplet and in the solid substrate is described by the energy equation. The arbitrary Lagrangian-Eulerian (ALE) formulation with finite elements is used to solve the time-dependent incompressible Navier-Stokes equation and the energy equation in the time-dependent moving domain. Moreover, the Marangoni convection is included in the variational form of the Navier-Stokes equations without calculating the partial derivatives of the temperature on the free surface. The heterogeneous wettability is incorporated into the numerical model by defining a space-dependent contact angle. An array of simulations for droplet impingement on a heated solid substrate with circular patterned heterogeneous wettability are presented. The numerical study includes the influence of wettability contrast, pattern diameter, Reynolds number and Weber number on the confinement of the spreading droplet within the inner region, which is more wettable than the outer region. Also, the influence of these parameters on the total heat transfer from the solid substrate to the liquid droplet is examined. We observe that the equilibrium position depends on the wettability contrast and the diameter of the inner surface. Consequently. the heat transfer is more when the wettability contrast is small and/or the diameter of inner region is large. The influence of the Weber number on the total heat transfer is more compared to the Reynolds number, and the total heat transfer increases when the Weber number increases. (C) 2015 Elsevier Ltd. All rights reserved.