Data sizes are growing rapidly, leading to large document sizes and higher processing times. With the unprecedented growth in structured and semi-structured data, and their processing in various applications, XML continues to be a preferred choice as a standard data format and exchange. This standardization permits vendors to build tools for parsing and querying XML data. Unfortunately, the absolute running times of these tools quickly become prohibitive for large XML data. In such a situation, parallel processing becomes imperative. However, parsing and querying XML documents in parallel present significant challenges. Parsing is particularly difficult due to the inherent sequential and hierarchical nature of XML data, while complex querying with regular expressions is constrained by memory limitations. In this work, we develop a parallel XML parser and a parallel XML query engine with support for regular expressions. It supports not only the traditional startswith and endswith XPath queries, but also presence of arbitrary Kleene-closures. An extensive experimental evaluation of our tool illustrates significant improvements over standard libXML, especially at scale, achieving over$32 \times$speedup.

Capacitated Vehicle Routing Problem (CVRP) is an important combinatorial optimization problem, which is also NP-hard. A wide array of heuristics have been proposed in the literature to obtain an approximate solution to CVRP. To improve the execution time, parallel methods have been developed for accelerating metaheuristics-based algorithms, genetic algorithms, and evolutionary algorithms for CVRP. Despite these advances, our experiments with the state-of-the-art parallel solutions indicate that their run times are too high to be practically useful. The combinatorial explosion is so high that the execution time is prohibitively large even on mid-sized CVRP instances having a few hundred customers. In this work, we propose a novel technique which combines local search and randomization for solving CVRP faster with reasonable accuracy, even on large problem instances. Our usage of randomization enables searching a large space of candidate solutions. We experimentally compare our proposed method with the state-of-the-art GPU implementations on diverse input instances and demonstrate the efficacy of our approach. Our sequential and shared-memory parallel implementations are on an average 36--1189× faster than the state-of-the-art GPU-parallel genetic algorithms while also achieving a superior solution quality. Furthermore, our reported solutions are close to the current best-known solutions from CVRPLIB.

Designing parallel graph algorithms on GPUs has been challenging. We observe three limitations with the existing work. First, algorithms often rely on only one of the strategies to propagate information: push or pull. We observe that neither is an optimal choice in many cases. Second, the cost of updating the underlying data structures per iteration is high. This results in a significant performance overhead. Third, considering the in-herent irregularity of graph processing, one-size-fits-all approach is too rigid for different types of graphs. In this work, we address these shortcomings by improving the processing of an existing graph framework, Subway. In particular, we propose a novel technique in terms of amalgamating the two propagation strategies (push and pull) into a hybrid traversal strategy. In this, the vertices of the graph propagate their information by pulling the information from the neighbours, performing a local computation, and subsequently pushing the result to all the neighbours, all within an iteration. We propose to reuse the SubCSR structure in Subway across a few iterations to significantly reduce the computational overhead, but without compromising the correctness or efficiency of the algorithm. Furthermore, we explore heuristics on when to use push, pull, or hybrid traversal strategies. We illustrate the effectiveness of our three-pronged approach by applying it to four popular graph algorithms: Connected Components (CC), Single-Source Shortest Path (SSSP), Breadth First Search (BFS) and Page Rank (PR) on an NVIDIA GeForce RTX 3060 GPU. Our extensive experimental evaluation on GeForce RTX 3060 GPU reveals that the proposed hybrid approach with adaptive heuristics and approximate subCSR computation is effective in reducing the execution time of CC, SSSP, and PR by 31 %, 7.56%, and 6.43% respectively, compared to the minimum of push or pull algorithm that uses subCSR structure.

Summary The surge in data sizes in fluid processing applications necessitates partitioning the data into clusters and studying their representatives instead of studying each voxel data point. In addition, the dynamic nature of these data poses further challenges. Under such circumstances, it becomes essential to develop an approach that can handle the delta data with minimal updates to the underlying data structure, without processing the complete data from scratch on every update. However, this poses synchronization challenges in parallelization. In this article, we propose SLCoDD (single‐linkage clustering of dynamic data), a geometric distance based dynamic clustering and its multi‐core parallelization using OpenMP. To improve efficiency, SLCoDD exploits geometric properties of the bounding squares. We illustrate trade‐offs in various ways of performing point additions to clusters, point deletions, and their batched versions. Using a suite of large inputs, we demonstrate the effectiveness of SLCoDD. SLCoDD's fully dynamic version achieves a substantial geomean speedup of over the static parallel version and of over the dynamic sequential version.

