Publications
Download everything as BibTeX or JSON. Names of my students are underlined.
Conferences
2027
-
Bring Your Own Formats and Kernels: Composable Abstractions for Sparse Matrix Computation
To appearAcceptance rate 23%
Real-world sparse matrices often feature multiple forms of structured sparsity—rectangular dense blocks, diagonal bands, and scattered entries—that no single storage format can efficiently exploit. Hybrid formats address this by storing each subregion of a matrix in its most efficient form. Existing hybrid approaches, however, only support fixed sets of formats and kernels, so incorporating a new representation or kernel requires modifying their internals. We present SABLE, a framework that lets users build bespoke hybrid formats compositionally through a plan–extract–dispatch interface. Users define extractors that carve a matrix into format-specific regions and kernels that emit specialized C code for each region; SABLE assembles these pieces into a single program specialized to the target matrix at compile time. Both components are independent and composable, so a new format automatically integrates with all existing kernels without any changes to the framework. We demonstrate this extensibility by introducing VDIA, a novel format for diagonal bands of non-uniform length, and composing it to build two new hybrid formats—VDIA+CSR and VDIA+VBR+CSR. We evaluate SABLE on SpMV and SpMM using matrices from the SuiteSparse benchmarks, demonstrating geometric-mean speedups over the best fully-sparse baselines of 1.10x/1.20× (SpMV/SpMM) for VBR+CSR, and 1.14×/1.31× for VDIA+CSR, with the full VDIA+VBR+CSR composition yielding a further 1.08×/1.25× over VBR+CSR.
2026
-
Taming the Hydra: Targeted Control-Flow Transformations for Dynamic Symbolic Execution
Acceptance rate 26%
Dynamic Symbolic Execution (DSE) suffers from the path explosion problem when the target program has many conditional branches. The classical approach for managing the path explosion problem is dynamic state merging. Dynamic state merging combines similar symbolic program states to avoid the exponential growth in the number of states during DSE. However, state merging still requires solver invocations at each program branch, even when both paths of the branch are feasible. Moreover, the best path search strategy for DSE may not create the best state merging opportunities. Some drawbacks of state merging can be mitigated by compile-time state merging (i.e., branch elimination by converting control-flow into dataflow). In this paper, we propose a non-semantics-preserving but failure-preserving compiler transformation for removing expensive symbolic branches in a program to improve the scalability of DSE. We have developed a framework for detecting spurious bugs that our transformation can insert. Finally, we show that our transformation can significantly improve the performance of DSE on various benchmark programs and help improve the performance of coverage and bug discovery of large real-world programs.
-
Rethinking Collision Detection on GPU Ray Tracing Architecture
Acceptance rate 20%
Discrete Collision Detection (DCD) is a fundamental task in several domains including particle-based physics simulations. Efficient DCD uses indexing structures such as Bounding Volume Hierarchy (BVH), but accelerating irregular BVH traversals demands meticulous efforts to achieve performance. Modern GPUs feature Ray Tracing (RT) architecture that provides hardware acceleration for BVH traversal and optimized drivers for BVH construction. Recent work has attempted to exploit RT architecture to accelerate DCD on spherical particles by reducing DCD to fixed-radius neighbor search. However, this reduction breaks down for particles with different radii, necessitating the use of large bounding boxes that result in a higher number of duplicate collisions and poor performance.
2025
-
Circuit Optimization using Arithmetic Table Lookups
Acceptance rate 29%
Fully Homomorphic Encryption (FHE) is a cryptographic technique that enables privacy-preserving computation. State-of-the-art Boolean FHE implementations provide a very low-level interface, usually exposing a limited set of Boolean gates that programmers must use to write their FHE applications. This programming model is unnecessarily restrictive: many Boolean FHE schemes support programmable bootstrapping , an operation that allows evaluation of an arbitrary fixed-size lookup table. However, most modern FHE compilers are only capable of reasoning about traditional Boolean circuits, and therefore struggle to take full advantage of programmable bootstrapping.
We present COATL, an FHE compiler that makes use of programmable bootstrapping to produce circuits that are smaller and more efficient than their traditional Boolean counterparts. COATL generates circuits using arithmetic lookup tables , a novel abstraction we introduce for reasoning about computations in Boolean FHE programs. We demonstrate on a variety of benchmarks that COATL can generate circuits that run up to 1.5× faster than those generated by other state-of-the-art compilation strategies.
-
RT–BarnesHut: Accelerating Barnes–Hut Using Ray-Tracing Hardware
Acceptance rate 20%
The n-body problem involves calculating the effect of bodies on each other. n-body simulations are ubiquitous in the fields of physics and astronomy and notoriously computationally expensive. The naïve algorithm for n-body simulations has the prohibiting O(n2) time complexity. Reducing the time complexity to O(n · lg(n)), the tree-based Barnes-Hut algorithm approximates the effect of bodies beyond a certain threshold distance. Other than algorithmic improvements, extensive research has gone into accelerating n-body simulations on GPUs and multi-core systems. However, Barnes-Hut is a tree-traversal algorithm, which makes it a poor target for acceleration using traditional GPU shader cores. In contrast, recent work shows that, for tree-based computations, GPU ray-tracing (RT) cores dominate shader cores. In this work, we reformulate the Barnes-Hut algorithm as a ray-tracing problem and implement it with NVIDIA OptiX. Our evaluation shows that the resulting system, RT-BarnesHut, outperforms current state-of-the-art GPU-based implementations.
2024
-
SparseAuto: An Auto-scheduler for Sparse Tensor Computations using Recursive Loop Nest Restructuring
Acceptance rate 39%
Automated code generation and performance enhancements for sparse tensor algebra have become essential in many real-world applications, such as quantum computing, physical simulations, computational chemistry, and machine learning. General sparse tensor algebra compilers are not always versatile enough to generate asymptotically optimal code for sparse tensor contractions. This paper shows how to generate asymptotically better schedules for complex sparse tensor expressions using kernel fission and fusion. We present generalized loop restructuring transformations to reduce asymptotic time complexity and memory footprint.
Furthermore, we present an auto-scheduler that uses a partially ordered set (poset)-based cost model that uses both time and auxiliary memory complexities to prune the search space of schedules. In addition, we highlight the use of Satisfiability Module Theory (SMT) solvers in sparse auto-schedulers to approximate the Pareto frontier of better schedules to the smallest number of possible schedules, with user-defined constraints available at compile-time. Finally, we show that our auto-scheduler can select better-performing schedules and generate code for them. Our results show that the auto-scheduler provided schedules achieve orders of-magnitude speedup compared to the code generated by the Tensor Algebra Compiler (TACO) for several computations on different real-world tensors.
-
Optimizing Layout of Recursive Datatypes with Marmoset: Or, Algorithms + Data Layouts = Efficient Programs
Acceptance rate 42%
While programmers know that memory representation of data structures can have significant effects on performance, compiler support to optimize the layout of those structures is an under-explored field. Prior work has optimized the layout of individual, non-recursive structures without considering how collections of those objects in linked or recursive data structures are laid out. This work introduces Marmoset, a compiler that optimizes the layouts of algebraic datatypes, with a special focus on producing highly optimized, packed data layouts where recursive structures can be traversed with minimal pointer chasing. Marmoset performs an analysis of how a recursive ADT is used across functions to choose a global layout that promotes simple, strided access for that ADT in memory. It does so by building and solving a constraint system to minimize an abstract cost model, yielding a predicted efficient layout for the ADT. Marmoset then builds on top of Gibbon, a prior compiler for packed, mostly-serial representations, to synthesize optimized ADTs. We show experimentally that Marmoset is able to choose optimal layouts across a series of microbenchmarks and case studies, outperforming both Gibbon’s baseline approach, as well as MLton, a Standard ML compiler that uses traditional pointer-heavy representations.
-
Garbage Collection for Mostly Serialized Heaps
Acceptance rate 47%
Over the years, traditional tracing garbage collectors have accumulated assumptions that may not hold in new language designs. For instance, we usually assume that run-time objects do not hold addressable sub-parts and have a size of at least one pointer. These fail in systems striving to eliminate pointers and represent data in a dense, serialized form, such as the Gibbon compiler. We propose a new memory management strategy for language runtimes with mostly serialized heaps. It uses a hybrid, generational collector, where regions are bump-allocated into the young generation and objects are bump-allocated within those regions. Minor collections copy data into larger regions in the old generation, compacting it further. The old generation uses region-level reference counting. The resulting system maintains high performance for data traversal programs, while significantly improving performance on other kinds of allocation patterns.
-
Arkade: k-Nearest Neighbor Search With Non-Euclidean Distances using GPU Ray Tracing
Best Paper AwardAcceptance rate 36%
High-performance implementations of k-Nearest Neighbor Search (kNN) in low dimensions use tree-based data structures. Tree algorithms are hard to parallelize on GPUs due to their irregularity. However, newer Nvidia GPUs offer hardware support for tree operations through ray-tracing cores. Recent works have proposed using RT cores to implement kNN search, but they all have a hardware-imposed constraint on the distance metric used in the search—the Euclidean distance. We propose and implement two reductions to support kNN for a broad range of distances other than the Euclidean distance: Arkade Filter-Refine and Arkade Monotone Transformation, each of which allows non-Euclidean distance-based nearest neighbor queries to be performed in terms of the Euclidean distance. With our reductions, we observe that kNN search time speedups range between 1.6x-200x and 1.3x-33.1x over various state-of-the-art GPU shader core and RT core baselines, respectively. In evaluation, we provide several insights on RT architectures’ ability to efficiently build and traverse the tree by analyzing the kNN search time trends.
2023
-
RT-kNNS Unbound: Using RT Cores to Accelerate Unrestricted Neighbor Search
Acceptance rate 29%
The problem of identifying the k-Nearest Neighbors (kNNS) of a point has proven to be very useful both as a standalone application and as a subroutine in larger applications. Given its far-reaching applicability in areas such as machine learning and point clouds, extensive research has gone into leveraging GPU acceleration to solve this problem. Recent work has shown that using Ray Tracing cores in recent GPUs to accelerate kNNS is much more efficient compared to traditional acceleration using shader cores. However, the existing translation of kNNS to a ray tracing problem imposes a constraint on the search space for neighbors. Due to this, we can only use RT cores to accelerate fixed-radius kNNS, which requires the user to set a search radius a priori and hence can miss neighbors. In this work, we propose TrueKNN, the first unbounded RT-accelerated neighbor search. TrueKNN adopts an iterative approach where we incrementally grow the search space until all points have found their k neighbors. We show that our approach is orders of magnitude faster than existing approaches and can even be used to accelerate fixed-radius neighbor searches.
-
RT-DBSCAN: Accelerating DBSCAN using Ray Tracing Hardware
Acceptance rate 26%
General Purpose computing on Graphical Processing Units (GPGPU) has resulted in unprecedented levels of speedup over its CPU counterparts, allowing programmers to harness the computational power of GPU shader cores to accelerate other computing applications. But this style of acceleration is best suited for regular computations (e.g., linear algebra). Recent GPUs feature new Ray Tracing (RT) cores that instead speed up the irregular process of ray tracing using Bounding Volume Hierarchies. While these cores seem limited in functionality, they can be used to accelerate n-body problems by leveraging RT cores to accelerate the required distance computations. In this work, we propose RT-DBSCAN, the first RT-accelerated DBSCAN implementation. We use RT cores to accelerate Density-Based Clustering of Applications with Noise (DBSCAN) by translating fixed-radius nearest neighbor queries to ray tracing queries. We show that leveraging the RT hardware results in speedups between 1.3x to 4x over current state-of-the-art, GPU-based DBSCAN implementations.
-
Synthesis of Distributed Agreement-Based Systems with Efficiently-Decidable Verification
Nominated for Best PaperAcceptance rate 38%
Distributed agreement-based (DAB) systems use common distributed agreement protocols such as leader election and consensus as building blocks for their target functionality. While automated verification for DAB systems is undecidable in general, recent work identifies a large class of DAB systems for which verification is efficiently-decidable. Unfortunately, the conditions characterizing such a class can be opaque and non-intuitive, and can pose a significant challenge to system designers trying to model their systems in this class.
In this paper, we present a synthesis-driven tool, Cinnabar, to help system designers building DAB systems ensure that their intended designs belong to an efficiently-decidable class. In particular, starting from an initial sketch provided by the designer, Cinnabar generates sketch completions using a counterexample-guided procedure. The core technique relies on compactly encoding root-causes of counterexamples to varied properties such as efficient-decidability and safety. We demonstrate Cinnabar ’s effectiveness by successfully and efficiently synthesizing completions for a variety of interesting DAB systems including a distributed key-value store and a distributed consortium system.
-
Coyote: A Compiler for Vectorizing Encrypted Arithmetic Circuits
Acceptance rate 21%
Fully Homomorphic Encryption (FHE) is a scheme that allows a computational circuit to operate on encrypted data and produce a result that, when decrypted, yields the result of the unencrypted computation. While FHE enables privacy-preserving computation, it is extremely slow. However, the mathematical formulation of FHE supports a SIMD-like execution style, so recent work has turned to vectorization to recover some of the missing performance. Unfortunately, these approaches do not work well for arbitrary computations: they do not account for the high cost of rotating vector operands to allow data to be used in multiple operations. Hence, the cost of rotation can outweigh the benefits of vectorization.
-
HyBF: A Hybrid Branch Fusion Strategy for Code Size Reduction
Acceptance rate 40%
Binary code size is a first-class design consideration in many computing domains and a critical factor in many more, but compiler optimizations targeting code size are few and often limited in functionality. When size reduction opportunities are left unexploited, it results in higher downstream costs such as memory, storage, bandwidth, or programmer time.
2022
-
Unirec: A Unimodular-like Framework for Nested Recursion and Loops
Acceptance rate 31%
Scheduling transformations reorder operations in a program to improve locality and/or parallelism. There are mature loop transformation frameworks such as the polyhedral model for composing and applying instance-wise scheduling transformations for loop nests.In recent years, there have been efforts to build frameworks for composing and applying scheduling transformations for nested recursion and loops, but these frameworks cannot employ the full power of transformations for loop nests since they have overly-restrictive representations. This paper describes a new framework, UniRec, that not only generalizes prior frameworks for reasoning about transformations on recursion, but also generalizes the unimodular framework, and hence unifies reasoning about perfectly-nested loops and recursion.
-
Cornucopia: A Framework for Feedback-Guided Generation of Binaries
Acceptance rate 22%
Binary analysis is an important capability required for many security and software engineering applications. Consequently, there are many binary analysis techniques and tools with varied capabilities. However, testing these tools requires a large, varied binary dataset with corresponding source-level information. In this paper, we present Cornucopia, an architecture agnostic automated framework that can generate a plethora of binaries from corresponding program source by exploiting compiler optimizations and feedback-guided learning. Our evaluation shows that Cornucopia was able to generate 309K binaries across four architectures (x86, x64, ARM, MIPS) with an average of 403 binaries for each program and outperforms BinTuner [53], a similar technique. Our experiments revealed issues with the LLVM optimization scheduler resulting in compiler crashes (∼ 300). Our evaluation of four popular binary analysis tools angr, Ghidra, ida, and radare, using Cornucopia generated binaries, revealed various issues with these tools. Specifically, we found 263 crashes in angr and one memory corruption issue in ida. Our differential testing on the analysis results revealed various semantic bugs in these tools. We also tested machine learning tools, Asm2Vec, SAFE, and Debin, that claim to capture binary semantics and show that they perform poorly (e.g., Debin F1 score dropped to 12.9% from reported 63.1%) on Cornucopia generated binaries. In summary, our exhaustive evaluation shows that Cornucopia is an effective mechanism to generate binaries for testing binary analysis techniques effectively.
-
SparseLNR: accelerating sparse tensor computations using loop nest restructuring
Best Paper AwardAcceptance rate 24%
Sparse tensor algebra computations have become important in many real-world applications like machine learning, scientific simulations, and data mining. Hence, automated code generation and performance optimizations for tensor algebra kernels are paramount. Recent advancements such as the Tensor Algebra Compiler (TACO) greatly generalize and automate the code generation for tensor algebra expressions. However, the code generated by TACO for many important tensor computations remains suboptimal due to the absence of a scheduling directive to support transformations such as distribution/fusion.
-
DARM: Control-Flow Melding for SIMT Thread Divergence Reduction
Acceptance rate 27%
GPGPUs use the Single-Instruction-Multiple-Thread (SIMT) execution model where a group of threads— wavefront or warp—execute instructions in lockstep. When threads in a group encounter a branching instruction, not all threads in the group take the same path, a phenomenon known as control-flow divergence. The control-flow divergence causes performance degradation because both paths of the branch must be executed one after the other. Prior research has primarily addressed this issue through architectural modifications. We observe that certain GPGPU kernels with control-flow divergence have similar control-flow structures with similar instructions on both sides of a branch. This structure can be exploited to reduce control-flow divergence by melding the two sides of the branch allowing threads to reconverge early, reducing divergence. In this work, we present DARM, a compiler analysis and transformation framework that can meld divergent control-flow structures with similar instruction sequences. We show that DARM can reduce the performance degradation from control-flow divergence.
2021
-
QuickSilver: Modeling and Parameterized Verification for Distributed Agreement-Based Systems
Acceptance rate 35%
The last decade has sparked several valiant efforts in deductive verification of distributed agreement protocols such as consensus and leader election. Oddly, there have been far fewer verification efforts that go beyond the core protocols and target applications that are built on top of agreement protocols. This is unfortunate, as agreement-based distributed services such as data stores, locks, and ledgers are ubiquitous and potentially permit modular, scalable verification approaches that mimic their modular design. We address this need for verification of distributed agreement-based systems through our novel modeling and verification framework, QuickSilver, that is not only modular, but also fully automated. The key enabling feature of QuickSilver is our encoding of abstractions of verified agreement protocols that facilitates modular, decidable, and scalable automated verification. We demonstrate the potential of QuickSilver by modeling and efficiently verifying a series of tricky case studies, adapted from real-world applications, such as a data store, a lock service, a surveillance system, a pathfinding algorithm for mobile robots, and more.
-
HACCLE: Metaprogramming for Secure Multi-Party Computation
Acceptance rate 50%
Cryptographic techniques have the potential to enable distrusting parties to collaborate in fundamentally new ways, but their practical implementation poses numerous challenges. An important class of such cryptographic techniques is known as Secure Multi-Party Computation (MPC). Developing Secure MPC applications in realistic scenarios requires extensive knowledge spanning multiple areas of cryptography and systems. And while the steps to arrive at a solution for a particular application are often straightforward, it remains difficult to make the implementation efficient, and tedious to apply those same steps to a slightly different application from scratch. Hence, it is an important problem to design platforms for implementing Secure MPC applications with minimum effort and using techniques accessible to non-experts in cryptography.
-
Efficient Tree-Traversals: Reconciling Parallelism and Dense Data Representations
Acceptance rate 33%
Recent work showed that compiling functional programs to use dense, serialized memory representations for recursive algebraic datatypes can yield significant constant-factor speedups for sequential programs. But serializing data in a maximally dense format consequently serializes the processing of that data, yielding a tension between density and parallelism. This paper shows that a disciplined, practical compromise is possible. We present Parallel Gibbon, a compiler that obtains the benefits of dense data formats and parallelism. We formalize the semantics of the parallel location calculus underpinning this novel implementation strategy, and show that it is type-safe. Parallel Gibbon exceeds the parallel performance of existing compilers for purely functional programs that use recursive algebraic datatypes, including, notably, abstract-syntax-tree traversals as in compilers.
-
Vectorized Secure Evaluation of Decision Forests
Acceptance rate 23%
As the demand for machine learning–based inference increases in tandem with concerns about privacy, there is a growing recognition of the need for secure machine learning, in which secret models can be used to classify private data without the model or data being leaked. Fully Homomorphic Encryption (FHE) allows arbitrary computation to be done over encrypted data, providing an attractive approach to providing such secure inference. While such computation is often orders of magnitude slower than its plaintext counterpart, the ability of FHE cryptosystems to do ciphertext packing—that is, encrypting an entire vector of plaintexts such that operations are evaluated elementwise on the vector—helps ameliorate this overhead, effectively creating a SIMD architecture where computation can be vectorized for more efficient evaluation. Most recent research in this area has targeted regular, easily vectorizable neural network models. Applying similar techniques to irregular ML models such as decision forests remains unexplored, due to their complex, hard-to-vectorize structures.
2020
-
Parameterized Verification of Systems with Global Synchronization and Guards
Acceptance rate 27%
Inspired by distributed applications that use consensus or other agreement protocols for global coordination, we define a new computational model for parameterized systems that is based on a general global synchronization primitive and allows for global transition guards. Our model generalizes many existing models in the literature, including broadcast protocols and guarded protocols. We show that reachability properties are decidable for systems without guards, and give sufficient conditions under which they remain decidable in the presence of guards. Furthermore, we investigate cutoffs for reachability properties and provide sufficient conditions for small cutoffs in a number of cases that are inspired by our target applications.
2019
-
D2P: From Recursive Formulations to Distributed Memory Codes
Acceptance rate 23%
Recursive formulations of programs are straightforward to reason about and write, often have good locality properties, and readily expose parallelism. We observe that it is easier to automatically generate distributed-memory codes for recursive formulations with certain properties: i) inclusive—a recursive method’s parameters summarize the data access done within the method body. ii) Intersection—data-set intersection tests among method invocations can be computed efficiently. In this paper we present D2P, a system that automatically generates distributed-memory codes for recursive divide-conquer algorithms with these properties. D2P produces MPI-based implementations starting from shared-memory specifications of the recursive algorithms. We evaluate D2P with recursive Dynamic Programming (DP) algorithms, since these algorithms have the desired properties and are well known. We show that the generated implementations are scalable and efficient: D2P-generated implementations execute faster than implementations generated by recent distributed DP frameworks, and are competitive with (and often faster than) hand-written implementations.
-
Composable, Sound Transformations of Nested Recursion and Loops
Acceptance rate 27%
Scheduling transformations reorder a program’s operations to improve locality and/or parallelism. The polyhedral model is a general framework for composing and applying instance-wise scheduling transformations for loop-based programs, but there is no analogous framework for recursive programs. This paper presents an approach for composing and applying scheduling transformations—like inlining, interchange, and code motion—to nested recursive programs. This paper describes the phases of the approach—representing dynamic instances, composing and applying transformations, reasoning about correctness—and shows that these techniques can verify the soundness of composed transformations.
-
Sound, Fine-Grained Traversal Fusion for Heterogeneous Trees
Acceptance rate 27%
Applications in many domains are based on a series of traversals of tree structures, and fusing these traversals together to reduce the total number of passes over the tree is a common, important optimization technique. In applications such as compilers and render trees, these trees are heterogeneous: different nodes of the tree have different types. Unfortunately, prior work for fusing traversals falls short in different ways: they do not handle heterogeneity; they require using domain-specific languages to express an application; they rely on the programmer to aver that fusing traversals is safe, without any soundness guarantee; or they can only perform coarse-grain fusion, leading to missed fusion opportunities. This paper addresses these shortcomings to build a framework for fusing traversals of heterogeneous trees that is automatic, sound, and fine-grained. We show across several case studies that our approach is able to allow programmers to write simple, intuitive traversals, and then automatically fuse them to substantially improve performance.
-
LoCal: A Language for Programs Operating on Serialized Data
Acceptance rate 27%
In a typical data-processing program, the representation of data in memory is distinct from its representation in a serialized form on disk. The former has pointers and arbitrary, sparse layout, facilitating easy manipulation by a program, while the latter is packed contiguously, facilitating easy I/O. We propose a language, LoCal, to unify in-memory and serialized formats. LoCal extends a region calculus into a location calculus, employing a type system that tracks the byte-addressed layout of all heap values. We formalize LoCal and prove type safety, and show how LoCal programs can be inferred from unannotated source terms.
We transform the existing Gibbon compiler to use LoCal as an intermediate language, with the goal of achieving a balance between code speed and data compactness by introducing just enough indirection into heap layouts, preserving the asymptotic complexity of traditional representations, but working with mostly or completely serialized data. We show that our approach yields significant performance improvement over prior approaches to operating on packed data, without abandoning idiomatic programming with recursive functions.
-
Efficient GPU Tree Walks for Effective Distributed N-Body Simulations
Acceptance rate 23%
N-body problems, such as simulating the motion of stars in a galaxy, are popularly solved using tree codes like Barnes-Hut. ChaNGa is a best-of-breed n-body platform that uses an asymptotically-efficient tree traversal strategy known as a dual-tree walk to quickly determine which bodies need to interact with each other to provide an accurate simulation result. However, this strategy does not work well on GPUs, due to the highly-irregular nature of the dual-tree algorithm. On GPUs, ChaNGa uses a hybrid strategy where the CPU performs the tree walk to determine which bodies interact while the GPU performs the force computation. In this paper, we show that a highly-optimized single-tree walk approach is able to achieve better GPU performance by significantly accelerating the tree walk and reducing CPU/GPU communication. Our experiments show that this new design can achieve a 8.25× speedup over baseline ChaNGa using a one node, one process per node configuration.
-
MULKSG: MULtiple K Simultaneous Graph Assembly
Acceptance rate 52%
This work shows how to parallelize multi K de Bruijn graph genome assembly simultaneously, removing the bottleneck of iterative multi K assembly. The expected execution time on a single node with 40 cores is variable, with the average execution time for the entire pipeline over 16 datasets tested being 1613 s for SPAdes vs. 1581 s for MULKSG, with the MULKSG graph creation and traversal averaging 15% faster than SPAdes. We implement a multi-node implementation for the graph creation and traversal portions of the assembly, showing the speedups in Fig. 4. We show that when implemented correctly with correction phases performed per graph in parallel, the expected outcome is very close to the original method, in some cases having less errors while keeping the same NGA50 and genome coverage %. We show this works in practice, implementing with the popular genome assembler SPAdes. Further, this algorithmic change gets rid of the single node sequential bottleneck on multi K genome assembly, allowing for the use of parallel error correction, graph building, graph correction, and graph traversal. We implement a parallel version of the assembly and show the statistics are the same as when run on a single node. The code is open source and can be found at https://github.com/cwright7101/mulksg.
-
XSTRESSOR: Automatic Generation of Large-Scale Test Inputs by Inferring Path Conditions
IEEE TCSE Distinguished Paper AwardAcceptance rate 28%
An important part of software testing is generation of worst-case test inputs, which exercise a program under extreme loads. For such a task, symbolic execution is a useful tool with its capability to reason about all possible execution paths of a program, including the one with the worst case behavior. However, symbolic execution suffers from the path explosion problem and frequent calls to a constraint solver, which make it impractical to be used at a large scale. To address the issue, this paper presents XSTRESSOR that is able to generate test inputs that can run specific loops in a program with the worst-case complexity in a large scale. XSTRESSOR synthetically generates the path condition for the large-scale, worst-case execution from a predictive model that is built from a set of small scale tests. XSTRESSOR avoids the scaling problem of prior techniques by limiting full-blown symbolic execution and run-time calls to constraint solver to small scale tests only. We evaluate XSTRESSOR against WISE and SPF-WCA, the most closely related tools to generate worst-case test inputs. Results show that XSTRESSOR can generate the test inputs faster than WISE and SPF-WCA, and also scale to much larger input sizes.
-
PySE: Automatic Worst-Case Test Generation by Reinforcement Learning
Acceptance rate 28%
Stress testing is an important task in software testing, which examines the behavior of a program under a heavy load. Symbolic execution is a useful tool to find out the worst-case input values for the stress testing. However, symbolic execution does not scale to a large program, since the number of paths to search grows exponentially with an input size. So far, such a scalability issue has been mostly managed by pruning out unpromising paths in the middle of searching based on heuristics, but this kind of work easily eliminates the true worst case as well, providing sub-optimal one only. Another way to achieve scalability is to learn a branching policy of worst-case complexity from small scale tests and apply it to a large scale. However, use cases of such a method are restricted to programs whose worst-case branching policy has a simple pattern. To address such limitations, we propose PySE that uses symbolic execution to collect the behaviors of a given branching policy, and updates the policy using a reinforcement learning approach through multiple executions. PySE’s branching policy keeps evolving in a way that the length of an execution path increases in the long term, and ultimately reaches the worst-case complexity. PySE can also learn the worst-case branching policy of a complex or irregular pattern, using an artificial neural network in a fully automatic way. Experiment results demonstrate that PySE can effectively find a path of worst-case complexity for various Python benchmark programs and scales.
2017
-
TreeFuser: A Framework for Analyzing and Fusing General Recursive Tree Traversals
Acceptance rate 30%
Series of traversals of tree structures arise in numerous contexts: abstract syntax tree traversals in compiler passes, rendering traversals of the DOM in web browsers, kd-tree traversals in computational simulation codes. In each of these settings, a tree is traversed multiple times to compute various values and modify various portions of the tree. While it is relatively easy to write these traversals as separate small updates to the tree, for efficiency reasons, traversals are often manually fused to reduce the number of times that each portion of the tree is traversed: by performing multiple operations on the tree simultaneously, each node of the tree can be visited fewer times, increasing opportunities for optimization and decreasing cache pressure and other overheads. This fusion process is often done manually, requiring careful understanding of how each of traversals of the tree interact. This paper presents an automatic approach to traversal fusion: tree traversals can be written independently, and then our framework analyzes the dependences between the traversals to determine how they can be fused to reduce the number of visits to each node in the tree. A critical aspect of our framework is that it exploits two opportunities to increase the amount of fusion: i) it automatically integrates code motion, and ii) it supports partial fusion, where portions of one traversal can be fused with another, allowing for a reduction in node visits without requiring that two traversals be fully fused. We implement our framework in Clang, and show across several case studies that we can successfully fuse complex tree traversals, reducing the overall number of traversals and substantially improving locality and performance.
-
Scalable Genomic Assembly through Parallel de Bruijn Graph Construction for Multiple K-mers
Acceptance rate 24%
Extraordinary progress in genome sequencing technologies has led to a tremendous increase in the number of sequenced genomes. However, biologists have run into a computational bottleneck to assemble large and complex genomes quickly, due to the lack of scalable and parallel de novo assembly algorithms. Among several approaches to assembly, the iterative de Bruijn graph (DBG) assemblers, such as IDBA-UD, generate high-quality assemblies by sequentially iterating from small to large k-values used in graph construction. However, this approach is time intensive because the creation of the graphs for increasing k-values proceeds sequentially. For example, with just eight k-values, graph construction takes 96% of the total time to assemble a metagenomic dataset with 33 million paired-end reads. In this paper, we propose ScalaDBG, which transforms the sequential process of DBG construction for a range of k values, to one where each graph is built independently and in parallel. We develop a novel mechanism whereby the graph for the higher k value can be “patched” with contigs generated from the graph with the lower k value. We show that for a variety of datasets our technique can assemble complex genomes much faster than IDBA-UD (6.7X faster for the most complex genome in our dataset) while maintaining the same accuracy for the assembled genome. Moreover, ScalaDBG’s multi-level parallelism allows it to simultaneously leverage the power of mighty server machines by using all their cores and of compute clusters by scaling out.
-
SPIRIT: A Framework for Creating Distributed Recursive Tree Applications
Acceptance rate 16%
An important set of applications, from diverse domains such as cosmological simulations, data mining, and computer graphics, involve repeated, depth-first traversal of trees. As these applications operate over massive data sets, it is often necessary to distribute the trees to process all of the data. In this paper, we introduce SPIRIT, a framework to ease the writing of distributed tree applications. SPIRIT automates the challenging tasks of tree distribution, optimizing communication and parallelizing independent computations. The common algorithmic pattern in tree traversals is exploited to effectively schedule parallel computations and improve locality. As a result, we identify systematic ways of exploiting pipeline parallelism in these applications and show how this parallelism can be complemented by selective application of data parallelism to provide greater speed-ups without requiring excessive data replication. SPIRIT is packaged into a set of application programming interfaces (APIs) that developers can use to create scalable applications. Evaluation of SPIRIT on various tree traversal algorithms shows a scalable system. We also find that SPIRIT implementations perform substantially less communication and achieve significant performance improvements over implementations in other distributed graph systems, and are competitive against state-of-the-art, hand-tuned, application-specific implementations.
-
Compiling Tree Transforms to Operate on Packed Representations
Acceptance rate 33%
When written idiomatically in most programming languages, programs that traverse and construct trees operate over pointer-based data structures, using one heap object per-leaf and per-node. This representation is efficient for random access and shape-changing modifications, but for traversals, such as compiler passes, that process most or all of a tree in bulk, it can be inefficient. In this work we instead compile tree traversals to operate on pointer-free pre-order serializations of trees. On modern architectures such programs often run significantly faster than their pointer-based counterparts, and additionally are directly suited to storage and transmission without requiring marshaling. We present a prototype compiler, Gibbon, that compiles a small first-order, purely functional language sufficient for tree traversals. The compiler transforms this language into intermediate representation with explicit pointers into input and output buffers for packed data. The key compiler technologies include an effect system for capturing traversal behavior, combined with an algorithm to insert destination cursors. We evaluate our compiler on tree transformations over a real-world dataset of source-code syntax trees. For traversals touching the whole tree, such as maps and folds, packed data allows speedups of over 2x compared to a highly-optimized pointer-based baseline.
-
Treelogy: A Benchmark Suite for Tree Traversals
Acceptance rate 30%
An interesting class of irregular algorithms is tree traversal algorithms, which repeatedly traverse various trees to perform efficient computations. Tree traversal algorithms form the algorithmic kernels in an important set of applications in scientific computing, computer graphics, bioinformatics, and data mining, etc. There has been increasing interest in understanding tree traversal algorithms, optimizing them, and applying them in a wide variety of settings. Crucially, while there are many possible optimizations for tree traversal algorithms, which optimizations apply to which algorithms is dependent on algorithmic characteristics.
In this work, we present a suite of tree traversal kernels, drawn from diverse domains, called Treelogy, to explore the connection between tree traversal algorithms and state-of-the-art optimizations. We characterize these algorithms by developing an ontology based on their structural properties. The attributes extracted through our ontology, for a given traversal kernel, can aid in quick analysis of the suitability of platform- and application- specific as well as independent optimizations. We provide reference implementations of these kernels for three platforms: shared memory multicores, distributed memory systems, and GPUs, and evaluate their scalability.
-
Locality Transformations for Nested Recursive Iteration Spaces
Acceptance rate 17%
There has been a significant amount of effort invested in designing scheduling transformations such as loop tiling and loop fusion that rearrange the execution of dynamic instances of loop nests to place operations that access the same data close together temporally. In recent years, there has been interest in designing similar transformations that operate on recursive programs, but until now these transformations have only considered simple scenarios: multiple recursions to be fused, or a recursion nested inside a simple loop. This paper develops the first set of scheduling transformations for nested recursions: recursive methods that call other recursive methods. These are the recursive analog to nested loops. We present a transformation called recursion twisting that automatically improves locality at all levels of the memory hierarchy, and show that this transformation can yield substantial performance improvements across several benchmarks that exhibit nested recursion.
-
Exploiting Vector and Multicore Parallelism for Recursive Data- and Task-Parallel Programs
Acceptance rate 22%
Modern hardware contains parallel execution resources that are well-suited for data-parallelism-vector units-and task parallelism-multicores. However, most work on parallel scheduling focuses on one type of hardware or the other. In this work, we present a scheduling framework that allows for a unified treatment of task- and data-parallelism. Our key insight is an abstraction, task blocks, that uniformly handles data-parallel iterations and task-parallel tasks, allowing them to be scheduled on vector units or executed independently as multicores. Our framework allows us to define schedulers that can dynamically select between executing task- blocks on vector units or multicores. We show that these schedulers are asymptotically optimal, and deliver the maximum amount of parallelism available in computation trees. To evaluate our schedulers, we develop program transformations that can convert mixed data- and task-parallel pro- grams into task block-based programs. Using a prototype instantiation of our scheduling framework, we show that, on an 8-core system, we can simultaneously exploit vector and multicore parallelism to achieve 14×-108× speedup over sequential baselines.
-
Processor-Oblivious Record and Replay
Acceptance rate Selected to appear in Special Issue of Transactions on Parallel Computing
Record-and-replay systems are useful tools for debugging non-deterministic parallel programs by first recording an execution and then replaying that execution to produce the same access pattern. Existing record-and-replay systems generally target thread-based execution models, and record the behaviors and interleavings of individual threads. Dynamic multithreaded languages and libraries, such as the Cilk family, OpenMP, TBB, etc., do not have a notion of threads. Instead, these languages provide a processor-oblivious model of programming, where programs expose task-parallelism using high-level constructs such as spawn/sync without regard to the number of threads/cores available to run the program. Thread-based record-and-replay would violate the processor-oblivious nature of these programs, as they incorporate the number of threads into the recorded information, constraining the replayed execution to the same number of threads.
In this paper, we present a processor-oblivious record-and-replay scheme for such languages where record and replay can use different number of processors and both are scheduled using work stealing. We provide theoretical guarantees for our record and replay scheme—namely that record is optimal for programs with one lock and replay is near-optimal for all cases. In addition, we implemented this scheme in the Cilk Plus runtime system and our evaluation indicates that processor-obliviousness does not cause substantial overheads.
-
Legato: End-to-End Bounded Region Serializability Using Commodity Hardware Transactional Memory
Acceptance rate 22%
Shared-memory languages and systems provide strong guarantees only for well-synchronized (data-race-free) programs. Prior work introduces support for memory consistency based on region serializability of executing code regions, but all approaches incur serious limitations such as adding high run-time overhead or relying on complex custom hardware.
This paper explores the potential for leveraging widely available, commodity hardware transactional memory to provide an end-to-end memory consistency model called dynamically bounded region serializability (DBRS). To amortize high per-transaction costs, yet mitigate the risk of unpredictable, costly aborts, we introduce dynamic runtime support called Legato that executes multiple dynamically bounded regions (DBRs) in a single transaction. Legato varies the number of DBRs per transaction on the fly, based on the recent history of committed and aborted transactions. Legato outperforms existing commodity enforcement of DBRS, and its costs are less sensitive to a program’s shared-memory communication patterns. These results demonstrate the potential for providing always-on strong memory consistency using commodity transactional hardware.
-
Data Structure–Aware Heap Partitioning
Acceptance rate 25%
There are many applications of program (or heap) partitioning, such as computation offloading, region-based memory management, and OS-driven memory locality optimizations. Although these applications are conceptually different, fundamentally, they must generate code such that objects in the heap (and hence the code that operates on those objects) get partitioned depending on how those objects are used. Regardless of the intended application goal, the granularity at which the heap is partitioned is the key factor in partition quality, and hence it needs to be carefully chosen.
Previous work suggested two main granularities: class-based and allocation site–based, where objects from the same class (or those allocated at the same allocation site) are co-located. Both approaches share a critical drawback: data structures that are used in different ways can share the same class, or the same allocation sites for internal objects, and hence are forced to be co-located despite their different usage patterns.
We introduce the notion of data structure–aware partitioning to allow different data structures to be placed in different partitions, even by existing tools and analyses that inherently operate in a class-based or allocation site–based manner. Our strategy consists of an analysis that infers ownership properties between objects to identify data structures, and a code generation phase that encodes this ownership information into objects’ data types and allocation sites without changing the semantics of the code.
We evaluate the quality of data structure–aware partitions by comparing it to the state-of-the-art allocation site–based partitioning on a subset of the DaCapo Benchmarks. Across a set of randomized trials, we had a median range of 5% to 25% reduction of cross-partition accesses, and, depending on partitioning decisions, up to a 95% reduction.
-
Efficient Collaborative Approximation in MapReduce without Missing Rare Keys
Recent proposals extend MapReduce, a widely-used Big Data processing framework, with sampling to improve performance by producing approximate results with statistical error bounds. However, because these systems perform global uniform sampling across the entire key space of input data, they may completely miss rare keys which may be unacceptable in some applications. Well-known stratified sampling avoids missing rare keys by obtaining the same number of samples for each key which also achieves good performance by sampling popular keys infrequently and rare keys more often. While online stratified sampling has been done in centralized settings, straightforward extension to MapReduce’s distributed setting cannot easily leverage the number of per-key samples seen globally by all the Mappers to reduce the sampling rate of each Mapper in the future. Because there are hundreds of Mappers in a typical MapReduce job, such feedback can drastically reduce oversampling and improve performance. We present MaDSOS (MapReduce with Distributed Stratified Online Sampling) which makes two contributions: (1) Instead of a fixed n per-key samples and the resultant sampling rates, we propose a telescoping algorithm that uses fixed sampling rates of the form 1/2^k and, between n and 2n samples. (2) We propose a collaborative feedback scheme, that is enabled by the specific form of sampling rates and the leniency in the sample counts, to efficiently cut the sampling rates, and thus oversampling, once the desired number of samples have been seen globally. For our MapReduce benchmarks, MaDSOS improves performance by 59% over Hadoop while guaranteeing never to miss rare keys and achieves 2.5% per-key error compared to 100% worst-case error under global sampling at a fixed rate for all the keys.
2016
-
SARVAVID: A Domain Specific Language for Developing Scalable Computational Genomics Applications
Acceptance rate 24%
Breakthroughs in gene sequencing technologies have led to an exponential increase in the amount of genomic data. Efficient tools to rapidly process such large quantities of data are critical in the study of gene functions, diseases, evolution, and population variation. These tools are designed in an ad-hoc manner, and require extensive programmer effort to develop and optimize them. Often, such tools are written with the currently available data sizes in mind, and soon start to under perform due to the exponential growth in data. Furthermore, to obtain high-performance, these tools require parallel implementations, adding to the development complexity.
This paper makes an observation that most such tools contain a recurring set of software modules, or kernels. The availability of efficient implementations of such kernels can improve programmer productivity, and provide effective scalability with growing data. To achieve this goal, the paper presents a domain-specific language, called Sarvavid, which provides these kernels as language constructs. Sarvavid comes with a compiler that performs domain-specific optimizations, which are beyond the scope of libraries and generic compilers. Furthermore, Sarvavid inherently supports exploitation of parallelism across multiple nodes.
To demonstrate the efficacy of Sarvavid, we implement five well-known genomics applications—BLAST, MUMmer, E-MEM, SPAdes, and SGA—using Sarvavid. Our versions of BLAST, MUMmer, and E-MEM show a speedup of 2.4X, 2.5X, and 2.1X respectively compared to hand-optimized implementations when run on a single node, while SPAdes and SGA show the same performance as hand-written code. Moreover, Sarvavid applications scale to 1024 cores using a Hadoop backend.
-
Hybrid CPU-GPU Scheduling and Execution of Tree Traversals
Acceptance rate 24%
GPUs offer the promise of massive, power-efficient parallelism. However, exploiting this parallelism requires code to be carefully structured to deal with the limitations of the SIMT execution model. In recent years, there has been much interest in mapping irregular applications to GPUs: applications with unpredictable, data-dependent behaviors. While most of the work in this space has focused on ad hoc implementations of specific algorithms, recent work has looked at generic techniques for mapping a large class of {\em tree traversal} algorithms to GPUs, through careful restructuring of the tree traversal algorithms to make them behave more regularly. Unfortunately, even this general approach for GPU execution of tree traversal algorithms is reliant on ad hoc, hand-written, algorithm-specific scheduling (i.e, assignment of threads to warps) to achieve high performance.
The key challenge of scheduling is that it is a highly irregular process, that requires the inspection of thread behavior and then careful sorting of those threads into warps. In this paper, we present a novel scheduling and execution technique for tree traversal algorithms that is both general and automatic. The key novelty is a hybrid, inspector-executor approach: the GPU partially executes tasks to inspect thread behavior and transmits information back to the CPU, which uses that information to perform the scheduling itself, before executing the remaining, carefully scheduled, portion of the traversals on the GPU. We applied this framework to six tree traversal algorithms, achieving significant speedups over optimized GPU code that does not perform application-specific scheduling. Further, we show that in many cases, our hybrid approach is able to deliver better performance even than GPU code that uses hand-tuned, application-specific scheduling.
2015
-
Toward Efficient Strong Memory Model Support for the Java Platform via Hybrid Synchronization
Acceptance rate 56%
The Java memory model provides strong behavior guarantees for data-race-free executions. However, it provides very weak guarantees for racy executions, leading to unexpected, unintuitive behaviors. This paper focuses on how to provide a memory model, called statically bounded region serializability (SBRS), that is substantially stronger than the Java memory model. Our prior work introduces SBRS, as well as compiler and runtime support for enforcing SBRS called EnfoRSer. EnfoRSer modifies the dynamic compiler to insert instrumentation to acquire a lock on each object accessed by the program. For most programs, EnfoRSer’s primary run-time cost is executing this instrumentation at essentially every memory access.
This paper focuses on reducing the run-time overhead of enforcing SBRS by avoiding instrumentation at every memory access that acquires a per-object lock. We experiment with an alternative approach for providing SBRS that instead acquires a single static lock before each executed region; all regions that potentially race with each other—according to a sound whole-program static analysis—must acquire the same lock. This approach slows most programs dramatically by needlessly serializing regions that do not actually conflict with each other. We thus introduce a hybrid approach that judiciously combines the two locking strategies, using a cost model and run-time profiling.
Our implementation and evaluation in a Java virtual machine use offline profiling and recompilation, thus demonstrating the potential of the approach without incurring online profiling costs. The results show that although the overall performance benefit is modest, our hybrid approach never significantly worsens performance, and for two programs, it significantly outperforms both approaches that each use only one kind of locking. These results demonstrate the potential of a technique based on combining synchronization mechanisms to provide a strong end-to-end memory model for Java and other JVM languages.
-
Efficient Deterministic Replay of Multithreaded Executions in a Managed Language Virtual Machine
Acceptance rate 56%
Shared-memory parallel programs are inherently nondeterministic, making it difficult to diagnose rare bugs and to achieve deterministic execution. Existing multithreaded record & replay approaches have serious limitations such as relying on custom hardware, handling only data-race-free executions, or slowing programs by an order of magnitude. Furthermore, language virtual machines (VMs) such as Java VMs (JVMs) introduce various sources of nondeterminism that thwart demonstrating deterministic replay.
This paper introduces an approach for multithreaded record & replay based on tracking and reproducing shared-memory dependences accurately and efficiently. Building on prior work that introduces an efficient dependence recorder, we develop a new analysis for replaying dependences. To demonstrate multithreaded record & replay, we modify a JVM to support a new methodology that enables demonstrating and evaluating replay in the inherently nondeterministic JVM. Overall, the performance of both recorded and replayed executions compares favorably with performance reported by prior work for competing record & replay approaches.
-
Efficient Execution of Recursive Programs on Commodity Vector Hardware
Acceptance rate 19%
The pursuit of computational efficiency has led to the proliferation of throughput-oriented hardware, from GPUs to increasingly wide vector units on commodity processors and accelerators. This hardware is designed to efficiently execute data-parallel computations in a vectorized manner. However, many algorithms are more naturally expressed as divide-and-conquer, recursive, task-parallel computations. In the absence of data parallelism, it seems that such algorithms are not well suited to throughput-oriented architectures. This paper presents a set of novel code transformations that expose the data parallelism latent in recursive, task-parallel programs. These transformations facilitate straightforward vectorization of task-parallel programs on commodity hardware. We also present scheduling policies that maintain high utilization of vector resources while limiting space usage. Across several task-parallel benchmarks, we demonstrate both efficient vector resource utilization and substantial speedup on chips using Intel’s SSE4.2 vector units, as well as accelerators using Intel’s AVX512 units.
-
Tree Dependence Analysis
Acceptance rate 19%
We develop a new framework for analyzing recursive methods that perform traversals over trees, called tree dependence analysis. This analysis translates dependence analysis techniques for regular programs to the irregular space, identifying the structure of dependences within a recursive method that traverses trees. We develop a dependence test that exploits the dependence structure of such programs, and can prove that several locality- and parallelism- enhancing transformations are legal. In addition, we extend our analysis with a novel path-dependent, conditional analysis to refine the dependence test and prove the legality of transformations for a wider range of algorithms. We then use these analyses to show that several common algorithms that manipulate trees recursively are amenable to several locality- and parallelism-enhancing transformations. This work shows that classical dependence analysis techniques, which have largely been confined to nested loops over array data structures, can be extended and translated to work for complex, recursive programs that operate over pointer-based data structures.
-
SemCache++: Semantics-Aware Caching for Efficient Multi-GPU Offloading
Acceptance rate 25%
Offloading computations to multiple GPUs is not an easy task. It requires decomposing data, distributing computations and handling communication manually. GPU drop-in libraries (which require no program rewrite) have made it easy to offload computations to multiple GPUs by hiding this complexity inside library calls. Such encapsulation prevents the reuse of data between successive kernel invocations resulting in redundant communication. This limitation exists in multi-GPU libraries like CUBLASXT.
In this paper, we introduce SemCache++, a semantics-aware GPU cache that automatically manages communication between the CPU and multiple GPUs in addition to optimizing communication by eliminating redundant transfers using caching. SemCache++ is used to build the first multi-GPU drop-in replacement library that (a) uses the virtual memory to automatically manage and optimize multi-GPU communication and (b) requires no program rewriting or annotations. Our caching technique is efficient; it uses a two level caching directory to track matrices and sub-matrices. Experimental results show that our system can eliminate redundant communication and deliver performance improvements over multi-GPU libraries like StarPU and CUBLASXT.
-
Hybrid Static–Dynamic Analysis for Statically Bounded Region Serializability
Acceptance rate 17%
Data races are common. They are difficult to detect, avoid, or eliminate, and programmers sometimes introduce them intentionally. However, shared-memory programs with data races have unexpected, erroneous behaviors. Intentional and unintentional data races lead to atomicity and sequential consistency (SC) violations, and they make it more difficult to understand, test, and verify software. Existing approaches for providing stronger guarantees for racy executions add high run-time overhead and/or rely on custom hardware. This paper shows how to provide stronger semantics for racy programs while providing relatively good performance on commodity systems. A novel hybrid static–dynamic analysis called EnfoRSer provides end-to-end support for a memory model called statically bounded region serializability (SBRS) that is not only stronger than weak memory models but is strictly stronger than SC. EnfoRSer uses static compiler analysis to transform regions, and dynamic analysis to detect and resolve conflicts at run time. By demonstrating commodity support for a reasonably strong memory model with reasonable overheads, we show its potential as an always-on execution model.
2014
-
Orion: Scaling Genomic Sequence Matching with Fine-Grained Parallelization
Acceptance rate 21%
Gene sequencing instruments are producing huge volumes of data, straining the capabilities of current database searching algorithms and hindering efforts of researchers analyzing larger collections of data to obtain greater insights. In the space of parallel genomic sequence search, most of the popular softwares, like mpiBLAST, use the database segmentation approach, wherein the entire database is sharded and searched on different nodes. However this approach does not scale well with the increasing length of individual query sequences as well as the rapid growth in size of sequence databases. In this paper, we propose a fine-grained parallelism technique, called Orion, that divides the input query into an adaptive number of fragments and shards the database. Our technique achieves higher parallelism (and hence speedup) and load balancing, while maintaining 100% accuracy. We show that it is 12.3X faster than mpiBLAST for solving a relevant comparative genomics problem.
2013
-
General transformations for GPU execution of tree traversals
Acceptance rate 20%
With the advent of programmer-friendly GPU computing environments, there has been much interest in offloading workloads that can exploit the high degree of parallelism available on modern GPUs. Exploiting this parallelism and optimizing for the GPU memory hierarchy is well-understood for regular applications that operate on dense data structures such as arrays and matrices. However, there has been significantly less work in the area of irregular algorithms and even less so when pointer-based dynamic data structures are involved. Recently, irregular algorithms such as Barnes-Hut and kd-tree traversals have been implemented on GPUs, yielding significant performance gains over CPU implementations. However, the implementations often rely on exploiting application-specific semantics to get acceptable performance. We argue that there are general-purpose techniques for implementing irregular algorithms on GPUs that exploit similarities in algorithmic structure rather than application-specific knowledge. We demonstrate these techniques on several tree traversal algorithms, achieving speedups of up to 38x over 32-thread CPU versions.
-
EventWave: Programming Model and Runtime Support for Tightly-Coupled Elastic Cloud Applications
Acceptance rate 20%
An attractive approach to leveraging the ability of cloud-computing platforms to provide resources on demand is to build elastic applications, which can dynamically scale up or down based on resource requirements. To ease the development of elastic applications, it is useful for programmers to write applications with simple sequential semantics, without considering elasticity, and rely on runtime support to provide that elasticity. While this approach has been useful in restricted domains, such as MapReduce, existing programming models for general distributed applications do not expose enough information about their inherent organization of state and computation to provide such transparent elasticity.
We introduce EventWave, an event-driven programming model that allows developers to design elastic programs with inelastic semantics while naturally exposing isolated state and computation with programmatic parallelism. In addition, we describe the runtime mechanism which takes the exposed parallelism to provide elasticity. Finally, we evaluate our implementation through microbenchmarks and case studies to demonstrate that EventWave can provide efficient, scalable, transparent elasticity for applications run in the cloud.
-
Octet: Capturing and Controlling Cross-Thread Dependences Efficiently
Acceptance rate 25%
Parallel programming is essential for reaping the benefits of parallel hardware, but it is notoriously difficult to develop and debug reliable, scalable software systems. One key challenge is that modern languages and systems provide poor support for ensuring concurrency correctness properties—atomicity, sequential consistency, and multithreaded determinism—because all existing approaches are impractical. Dynamic, software-based approaches slow programs by up to an order of magnitude because capturing and controlling cross-thread dependences (i.e., conflicting accesses to shared memory) requires synchronization at virtually every access to potentially shared memory.
This paper introduces a new software-based concurrency control mechanism called Octet that soundly captures cross-thread dependences and can be used to build dynamic analyses for concurrency correctness. Octet achieves low overheads by tracking the locality state of each potentially shared object. Non-conflicting accesses conform to the locality state and require no synchronization; only conflicting accesses require a state change and heavyweight synchronization. This optimistic tradeoff leads to significant efficiency gains in capturing cross-thread dependences: a prototype implementation of Octet in a high-performance Java virtual machine slows real-world concurrent programs by only 26% on average. A dependence recorder, suitable for record & replay, built on top of Octet adds an additional 5% overhead on average. These results suggest that Octet can provide a foundation for developing low-overhead analyses that check and enforce concurrency correctness.
-
Automatic Vectorization of Tree Traversals
Acceptance rate 17%
Repeated tree traversals are ubiquitous in many domains such as scientific simulation, data mining and graphics. Modern commodity processors support SIMD instructions, and using these instructions to process multiple traversals at once has the potential to provide substantial performance improvements. Unfortunately these algorithms often feature highly diverging traversals which inhibit efficient SIMD utilization, to the point that other, less profitable sources of vectorization must be exploited instead.
Previous work has proposed traversal splicing, a locality transformation for tree traversals, which dynamically reorders traversals based on previous behavior, based on the insight that traversals which have behaved similarly so far are likely to behave similarly in the future. In this work, we cast this dynamic reordering as a scheduling for efficient SIMD execution, and show that it can dramatically improve the SIMD utilization of diverging traversals, close to ideal utilization. For five irregular tree traversal algorithms, our techniques are able to deliver speedups of 2.78 on average over baseline implementations. Furthermore our techniques can effectively SIMDize algorithms that prior, manual vectorization attempts could not.
-
Exploiting Domain Knowledge to Optimize Parallel Computational Mechanics Codes
Acceptance rate 21%
An important emerging problem domain in computational science and engineering is the development of multi-scale computational methods for complex problems in mechanics that span multiple spatial and temporal scales. An attractive approach to solving these problems is recursive decomposition: the problem is broken up into a tree of loosely coupled sub-problems which can be solved independently and then coupled back together to obtain the desired solution. However, a particular problem can be solved in myriad ways by coupling the sub-problems together in different tree orders. As we argue in this paper, the space of possible orders is vast, the performance gap between an arbitrary order and the best order is potentially quite large, and the likelihood that a domain scientist can find the best order to solve a problem on a particular machine is vanishingly small.
In this paper, we present a system that uses domain-specific knowledge captured in computational libraries to optimize code written in a conventional language (C). The system generates efficient coupling orders to solve computational mechanics problems using recursive decomposition. Our system adopts the inspector-executor paradigm, where the problem is inspected and a novel heuristic finds an effective implementation based on domain properties evaluated by a cost model. The derived implementation is then executed by a parallel run-time system (Cilk) which achieves optimal parallel performance. We demonstrate that our cost model is highly correlated with actual application runtime, that our proposed technique outperforms non-decomposed and non-multiscale methods. The code generated by the heuristic also outperforms alternate scheduling strategies, as well as over 99% of randomly-generated recursive decompositions sampled from the space of possible solutions.
-
SemCache: Semantics-aware Caching for Efficient GPU Offloading
Acceptance rate 21%
Recently, GPU libraries have made it easy to improve application performance by offloading computation to the GPU. However, using such libraries introduces the complexity of manually handling explicit data movements between GPU and CPU memory spaces. Unfortunately, when using these libraries with complex applications, it is very difficult to optimize CPU-GPU communication between multiple kernel invocations to avoid redundant communication.
In this paper, we introduce SemCache, a semantics-aware GPU cache that automatically manages CPU-GPU communication and dynamically optimizes communication by eliminating redundant transfers using caching. It’s key feature is the use of library semantics to determine the appropriate caching granularity for a given offloaded library (e.g., matrices in BLAS). We applied SemCache to BLAS libraries to provide a GPU drop-in replacement library which handles communications and optimizations automatically. Our caching technique is efficient; it only tracks matrices instead of tracking every memory access at fine granularity. Experimental results show that our system can dramatically reduce redundant communication for real-world computational science application and deliver significant performance improvements, beating GPU-based implementations like CULA and CUBLAS.
-
WuKong: Automatically Detecting and Localizing Bugs that Manifest at Large System Scales
Acceptance rate 15%
A key challenge in developing large scale applications is finding bugs that are latent at the small scales of testing, but manifest themselves when the application is deployed at a large scale. Here, we ascribe a dual meaning to “large scale”—it could mean a large number of executing processes or applications ingesting large amounts of input data (or both). Traditional statistical techniques fail to detect or diagnose such kinds of bugs because no error-free run is available at the large deployment scales for training purposes. Prior work used scaling models to detect anomalous behavior at large scales without training on correct behavior at that scale. However, that work cannot localize bugs automatically, i.e., cannot pinpoint the region of code responsible for the error. In this paper, we resolve that shortcoming by making the following three contributions: (i) we develop an automatic diagnosis technique, based on * feature reconstruction*; (ii) we design a heuristic to effectively prune the large feature space; and (iii) we demonstrate that our system scales well, in terms of both accuracy and overhead. We validate our design through a large-scale fault-injection study and two case-studies of real-world bugs, finding that our system can effectively localize bugs in 92.5% of the cases, dramatically easing the challenge of finding bugs in large-scale programs.
2012
-
Automatically Enhancing Locality for Tree Traversals with Traversal Splicing
Acceptance rate 25%
Generally applicable techniques for improving temporal locality in irregular programs, which operate over pointer-based data structures such as trees and graphs, are scarce. Focusing on a subset of irregular programs, namely, tree traversal algorithms like Barnes-Hut and nearest neighbor, previous work has proposed point blocking, a technique analogous to loop tiling in regular programs, to improve locality. However point blocking is highly dependent on point sorting, a technique to reorder points so that consecutive points will have similar traversals. Performing this a priori sort requires an understanding of the semantics of the algorithm and hence highly application specific techniques.
In this work, we propose traversal splicing, a new, general, automatic locality optimization for irregular tree traversal codes, that is less sensitive to point order, and hence can deliver substantially better performance, even in the absence of semantic information. For six benchmark algorithms, we show that traversal splicing can deliver single-thread speedups of up to 9.147 (geometric mean: 3.095) over baseline implementations, and up to 4.752 (geometric mean: 2.079) over point-blocked implementations. Further, we show that in many cases, automatically applying traversal splicing to a baseline implementation yields performance that is better than carefully hand-optimized implementations.
2011
-
Enhancing Locality for Recursive Traversals of Recursive Structures
Acceptance rate 37%
While there has been decades of work on developing automatic, locality-enhancing transformations for regular programs that operate over dense matrices and arrays, there has been little investigation of such transformations for irregular programs, which operate over pointer-based data structures such as graphs, trees and lists. In this paper, we argue that, for a class of irregular applications we call traversal codes, there exists substantial data reuse and hence opportunity for locality exploitation.
We develop a novel optimization called point blocking, inspired by the classic tiling loop transformation, and show that it can substantially enhance temporal locality in traversal codes. We then present a transformation and optimization framework called TreeTiler that automatically detects opportunities for applying point blocking and applies the transformation. TreeTiler uses autotuning techniques to determine appropriate parameters for the transformation. For a series of traversal algorithms drawn from real-world applications, we show that TreeTiler is able to deliver performance improvements of up to 245% over an optimized (but non-transformed) parallel baseline, and in several cases, significantly better scalability.
-
The Tao of Parallelism in Algorithms
Acceptance rate 23%
For more than thirty years, the parallel programming community has used the dependence graph as the main abstraction for reasoning about and exploiting parallelism in
regular'' algorithms that use dense arrays, such as finite-differences and FFTs. In this paper, we argue that the dependence graph is not a suitable abstraction for algorithms in new application areas like machine learning and network analysis in which the key data structures areirregular’’ data structures like graphs, trees, and sets.To address the need for better abstractions, we introduce a data-centric formulation of algorithms called the operator formulation in which an algorithm is expressed in terms of its action on data structures. This formulation is the basis for a structural analysis of algorithms that we call tao-analysis. Tao-analysis can be viewed as an abstraction of algorithms that distills out algorithmic properties important for parallelization. It reveals that a generalized form of data-parallelism called amorphous data-parallelism is ubiquitous in algorithms, and that, depending on the tao-structure of the algorithm, this parallelism may be exploited by compile-time, inspector-executor or optimistic parallelization, thereby unifying these seemingly unrelated parallelization techniques. Regular algorithms emerge as a special case of irregular algorithms, and many application-specific optimization techniques can be generalized to a broader context.
These results suggest that the operator formulation and tao-analysis of algorithms can be the foundation of a systematic approach to parallel programming.
-
Exploiting the Commutativity Lattice
Acceptance rate 23%
Speculative execution is a promising approach for exploiting parallelism in many programs, but it requires efficient schemes for detecting conflicts between concurrently executing threads. Prior work has argued that checking semantic commutativity of method invocations is the right way to detect conflicts for complex data structures such as kd-trees. Several ad hoc ways of checking commutativity have been proposed in the literature, but there is no systematic approach for producing implementations.
In this paper, we describe a novel framework for reasoning about commutativity conditions: the commutativity lattice. We show how commutativity specifications from this lattice can be systematically implemented in one of three different schemes: abstract locking, forward gatekeeping and general gatekeeping. We also discuss a disciplined approach to exploiting the lattice to find different implementations that trade off precision in conflict detection for performance. Finally, we show that our novel conflict detection schemes are practical and can deliver speedup on three real-world applications.
-
Vrisha: Using Scaling Properties of Parallel Programs for Bug Detection and Localization
Acceptance rate 13%
Detecting and isolating bugs that arise in parallel programs is a tedious and a challenging task. An especially subtle class of bugs are those that are scale-dependent: while small-scale test cases may not exhibit the bug, the bug arises in large-scale production runs, and can change the result or performance of an application. A popular approach to finding bugs is statistical bug detection, where abnormal behavior is detected through comparison with bug-free behavior. Unfortunately, for scale-dependent bugs, there may not be bug-free runs at large scales and therefore traditional statistical techniques are not viable. In this paper, we propose Vrisha, a statistical approach to detecting and localizing scale-dependent bugs. Vrisha detects bugs in large-scale programs by building models of behavior based on bug-free behavior at small scales. These models are constructed using kernel canonical correlation analysis (KCCA) and exploit scale-determined properties, whose values are predictably dependent on application scale. We use Vrisha to detect and diagnose two bugs caused by errors in popular MPI libraries and show that our techniques can be implemented with low overhead and low false-positive rates.
-
InContext: Simple Parallelism for Distributed Applications
Acceptance rate 13%
As networking services, such as DHTs, provide increasingly complex functionality, providing acceptable performance will require parallelizing their operations on individual nodes. Unfortunately, the event-driven style in which these applications have traditionally been written makes it difficult to reason about parallelism, and providing safe, efficient parallel implementations of distributed systems remains a challenge. In this paper, we introduce a declarative programming model based on contexts, which allows programmers to specify the sharing behavior of event handlers. Programs that adhere to the programming model can be safely parallelized according to an abstract execution model, with parallel behavior that is well-defined with respect to the expected sequential behavior. The declarative nature of the programming model allows conformance to be captured as a safety property that can be verified using a model checker.
We develop a prototype implementation of our abstract execution model and show that distributed applications written in our programming model can be automatically and efficiently parallelized. To recover additional parallelism, we present an optimization to the implementation based on state snapshots that permits more events to proceed in parallel. We evaluate our prototype implementation through several case studies and demonstrate significant speedup over optimized sequential implementations.
-
Techniques for fine-grained, multi-site computation offloading
Acceptance rate 29%
Increasingly, mobile devices are becoming the preferred platform for computation for many users. Unfortunately, the resource limitations, in battery life, computation power and storage, restricts the richness of applications that can be run on such devices. To alleviate these concerns, a popular approach that has gained currency in recent years is computation offloading, where a portion of an application is run off-site, leveraging the far greater resources of the cloud.
Prior work in this area has focused on a constrained form of the problem: a single mobile device offloading computation to a single server. However, with the increased popularity of cloud computing and storage, it is more common for the data that an application accesses to be distributed among several servers. This paper describes algorithmic approaches for performing fine-grained, multi-site offloading. This allows portions of an application to be offloaded in a data-centric manner, even if that data exists at multiple sites. Our approach is based on a novel partitioning algorithm, and a novel data representation. We demonstrate that our partitioning algorithm outperforms existing multi-site offloading algorithms, and that our data representation provides for more efficient, fine-grained offloading than prior approaches.
-
μSETL: A Set Based Programming Abstraction for Wireless Sensor Networks
Acceptance rate 21%
Programming wireless sensor networks is a major challenge, even for experienced programmers. To alleviate this problem, prior work has proposed a paradigm shift from node-level microprogramming to macroprogramming, where the user specifies a distributed application using a single macroprogram that is automatically translated into a set of node-level microprograms. This paper makes the case that node-level microprogramming itself can be made much easier by using the right set of programming abstractions. To support this claim, this paper presents μSETL, a programming abstraction for sensor networks based on {\it set theory}. Sets offer a powerful formalism and high expressiveness, yet are a natural way of thinking about resource abstraction in sensor networks. In addition to the set abstraction, μSETL features programming constructs that enable event-driven programming at a high level of abstraction, thereby significantly simplifying node-level microprogramming. μSETL consists of a set-based programming language, a compiler that translates μSETL programs into node-specific application code, and a runtime environment that provides various services to support the set-based programming abstraction. μSETL has been implemented using the Contiki operating system and runs on the Telos motes. Experimental results demonstrate that μSETL enables programmers to write various sensor network applications in a natural and highly compact manner with minimal overheads.
2010
-
Accelerating Multicore Reuse Distance Analysis with Sampling and Parallelization
Acceptance rate 17%
Reuse distance analysis is a well-established tool for predicting cache performance, driving compiler optimizations, and assisting visualization and manual optimization of programs. Existing reuse distance analysis methods either do not account for the effects of multithreading, or suffer severe performance penalties. This paper presents a sampled, parallelized method of measuring reuse distance profiles for multithreaded programs, modeling private and shared cache configurations. The sampling technique allows it to spend much of its execution in a fast low-overhead mode, and allows the use of a new measurement method since sampled analysis does not need to consider the full state of the reuse stack. This measurement method uses $O(1)$ data structures that may be made thread-private, allowing parallelization to reduce overhead in analysis mode. The performance of the resulting system is analyzed for a diverse set of parallel benchmarks and shown to generate accurate output compared to non-sampled full analysis as well as good results for the common application of locating low-locality code in the benchmarks, all with a performance overhead comparable to the best single-threaded analysis techniques.
-
Structure-driven Optimizations for Amorphous Data-Parallel Programs
Nominated for Best PaperAcceptance rate 17%
Irregular algorithms are organized around pointer-based data structures such as graphs and trees, and they are ubiquitous in applications. Recent work by the Galois project has provided a systematic approach for parallelizing irregular applications based on the idea of optimistic or speculative execution of programs. However, the overhead of optimistic parallel execution can be substantial. In this paper, we show that many irregular algorithms have structure that can be exploited and present three key optimizations that take advantage of algorithmic structure to reduce speculative overheads. We describe the implementation of these optimizations in the Galois system and present experimental results to demonstrate their benefits. To the best of our knowledge, this is the first system to exploit algorithmic structure to optimize the execution of irregular programs.
2009
-
Lonestar: A Suite of Parallel Irregular Programs
Acceptance rate 29%
Until recently, parallel programming has mainly focused on the exploitation of data-parallelism in dense matrix programs. However, many important application domains, including meshing, clustering, simulation, and machine learning, have very different algorithmic foundations: they require building, computing with, and modifying large sparse graphs. In the parallel programming literature, these types of applications are usually classified as irregular applications, and relatively little attention has been paid to them. To better study and understand the patterns of parallelism and locality in sparse graph computations, we implemented five programs that target domains such as data mining, survey propagation, and design automation. applications often expose large amounts of parallelism in the form of amorphous data-parallelism. Our speedup numbers demonstrate that this new type of parallelism can successfully be exploited on modern multi-core machines.
-
How Much Parallelism is There in Irregular Applications?
Acceptance rate 24%
Irregular programs are programs organized around pointer-based data structures such as trees and graphs. Recent investigations by the Galois project have shown that many irregular programs have a generalized form of data-parallelism called amorphous data-parallelism. However, in many programs, amorphous data-parallelism cannot be uncovered using static techniques, and its exploitation requires runtime strategies such as optimistic parallel execution. This raises a natural question: how much amorphous data-parallelism actually exists in irregular programs?
In this paper, we describe the design and implementation of a tool called ParaMeter that produces parallelism profiles for irregular programs. Parallelism profiles are an abstract measure of the amount of amorphous data-parallelism at different points in the execution of an algorithm, independent of implementation-dependent details such as the number of cores, cache sizes, load-balancing, etc. ParaMeter can also generate constrained parallelism profiles for a fixed number of cores. We show parallelism profiles for seven irregular applications, and explain how these profiles provide insight into the behavior of these applications.
2008
-
Fast Agglomerative Clustering for Rendering
Acceptance rate 52%
Hierarchical representations of large data sets, such as binary cluster trees, are a crucial component in many scalable algorithms used in various fields. Two major approaches for building these trees are agglomerative, or bottom-up, clustering and divisive, or top-down, clustering. The agglomerative approach offers some real advantages such as more flexible clustering and often produces higher quality trees, but has been little used in graphics because it is frequently assumed to be prohibitively expensive (O(N^2) or worse).
In this paper we show that agglomerative clustering can be done efficiently even for very large data sets. We introduce a novel locally-ordered algorithm that is faster than traditional heap-based agglomerative clustering and show that the complexity of the tree build time is much closer to linear than quadratic. We also evaluate the quality of the agglomerative clustering trees compared to the best known divisive clustering strategies in two sample applications: bounding volume hierarchies for ray tracing and light trees in the Lightcuts rendering algorithm. Tree quality is highly application, data set, and dissimilarity function specific. In our experiments the agglomerative-built tree quality is consistently higher by margins ranging from slight to significant, with up to 35% reduction in tree query times.
-
Scheduling Strategies for Optimistic Parallel Execution of Irregular Programs
Acceptance rate 28%
Recent application studies have shown that many irregular applications have a generalized data parallelism that manifests itself as iterative computations over worklists of different kinds. In general, there are complex dependencies between iterations. These dependencies cannot be elucidated statically because they depend on the inputs to the program; thus, optimistic parallel execution is the only tractable approach to parallelizing these applications.
We have built a system called Galois that supports this style of parallel execution. Its main features are (i) set iterators for expressing worklist-based data parallelism, and (ii) a runtime system that performs optimistic parallelization of these iterators, detecting conflicts and rolling back computations as needed.
Our work builds on the Galois system, and it addresses the problem of scheduling iterations of set iterators on multiple cores. The policy used by the base Galois system is to assign an iteration to a core whenever it needs work to do, but we show in this paper that this policy is not optimal for many applications. We also argue that OpenMP-style DO-ALL loop scheduling directives such as chunked and guided self-scheduling are too simplistic for irregular programs. These difficulties led us to develop a general scheduling framework for irregular problems; OpenMP-style scheduling strategies are special cases of this general approach. We also provide hooks into our framework, allowing the programmer to leverage application knowledge to further tune a schedule for a particular application.
To evaluate this framework, we implemented it as an extension of the Galois system. We then tested the system using five real-world, irregular, data-parallel applications. Our results show that (i) the optimal scheduling policy can be different for different applications and often leverages application-specific knowledge and (ii) implementing these schedules in the Galois system is relatively straightforward.
-
Optimistic Parallelism Benefits From Data Partitioning
Acceptance rate 24%
Recent studies of irregular applications such as finite-element mesh generators and data-clustering codes have shown that these applications have a generalized data parallelism arising from the use of iterative algorithms that perform computations on elements of worklists. In some irregular applications, the computations on different elements are independent. In other applications, there may be complex patterns of dependences between these computations.
The Galois system was designed to exploit this kind of irregular data parallelism on multicore processors. Its main features are (i) two kinds of set iterators for expressing worklist-based data parallelism, and (ii) a runtime system that performs optimistic parallelization of these iterators, detecting conflicts and rolling back computations as needed. Detection of conflicts and rolling back iterations requires information from class implementors.
In this paper, we introduce mechanisms to improve the execution efficiency of Galois programs: data partitioning, data-centric work assignment, lock coarsening, and over-decomposition. These mechanisms can be used to exploit locality of reference, reduce mis-speculation, and lower synchronization overhead. We also argue that the design of the Galois system permits these mechanisms to be used with relatively little modification to the user code. Finally, we present experimental results that demonstrate the utility of these mechanisms.
2007
-
Optimistic Parallelization Requires Abstractions
Acceptance rate 25%
Irregular applications, which manipulate large, pointer-based data structures like graphs, are difficult to parallelize manually. Automatic tools and techniques such as restructuring compilers and run-time speculative execution have failed to uncover much parallelism in these applications, in spite of a lot of effort by the research community. These difficulties have even led some researchers to wonder if there is any coarse-grain parallelism worth exploiting in irregular applications.
In this paper, we describe two real-world irregular applications: a Delaunay mesh refinement application and a graphics application that performs agglomerative clustering. By studying the algorithms and data structures used in these applications, we show that there is substantial coarse-grain, data parallelism in these applications, but that this parallelism is very dependent on the input data and therefore cannot be uncovered by compiler analysis. In principle, optimistic techniques such as thread-level speculation can be used to uncover this parallelism, but we argue that current implementations cannot accomplish this because they do not use the proper abstractions for the data structures in these programs.
These insights have informed our design of the Galois system, an object-based optimistic parallelization system for irregular applications. There are three main aspects to Galois: (1) a small number of syntactic constructs for packaging optimistic parallelism as iteration over ordered and unordered sets, (2) assertions about methods in class libraries, and (3) a runtime scheme for detecting and recovering from potentially unsafe accesses to shared memory made by an optimistic computation.
We show that Delaunay mesh generation and agglomerative clustering can be parallelized in a straight-forward way using the Galois approach, and we present experimental measurements to show that this approach is practical. These results suggest that Galois is a practical approach to exploiting data parallelism in irregular programs.
Journals
2024
-
Orchard: Heterogeneous Parallelism and Fine-grained Fusion for Complex Tree Traversals
Many applications are designed to perform traversals on tree-like data structures. Fusing and parallelizing these traversals enhance the performance of applications. Fusing multiple traversals improves the locality of the application. The runtime of an application can be significantly reduced by extracting parallelism and utilizing multi-threading. Prior frameworks have tried to fuse and parallelize tree traversals using coarse-grained approaches, leading to missed fine-grained opportunities for improving performance. Other frameworks have successfully supported fine-grained fusion on heterogeneous tree types but fall short regarding parallelization. We introduce a new framework Orchard built on top of Grafter . Orchard ’s novelty lies in allowing the programmer to transform tree traversal applications by automatically applying fine-grained fusion and extracting heterogeneous parallelism. Orchard allows the programmer to write general tree traversal applications in a simple and elegant embedded Domain-Specific Language (eDSL). We show that the combination of fine-grained fusion and heterogeneous parallelism performs better than each alone when the conditions are met.
-
METS-R SIM: A Simulator for Multi-modal Energy-optimal Trip Scheduling in Real-time with Shared Autonomous Electric Vehicles
2022
-
Challenges in Firmware Re-Hosting, Emulation, and Analysis
System emulation and firmware re-hosting have become popular techniques to answer various security and performance related questions, such as determining whether a firmware contain security vulnerabilities or meet timing requirements when run on a specific hardware platform. While this motivation for emulation and binary analysis has previously been explored and reported, starting to either work or research in the field is difficult. To this end, we provide a comprehensive guide for the practitioner or system emulation researcher. We layout common challenges faced during firmware re-hosting, explaining successive steps and surveying common tools used to overcome these challenges. We provide classification techniques on five different axes, including emulator methods, system type, fidelity, emulator purpose, and control. These classifications and comparison criteria enable the practitioner to determine the appropriate tool for emulation. We use our classifications to categorize popular works in the field and present 28 common challenges faced when creating, emulating, and analyzing a system from obtaining firmwares to post emulation analysis.
2020
-
Vision Paper: Grand Challenges in Resilience: Autonomous System Resilience through Design and Runtime Measures
In this article, we put forward the substantial challenges in cyber resilience in the domain of autonomous systems and outline foundational solutions to address these challenges. These solutions fall into two broad themes: resilience-by-design and resilience-by-reaction. We use several application drivers from autonomous systems to motivate the challenges in cyber resilience and to demonstrate the benefit of the solutions. We focus on some autonomous systems in the near horizon (autonomous ground and aerial vehicles) and also a little more distant (autonomous rescue and relief). For resilience-by-design, we focus on design methods in software that are needed for our cyber systems to be resilient. In contrast, for resilience-by-reaction, we discuss how to make systems resilient by responding, reconfiguring, or recovering at runtime when failures happen. We also discuss the notion of adaptive execution to improve resilience, execution transparently and adaptively among available execution platforms (mobile/embedded, edge, and cloud). For each of the two themes, we survey the current state, and the desired state and ways to get there. We conclude the paper by looking at the research challenges we will have to solve in the short and the mid-term to make the vision of resilient autonomous systems a reality. This article came out of discussions that started at the NSF-sponsored Grand Challenges in Resilience Workshop held at Purdue in 2019 with the co-authors contributing to going into the depth of the issues and then this article.
2019
-
Extracting SIMD Parallelism from Recursive Task-Parallel Programs
The pursuit of computational efficiency has led to the proliferation of throughput-oriented hardware, from GPUs to increasingly wide vector units on commodity processors and accelerators. This hardware is designed to execute data-parallel computations in a vectorized manner efficiently. However, many algorithms are more naturally expressed as divide-and-conquer, recursive, task-parallel computations. In the absence of data parallelism, it seems that such algorithms are not well suited to throughput-oriented architectures. This article presents a set of novel code transformations that expose the data parallelism latent in recursive, task-parallel programs. These transformations facilitate straightforward vectorization of task-parallel programs on commodity hardware. We also present scheduling policies that maintain high utilization of vector resources while limiting space usage. Across several task-parallel benchmarks, we demonstrate both efficient vector resource utilization and substantial speedup on chips using Intel’s SSE4.2 vector units, as well as accelerators using Intel’s AVX512 units. We then show through rigorous sampling that, in practice, our vectorization techniques are effective for a much larger class of programs.
-
Processor-Oblivious Record and Replay
Record-and-replay systems are useful tools for debugging non-deterministic parallel programs by first recording an execution and then replaying that execution to produce the same access pattern. Existing record-and-replay systems generally target thread-based execution models, and record the behaviors and interleavings of individual threads. Dynamic multithreaded languages and libraries, such as the Cilk family, OpenMP, TBB, and the like, do not have a notion of threads. Instead, these languages provide a processor-oblivious model of programming, where programs expose task parallelism using high-level constructs such as spawn/sync without regard to the number of threads/cores available to run the program. Thread-based record-and-replay would violate the processor-oblivious nature of these programs, as they incorporate the number of threads into the recorded information, constraining the replayed execution to the same number of threads.
In this article, we present a processor-oblivious record-and-replay scheme for dynamic multithreaded languages where record and replay can use different number of processors and both are scheduled using work stealing. We provide theoretical guarantees for our record and replay scheme—namely that record is optimal for programs with one lock and replay is near-optimal for all cases. In addition, we implemented this scheme in the Cilk Plus runtime system and our evaluation indicates that processor-obliviousness does not cause substantial overheads.
-
Scalable Genome Assembly through Parallel de Bruijn Graph Construction for Multiple k-mers
Remarkable advancements in high-throughput gene sequencing technologies have led to an exponential growth in the number of sequenced genomes. However, unavailability of highly parallel and scalable de novo assembly algorithms have hindered biologists attempting to swiftly assemble high-quality complex genomes. Popular de Bruijn graph assemblers, such as IDBA-UD, generate high-quality assemblies by iterating over a set of k -values used in the construction of de Bruijn graphs (DBG). However, this process of sequentially iterating from small to large k -values slows down the process of assembly. In this paper, we propose ScalaDBG, which metamorphoses this sequential process, building DBGs for each distinct k -value in parallel. We develop an innovative mechanism to “patch” a higher k -valued graph with contigs generated from a lower k -valued graph. Moreover, ScalaDBG leverages multi-level parallelism, by both scaling up on all cores of a node, and scaling out to multiple nodes simultaneously . We demonstrate that ScalaDBG completes assembling the genome faster than IDBA-UD, but with similar accuracy on a variety of datasets (6.8X faster for one of the most complex genome in our dataset).
-
A-RESCUE 2.0. A High Fidelity, Parallel, Agent-based Evacuation Simulator
Effective evacuation of residents in hurricane-affected areas is essential in reducing the overall damage and ensuring public safety. However, traffic flow patterns in evacuation contexts is far more complex than normal traffic and is usually accompanied with severe congestion due to the presence of evacuees. In such scenarios, agent-based simulation can accurately capture evacuation traffic patterns, which can be extremely useful in evacuation management. However, existing simulators are not fully capable of simultaneously handling highly detailed household behaviors as well as large-scale traffic in evacuation contexts. In this study, we develop a parallelizable, large-scale version of A-RESCUE (an agent-based regional evacuation simulator coupled with user-enriched behavior) called A-RESCUE 2.0. Detailed household evacuation behaviors are modeled using a comprehensive decision-making module. Computation loads induced by the large number of evacuation vehicles are distributed by a parallelization scheme that involves partitioning the road network into subnetworks such that traffic updates in each subnetwork are simultaneously updated in parallel. Dynamic load balancing among different subnetworks is ensured by periodically repartitioning the network using a mutilevel graph partitioning algorithm. A predictive network-weighing scheme is developed that assigns weights (reflecting computational load) to the roads of a network based on current and predicted future network traffic loadings. An on-demand routing strategy is also developed that allows effective rerouting computation based on changing traffic patterns. A-RESCUE 2.0 is capable of representing nonevacuee background traffic, as well as uncertain events on the network like road closures. In addition, real-time monitoring of traffic patterns is made possible using a visualization module that is connected to the simulator through an efficient data communication layer. Comprehensive experiments are conducted on the Miami-Dade County network to validate the applicability of the developed simulator on real-world networks. Findings from experimental tests confirm that the parallelization scheme is effective in improving computational performance.
2017
-
Exploiting Semantics of Temporal Multi-scale Methods to Optimize Multi-level Mesh Partitioning
Multi‐scale problems are often solved by decomposing the problem domain into multiple subdomains, solving them independently using different levels of spatial and temporal refinement, and coupling the subdomain solutions back to obtain the global solution. Most commonly, finite elements are used for spatial discretization, and finite difference time stepping is used for time integration. Given a finite element mesh for the global problem domain, the number of possible decompositions into subdomains and the possible choices for associated time steps is exponentially large, and the computational costs associated with different decompositions can vary by orders of magnitude. The problem of finding an optimal decomposition and the associated time discretization that minimizes computational costs while maintaining accuracy is nontrivial. Existing mesh partitioning tools, such as METIS, overlook the constraints posed by multi‐scale methods and lead to suboptimal partitions with a high performance penalty. We present a multi‐level mesh partitioning approach that exploits domain‐specific knowledge of multi‐scale methods to produce nearly optimal mesh partitions and associated time steps automatically. Results show that for multi‐scale problems, our approach produces decompositions that outperform those produced by state‐of‐the‐art partitioners like METIS and even those that are manually constructed by domain experts.
2008
-
An Experimental Study of Self-optimizing Dense Linear Algebra Software [Invited Paper]
Memory hierarchy optimizations have been studied by researchers in many areas including compilers, numerical linear algebra, and theoretical computer science. However, the approaches taken by these communities are very different. The compiler community has invested considerable effort in inventing loop transformations like loop permutation and tiling, and in the development of simple analytical models to determine the values of numerical parameters such as tile sizes required by these transformations. Although the performance of compiler-generated code has improved steadily over the years, it is difficult to retarget restructuring compilers to new platforms because of the need to develop analytical models manually for new platforms.
The search for performance portability has led to the development of self-optimizing software systems. One approach to self-optimizing software is the generate-and-test approach, which has been used by the dense numerical linear algebra community to produce high-performance BLAS and FFT libraries. Another approach to portable memory hierarchy optimization is to use the divide-and-conquer approach to implementing cache-oblivious algorithms. Each step of divide-and-conquer generates problems of smaller size and when the working set of the sub-problems fits in some level of the memory hierarchy, that sub-problem can be executed without capacity misses at that level.
Although all three approaches have been studied extensively, there are few experimental studies that have compared these approaches. How well does the code produced by current self-optimizing systems perform compared to hand-tuned code? Is empirical search essential to the generate-and-test approach or is it possible to use analytical models with platform-specific parameters to reduce the size of the search space? The cache-oblivious approach uses divide-and-conquer to perform approximate blocking; how well does approximate blocking perform compared to precise blocking? This paper addresses such questions for matrix multiplication, which is the most important dense linear algebra kernel.
Magazines
2015
-
Debugging High-Performance Computing Applications at Massive Scales
Dynamic analysis techniques help programmers find the root cause of bugs in large-scale parallel applications.
2009
-
Optimistic Parallelism Requires Abstractions
The problem of writing software for multicore processors is greatly simplified if we could automatically parallelize sequential programs. Although auto-parallelization has been studied for many decades, it has succeeded only in a few application areas such as dense matrix computations. In particular, auto-parallelization of irregular programs, which are organized around large, pointer-based data structures like graphs, has seemed intractable.
The Galois project is taking a fresh look at auto-parallelization. Rather than attempt to parallelize all programs no matter how obscurely they are written, we are designing programming abstractions that permit programmers to highlight opportunities for exploiting parallelism in sequential programs, and building a runtime system that uses these hints to execute the program in parallel. In this paper, we describe the design and implementation of a system based on these ideas. Experimental results for two real-world irregular applications, a Delaunay mesh refinement application and a graphics application that performs agglomerative clustering, demonstrate that this approach is promising.
Workshops
2016
-
Evaluating Performance of Task and Data Coarsening in Concurrent Collections
Programmers are faced with many challenges for obtaining performance on machines with increasingly capable, yet increasingly complex hardware. A trend towards task-parallel and asynchronous many-task programming models aim to alleviate the burden of parallel programming on a vast array of current and future platforms. One such model, Concurrent Collections (CnC), provides a programming paradigm that emphasizes the separation of the concerns–domain experts concentrate on their algorithms and correctness, whereas performance experts handle mapping and tuning to a target platform. Deep understanding of parallel constructs and behavior is not necessary to write parallel applications that will run on various multi-threaded and multi-core platforms when using the CnC model. However, performance can vary greatly depending on the granularity of tasks and data declared by the programmer. These program-specific decisions are not part of the CnC tuning capabilities and must be tuned in the program. We analyze the performance behavior based on tuning various elements in each collection for the LULESH application using CnC. We demonstrate the effects of different techniques to modify task and data granularity in CnC collections. Our fully tiled CnC implementation outperforms the OpenMP counterpart by 3(\times ) for 48 processors. Finally, we propose guidelines to emulate the techniques used to obtain high performance while improving programmability.
-
Locality-aware Task-parallel Execution on GPUs
GPGPUs deliver high speedup for regular applications while remaining energy efficient. In recent years, there has been much focus on tuning irregular, task-parallel applications and/or the GPU architecture in order to achieve similar benefits for irregular applications running on GPUs. While most of the previous works have focused on minimizing the effect of control and memory divergence, which are prominent in irregular applications and which degrade the performance, there has been less attention paid to decreasing cache pressure and hence improving performance of applications given the small cache sizes on GPUs.
2015
-
Optimizing the LULESH Stencil Code using Concurrent Collections
Writing scientific applications for modern multicore ma- chines is a challenging task. There are a myriad of hardware solutions available for many different target applications, each having their own advantages and trade-offs. An attractive approach is Concurrent Collections (CnC), which provides a programming model that separates the concerns of the application expert from the performance expert. CnC uses a data and control flow model paired with philosophies from previous data-flow programming models and tuple-space influences. By following the CnC programming paradigm, the runtime will seamlessly exploit available parallelism regardless of the platform; however, there are limitations to its effectiveness depending on the algo- rithm. In this paper, we explore ways to optimize the performance of the proxy application, Livermore Unstructured Lagrange Explicit Shock Hydrodynamics (LULESH), written using Concurrent Collections. The LULESH algorithm is expressed as a minimally-constrained set of partially-ordered operations with explicit dependencies. However, performance is plagued by scheduling overhead and synchronization costs caused by the fine granularity of computation steps. In LULESH and similar stencil-codes, we show that an algorithmic CnC program can be tuned by coalescing CnC elements through step fusion and tiling to become a well-tuned and scalable application running on multi-core systems. With these optimizations, we achieve up to 38x speedup over the original implementation with good scalability for up to 48 processor machines.
2012
-
Abhranta: Localizing Bugs that Manifest at Large System Scales
Acceptance rate 42%Partly superseded by HPDC 2013
A key challenge in developing large scale applications (both in system size and in input size) is finding bugs that are latent at the small scales of testing, only manifesting when a program is deployed at large scales. Traditional statistical techniques fail because no error-free run is available at deployment scales for training purposes. Prior work used scaling models to detect anomalous behavior at large scales without being trained on correct behavior at that scale. However, that work cannot localize bugs automatically. In this paper, we extend that work with automatic diagnosis technique, based on feature reconstruction, and validate our design through case studies with two real bugs from an MPI library and a DHT-based file sharing application.
-
Programming Model Support for Dependable, Elastic Cloud Applications
Acceptance rate 42%
An attractive approach to leveraging the ability of cloud-computing platforms to provide resources on demand is to build elastic applications, which can scale up or down based on resource requirements. To ease the development of elastic applications, it is useful for programmers to write applications with simple, inelastic semantics and rely on runtime systems to provide elasticity. While this approach has been useful in restricted domains, such as MapReduce, we argue in this paper that adding elasticity to general distributed applications introduces new fault-tolerance challenges that must be addressed at the programming model and run-time level. We discuss a programming model for writing elastic, distributed applications, and describe an approach to fault-tolerance that integrates with the elastic run-time to provide transparent elasticity and fault-tolerance.
2010
-
Towards Architecture Independent Metrics for Multicore Performance Analysis
Acceptance rate 37%Also appeared in ACM SIGMETRICS Performance Evaluation Review, 38(3):10–14
The prevalence of multicore architectures has made the performance analysis of multithreaded applications an intriguing area of inquiry. An understanding of locality effects and communication behavior can provide programmers with valuable information about performance bottlenecks and opportunities for optimization. Unfortunately, most performance analyses are architecture dependent, and hence insights gleaned from an application’s behavior on one platform may not apply when the application is run on another. In this position paper, we argue that what is needed are * architecture independent* metrics that characterize the behavior of an application in a system-agnostic manner. Such metrics will allow a program’s performance to be analyzed across a range of architectures without incurring the overhead of repeated profiling and analysis. We propose two specific analyses: multicore-aware reuse distance, which captures the locality properties of an application and communication analysis, which exposes the structure of communication in an application. We also discuss a number of applications of these analyses, in the domains of optimization, code restructuring and performance modeling.
2008
-
On the Scalability of an Automatically Parallelized Irregular Application
Acceptance rate 51%
Irregular applications, i.e., programs that manipulate pointer-based data structures such as graphs and trees, constitute a challenging target for parallelization because the amount of parallelism is input dependent and changes dynamically. Traditional dependence analysis techniques are too conservative to expose this parallelism. Even manual parallelization is difficult, time consuming, and error prone. The Galois system parallelizes such applications using an optimistic approach that exploits higher-level semantics of abstract data types.
In this paper, we study the performance and scalability of a Galoised, i.e., automatically parallelized, version of Delaunay mesh refinement (DR) on a shared-memory system with 128 CPUs. DR is an important irregular application that is used, e.g., in graphics and finite-element codes. The parallelized program scales to 64 threads, where it reaches a speedup of 25.8. For large numbers of threads, the performance is hampered by the load imbalance and the nonuniform memory latency, both of which grow as the number of threads increases. While these two issues will have to be addressed in future work, we believe our results already show the Galois approach to be very promising.
2006
-
Using Transactions in Delaunay Mesh Generation
Mesh generation is a key step in graphics rendering and in using the finite-element method to solve partial differential equations. The goal of mesh generation is to discretize the domain of interest using polygonal elements such as triangles (in 2-D) or tetrahedra (in 3-D).
One popular mesh generation algorithm is Delaunay mesh generation, which produces meshes with certain quality guarantees that are important for problems in which the geometry of the problem changes with time. Delaunay mesh generation works by iterative refinement of a coarse initial mesh. The sequential algorithm repeatedly looks for a ``bad” mesh element that does not satisfy the quality constraints, computes a neighborhood of that element called its cavity, and replaces the elements in that cavity with new elements, some of which may not satisfy the quality guarantees themselves. It can be shown that the algorithm always terminates and produces a guaranteed quality mesh, regardless of the order in which bad elements are processed.
Delaunay mesh generation can be parallelized in a natural way because elements that are far away in the mesh do not interfere with each other as they are being processed. We present experimental results showing that in practice, there is indeed a lot of parallelism that is exposed in this way. However, exploiting this parallelism in practice can be complicated. Compile-time analysis and parallelization are infeasible because of the input-dependent nature of the algorithm. One alternative is optimistic parallelization. We show how logical transactions can be identified in a natural way in this code, argue that current transactional memory implementations are inadequate for this application, and suggest an alternative conception of transactional memory that addresses these problems.
Tech Reports
2012
-
Automatically Enhancing Locality for Tree Traversals with Traversal Splicing
Partly superseded by OOPSLA 2012
Generally applicable techniques for improving locality in irregular programs, which operate over pointer-based data structures such as trees and graphs, are scarce. Focusing on a subset of irregular programs, namely, tree traversal algorithms like Barnes-Hut and nearest neighbor, recent work has proposed point blocking, a technique analogous to loop tiling in regular algorithms, to improve locality. However, point blocking requires that programs be “pre-optimized” using application-specific techniques to be effective. In this work, we identify the root cause of point blocking’s poor performance on baseline irregular algorithms, and propose traversal splicing, a new, general, automatic locality optimization for irregular tree traversal codes, that addresses these drawbacks. For four benchmark algorithms, we show that traversal splicing can deliver substantial single-thread performance improvements of up to 338% (geometric mean: 138%) over baseline implementations, and up to 112% (geometric mean: 77%) over point-blocked implementations. Further, we show that in many cases, applying traversal splicing to a baseline implementation yields performance that is competitive with carefully hand-optimized implementations.
-
Tracking Conflicting Accesses Efficiently for Record and Replay
Record and replay, which records a multithreaded program’s execution in one run and reproduces it deterministically in a second run, is useful for program debugging, fault detection and analysis. The key challenge in multithreaded record and replay is ensuring that conflicting, cross-thread accesses to shared variables are properly detected, recorded and reproduced. Numerous solutions have been proposed in both hardware and software to track these cross-thread accesses, but to date all general-purpose software solutions suffer from high overhead or have serious limitations. This paper introduces Roctet, an approach for performing software-only deterministic record and replay. Roctet is built on top of a novel dynamic analysis infrastructure, Octet, which can detect at low overhead any cross-thread dependences during execution by exploiting the fact that most accesses, even of shared objects, are not part of cross-thread dependences. We implement Octet and Roctet in a JVM and show they add low overhead for several multithreaded applications. We also show that our implementation of Roctet can successfully replay recorded executions when it can successfully control or ignore extraneous sources of nondeterminism in the VM, libraries, and system.
2011
-
Locality-enhancing loop transformations for parallel tree traversal algorithms
Partly superseded by OOPSLA 2011
Exploiting locality is critical to achieving good performance. For regular programs, which operate on dense arrays and matrices, techniques such as loop interchange and tiling have long been known to improve locality and deliver improved performance. However, there has been relatively little work investigating similar locality-improving transformations for irregular programs that operate on trees or graphs. Often, it is not even clear that such transformations are possible. In this paper, we discuss two transformations that can be applied to irregular programs that perform graph traversals. We show that these transformations can be seen as analogs of the popular regular transformations of loop interchange and tiling. We demonstrate the utility of these transformations on two tree traversal algorithms, the Barnes-Hut algorithm and raytracing, achieving speedups of up to 251% over the baseline implementation.
2009
-
Defining and Implementing Commutativity Conditions for Parallel Execution
Partly superseded by PLDI 2011(a)
Irregular applications, which manipulate complex, pointer-based data structures, are a promising target for parallelization. Recent studies have shown that these programs exhibit a kind of parallelism called amorphous data-parallelism. Prior approaches to parallelizing these applications, such as thread-level speculation and transactional memory, often obscure parallelism because they do not distinguish between the concrete representation of a data structure and its semantic state; they conflate metadata and data.
Exploiting the semantic commutativity of methods in complex data structures is a promising approach to exposing more parallelism. Prior work has shown that abstract locks can be used to capture a subset of commutativity properties, however, abstract locks cannot uncover the parallelism in some complex data structures, such as kd-trees and union-find structures. In this paper, we propose a more flexible implementation of commutativity properties, called gatekeepers, which capture more complex commutativity conditions and thus expose more parallelism.
We provide a formal definition of semantic commutativity and define conditions under which abstract locking can be applied and those under which gatekeeping is necessary.We present a quantitative study demonstrating the benefits of abstract locking and gatekeeping in amorphous data-parallel programs. We also present an efficient implementation of gatekeeping, which we evaluate on a real-world application.
-
Amorphous Data-parallelism in Irregular Algorithms
Partly superseded by PLDI 2011(b)
Most client-side applications running on multicore processors are likely to be irregular programs that deal with complex, pointer-based data structures such as large sparse graphs and trees. However, we understand very little about the nature of parallelism in irregular algorithms, let alone how to exploit it effectively on multicore processors.
In this paper, we show that, although the behavior of irregular algorithms can be very complex, many of them have a generalized data-parallelism that we call amorphous data-parallelism. The algorithms in our study come from a variety of important disciplines such as data-mining, AI, compilers, networks, and scientific computing. We also argue that these algorithms can be divided naturally into a small number of categories, and that this categorization provides a lot of insight into their behavior. Finally, we discuss how these insights should guide programming language support and parallel system implementation for irregular algorithms.
Miscellaneous
2016
-
Position Paper: Programming Language Support for Analyzing Non-Persistent Data
-
Hybrid CPU-GPU scheduling and execution of tree traversals
Poster
GPUs offer the promise of massive, power-efficient parallelism. However, exploiting this parallelism requires code to be carefully structured to deal with the limitations of the SIMT execution model. In recent years, there has been much interest in mapping irregular applications to GPUs: applications with unpredictable, data-dependent behaviors. While most of the work in this space has focused on ad hoc implementations of specific algorithms, recent work has looked at generic techniques for mapping a large class of tree traversal algorithms to GPUs, through careful restructuring of the tree traversal algorithms to make them behave more regularly. Unfortunately, even this general approach for GPU execution of tree traversal algorithms is reliant on ad hoc, handwritten, algorithm-specific scheduling (i.e., assignment of threads to warps) to achieve high performance.
-
SPIRIT: a runtime system for distributed irregular tree applications
Poster
Repeated, depth-first traversal of trees is a common algorithmic pattern in an important set of applications from diverse domains such as cosmological simulations, data mining, and computer graphics. As these applications operate over massive data sets, it is often necessary to distribute the trees to process all of the data.
In this work, we introduce SPIRIT, a runtime system to ease the writing of distributed tree applications. SPIRIT automates the challenging tasks of tree distribution, optimizing communication and parallelizing independent computations. The common algorithmic pattern in tree traversals is exploited to effectively schedule parallel computations and improve locality. As a result, pipeline parallelism in distributed traversals is identified, which is complemented by load-balancing, and locality-enhancing, message aggregation optimizations. Evaluation of SPIRIT on tree traversal in Point Correlation (PC) shows a scalable system, achieving speedups upto 38x on a 16-node, 64 process system compared to a 1-node, baseline configuration. We also find that SPIRIT results in substantially less communication and achieves significant performance improvements over implementations in other distributed graph systems.
-
Treelogy: a benchmark suite for tree traversal applications
Poster
An interesting class of irregular algorithms are tree traversal algorithms, which repeatedly traverse spatial trees to perform efficient computations. Optimizing tree traversal algorithms requires understanding specific characteristics of these algorithms which affect their behavior and govern which types of optimizations are likely to perform well. In this work, we present a set of tree traversal applications, drawn from multiple domains, called Treelogy. This benchmark suite can be studied through the use of an ontology that characterizes tree traversal algorithms according to structural properties of the algorithm. We describe how each of these attributes constrains or allows different kinds of traversal optimizations. We characterize the applications of Treelogy both according to our structural ontology as well as by various applicationand input-dependent metrics that measure the irregularity of these applications. We then show the scalability of these applications implemented using generic frameworks for GPU, shared memory, and distributed memory systems. We also find that for certain input distributions, Barnes-Hut and 2-point correlation yield better performance when implemented with tree types other than the “standard” tree.
2015
-
Poster: Exploiting Domain Knowledge to Optimize Mesh Partitioning for Multi-Scale Methods
-
Position Paper: Beyond Big Data-Rethinking Programming Languages for Non-Persistent Data
In “Big Data” research, the data acquired from many sources are fused and analyzed to obtain valuable and sometimes unexpected information. Even though the volumes of data are unprecedented, the data are usually stored for post-experiment analysis and for sharing among scientists. Typical scenarios implicitly assume that the data are stored and can be re-analyzed later. The reality is, unfortunately, not so ideal because the data may be “non-persistent” and allow only one-time use. We propose to reformulate how big data programs are developed, and introduce the notion of data-carrying programs that are, in a sense, self-validating. By writing these programs in a specially-defined language, and transforming them to store sample data, programs can save enough data to provide high-confidence validation of their results.
-
Poster: MANGO: scalable modularity for transparently elastic cloud applications
-
Poster: SemCache++: Semantics-Aware Caching for Efficient Multi-GPU Offloading
Superseded by ICS 2015
Offloading computations to multiple GPUs is not an easy task. It re- quires decomposing data, distributing computations and handling communication manually. GPU libraries have made it easy to offload computations to multiple GPUs by hiding this complexity in- side library calls. Such encapsulation prevents the reuse of the data between successive kernel invocations resulting in redundant communication.
In this work, we introduce SemCache++, a semantics-aware GPU cache that automatically manages communication between the CPU and multiple GPUs in addition to optimizing communication by eliminating redundant transfers using caching. SemCache++ is used to build the first multi-GPU drop-in replacement library that (a) uses the virtual memory to automatically manage and optimize multi-GPU communication and (b) requires no pro- gram rewriting or annotations. Our caching technique is efficient; it uses a two level caching directory to track matrices and sub- matrices. Experimental results show that our system can eliminate redundant communication and deliver significant performance improvements over multi-GPU libraries like CUBLASXT.
2014
-
Programming Model and Software for Exploiting Parallelism in Irregular Programs
Systems and methods for parallelizing applications that operate on irregular data structures. In an embodiment, the methods and systems enable programmers to use set iterators to express algorithms containing amorphous data parallelism. Parallelization can be achieved by speculatively executing multiple iterations of the iterator in parallel. Conflicts between speculatively executing iterations can be detected and handled using information in class libraries.
2013
-
Poster: WuKong: Locating Bugs that Manifest at Large System Scales
Superseded by HPDC 2013
A key challenge in developing large scale applications (both in system size and in input size) is finding bugs that are latent at the small scales of testing, only manifesting when a program is deployed at large scales. Traditional statistical techniques fail because no error-free run is available at deployment scales for training purposes. Prior work used scaling models to detect anomalous behavior at large scales without being trained on correct behavior at that scale. However, that work cannot localize bugs automatically. In this paper, we extend that work in three ways: (i) we develop an automatic diagnosis technique, based on feature reconstruction; (ii) we design a heuristic to effectively prune the feature space; and (iii) we validate our design through one fault-injection study, finding that our system can effectively localize bugs in a majority of cases.
2011
-
Brief Announcement: Locality-enhancing Transformations for Tree Traversal Algorithms
Superseded by OOPSLA 2011
In this paper, we discuss transformations that can be applied to irregular programs that perform tree traversals, which can be seen as analogs of the popular regular transformations of loop tiling. We demonstrate the utility of these transformations on two tree traversal algorithms, the Barnes-Hut algorithm and raytracing, achieving speedups of up to 237% over the baseline implementation.
2010
-
Brief Announcement: Locality-aware Load Balancing for Speculatively-parallelized Irregular Applications
Load balancing is an important consideration when running data-parallel programs. While traditional techniques trade off the cost of load imbalance with the overhead of mitigating that imbalance, when speculatively parallelizing amorphous data-parallel applications, we must also consider the effects of load balancing decisions on locality and speculation accuracy. We present two data centric load balancing strategies which account for the intricacies of amorphous data-parallel execution. We implement these strategies as schedulers in the Galois system and demonstrate that they outperform traditional load balancing schedulers, as well as a data-centric, non-load-balancing scheduler.
2008
-
The Galois System: Optimistic Parallelization of Irregular Applications
The last several years have seen multicore architectures become ascendant in the computing world. As a result, it is no longer sufficient to rely on increasing single-threaded performance to improve application performance; instead, programmers must turn to parallelization to realize the performance gains of multicore architectures. While much research over the past three decades have focused on parallelizing regular programs which operate over arrays and matrices, much less effort has been focused on irregular programs which operate over pointer-based data structures such as trees and graphs. In fact, it is not even clear that a significant amount of parallelism even exists in these applications.
We identify a common type of parallelism that arises in irregular programs that operate over worklists of various kinds, which we call amorphous dataparallelism. Due to the data-dependent nature of these applications, static compiler analysis does not suffice to uncover any parallelism. Instead, successful parallelization requires speculative, or optimistic, parallelization. However, existing speculation techniques, such as thread-level speculation, are too low-level to recognize and extract useful parallelism from these applications.
We present the Galois system for optimistic parallelization which uses highlevel abstractions to express amorphous data-parallelism in irregular programs, and uses semantic properties of data structures to automatically parallelize such programs. These abstractions allow programs with amorphous data-parallelism to be written in a sequential manner, relying on run-time support to extract parallelism.
We then develop abstractions which allow programmers to succinctly capture locality properties of irregular data structures. We show how these abstractions can be used to improve locality , improve speculation performance and reduce speculation overhead. We also present a novel parallel scheduling framework which allows programmers to leverage algorithm semantics to intelligently schedule concurrent computation, improving performance.
We demonstrate the utility of the Galois approach, as well as the extensions that we propose, across a wide range of irregular applications demonstrating amorphous data-parallelism. We find that the Galois approach can be used to extract significant parallelism with low programmer overhead.
2007
-
Scheduling Issues in Optimistic Parallelization
Irregular applications, which rely on pointer-based data structures, are often difficult to parallelize. The input-dependent nature of their execution means that traditional parallelization techniques are unable to exploit any latent parallelism in these algorithms. Instead, we turn to optimistic parallelism, where regions of code are speculatively run in parallel while runtime mechanisms ensure proper execution. The performance of such optimistically parallelized algorithms is often dependent on the schedule for parallel execution; improper choices can prevent successful parallel execution.
We demonstrate this through the motivating example of Delaunay mesh refinement, an irregular algorithm, which we have parallelized optimistically using the Galois system. We apply several scheduling policies to this algorithm and investigate their performance, showing that careful consideration of scheduling is necessary to maximize parallel performance.