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.

Phase space path integral approach to harmonic oscillator with a time-dependent force constant

The quantum statistical mechanical propagator for a harmonic oscillator with a time-dependent force constant, m omega(2)(t), has been investigated in the past and was found to have only a formal solution in terms of the solutions of certain ordinary differential equations. Such path integrals are frequently encountered in semiclassical path integral evaluations and having exact analytical expressions for such path integrals is of great interest. In a previous work, we had obtained the exact propagator for motion in an arbitrary time-dependent harmonic potential in the overdamped limit of friction using phase space path integrals in the context of Levy flights - a result that can be easily extended to Brownian motion. In this paper, we make a connection between the overdamped Brownian motion and the imaginary time propagator of quantum mechanics and thereby get yet another way to evaluate the latter exactly. We find that explicit analytic solution for the quantum statistical mechanical propagator can be written when the time-dependent force constant has the form omega(2)(t) = lambda(2)(t) - d lambda(t)/dt where lambda(t) is any arbitrary function of t and use it to evaluate path integrals which have not been evaluated previously. We also employ this method to arrive at a formal solution of the propagator for both Levy flights and Brownian subjected to a time-dependent harmonic potential in the underdamped limit of friction. (C) 2015 Elsevier B.V. All rights reserved.

Modeling Ultrasonic NDE and Guided Wave based Structural Health Monitoring

Structural Health Monitoring (SHM) systems require integration of non-destructive technologies into structural design and operational processes. Modeling and simulation of complex NDE inspection processes are important aspects in the development and deployment of SHM technologies. Ray tracing techniques are vital simulation tools to visualize the wave path inside a material. These techniques also help in optimizing the location of transducers and their orientation with respect to the zone of interrogation. It helps in increasing the chances of detection and identification of a flaw in that zone. While current state-of-the-art techniques such as ray tracing based on geometric principle help in such visualization, other information such as signal losses due to spherical or cylindrical shape of wave front are rarely taken into consideration. The problem becomes a little more complicated in the case of dispersive guided wave propagation and near-field defect scattering. We review the existing models and tools to perform ultrasonic NDE simulation in structural components. As an initial step, we develop a ray-tracing approach, where phase and spectral information are preserved. This enables one to study wave scattering beyond simple time of flight calculation of rays. Challenges in terms of theory and modelling of defects of various kinds are discussed. Various additional considerations such as signal decay and physics of scattering are reviewed and challenges involved in realistic computational implementation are discussed. Potential application of this approach to SHM system design is highlighted and by applying this to complex structural components such as airframe structures, SHM is demonstrated to provide additional value in terms of lighter weight and/or longevity enhancement resulting from an extension of the damage tolerance design principle not compromising safety and reliability.

A Reliable Residual Based A Posteriori Error Estimator for a Quadratic Finite Element Method for the Elliptic Obstacle Problem

A residual based a posteriori error estimator is derived for a quadratic finite element method (FEM) for the elliptic obstacle problem. The error estimator involves various residuals consisting of the data of the problem, discrete solution and a Lagrange multiplier related to the obstacle constraint. The choice of the discrete Lagrange multiplier yields an error estimator that is comparable with the error estimator in the case of linear FEM. Further, an a priori error estimate is derived to show that the discrete Lagrange multiplier converges at the same rate as that of the discrete solution of the obstacle problem. The numerical experiments of adaptive FEM show optimal order convergence. This demonstrates that the quadratic FEM for obstacle problem exhibits optimal performance.

A Remark on the A Posteriori Error Analysis of Discontinuous Galerkin Methods for the Obstacle Problem

We revisit the a posteriori error analysis of discontinuous Galerkin methods for the obstacle problem derived in 25]. Under a mild assumption on the trace of obstacle, we derive a reliable a posteriori error estimator which does not involve min/max functions. A key in this approach is an auxiliary problem with discrete obstacle. Applications to various discontinuous Galerkin finite element methods are presented. Numerical experiments show that the new estimator obtained in this article performs better.

Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

Taming Control Divergence in GPUs through Control Flow Linearization