Betweenness centrality (BC) is a popular centrality measure, based on shortest paths, used to quantify the importance of vertices in networks. It is used in a wide array of applications including social network analysis, community detection, clustering, biological network analysis, and several others. The state-of-the-art Brandes’ algorithm for computing BC has time complexities of and for unweighted and weighted graphs, respectively. Brandes’ algorithm has been successfully parallelized on multicore and manycore platforms. However, the computation of vertex BC continues to be time-consuming for large real-world graphs. Often, in practical applications, it suffices to identify the most important vertices in a network; that is, those having the highest BC values. Such applications demand only the top vertices in the network as per their BC values but do not demand their actual BC values. In such scenarios, not only is computing the BC of all the vertices unnecessary but also exact BC values need not be computed. In this work, we attempt to marry controlled approximations with parallelization to estimate the k -highest BC vertices faster, without having to compute the exact BC scores of the vertices. We present a host of techniques to determine the top- k vertices faster , with a small inaccuracy, by computing approximate BC scores of the vertices. Aiding our techniques is a novel vertex-renumbering scheme to make the graph layout more structured , which results in faster execution of parallel Brandes’ algorithm on GPU. Our experimental results, on a suite of real-world and synthetic graphs, show that our best performing technique computes the top- k vertices with an average speedup of 2.5× compared to the exact parallel Brandes’ algorithm on GPU, with an error of less than 6%. Our techniques also exhibit high precision and recall, both in excess of 94%.

The problem of test-case prioritization has been pursued for over three decades now and continues to be one of the active topics in software testing research. In this paper, we focus on a code-coverage based regression test-prioritization solution (${{\sf Colosseum}}$) that takes into account the position of changed (delta) code elements (basic-blocks) along the loop-free straight-line execution path of the regression test-cases. We propose a heuristic that logically associates each of these paths with three parameters: (i) the offset (displacementa) of the first delta from the starting basic-block, (ii) the offset (displacementc) of the last delta from the terminating basic block, and (iii) the average scattering (displacementb) within all the intermediate basic-blocks. We hypothesize that a regression test-case path with a shorter overall displacement has a good chance of propagating the affects of the code-changes to the observable outputs in the program.${{\sf Colosseum}}$prioritizes test-cases with smaller overall displacements and executes them early in the regression test-execution cycle. The underlying intuition is that the probability of a test-case revealing a regression fault depends on the probability of the corresponding change propagation. The change in this context can potentially lead to an error. Extending this logic, delta displacement provides an approximation to failed error propagation. Evaluation on 20 open-source C projects from the Software-artifact Infrastructure Repository and GitHub (totaling: 694,512 SLOC, 280 versions, and 69,305 test-cases) against four state-of-the-art prioritizations reveals that:${{\sf Colosseum}}$outperforms the competitors with an overall 84.61% success in terms of 13 prioritization effectiveness metrics, majority of which prefer to execute top-$k\%$prioritized test-cases.

In this extended abstract, we present consensus test-case prioritization by applying a few well-established social choice theoretic rank-aggregation mechanisms to multiple independent (stand-alone) test-case prioritizations. Our end-goal is to derive a black-box consensus ordering of test-cases by rank-aggregating the stand-alone test-execution sequences using various consensus operators.

