The misuse of lock() and unlock() primitives is a significant source of concurrency bugs in parallel software. Two common yet critical errors are releasing a lock not owned by the releasing thread and attempting to acquire a non-recursive lock recursively. This paper presents a novel technique, Lock Shielding, to augment existing locking algorithms with misuse detection. Lock Shielding maintains a thread-local data structure to track the set of locks currently held by each thread, enabling efficient, runtime verification of synchronization operations. We show that, Lock Shielding adds negligible overhead when applied to a variety of locking algorithms and evaluated on the PARSEC 3.0, SPLASH-2x, and Synchrobench benchmark suites. The resulting augmented locks provide robust protection against common programming errors while maintaining performance nearly identical to their original, unsafe versions. Lock Shielding can be readily integrated into applications using Pthreads, OpenMP, or C++ locks, thereby enabling them with robust error detection capabilities. We integrate with several popular GitHub repositories and identify new lock misuse bugs in popular packages such as TensorFlow and MPL.

Matrix-multiplication is an important kernel in domains ranging from machine learning to high-performance computing. Developers devote significant time and effort to optimizing the matrix-multiplication kernel. In this paper, we simplify the development of optimized matrix-multiplication codes for various platforms and heterogeneous systems. We target codes for CPUs on x86 (AVX, AVX2) and ARM (Neon) platforms, as well as Nvidia GPUs and Jetson Nano. To achieve this, we employ a tool to generate a novel, hybrid-parallel, implementation of matrix-multiplication that exploits parallelism within a core, across cores, across nodes, and across GPU devices.

In this paper, we consider the efficient computation of all eigenvalues and eigenvectors of Symmetric Hierarchically Semiseparable (HSS) matrices, which have an inherent structure: the off-diagonal blocks have hierarchical bases and have low ranks. State-of-the-art is a divide-conquer algorithm, SuperDC, to compute eigenvectors and eigenvalues in an order of magnitude faster than popular and commercial solvers. We improve on the state-of-the-art and present novel shared- and distributed-memory parallel algorithms for computing eigenvalues of HSS matrices. We take advantage of the recursive divide-conquer approach employed in SuperDC to parallelize the eigenvalue computation, present a span and available parallelism analysis, and optimize the original SuperDC algorithm to reduce the storage requirement from O(N2) to O(N) in the case of banded matrices. We do a systematic evaluation with different parallel programming paradigms, scheduling policies, and scalability configurations. We observe that in the shared-memory parallel implementations, OpenMP implementations perform better than Cilk versions, work stealing offers no significant performance advantage, and in the distributed-memory implementations, asynchronous communication yields better performance than implementation with barrier-based communication. We find the optimal input decomposition at which the parallel implementations provide the best speedup. For input symmetric matrices of different sparsity structures and sizes ranging from 4096 to 256k rows, on up to 512 cores, the implementations scale well and show a significant speedup of up to 147 × compared to the available SuperDC implementation.

The lock is a building-block synchronization primitive that enables mutually exclusive access to shared data in shared-memory parallel programs. Mutual exclusion is typically achieved by guarding the code that accesses the shared data with a pair of lock() and unlock() operations. Concurrency bugs arise when this ordering of operations is violated.

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.

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.

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.

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, hand-written, algorithm-specific scheduling (i.e., assignment of threads to warps) to achieve high performance.

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.

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.