Branch divergence is a very commonly occurring performance problem in GPGPU in which the execution of diverging branches is serialized to execute only one control flow path at a time. Existing hardware mechanism to reconverge threads using a stack causes duplicate execution of code for unstructured control flow graphs. Also the stack mechanism cannot effectively utilize the available parallelism among diverging branches. Further, the amount of nested divergence allowed is also limited by depth of the branch divergence stack. In this paper we propose a simple and elegant transformation to handle all of the above mentioned problems. The transformation converts an unstructured CFG to a structured CFG without duplicating user code. It incurs only a linear increase in the number of basic blocks and also the number of instructions. Our solution linearizes the CFG using a predicate variable. This mechanism reconverges the divergent threads as early as possible. It also reduces the depth of the reconvergence stack. The available parallelism in nested branches can be effectively extracted by scheduling the basic blocks to reduce the effect of stalls due to memory accesses. It can also increase execution efficiency of nested loops with different trip counts for different threads. We implemented the proposed transformation at PTX level using the Ocelot compiler infrastructure. We evaluated the technique using various benchmarks to show that it can be effective in handling the performance problem due to divergence in unstructured CFGs.

A Variant of the Hadwiger-Debrunner (p, q)-Problem in the Plane

Let X be a convex curve in the plane (say, the unit circle), and let be a family of planar convex bodies such that every two of them meet at a point of X. Then has a transversal of size at most . Suppose instead that only satisfies the following ``(p, 2)-condition'': Among every p elements of , there are two that meet at a common point of X. Then has a transversal of size . For comparison, the best known bound for the Hadwiger-Debrunner (p, q)-problem in the plane, with , is . Our result generalizes appropriately for if is, for example, the moment curve.

A posteriori error estimates of discontinuous Galerkin methods for the Signorini problem

A reliable and efficient a posteriori error estimator is derived for a class of discontinuous Galerkin (DG) methods for the Signorini problem. A common property shared by many DG methods leads to a unified error analysis with the help of a constraint preserving enriching map. The error estimator of DG methods is comparable with the error estimator of the conforming methods. Numerical experiments illustrate the performance of the error estimator. (C) 2015 Elsevier B.V. All rights reserved.

1D Tight-Binding Models Render Quantum First Passage Time ``Speakable''

The calculation of First Passage Time (moreover, even its probability density in time) has so far been generally viewed as an ill-posed problem in the domain of quantum mechanics. The reasons can be summarily seen in the fact that the quantum probabilities in general do not satisfy the Kolmogorov sum rule: the probabilities for entering and non-entering of Feynman paths into a given region of space-time do not in general add up to unity, much owing to the interference of alternative paths. In the present work, it is pointed out that a special case exists (within quantum framework), in which, by design, there exists one and only one available path (i.e., door-way) to mediate the (first) passage -no alternative path to interfere with. Further, it is identified that a popular family of quantum systems - namely the 1d tight binding Hamiltonian systems - falls under this special category. For these model quantum systems, the first passage time distributions are obtained analytically by suitably applying a method originally devised for classical (stochastic) mechanics (by Schroedinger in 1915). This result is interesting especially given the fact that the tight binding models are extensively used in describing everyday phenomena in condense matter physics.

QoS Constrained Optimal Sink and Relay Placement in Planned Wireless Sensor Networks

We are given a set of sensors at given locations, a set of potential locations for placing base stations (BSs, or sinks), and another set of potential locations for placing wireless relay nodes. There is a cost for placing a BS and a cost for placing a relay. The problem we consider is to select a set of BS locations, a set of relay locations, and an association of sensor nodes with the selected BS locations, so that the number of hops in the path from each sensor to its BS is bounded by h(max), and among all such feasible networks, the cost of the selected network is the minimum. 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, and is hard to even approximate within a constant factor. For this problem, we propose a polynomial time approximation algorithm (SmartSelect) based on a relay placement algorithm proposed in our earlier work, along with a modification of the greedy algorithm for weighted set cover. We have analyzed the worst case approximation guarantee for this algorithm. We have also proposed a polynomial time heuristic to improve upon the solution provided by SmartSelect. Our numerical results demonstrate that the algorithms provide good quality solutions using very little computation time in various randomly generated network scenarios.

Ray tracing based path-length calculations for polarized light tomographic imaging