Given a temporal graph G, a source vertex s, and a departure time at source vertex ts, the earliest arrival time problem (EAT) is to start from s on or after tsand reach all the vertices in G as early as possible. Ni et al. have proposed a parallel algorithm for EAT and obtained a speedup up to 9.5× on real-world graphs with respect to the connection-scan serial algorithm by using multi-core processors. We propose a topology-driven parallel algorithm for EAT on public transport networks and implement using general-purpose programming on the graphics processing unit (GPU). A temporal connection in a temporal graph for a public transport network is associated with a departure time and a duration time, and many connections exist from u to v for an edge ( u, v). We propose two pruning techniques connection-type and clustering, and use arithmetic progression technique appropriately to process many connections of an edge, without scanning all of them. In the connection-type technique, the connections of an edge with the same duration are grouped together. In the clustering technique, we follow 24-hour format and the connections of an edge are partitioned into 24 clusters so that the departure time of connections in the ithcluster is at least i-hour and at most i+1-hour. The arithmetic progression technique helps to store a sequence of departure times of various connections in a compact way. We propose a hybrid approach to combine the three techniques (connection-type, clustering and arithmetic progression) in an efficient way. Our techniques achieve an average speedup up to 61× when compared to the existing connection-scan serial algorithm running on CPU. Also, the average speedup of our algorithm is 12.65× against the parallel edge-scan-dependency graph algorithm running on GPU.

Parallelizing graph algorithms on GPUs is challenging due to the irregular memory accesses involved in graph traversals. In particular, three important GPU-specific aspects affect performance: memory coalescing, memory latency, and thread divergence. In this work, we attempt to tame these challenges using approximate computing. We target graph applications on GPUs that can tolerate some degradation in the quality of the output for obtaining the result in short order. We propose three techniques for boosting the performance of graph processing on the GPU by injecting approximations in a controlled manner. The first one creates a graph isomorph that brings relevant nodes nearby in memory and adds controlled replica of nodes to improve coalescing. The second reduces memory latency by facilitating the processing of subgraphs inside shared memory by adding edges among specific nodes and processing well-connected subgraphs iteratively inside shared-memory. The third technique normalizes degrees across nodes assigned to a warp to reduce thread divergence. Each of the techniques offers notable performance benefits, and provides a knob to control the amount of inaccuracy added to an execution. We demonstrate the effectiveness of the proposed techniques using a suite of five large graphs with varied characteristics and five popular graph algorithms.

Summary The syntactic information of a program can be represented as resource description framework (RDF) triples called program triples. We propose an extensible static analysis framework, called OPAL—Ontology‐based Program AnaLysis. The framework enables formal representation of external knowledge, such as usage knowledge of libraries and domain knowledge. Utilizing this knowledge and the program triples, we compute the semantic information, called static trace of the program. It is generated through path‐sensitive intraprocedural traversal of the program. We approximate information in case of loops by unrolling them a fixed number of times. The main contribution of the framework is to store the static trace as RDF triples called semantic triples. They are described using the Program Analysis ontology proposed in this article. The program triples and the semantic triples are together called consolidated program triples. These triples are stored and used to accelerate the execution of client‐analyses specified by the end user. In the framework, a client‐analysis is specified by a set of conjunctive expressions that use SPARQL (W3C RDF query language) queries. The framework is effective for the client‐analyses that warrant sound and approximate information. The effectiveness is assessed first, using two source‐code‐analyses that require only the program triples, and then 10 intraprocedural path‐sensitive analyses that require the consolidated program triples. Using NPB and SPEC 2006 benchmarks, we achieve an improvement in the conciseness of analysis specifications. Also, the execution time using OPAL is competitive to LLVM's clang for individual analysis and outperforms clang over a series of analyses because of the reuse of consolidated program triples.

Popular Android applications undergo frequent releases. Ensuring functional testing of the new features, as well as regression testing of the previous functionality, are time-consuming and error-prone. Thus, there is a need for a tool that eases the testing efforts as well as saves the overall time of the product release cycle. In this work, we present QADroid, the first activity- and event-aware regression selection tool for Android apps. Salient features of QADroid are: (i) a richer change-set analyzer that covers code as well as non-code components for regression, (ii) it presents a pictorial representation of the app’s functioning, and (iii) it displays the regression points in the app as a mapping between activities to user-elements to events. Features (ii) and (iii) help the testers in understanding the technical findings better. We evaluated QADroid on 1105 releases of 50 open source Android projects. The results show that QADroid reduced the activity selection by 58% and event selection by 74% compared to the traditional way of exhaustive testing of all activities and events, thereby significantly reducing the manual testing efforts.

Parallelizing graph algorithms on GPUs is challenging due to the irregular memory accesses and control-flow involved in graph traversals. In this work, we tame these challenges by injecting approximations. In particular, we improve memory coalescing by renumbering and replicating nodes, memory latency by adding edges among specific nodes brought into shared memory, and thread-divergence by normalizing degrees across nodes assigned to a warp. Using a suite of graphs with varied characteristics and five popular algorithms, we demonstrate the effectiveness of our proposed techniques. Our approximations for coalescing, memory latency and thread-divergence lead to mean speedups of 1.3×, 1.41× and 1.06× achieving accuracies of 83%, 78% and 84%, respectively.

Summary We study five popular auto‐parallelization frameworks (Cetus, Par4all, Rose, ICC, and Pluto) and compare them qualitatively as well as quantitatively. All the frameworks primarily deal with loop parallelization but differ in the techniques used to identify parallelization opportunities. Due to this variance, various aspects, such as certain loop transformations, are supported only in a few frameworks. The frameworks exhibit varying abilities in handling loop‐carried dependence and, therefore, achieve different amounts of speedup on widely used PolyBench and NAS parallel benchmarks. In particular, Intel C Compiler (ICC) fares as an overall good parallelizer. Our study also highlights the need for more sophisticated analyses, user‐driven parallelization, and meta‐auto‐parallelizer that provides combined benefits of various frameworks.

We study multi-granularity locking in hierarchies. Existing popular mechanisms for multi-granularity locking work on two extremes: fine-grained locking which maximizes concurrency, and coarsegrained locking which minimizes the locking cost. Between the two extremes, there exist several pareto-optimal options which provide a trade-off between the concurrency cost and the locking cost. These options are captured under multi-granularity locking (MGL) protocol, but there exists no methodical way to choose a good MGL option. In this work, we present a locking technique, NumLock, which chooses optimal locking combination to serve MGL requests. NumLock works in two phases: first, it generates few pareto-optimal MGL options and second, it quickly analyzes these options to report the optimal one. We propose a greedy algorithm to generate a subset of the pareto-optimal options. We further improve the concurrency by abstracting the non-planar hierarchy as logical planar sub-hierarchies using multiple intervals. Our study reveals that the lock manager must explore various MGL options for achieving the best parallel performance, and that the extreme options often used in practice are suboptimal. We validate our claim quantitatively using an XML database as well as STMBench7, and show that the intermediate MGL options perform better compared to the existing state-of-the-art methods. In particular, NumLock achieves 65% reduction in execution time for the XML database, and 25% throughput improvement on STMBench7.

Asymmetric multicore processors (AMP) fall under a special subcategory of modern-day heterogeneous multicore architectures with different participating core types executing a common instruction set architecture. The innate asymmetry in the performance of different cores in AMPs poses interesting challenges. Irregular workloads, such as graph algorithms, intensify these challenges as the parallel workloads in these algorithms cannot be precisely characterized at compile time. In this paper, we propose a framework named scheduler for irregular AMPs, which optimizes the efficiency of the given AMP system for a given algorithm-graph pair by optimizing the graph representation and using a predictor to find the optimal configurations to run the algorithm-graph pair. The optimization is performed in two stages: 1) finding an optimal graph representation and 2) finding an optimal hardware configuration to run the input algorithm-graph pair. We have tested the efficiency of our system on five different graph algorithms over eight real-world and synthetic graphs. On an average, we see 42.82% improvement in energy delay product over the base case.

Graph models of social information systems typically contain trillions of edges. Such big graphs cannot beprocessed on a single machine. The graph object must bepartitioned and distributed among machines and processedin parallel on a computer cluster. Programming such systemsis very challenging. In this work, we present DH-Falcon, a graph DSL (domain-specific language) which can be usedto implement parallel algorithms for large-scale graphs, tar-geting Distributed Heterogeneous (CPU and GPU) clusters. DH-Falcon compiler is built on top of the Falcon compiler, which targets single node devices with CPU and multipleGPUs. An important facility provided by DH-Falcon is that itsupports mutation of graph objects, which allows programmerto write dynamic graph algorithms. Experimental evaluationshows that DH-Falcon matches or outperforms state-of-the-art frameworks and gains a speedup of up to 13×.