A ray tracing based path length calculation is investigated for polarized light transport in a pixel space. Tomographic imaging using polarized light transport is promising for applications in optical projection tomography of small animal imaging and turbid media with low scattering. Polarized light transport through a medium can have complex effects due to interactions such as optical rotation of linearly polarized light, birefringence, diattenuation and interior refraction. Here we investigate the effects of refraction of polarized light in a non-scattering medium. This step is used to obtain the initial absorption estimate. This estimate can be used as prior in Monte Carlo (MC) program that simulates the transport of polarized light through a scattering medium to assist in faster convergence of the final estimate. The reflectance for p-polarized (parallel) and s-polarized (perpendicular) are different and hence there is a difference in the intensities that reach the detector end. The algorithm computes the length of the ray in each pixel along the refracted path and this is used to build the weight matrix. This weight matrix with corrected ray path length and the resultant intensity reaching the detector for each ray is used in the algebraic reconstruction (ART) method. The proposed method is tested with numerical phantoms for various noise levels. The refraction errors due to regions of different refractive index are discussed, the difference in intensities with polarization is considered. The improvements in reconstruction using the correction so applied is presented. This is achieved by tracking the path of the ray as well as the intensity of the ray as it traverses through the medium.

Framework for morphometric classification of cells in imaging flow cytometry

Imaging flow cytometry is an emerging technology that combines the statistical power of flow cytometry with spatial and quantitative morphology of digital microscopy. It allows high-throughput imaging of cells with good spatial resolution, while they are in flow. This paper proposes a general framework for the processing/classification of cells imaged using imaging flow cytometer. Each cell is localized by finding an accurate cell contour. Then, features reflecting cell size, circularity and complexity are extracted for the classification using SVM. Unlike the conventional iterative, semi-automatic segmentation algorithms such as active contour, we propose a noniterative, fully automatic graph-based cell localization. In order to evaluate the performance of the proposed framework, we have successfully classified unstained label-free leukaemia cell-lines MOLT, K562 and HL60 from video streams captured using custom fabricated cost-effective microfluidics-based imaging flow cytometer. The proposed system is a significant development in the direction of building a cost-effective cell analysis platform that would facilitate affordable mass screening camps looking cellular morphology for disease diagnosis. Lay description In this article, we propose a novel framework for processing the raw data generated using microfluidics based imaging flow cytometers. Microfluidics microscopy or microfluidics based imaging flow cytometry (mIFC) is a recent microscopy paradigm, that combines the statistical power of flow cytometry with spatial and quantitative morphology of digital microscopy, which allows us imaging cells while they are in flow. In comparison to the conventional slide-based imaging systems, mIFC is a nascent technology enabling high throughput imaging of cells and is yet to take the form of a clinical diagnostic tool. The proposed framework process the raw data generated by the mIFC systems. The framework incorporates several steps: beginning from pre-processing of the raw video frames to enhance the contents of the cell, localising the cell by a novel, fully automatic, non-iterative graph based algorithm, extraction of different quantitative morphological parameters and subsequent classification of cells. In order to evaluate the performance of the proposed framework, we have successfully classified unstained label-free leukaemia cell-lines MOLT, K562 and HL60 from video streams captured using cost-effective microfluidics based imaging flow cytometer. The cell lines of HL60, K562 and MOLT were obtained from ATCC (American Type Culture Collection) and are separately cultured in the lab. Thus, each culture contains cells from its own category alone and thereby provides the ground truth. Each cell is localised by finding a closed cell contour by defining a directed, weighted graph from the Canny edge images of the cell such that the closed contour lies along the shortest weighted path surrounding the centroid of the cell from a starting point on a good curve segment to an immediate endpoint. Once the cell is localised, morphological features reflecting size, shape and complexity of the cells are extracted and used to develop a support vector machine based classification system. We could classify the cell-lines with good accuracy and the results were quite consistent across different cross validation experiments. We hope that imaging flow cytometers equipped with the proposed framework for image processing would enable cost-effective, automated and reliable disease screening in over-loaded facilities, which cannot afford to hire skilled personnel in large numbers. Such platforms would potentially facilitate screening camps in low income group countries; thereby transforming the current health care paradigms by enabling rapid, automated diagnosis for diseases like cancer.