Generational Mark-Sweep Garbage Collection is a widely used garbage collection technique. However, the garbage collector has poor execution efficiency for large programs. Aggressive collection causes execution pauses in the program, while reducing the collection frequency leads to memory wastage. In this work, we develop FastCollect, a parallel version of the generational mark-sweep garbage collector running on a graphics processing unit (GPU). At the core of our parallel implementation lies a parallel Depth First Search using a space-efficient concurrent stack, which we develop for the young and the mature garbage collection. To further improve performance, (i) we reduce thread-divergence and improve load-balancing by devising a distributed work-stealing approach, (ii) we optimize our garbage collection algorithm to reduce the number of atomic instructions, (iii) we exploit the memory hierarchy to design a hybrid stack, and (iv) we extract multiple adjacent objects simultaneously by exploiting vectorized memory accesses. We implemented FastCollect in Java Hotspot VM and evaluated our results by executing DaCapo benchmarks. FastCollect is 4-5x faster than the Parallel Hotspot garbage collector and 42% faster than a previous GPU implementation. In addition, while the existing GPU version requires memory linear in the number of compute units, FastCollect's memory requirement is fixed and low. FastCollect not only improves execution time of garbage collection, but also relieves the CPU for improved user interaction.

We present an information-merging technique for efficient computation of points-to information for C programs. Invalid use of pointers can lead to hard-to-find bugs and may expose security vulnerabilities. Thus, analyzing them is critical for software analysis as well as optimization. Pointer analysis is a key step during compilation, and the computed points-to information is useful for client analyses from varied domains such as bug finding, data-flow analysis, identifying security vulnerabilities, and parallelization, to name a few. Former research on pointer analysis has indicated that the main bottleneck towards scalability is large propagation of points-to information in the constraint graph. To reduce the propagation cost, we present a technique based on temporal similarity of points-to sets. The method tracks pointers whose dynamically changing points-to information remains equal for a while. Based on the optimism gained by observing the points-to sets over time, the analysis decides to merge the corresponding nodes. Using the notion of merge and split, we build a family of points-to analyses, and compare their relative precisions in the context of existing analyses. We illustrate the effectiveness of our approach using a suite of sixteen SPEC 2000 benchmarks and three large open-source programs, and show that the technique improves the analysis time over BDD and bitmap based Hybrid Cycle Detection, well-known Andersen's analysis, and Deep Propagation, affecting minimal precision (precision is 96.4% on an average). Specifically, it is faster than Deep Propagation by 45%.

We present efficient locking mechanisms for hierarchical data structures. Several applications work on an abstract hierarchy of objects, and a parallel execution on this hierarchy necessitates synchronization across workers operating on different parts of the hierarchy. Existing synchronization mechanisms are either too coarse, too inefficient, or too ad hoc, resulting in reduced or unpredictable amount of concurrency. We propose a new locking approach based on the structural properties of the underlying hierarchy. We show that the developed techniques are efficient even when the hierarchy is an arbitrary graph, and are applicable even when the hierarchy involves mutation. Theoretically, we present our approach as a locking-cost-minimizing instance of a generic algebraic model of synchronization for hierarchical data structures. Using STMBench7, we illustrate considerable reduction in the locking cost, resulting in an average throughput improvement of 42%.

Summary Pointer analysis is a key static analysis during compilation. Several client analyses and transformations rely on precise pointer information to optimize programs. Therefore, it is paramount to improve the efficiency of pointer analysis. A critical piece of an inclusion‐based pointer analysis is online cycle detection. The efficiency of pointer analysis is significantly influenced by the efficacy of detecting cycles. Existing approaches perform poorly when theyguesscycle formation in the constraint graph. Thus, the number of false cycle‐detection triggers of the state‐of‐the‐art methods is considerably high (over 99% on Standard Performance Evaluation Corporation (SPEC) benchmarks). In this paper, we propose bootstrapping as a way to improve cycle detection predictability of pointer analysis. The main idea is to run a sequence of increasingly precise analyses to feed into the next more precise analysis to improve the efficiency of the latter analysis. In this process, we develop a new notion of pointer equivalence called constraint equivalence. Using Steensgaard's fast unification algorithm as the bootstrap, we devise a new cycle detection method for Andersen's inclusion‐based analysis. We measure the effectiveness of our approach using a suite of programs including SPEC 2000 benchmarks and two open‐source programs, and find that our method can reduce the number of false cycle detections by almost 22× compared with a state‐of‐the‐art method. This leads to an overall analysis time improvement of 18% on an average. Copyright © 2015 John Wiley & Sons, Ltd.

Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy—even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particular hardware configuration of heterogeneous systems consisting of multicore CPUs and GPUs is challenging, time consuming, and error prone. To address these issues, we propose a domain-specific language (DSL), Falcon, for implementing graph algorithms that (i) abstracts the hardware, (ii) provides constructs to write explicitly parallel programs at a higher level, and (iii) can work with general algorithms that may change the graph structure (morph algorithms). We illustrate the usage of our DSL to implement local computation algorithms (that do not change the graph structure) and morph algorithms such as Delaunay mesh refinement, survey propagation, and dynamic SSSP on GPU and multicore CPUs. Using a set of benchmark graphs, we illustrate that the generated code performs close to the state-of-the-art hand-tuned implementations.

We present an auto-parallelization technique for generating GPU implementation of data-structure operations from a sequential specification. The technique partitions the data-structure operations into barrier-separated phases such that each phase executes only homogeneous operations. Homogeneity is dictated by the method type, which is derived from the specification. Two key aspects of our technique are: (i) it ensures linearizability of the data-structure, and (ii) it is capable of composing multiple data-structure operations with the guarantee of optimal barrier placement, which we formally prove. We illustrate the usefulness of our techniques by synthesizing efficient GPU implementations of practical graph algorithms like single-source shortest paths which uses a concurrent worklist, Delaunay mesh refinement that uses a worklist and a mesh, and a doubly linked-list supporting arbitrary insertion and deletion.

We present techniques for efficient computation of points-to information for C programs. Pointer analysis is an important phase in the compilation process. The computed points-to information and the alias information is useful for client analyses from varied domains such as bug finding, data-flow analysis, identifying security vulnerabilities, and parallelization, to name a few. Former research on pointer analysis has indicated that the main bottleneck towards scalability is manifested by the presence of complex constraints (load p = *q and store *p = q constraints) in the program. Complex constraints add edges to the constraint graph in an unpredictable manner and are responsible for initiating propagation of large amounts of points-to information across edges. We identify that the root cause to this issue is in the homogeneous structure in the constraint graph, due to which existing analyses treat loads and stores in a uniform manner. To address these issues, we present two techniques. First, we represent a constraint graph in a non-homogeneous manner, treat loads and stores in different ways, and employ a push-pull model for non-uniform propagation. Second, we propose lazy propagation which propagates information in the constraint graph only when necessary. We illustrate the effectiveness of our techniques using six large open-source programs and show that they improve the analysis time over a state-of-the-art BDD-based analysis by 33% and over Deep Propagation by 21%.

Irregular algorithms are algorithms with complex main data structures such as directed and undirected graphs, trees, etc. A useful abstraction for many irregular algorithms is its operator formulation in which the algorithm is viewed as the iterated application of an operator to certain nodes, called active nodes, in the graph. Each operator application, called an activity, usually touches only a small part of the overall graph, so nonoverlapping activities can be performed in parallel. In topology-driven implementations, all nodes are assumed to be active so the operator is applied everywhere in the graph even if there is no work to do at some nodes. In contrast, in data-driven implementations the operator is applied only to nodes at which there might be work to do. Multicore implementations of irregular algorithms are usually data-driven because current multicores only support small numbers of threads and work-efficiency is important. Conversely, many irregular GPU implementations use a topology-driven approach because work inefficiency can be counterbalanced by the large number of GPU threads. In this paper, we study data-driven and topology-driven implementations of six important graph algorithms on GPUs. Our goal is to understand the tradeoffs between these implementations and how to optimize them. We find that data-driven versions are generally faster and scale better despite the cost of maintaining a worklist. However, topology-driven versions can be superior when certain algorithmic properties are exploited to optimize the implementation. These results led us to devise hybrid approaches that combine the two techniques and outperform both of them.

There is growing interest in using GPUs to accelerate graph algorithms such as breadth-first search, computing page-ranks, and finding shortest paths. However, these algorithms do not modify the graph structure, so their implementation is relatively easy compared to general graph algorithms like mesh generation and refinement, which morph the underlying graph in non-trivial ways by adding and removing nodes and edges. We know relatively little about how to implement morph algorithms efficiently on GPUs.

Compilation of real-world programs often requires hours. The term nightly build known to industrial researchers is an artifact of long compilation times. Our goal is to reduce the absolute analysis times for large C codes (of the order of millions of lines). Pointer analysis is one of the key analyses performed during compilation. Its scalability is paramount to achieve the efficiency of the overall compilation process and its precision directly affects that of the client analyses. In this work, we design a time- and space-efficient flow-sensitive pointer analysis and parallelize it on graphics processing units. Our analysis proposes to use an extended bloom filter, called multibloom, to store points-to information in an approximate manner and develops an analysis in terms of the operations over the multibloom. Since bloom filter is a probabilistic data structure, we develop ways to gain back the analysis precision. We achieve effective parallelization by achieving memory coalescing, reducing thread divergence, and improving load balance across GPU warps. Compared to a state-of-the-art sequential solution, our parallel version achieves a 7.8 × speedup with less than 5% precision loss on a suite of six large programs. Using two client transformations, we show that this loss in precision only minimally affects a client’s precision.

Points-to analysis is a key compiler analysis. Several memory related optimizations use points-to information to improve their effectiveness. Points-to analysis is performed by building a constraint graph of pointer variables and dynamically updating it to propagate more and more points-to information across its subset edges. So far, the structure of the constraint graph has been only trivially exploited for efficient propagation of information, e.g., in identifying cyclic components or to propagate information in topological order. We perform a careful study of its structure and propose a new inclusion-based flow-insensitive context-sensitive points-to analysis algorithm based on the notion of dominant pointers. We also propose a new kind of pointer-equivalence based on dominant pointers which provides significantly more opportunities for reducing the number of pointers tracked during the analysis. Based on this hitherto unexplored form of pointer-equivalence, we develop a new context-sensitive flow insensitive points-to analysis algorithm which uses incremental dominator update to efficiently compute points-to information. Using a large suite of programs consisting of SPEC 2000 benchmarks and five large open source programs we show that our points-to analysis is 88% faster than BDD-based Lazy Cycle Detection and 2× faster than Deep Propagation. We argue that our approach of detecting dominator-based pointer-equivalence is a key to improve points-to analysis efficiency.

Pervasive use of pointers in large-scale real-world applications continues to make points-to analysis an important optimization-enabler. Rapid growth of software systems demands a scalable pointer analysis algorithm. A typical inclusion-based points-to analysis iteratively evaluates constraints and computes a points-to solution until a fixpoint. In each iteration, (i) points-to information is propagated across directed edges in a constraint graph G and (ii) more edges are added by processing the points-to constraints. We observe that prioritizing the order in which the information is processed within each of the above two steps can lead to efficient execution of the points-to analysis. While earlier work in the literature focuses only on the propagation order, we argue that the other dimension, that is, prioritizing the constraint processing, can lead to even higher improvements on how fast the fixpoint of the points-to algorithm is reached. This becomes especially important as we prove that finding an optimal sequence for processing the points-to constraints is NP-Complete. The prioritization scheme proposed in this paper is general enough to be applied to any of the existing points-to analyses. Using the prioritization framework developed in this paper, we implement prioritized versions of Andersen's analysis, Deep Propagation, Hardekopf and Lin's Lazy Cycle Detection and Bloom Filter based points-to analysis. In each case, we report significant improvements in the analysis times (33%, 47%, 44%, 20% respectively) as well as the memory requirements for a large suite of programs, including SPEC 2000 benchmarks and five large open source programs.

The BANKS system supports keyword search on databases storing structured/semi-structured data. Answers to keyword queries are ranked, and as in IR systems, the top answers may not be exactly what a user is looking for. Further interaction with the system is required to narrow in on desired answers. We describe some of the new features that we have added to the BANKS system to improve user interaction. These include an extended query model, richer support for user feedback and better display of answers. 1.