title: Exploiting accelerators for efficient high dimensional similarity search

authors:
Sandeep R. Agrawal
Christopher M. Dee
Alvin R. Lebeck

abstract: Similarity search finds the most similar matches in an object collection for a given query; making it an important problem across a wide range of disciplines such as web search, image recognition and protein sequencing. Practical implementations of High Dimensional Similarity Search (HDSS) search across billions of possible solutions for multiple queries in real time, making its performance and efficiency a significant challenge. Existing clusters and datacenters use commercial multicore hardware to perform search, which may not provide the optimal performance and performance per Watt.


venue: ppopp

title: GPU multisplit

authors:
Saman Ashkiani
Andrew A. Davidson
Ulrich Meyer
John D. Owens

abstract: Multisplit is a broadly useful parallel primitive that permutes its input data into contiguous buckets or bins, where the function that categorizes an element into a bucket is provided by the programmer. Due to the lack of an efficient multisplit on GPUs, programmers often choose to implement multisplit with a sort. However, sort does more work than necessary to implement multisplit, and is thus inefficient. In this work, we provide a parallel model and multiple implementations for the multisplit problem. Our principal focus is multisplit for a small number of buckets. In our implementations, we exploit the computational hierarchy of the GPU to perform most of the work locally, with minimal usage of global operations. We also use warp-synchronous programming models to avoid branch divergence and reduce memory usage, as well as hierarchical reordering of input elements to achieve better coalescing of global memory accesses. On an NVIDIA K40c GPU, for key-only (key-value) multisplit, we demonstrate a 3.0-6.7x (4.4-8.0x) speedup over radix sort, and achieve a peak throughput of 10.0 G keys/s.


title: Multi-core on-the-fly SCC decomposition

authors:
Vincent Bloemen
Alfons Laarman
Jaco van de Pol

abstract: The main advantages of Tarjan's strongly connected component (SCC) algorithm are its linear time complexity and ability to return SCCs on-the-fly, while traversing or even generating the graph. Until now, most parallel SCC algorithms sacrifice both: they run in quadratic worst-case time and/or require the full graph in advance.


title: Drinking from both glasses: combining pessimistic and optimistic tracking of cross-thread dependences

authors:
Man Cao
Minjia Zhang
Aritra Sengupta
Michael D. Bond

abstract: It is notoriously challenging to develop parallel software systems that are both scalable and correct. Runtime support for parallelism---such as multithreaded record & replay, data race detectors, transactional memory, and enforcement of stronger memory models---helps achieve these goals, but existing commodity solutions slow programs substantially in order to track (i.e., detect or control) an execution's cross-thread dependences accurately. Prior work tracks cross-thread dependences either "pessimistically," slowing every program access, or "optimistically," allowing for lightweight instrumentation of most accesses but dramatically slowing accesses involved in cross-thread dependences.


title: Contention-conscious, locality-preserving locks

authors:
Milind Chabbi
John M. Mellor-Crummey

abstract: Over the last decade, the growing use of cache-coherent NUMA architectures has spurred the development of numerous locality-preserving mutual exclusion algorithms. NUMA-aware locks such as HCLH, HMCS, and cohort locks exploit locality of reference among nearby threads to deliver high lock throughput under high contention. However, the hierarchical nature of these locality-aware locks increases latency, which reduces the throughput of uncontended or lightly-contended critical sections. To date, no lock design for NUMA systems has delivered both low latency under low contention and high throughput under high contention.


title: A programming system for future proofing performance critical libraries

authors:
Li-Wen Chang
Izzat El Hajj
Hee-Seok Kim
Juan Gómez-Luna
Abdul Dakkak
Wen-mei W. Hwu

abstract: We present Tangram, a programming system for writing performance-portable programs. The language enables programmers to write computation and composition codelets, supported by tuning knobs and primitives for expressing data parallelism and work decomposition. The compiler and runtime use a set of techniques such as hierarchical composition, coarsening, data placement, tuning, and runtime selection based on input characteristics and micro-profiling. The resulting performance is competitive with optimized vendor libraries.


title: ESTIMA: extrapolating scalability of in-memory applications

authors:
Georgios Chatzopoulos
Aleksandar Dragojevic
Rachid Guerraoui

abstract: This paper presents ESTIMA, an easy-to-use tool for extrapolating the scalability of in-memory applications. ESTIMA is designed to perform a simple, yet important task: given the performance of an application on a small machine with a handful of cores, ESTIMA extrapolates its scalability to a larger machine with more cores, while requiring minimum input from the user. The key idea underlying ESTIMA is the use of stalled cycles (e.g. cycles that the processor spends waiting for various events, such as cache misses or waiting on a lock). ESTIMA measures stalled cycles on a few cores and extrapolates them to more cores, estimating the amount of waiting in the system. ESTIMA can be effectively used to predict the scalability of in-memory applications. For instance, using measurements of memcached and SQLite on a desktop machine, we obtain accurate predictions of their scalability on a server. Our extensive evaluation on a large number of in-memory benchmarks shows that ESTIMA has generally low prediction errors.


title: Samsara parallel: a non-BSP parallel-in-time model

authors:
Yifeng Chen
Kun Huang
Bei Wang
Guohui Li
Xiang Cui

abstract: Many time-dependent problems like molecular dynamics of protein folding require a large number of time steps. The latencies and overheads of common-purpose clusters with accelerators are too big for high-frequency iteration. We introduce an algorithmic model called Samsara Parallel (or SP) which, unlike BSP, relies on asynchronous communications and can repeatedly return to earlier time steps to refine the precision of computation. This also extends a line of research called Parallel-in-Time in computational chemistry and physics.


title: AUTOGEN: automatic discovery of cache-oblivious parallel recursive algorithms for solving dynamic programs

authors:
Rezaul Alam Chowdhury
Pramod Ganapathi
Jesmin Jahan Tithi
Charles Bachmeier
Bradley C. Kuszmaul
Charles E. Leiserson
Armando Solar-Lezama
Yuan Tang

abstract: We present AUTOGEN---an algorithm that for a wide class of dynamic programming (DP) problems automatically discovers highly efficient cache-oblivious parallel recursive divide-and-conquer algorithms from inefficient iterative descriptions of DP recurrences. AUTOGEN analyzes the set of DP table locations accessed by the iterative algorithm when run on a DP table of small size, and automatically identifies a recursive access pattern and a corresponding provably correct recursive algorithm for solving the DP recurrence. We use AUTOGEN to autodiscover efficient algorithms for several well-known problems. Our experimental results show that several autodiscovered algorithms significantly outperform parallel looping and tiled loop-based algorithms. Also these algorithms are less sensitive to fluctuations of memory and bandwidth compared with their looping counterparts, and their running times and energy profiles remain relatively more stable. To the best of our knowledge, AUTOGEN is the first algorithm that can automatically discover new nontrivial divide-and-conquer algorithms.


title: Declarative coordination of graph-based parallel programs

authors:
Flávio Cruz
Ricardo Rocha
Seth Copen Goldstein

abstract: Declarative programming has been hailed as a promising approach to parallel programming since it makes it easier to reason about programs while hiding the implementation details of parallelism from the programmer. However, its advantage is also its disadvantage as it leaves the programmer with no straightforward way to optimize programs for performance. In this paper, we introduce Coordinated Linear Meld (CLM), a concurrent forward-chaining linear logic programming language, with a declarative way to coordinate the execution of parallel programs allowing the programmer to specify arbitrary scheduling and data partitioning policies. Our approach allows the programmer to write graph-based declarative programs and then optionally to use coordination to fine-tune parallel performance. In this paper we specify the set of coordination facts, discuss their implementation in a parallel virtual machine, and show---through example---how they can be used to optimize parallel execution. We compare the performance of CLM programs against the original uncoordinated Linear Meld and several other frameworks.


title: Distributed Halide

authors:
Tyler Denniston
Shoaib Kamil
Saman P. Amarasinghe

abstract: Many image processing tasks are naturally expressed as a pipeline of small computational kernels known as stencils. Halide is a popular domain-specific language and compiler designed to implement image processing algorithms. Halide uses simple language constructs to express what to compute and a separate scheduling co-language for expressing when and where to perform the computation. This approach has demonstrated performance comparable to or better than hand-optimized code. Until now, however, Halide has been restricted to parallel shared memory execution, limiting its performance for memory-bandwidth-bound pipelines or large-scale image processing tasks.


title: Refined transactional lock elision

authors:
Dave Dice
Alex Kogan
Yossi Lev

abstract: Transactional lock elision (TLE) is a well-known technique that exploits hardware transactional memory (HTM) to introduce concurrency into lock-based software. It achieves that by attempting to execute a critical section protected by a lock in an atomic hardware transaction, reverting to the lock if these attempts fail. One significant drawback of TLE is that it disables hardware speculation once there is a thread running under lock. In this paper we present two algorithms that rely on existing compiler support for transactional programs and allow threads to speculate concurrently on HTM along with a thread holding the lock. We demonstrate the benefit of our algorithms over TLE and other related approaches with an in-depth analysis of a number of benchmarks and a wide range of workloads, including an AVL tree-based micro-benchmark and ccTSA, a real sequence assembler application.


title: NUMA-aware scheduling and memory allocation for data-flow task-parallel applications

authors:
Andi Drebes
Antoniu Pop
Karine Heydemann
Nathalie Drach
Albert Cohen

abstract: Dynamic task parallelism is a popular programming model on shared-memory systems. Compared to data parallel loop-based concurrency, it promises enhanced scalability, load balancing and locality. These promises, however, are undermined by non-uniform memory access (NUMA) systems. We show that it is possible to preserve the uniform hardware abstraction of contemporary task-parallel programming models, for both computing and memory resources, while achieving near-optimal data locality. Our run-time algorithms for NUMA-aware task and data placement are fully automatic, application-independent, performance-portable across NUMA machines, and adapt to dynamic changes. Placement decisions use information about inter-task data dependences and reuse. This information is readily available in the run-time systems of modern task-parallel programming frameworks, and from the operating system regarding the placement of previously allocated memory. Our algorithms take advantage of data-flow style task parallelism, where the privatization of task data enhances scalability through the elimination of false dependences and enables fine-grained dynamic control over the placement of application data. We demonstrate that the benefits of dynamically managing data placement outweigh the privatization cost, even when comparing with target-specific optimizations through static, NUMA-aware data interleaving. Our implementation and the experimental evaluation on a set of high-performance benchmarks executing on a 192-core system with 24 NUMA nodes show that the fraction of local memory accesses can be increased to more than 99%, resulting in a speedup of up to 5× compared to a NUMA-aware hierarchical work-stealing baseline.


title: Affinity-aware work-stealing for integrated CPU-GPU processors

authors:
Naila Farooqui
Rajkishore Barik
Brian T. Lewis
Tatiana Shpeisman
Karsten Schwan

abstract: Recent integrated CPU-GPU processors like Intel's Broadwell and AMD's Kaveri support hardware CPU-GPU shared virtual memory, atomic operations, and memory coherency. This enables fine-grained CPU-GPU work-stealing, but architectural differences between the CPU and GPU hurt the performance of traditionally-implemented work-stealing on such processors. These architectural differences include different clock frequencies, atomic operation costs, and cache and shared memory latencies. This paper describes a preliminary implementation of our work-stealing scheduler, Libra, which includes techniques to deal with these architectural differences in integrated CPU-GPU processors. Libra's affinity-aware techniques achieve significant performance gains over classically-implemented work-stealing. We show preliminary results using a diverse set of nine regular and irregular workloads running on an Intel Broadwell Core-M processor. Libra currently achieves up to a 2× performance improvement over classical work-stealing, with a 20% average improvement.


title: An interval constrained memory allocator for the Givy GAS runtime

authors:
François Gindraud
Fabrice Rastello
Albert Cohen
François Broquedis

abstract: The shared memory model helps parallel programming productivity, but it also has a high hardware cost and imposes scalability constraints. Ultimately, higher performance will use distributed memories, which scales better but requires programmers to manually transfer data between local memories, which is a complex task. Distributed memories are also more energy efficient than shared memories, and are used in a family of embedded computing solutions called multi processor system on chip (MPSoC).


title: Optimistic concurrency with OPTIK

authors:
Rachid Guerraoui
Vasileios Trigonakis

abstract: We introduce OPTIK, a new practical design pattern for designing and implementing fast and scalable concurrent data structures. OPTIK relies on the commonly-used technique of version numbers for detecting conflicting concurrent operations. We show how to implement the OPTIK pattern using the novel concept of OPTIK locks. These locks enable the use of version numbers for implementing very efficient optimistic concurrent data structures. Existing state-of-the-art lock-based data structures acquire the lock and then check for conflicts. In contrast, with OPTIK locks, we merge the lock acquisition with the detection of conflicting concurrency in a single atomic step, similarly to lock-free algorithms. We illustrate the power of our OPTIK pattern and its implementation by introducing four new algorithms and by optimizing four state-of-the-art algorithms for linked lists, skip lists, hash tables, and queues. Our results show that concurrent data structures built using OPTIK are more scalable than the state of the art.


title: Lease/release: architectural support for scaling contended data structures

authors:
Syed Kamran Haider
William Hasenplaugh
Dan Alistarh

abstract: High memory contention is generally agreed to be a worst-case scenario for concurrent data structures. There has been a significant amount of research effort spent investigating designs which minimize contention, and several programming techniques have been proposed to mitigate its effects. However, there are currently few architectural mechanisms to allow scaling contended data structures at high thread counts.


title: SPIRIT: a runtime system for distributed irregular tree applications

authors:
Nikhil Hegde
Jianqiao Liu
Milind Kulkarni

abstract: 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.


title: DomLock: a new multi-granularity locking technique for hierarchies

authors:
Saurabh Kalikar
Rupesh Nasre

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


title: A high-performance parallel algorithm for nonnegative matrix factorization

authors:
Ramakrishnan Kannan
Grey Ballard
Haesun Park

abstract: Non-negative matrix factorization (NMF) is the problem of determining two non-negative low rank factors W and H, for the given input matrix A, such that A ≈ WH. NMF is a useful tool for many applications in different domains such as topic modeling in text mining, background separation in video analysis, and community detection in social networks. Despite its popularity in the data mining community, there is a lack of efficient distributed algorithms to solve the problem for big data sets.


title: User-assisted storage reuse determination for dynamic task graphs

authors:
Mehmet Can Kurt
Bin Ren
Sriram Krishnamoorthy
Gagan Agrawal

abstract: Models based on task graphs that operate on single-assignment data are attractive in several ways, but also require nuanced algorithms for scheduling and memory management for efficient execution. In this paper, we consider memory-efficient dynamic scheduling of task graphs, and present a novel approach for dynamically recycling the memory locations assigned to data items as they are produced by tasks.


title: Work stealing for interactive services to meet target latency

authors:
Jing Li
Kunal Agrawal
Sameh Elnikety
Yuxiong He
I-Ting Angelina Lee
Chenyang Lu
Kathryn S. McKinley

abstract: Interactive web services increasingly drive critical business workloads such as search, advertising, games, shopping, and finance. Whereas optimizing parallel programs and distributed server systems have historically focused on average latency and throughput, the primary metric for interactive applications is instead consistent responsiveness, i.e., minimizing the number of requests that miss a target latency. This paper is the first to show how to generalize work-stealing, which is traditionally used to minimize the makespan of a single parallel job, to optimize for a target latency in interactive services with multiple parallel requests.


title: Hybrid CPU-GPU scheduling and execution of tree traversals

authors:
Jianqiao Liu
Nikhil Hegde
Milind Kulkarni

abstract: 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.


title: Data-centric combinatorial optimization of parallel code

authors:
Hao Luo
Guoyang Chen
Pengcheng Li
Chen Ding
Xipeng Shen

abstract: Memory performance is one essential factor for tapping into the full potential of the massive parallelism of GPU. It has motivated some recent efforts in GPU cache modeling. This paper presents a new data-centric way to model the performance of a system with heterogeneous memory resources. The new model is composable, meaning it can predict the performance difference due to placing data differently by profiling the execution just once.


title: Production-guided concurrency debugging

authors:
Nuno Machado
Brandon Lucia
Luís E. T. Rodrigues

abstract: Concurrency bugs that stem from schedule-dependent branches are hard to understand and debug, because their root causes imply not only different event orderings, but also changes in the control-flow between failing and non-failing executions. We present Cortex: a system that helps exposing and understanding concurrency bugs that result from schedule-dependent branches, without relying on information from failing executions. Cortex preemptively exposes failing executions by perturbing the order of events and control-flow behavior in non-failing schedules from production runs of a program. By leveraging this information from production runs, Cortex synthesizes executions to guide the search for failing schedules. Production-guided search helps cope with the large execution search space by targeting failing executions that are similar to observed non-failing executions. Evaluation on popular benchmarks shows that Cortex is able to expose failing schedules with only a few perturbations to non-failing executions, and takes a practical amount of time.


title: Concurrent hash tables: fast and general?(!)

authors:
Tobias Maier
Peter Sanders
Roman Dementiev

abstract: Concurrent hash tables are one of the most important concurrent data structures with numerous applications. Since hash table accesses can dominate the execution time of the overall application, we need implementations that achieve good speedup. Unfortunately, currently available concurrent hashing libraries turn out to be far away from this requirement in particular when contention on some elements occurs.


title: DSMR: a shared and distributed memory algorithm for single-source shortest path problem

authors:
Saeed Maleki
Donald Nguyen
Andrew Lenharth
María Jesús Garzarán
David A. Padua
Keshav Pingali

abstract: The Single-Source Shortest Path (SSSP) problem is to find the shortest paths from a source vertex to all other vertices in a graph. In this paper, we introduce the Dijkstra Strip-Mined Relaxation (DSMR) algorithm, an efficient parallel SSSP algorithm for shared and distributed memory systems. Our results show that, DSMR is faster than parallel Δ-Stepping by a factor of up-to 1.66.


title: Unifying fixed code and fixed data mapping of load-imbalanced pipelined loops

authors:
Aristeidis Mastoras
Thomas R. Gross

abstract: Some loops with cross-iteration dependences can execute in parallel by pipelining. The loop body is partitioned into stages such that the data dependences are not violated and then the stages are mapped onto threads. Two well-known mapping techniques are fixed code and fixed data; they achieve high performance for load-balanced loops, but they fail to perform well for load-imbalanced loops. In this article, we present a novel hybrid mapping that eliminates drawbacks of both prior mapping techniques and enables dynamic scheduling of stages.


title: Keep calm and react with foresight: strategies for low-latency and energy-efficient elastic data stream processing

authors:
Tiziano De Matteis
Gabriele Mencagli

abstract: This paper addresses the problem of designing scaling strategies for elastic data stream processing. Elasticity allows applications to rapidly change their configuration on-the-fly (e.g., the amount of used resources) in response to dynamic workload fluctuations. In this work we face this problem by adopting the Model Predictive Control technique, a control-theoretic method aimed at finding the optimal application configuration along a limited prediction horizon in the future by solving an online optimization problem. Our control strategies are designed to address latency constraints, using Queueing Theory models, and energy consumption by changing the number of used cores and the CPU frequency through the Dynamic Voltage and Frequency Scaling (DVFS) support available in the modern multicore CPUs. The proactive capabilities, in addition to the latency- and energy-awareness, represent the novel features of our approach. To validate our methodology, we develop a thorough set of experiments on a high-frequency trading application. The results demonstrate the high-degree of flexibility and configurability of our approach, and show the effectiveness of our elastic scaling strategies compared with existing state-of-the-art techniques used in similar scenarios.


title: Merge-based sparse matrix-vector multiplication (SpMV) using the CSR storage format

authors:
Duane Merrill
Michael Garland

abstract: We present a perfectly balanced, "merge-based" parallel method for computing sparse matrix-vector products (SpMV). Our algorithm operates directly upon the Compressed Sparse Row (CSR) sparse matrix format, a predominant in-memory representation for general-purpose sparse linear algebra computations. Our CsrMV performs an equitable multi-partitioning of the input dataset, ensuring that no single thread can be overwhelmed by assignment to (a) arbitrarily-long rows or (b) an arbitrarily-large number of zero-length rows. This parallel decomposition requires neither offline preprocessing nor specialized/ancillary data formats. We evaluate our method on both CPU and GPU microarchitecture across an enormous corpus of diverse real world matrix datasets. We show that traditional CsrMV methods are inconsistent performers subject to order-of-magnitude slowdowns, whereas the performance response of our method is substantially impervious to row-length heterogeneity.


title: On designing NUMA-aware concurrency control for scalable transactional memory

authors:
Mohamed Mohamedin
Roberto Palmieri
Sebastiano Peluso
Binoy Ravindran

abstract: NUMA architectures posed the challenge of rethinking parallel applications due to the non-homogeneity introduced by their design, and their real benefits are limited to the characteristics of the particular workload. We name as partitionable transactional workloads such workloads that may be able to exploit the distributed nature of NUMA, such as transactional workloads where data and accesses can be easily partitioned among the so called NUMA zones. However, in case those workloads require the synchronization on shared data, we have to face the issue of exploiting the NUMA architecture also in the concurrency control for their transactions. Therefore in this paper we present a NUMA-aware concurrency control for transactional memory that we designed for promoting scalability in scenarios where both the transactional workload is prone to scale, and the characteristics of the underlying memory model are inherently non-uniform, such as NUMA architectures.


title: Grain graphs: OpenMP performance analysis made easy

authors:
Ananya Muddukrishna
Peter A. Jonsson
Artur Podobas
Mats Brorsson

abstract: Average programmers struggle to solve performance problems in OpenMP programs with tasks and parallel for-loops. Existing performance analysis tools visualize OpenMP task performance from the runtime system's perspective where task execution is interleaved with other tasks in an unpredictable order. Problems with OpenMP parallel for-loops are similarly difficult to resolve since tools only visualize aggregate thread-level statistics such as load imbalance without zooming into a per-chunk granularity. The runtime system/threads oriented visualization provides poor support for understanding problems with task and chunk execution time, parallelism, and memory hierarchy utilization, forcing average programmers to rely on experts or use tedious trial-and-error tuning methods for performance. We present grain graphs, a new OpenMP performance analysis method that visualizes grains -- computation performed by a task or a parallel for-loop chunk instance -- and highlights problems such as low parallelism, work inflation and poor parallelization benefit at the grain level. We demonstrate that grain graphs can quickly reveal performance problems that are difficult to detect and characterize in fine detail using existing visualizations in standard OpenMP programs, simplifying OpenMP performance analysis. This enables average programmers to make portable optimizations for poor performing OpenMP programs, reducing pressure on experts and removing the need for tedious trial-and-error tuning.


title: The virtues of conflict: analysing modern concurrency

authors:
Ganesh Narayanaswamy
Saurabh Joshi
Daniel Kroening

abstract: Modern shared memory multiprocessors permit reordering of memory operations for performance reasons. These reorderings are often a source of subtle bugs in programs written for such architectures. Traditional approaches to verify weak memory programs often rely on interleaving semantics, which is prone to state space explosion, and thus severely limits the scalability of the analysis. In recent times, there has been a renewed interest in modelling dynamic executions of weak memory programs using partial orders. However, such an approach typically requires ad-hoc mechanisms to correctly capture the data and control-flow choices/conflicts present in real-world programs. In this work, we propose a novel, conflict-aware, composable, truly concurrent semantics for programs written using C/C++ for modern weak memory architectures. We exploit our symbolic semantics based on general event structures to build an efficient decision procedure that detects assertion violations in bounded multi-threaded programs. Using a large, representative set of benchmarks, we show that our conflict-aware semantics outperforms the state-of-the-art partial-order based approaches.


title: Parallel type-checking with haskell using saturating LVars and stream generators

authors:
Ryan R. Newton
Ömer S. Agacan
Peter P. Fogg
Sam Tobin-Hochstadt

abstract: Given the sophistication of recent type systems, unification-based type-checking and inference can be a time-consuming phase of compilation---especially when union types are combined with subtyping. It is natural to consider improving performance through parallelism, but these algorithms are challenging to parallelize due to complicated control structure and difficulties representing data in a way that is both efficient and supports concurrency. We provide techniques that address these problems based on the LVish approach to deterministic-by-default parallel programming. We extend LVish with Saturating LVars, the first LVars implemented to release memory during the object's lifetime. Our design allows us to achieve a parallel speedup on worst-case (exponential) inputs of Hindley-Milner inference, and on the Typed Racket type-checking algorithm, which yields up an 8.46× parallel speedup on 14 cores for type-checking examples drawn from the Racket repository.


title: A scalable lock-free hash table with open addressing

authors:
Jesper Puge Nielsen
Sven Karlsson

abstract: Concurrent data structures synchronized with locks do not scale well with the number of threads. As more scalable alternatives, concurrent data structures and algorithms based on widely available, however advanced, atomic operations have been proposed. These data structures allow for correct and concurrent operations without any locks. In this paper, we present a new fully lock-free open addressed hash table with a simpler design than prior published work. We split hash table insertions into two atomic phases: first inserting a value ignoring other concurrent operations, then in the second phase resolve any duplicate or conflicting values.


title: Efficient distributed workstealing via matchmaking

authors:
Hrushit Parikh
Vinit Deodhar
Ada Gavrilovska
Santosh Pande

abstract: Many classes of high-performance applications and combinatorial problems exhibit large degree of runtime load variability. One approach to achieving balanced resource use is to over decompose the problem on fine-grained tasks that are then dynamically balanced using approaches such as workstealing. Existing work stealing techniques for such irregular applications, running on large clusters, exhibit high overheads due to potential untimely interruption of busy nodes, excessive communication messages and delays experienced by idle nodes in finding work due to repeated failed steals. We contend that the fundamental problem of distributed work-stealing is of rapidly bringing together work producers and consumers. In response, we develop an algorithm that performs timely, lightweight and highly efficient matchmaking between work producers and consumers which results in accurate load balance. Experimental evaluations show that our scheduler is able to outperform other distributed work stealing schedulers, and to achieve scale beyond what is possible with current approaches.


title: Causal consistency: beyond memory

authors:
Matthieu Perrin
Achour Mostéfaoui
Claude Jard

abstract: In distributed systems where strong consistency is costly when not impossible, causal consistency provides a valuable abstraction to represent program executions as partial orders. In addition to the sequential program order of each computing entity, causal order also contains the semantic links between the events that affect the shared objects -- messages emission and reception in a communication channel, reads and writes on a shared register. Usual approaches based on semantic links are very difficult to adapt to other data types such as queues or counters because they require a specific analysis of causal dependencies for each data type. This paper presents a new approach to define causal consistency for any abstract data type based on sequential specifications. It explores, formalizes and studies the differences between three variations of causal consistency and highlights them in the light of PRAM, eventual consistency and sequential consistency: weak causal consistency, that captures the notion of causality preservation when focusing on convergence; causal convergence that mixes weak causal consistency and convergence; and causal consistency, that coincides with causal memory when applied to shared memory.


title: CUDA acceleration for Xen virtual machines in infiniband clusters with rCUDA

authors:
Javier Prades
Carlos Reaño
Federico Silla

abstract: Many data centers currently use virtual machines (VMs) to achieve a more efficient usage of hardware resources. However, current virtualization solutions, such as Xen, do not easily provide graphics processing unit (GPU) accelerators to applications running in the virtualized domain with the flexibility usually required in data centers (i.e., managing virtual GPU instances and concurrently sharing them among several VMs). Remote GPU virtualization frameworks such as the rCUDA solution may address this problem.


title: OPR: deterministic group replay for one-sided communication

authors:
Xuehai Qian
Koushik Sen
Paul Hargrove
Costin Iancu

abstract: The ability to reproduce a parallel execution is desirable for debugging and program reliability purposes. In debugging (13), the programmer needs to manually step back in time, while for resilience (6) this is automatically performed by the the application upon failure. To be useful, replay has to faithfully reproduce the original execution. For parallel programs the main challenge is inferring and maintaining the order of conflicting operations (data races). Deterministic record and replay (R&R) techniques have been developed for multithreaded shared memory programs (5), as well as distributed memory programs (14). Our main interest is techniques for large scale scientific (3; 4) programming models.


title: Preemption-aware planning on big-data systems

authors:
Marco Rabozzi
Matteo Mazzucchelli
Roberto Cordone
Giovanni Matteo Fumarola
Marco D. Santambrogio

abstract: Recent developments in Big Data frameworks are moving towards reservation based approaches as a mean to manage the increasingly complex mix of computations, whereas preemption techniques are employed to meet strict jobs deadlines. Within this work we propose and evaluate a new planning algorithm in the context of reservation based scheduling. Our approach is able to achieve high cluster utilization while minimizing the need for preemption that causes system overheads and planning mispredictions.


title: Improving efficacy of internal binary search trees using local recovery

authors:
Arunmoezhi Ramachandran
Neeraj Mittal

abstract: Binary Search Tree (BST) is an important data structure for managing ordered data. Many algorithms---blocking as well as non-blocking---have been proposed for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations based on both external and internal representations of a search tree.


title: Tidex: a mutual exclusion lock

authors:
Pedro Ramalhete
Andreia Correia

abstract: Several basic mutual exclusion lock algorithms are known, with one of the simplest being the Ticket Lock. We present a new mutual exclusion lock with properties similar to the Ticket Lock but using atomic_exchange() instead of atomic_fetch_add() that can be more efficient on systems without a native instruction for atomic_fetch_add(), or in which the native instruction for atomic_exchange() is faster than the one for atomic_fetch_add(). Similarly to the Ticket Lock, our lock has small memory foot print, is extremely simple, respects FIFO order, and provides starvation freedom in architectures that implement atomic_exchange() as a single instruction, like x86.


title: Verification of MPI Java programs using software model checking

authors:
Waqas ur Rehman
Muhammad Sohaib Ayub
Junaid Haroon Siddiqui

abstract: Development of concurrent software requires the programmer to be aware of non-determinism, data races, and deadlocks. MPI (message passing interface) is a popular standard for writing message oriented distributed applications. Some messages in MPI systems can be processed by one of the many machines and in many possible orders. This non-determinism can affect the result of an MPI application. The alternate results may or may not be correct. To verify MPI applications, we need to check all these possible orderings and use an application specific oracle to decide if these orderings give correct output. MPJ Express is an open source Java implementation of the MPI standard. We developed a Java based model of MPJ Express, where processes are modeled as threads, and which can run unmodified MPI Java programs on a single system. This enabled us to adapt the Java PathFinder explicit state software model checker (JPF) using a custom listener to verify our model running real MPI Java programs. We evaluated our approach using small examples where model checking revealed message orders that would result in incorrect system behavior.


title: Benchmarking weak memory models

authors:
Carl G. Ritson
Scott Owens

abstract: To achieve good multi-core performance, modern microprocessors have weak memory models, rather than enforce sequential consistency. This gives the programmer a wide scope for choosing exactly how to implement various aspects of inter-thread communication through the system's shared memory. However, these choices come with both semantic and performance consequences, often in tension with each other. In this paper, we focus on the performance side, and define techniques for evaluating the impact of various choices in using weak memory models, such as where to put fences, and which fences to use. We make no attempt to judge certain strategies as best or most efficient, and instead provide the techniques that will allow the programmer to understand the performance implications when identifying and resolving any semantic/performance trade-offs. In particular, our technique supports the reasoned selection of macrobenchmarks to use in investigating trade-offs in using weak memory models. We demonstrate our technique on both synthetic benchmarks and real-world applications for the Linux Kernel and OpenJDK Hotspot Virtual Machine on the ARMv8 and POWERv7 architectures.


title: On ordering transaction commit

authors:
Mohamed M. Saad
Roberto Palmieri
Binoy Ravindran

abstract: In this poster paper, we briefly introduce an effective solution to address the problem of committing transactions enforcing a predefined order. To do that, we overview the design of two algorithms that deploy a cooperative transaction execution that circumvents the transaction isolation constraint in favor of propagating written values among conflicting transactions. A preliminary implementation shows that even in the presence of data conflicts, the proposed algorithms outperform other competitors, significantly.


title: Generic messages: capability-based shared memory parallelism for event-loop systems

authors:
Luca Salucci
Daniele Bonetta
Stefan Marr
Walter Binder

abstract: Systems based on event-loops have been popularized by Node.JS, and are becoming a key technology in the domain of cloud computing. Despite their popularity, such systems support only share-nothing parallelism via message passing between parallel entities usually called workers. In this paper, we introduce a novel parallel programming abstraction called Generic Messages (GEMs), which enables shared-memory parallelism for share-nothing event-based systems. A key characteristic of GEMs is that they enable workers to share state by specifying how the state can be accessed once it is shared. We call this aspect of the GEMs model capability-based parallelism.


title: Adding approximate counters

authors:
Guy L. Steele Jr.
Jean-Baptiste Tristan

abstract: We describe a general framework for adding the values of two approximate counters to produce a new approximate counter value whose expected estimated value is equal to the sum of the expected estimated values of the given approximate counters. (To the best of our knowledge, this is the first published description of any algorithm for adding two approximate counters.) We then work out implementation details for five different kinds of approximate counter and provide optimized pseudocode. For three of them, we present proofs that the variance of a counter value produced by adding two counter values in this way is bounded, and in fact is no worse, or not much worse, than the variance of the value of a single counter to which the same total number of increment operations have been applied. Addition of approximate counters is useful in massively parallel divide-and-conquer algorithms that use a distributed representation for large arrays of counters. We describe two machine-learning algorithms for topic modeling that use millions of integer counters, and confirm that replacing the integer counters with approximate counters is effective, speeding up a GPU-based implementation by over 65% and a CPU-based by nearly 50%, as well as reducing memory requirements, without degrading their statistical effectiveness.


title: Coarse grain parallelization of deep neural networks

abstract: Deep neural networks (DNN) have recently achieved extraordinary results in domains like computer vision and speech recognition. An essential element for this success has been the introduction of high performance computing (HPC) techniques in the critical step of training the neural network. This paper describes the implementation and analysis of a network-agnostic and convergence-invariant coarse-grain parallelization of the DNN training algorithm. The coarse-grain parallelization is achieved through the exploitation of the batch-level parallelism. This strategy is independent from the support of specialized and optimized libraries. Therefore, the optimization is immediately available for accelerating the DNN training. The proposal is compatible with multi-GPU execution without altering the algorithm convergence rate. The parallelization has been implemented in Caffe, a state-of-the-art DNN framework. The paper describes the code transformations for the parallelization and we also identify the limiting performance factors of the approach. We show competitive performance results for two state-of-the-art computer vision datasets, MNIST and CIFAR-10. In particular, on a 16-core Xeon E5-2667v2 at 3.30GHz we observe speedups of 8× over the sequential execution, at similar performance levels of those obtained by the GPU optimized Caffe version in a NVIDIA K40 GPU.


title: Effect of portable fine-grained locality on energy efficiency and performance in concurrent search trees

authors:
Ibrahim Umar
Otto J. Anshus
Phuong Hoai Ha

abstract: Recent research has suggested that improving fine-grained data-locality is one of the main approaches to improving energy efficiency and performance. However, no previous research has investigated the effect of the approach on these metrices in the case of concurrent data structures.


title: Be my guest: MCS lock now welcomes guests

authors:
Tianzheng Wang
Milind Chabbi
Hideaki Kimura

abstract: The MCS lock is one of the most prevalent queuing locks. It provides fair scheduling and high performance on massively parallel systems. However, the MCS lock mandates a bring-your-own-context policy: each lock user must provide an additional context (i.e., a queue node) to interact with the lock. This paper proposes MCSg, a variant of the MCS lock that relaxes this restriction.


title: Gunrock: a high-performance graph processing library on the GPU

authors:
Yangzihao Wang
Andrew A. Davidson
Yuechao Pan
Yuduo Wu
Andy Riffel
John D. Owens

abstract: For large-scale graph analytics on the GPU, the irregularity of data access/control flow and the complexity of programming GPUs have been two significant challenges for developing a programmable high-performance graph library. "Gunrock," our high-level bulk-synchronous graph-processing system targeting the GPU, takes a new approach to abstracting GPU graph analytics: rather than designing an abstraction around computation, Gunrock instead implements a novel data-centric abstraction centered on operations on a vertex or edge frontier. Gunrock achieves a balance between performance and expressiveness by coupling high-performance GPU computing primitives and optimization strategies with a high-level programming model that allows programmers to quickly develop new graph primitives with small code size and minimal GPU programming knowledge. We evaluate Gunrock on five graph primitives (BFS, BC, SSSP, CC, and PageRank) and show that Gunrock has on average at least an order of magnitude speedup over Boost and PowerGraph, comparable performance to the fastest GPU hardwired primitives, and better performance than any other GPU high-level graph library.


title: High performance model based image reconstruction

authors:
Xiao Wang
Amit Sabne
Sherman J. Kisner
Anand Raghunathan
Charles A. Bouman
Samuel P. Midkiff

abstract: Computed Tomography (CT) Image Reconstruction is an important technique used in a wide range of applications, ranging from explosive detection, medical imaging to scientific imaging. Among available reconstruction methods, Model Based Iterative Reconstruction (MBIR) produces higher quality images and allows for the use of more general CT scanner geometries than is possible with more commonly used methods. The high computational cost of MBIR, however, often makes it impractical in applications for which it would otherwise be ideal. This paper describes a new MBIR implementation that significantly reduces the computational cost of MBIR while retaining its benefits. It describes a novel organization of the scanner data into super-voxels (SV) that, combined with a super-voxel buffer (SVB), dramatically increase locality and prefetching, enable parallelism across SVs and lead to an average speedup of 187 on 20 cores.


title: A wait-free queue as fast as fetch-and-add

authors:
Chaoran Yang
John M. Mellor-Crummey

abstract: Concurrent data structures that have fast and predictable performance are of critical importance for harnessing the power of multicore processors, which are now ubiquitous. Although wait-free objects, whose operations complete in a bounded number of steps, were devised more than two decades ago, wait-free objects that can deliver scalable high performance are still rare.


title: Scalable adaptive NUMA-aware lock: combining local locking and remote locking for efficient concurrency

authors:
Mingzhe Zhang
Francis C. M. Lau
Cho-Li Wang
Luwei Cheng
Haibo Chen

abstract: Scalable locking is a key building block for scalable multi-threaded software. Its performance is especially critical in multi-socket, multi-core machines with non-uniform memory access (NUMA). Previous schemes such as local locking and remote locking only perform well under a certain level of contention, and often require non-trivial tuning for a particular configuration. Besides, for large NUMA systems, because of unmanaged lock server's nomination, current distance-first NUMA policies cannot perform satisfactorily.


title: POSTER: Cache-Oblivious MPI All-to-All Communications on Many-Core Architectures

authors:
Shigang Li
Yunquan Zhang
Torsten Hoefler

abstract: In the many-core era, the performance of MPI collectives is more dependent on the intra-node communication component. However, the communication algorithms generally inherit from the inter-node version and ignore the cache complexity. We propose cache-oblivious algorithms for MPI all-to-all operations, in which data blocks are copied into the receive buffers in Morton order to exploit data locality. Experimental results on different many-core architectures show that our cache-oblivious implementations significantly outperform the naive implementations based on shared heap and the highly optimized MPI libraries.


title: Contention in Structured Concurrency: Provably Efficient Dynamic Non-Zero Indicators for Nested Parallelism

authors:
Umut A. Acar
Naama Ben-David
Mike Rainey

abstract: Over the past two decades, many concurrent data structures have been designed and implemented. Nearly all such work analyzes concurrent data structures empirically, omitting asymptotic bounds on their efficiency, partly because of the complexity of the analysis needed, and partly because of the difficulty of obtaining relevant asymptotic bounds: when the analysis takes into account important practical factors, such as contention, it is difficult or even impossible to prove desirable bounds.


title: POSTER: Reuse, don't Recycle: Transforming Algorithms that Throw Away Descriptors

authors:
Maya Arbel-Raviv
Trevor Brown

abstract: Lock-free algorithms guarantee progress by having threads help one another. Complex lock-free operations facilitate helping by creating descriptor objects that describe how other threads should help them. In many lock-free algorithms, a new descriptor is allocated for each operation. After an operation completes, its descriptor must be reclaimed by a memory reclamation scheme. Allocating and reclaiming descriptors introduces significant space and time overhead.


title: S-Caffe: Co-designing MPI Runtimes and Caffe for Scalable Deep Learning on Modern GPU Clusters

authors:
Ammar Ahmad Awan
Khaled Hamidouche
Jahanzeb Maqbool Hashmi
Dhabaleswar K. Panda

abstract: Availability of large data sets like ImageNet and massively parallel computation support in modern HPC devices like NVIDIA GPUs have fueled a renewed interest in Deep Learning (DL) algorithms. This has triggered the development of DL frameworks like Caffe, Torch, TensorFlow, and CNTK. However, most DL frameworks have been limited to a single node. In order to scale out DL frameworks and bring HPC capabilities to the DL arena, we propose, S-Caffe; a scalable and distributed Caffe adaptation for modern multi-GPU clusters. With an in-depth analysis of new requirements brought forward by the DL frameworks and limitations of current communication runtimes, we present a co-design of the Caffe framework and the MVAPICH2-GDR MPI runtime. Using the co-design methodology, we modify Caffe's workflow to maximize the overlap of computation and communication with multi-stage data propagation and gradient aggregation schemes. We bring DL-Awareness to the MPI runtime by proposing a hierarchical reduction design that benefits from CUDA-Aware features and provides up to a massive 133x speedup over OpenMPI and 2.6x speedup over MVAPICH2 for 160 GPUs. S-Caffe successfully scales up to 160 K-80 GPUs for GoogLeNet (ImageNet) with a speedup of 2.5x over 32 GPUs. To the best of our knowledge, this is the first framework that scales up to 160 GPUs. Furthermore, even for single node training, S-Caffe shows an improvement of 14\% and 9\% over Nvidia's optimized Caffe for 8 and 16 GPUs, respectively. In addition, S-Caffe achieves up to 1395 samples per second for the AlexNet model, which is comparable to the performance of Microsoft CNTK.


title: POSTER: An Architecture and Programming Model for Accelerating Parallel Commutative Computations via Privatization

authors:
Vignesh Balaji
Dhruva Tirumala
Brandon Lucia

abstract: Synchronization and data movement are the key impediments to an efficient parallel execution. To ensure that data shared by multiple threads remain consistent, the programmer must use synchronization (e.g., mutex locks) to serialize threads' accesses to data. This limits parallelism because it forces threads to sequentially access shared resources. Additionally, systems use cache coherence to ensure that processors always operate on the most up-to-date version of a value even in the presence of private caches. Coherence protocol implementations cause processors to serialize their accesses to shared data, further limiting parallelism and performance.


title: KiWi: A Key-Value Map for Scalable Real-Time Analytics

authors:
Dmitry Basin
Edward Bortnikov
Anastasia Braginsky
Guy Golan-Gueta
Eshcar Hillel
Idit Keidar
Moshe Sulamy

abstract: Modern big data processing platforms employ huge in-memory key-value (KV) maps. Their applications simultaneously drive high-rate data ingestion and large-scale analytics. These two scenarios expect KV-map implementations that scale well with both real-time updates and large atomic scans triggered by range queries.


title: Synchronized-by-Default Concurrency for Shared-Memory Systems

authors:
Martin Bättig
Thomas R. Gross

abstract: We explore a programming approach for concurrency that synchronizes all accesses to shared memory by default. Synchronization takes place by ensuring that all program code runs inside atomic sections even if the program code has external side effects. Threads are mapped to atomic sections that a programmer must explicitly split to increase concurrency.


title: Groute: An Asynchronous Multi-GPU Programming Model for Irregular Computations

authors:
Tal Ben-Nun
Michael Sutton
Sreepathi Pai
Keshav Pingali

abstract: Nodes with multiple GPUs are becoming the platform of choice for high-performance computing. However, most applications are written using bulk-synchronous programming models, which may not be optimal for irregular algorithms that benefit from low-latency, asynchronous communication. This paper proposes constructs for asynchronous multi-GPU programming, and describes their implementation in a thin runtime environment called Groute. Groute also implements common collective operations and distributed work-lists, enabling the development of irregular applications without substantial programming effort. We demonstrate that this approach achieves state-of-the-art performance and exhibits strong scaling for a suite of irregular applications on 8-GPU and heterogeneous systems, yielding over 7x speedup for some algorithms.


title: POSTER: HythTM: Extending the Applicability of Intel TSX Hardware Transactional Support

authors:
Arnamoy Bhattacharyya
Mike Dai Wang
Mihai Burcea
Yi Ding
Allen Deng
Sai Varikooty
Shafaaf Hossain
Cristiana Amza

abstract: In this work, we introduce and experimentally evaluate a new hybrid software-hardware Transactional Memory prototype based on Intel's Haswell TSX architecture. Our prototype extends the applicability of the existing hardware support for TM by interposing a hybrid fall-back layer before the sequential, big-lock fall-back path, used by standard TSX-supported solutions in order to guarantee progress. In our experimental evaluation we use SynQuake, a realistic game benchmark modeled after Quake. Our results show that our hybrid transactional system,which we call HythTM, is able to reduce the number of transactions that go to the sequential software layer, hence avoiding hardware transaction aborts and loss of parallelism. HythTM optimizes application throughput and scalability up to 5.05x, when compared to the hardware TM with sequential fall-back path.


title: An Efficient Abortable-locking Protocol for Multi-level NUMA Systems

authors:
Milind Chabbi
Abdelhalim Amer
Shasha Wen
Xu Liu

abstract: The popularity of Non-Uniform Memory Access (NUMA) architectures has led to numerous locality-preserving hierarchical lock designs, such as HCLH, HMCS, and cohort locks. Locality-preserving locks trade fairness for higher throughput. Hence, some instances of acquisitions can incur long latencies, which may be intolerable for certain applications. Few locks admit a waiting thread to abandon its protocol on a timeout. State-of-the-art abortable locks are not fully locality aware, introduce high overheads, and unsuitable for frequent aborts. Enhancing locality-aware locks with lightweight timeout capability is critical for their adoption. In this paper, we design and evaluate the HMCS-T lock, a Hierarchical MCS (HMCS) lock variant that admits a timeout. HMCS-T maintains the locality benefits of HMCS while ensuring aborts to be lightweight. HMCS-T offers the progress guarantee missing in most abortable queuing locks. Our evaluations show that HMCS-T offers the timeout feature at a moderate overhead over its HMCS analog. HMCS-T, used in an MPI runtime lock, mitigated the poor scalability of an MPI+OpenMP BFS code and resulted in 4.3x superior scaling.


title: EffiSha: A Software Framework for Enabling Effficient Preemptive Scheduling of GPU

authors:
Guoyang Chen
Yue Zhao
Xipeng Shen
Huiyang Zhou

abstract: Modern GPUs are broadly adopted in many multitasking environments, including data centers and smartphones. However, the current support for the scheduling of multiple GPU kernels (from different applications) is limited, forming a major barrier for GPU to meet many practical needs. This work for the first time demonstrates that on existing GPUs, efficient preemptive scheduling of GPU kernels is possible even without special hardware support. Specifically, it presents EffiSha, a pure software framework that enables preemptive scheduling of GPU kernels with very low overhead. The enabled preemptive scheduler offers flexible support of kernels of different priorities, and demonstrates significant potential for reducing the average turnaround time and improving the system overall throughput of programs that time share a modern GPU.


title: POSTER: Provably Efficient Scheduling of Cache-Oblivious Wavefront Algorithms

authors:
Rezaul Chowdhury
Pramod Ganapathi
Yuan Tang
Jesmin Jahan Tithi

abstract: Standard cache-oblivious recursive divide-and-conquer algorithms for evaluating dynamic programming recurrences have optimal serial cache complexity but often have lower parallelism compared with iterative wavefront algorithms due to artificial dependencies among subtasks. Very recently cache-oblivious recursive wavefront (COW) algorithms have been introduced which do not have any artificial dependencies. Though COW algorithms are based on fork-join primitives, they extensively use atomic operations, and as a result, performance guarantees provided by state-of-the-art schedulers for programs with fork-join primitives do not apply.


title: POSTER: State Teleportation via Hardware Transactional Memory

authors:
Nachshon Cohen
Maurice Herlihy
Erez Petrank
Elias Wald

abstract: State teleportation is a new technique for exploiting hardware transactional memory (HTM) to improve existing synchronization and memory management schemes for highly-concurrent data structures. When applied to fine-grained locking, a thread holding the lock for a node launches a hardware transaction that traverses multiple successor nodes, acquires the lock for the last node reached, and releases the lock on the starting node, skipping lock acquisitions for intermediate nodes. When applied to lock-free data structures, a thread visiting a node protected by a hazard pointer launches a hardware transaction that traverses multiple successor nodes, and publishes the hazard pointer only for the last node reached, skipping the memory barriers needed to publish intermediate hazard pointers. Experimental results show that these applications of state teleportation can substantially increase the performance of both lock-based and lock-free data structures.


title: Layout Lock: A Scalable Locking Paradigm for Concurrent Data Layout Modifications

authors:
Nachshon Cohen
Arie Tal
Erez Petrank

abstract: Data-structures can benefit from dynamic data layout modifications when the size or the shape of the data structure changes during the execution, or when different phases in the program execute different workloads. However, in a modern multi-core environment, layout modifications involve costly synchronization overhead. In this paper we propose a novel layout lock that incurs a negligible overhead for reads and a small overhead for updates of the data structure. We then demonstrate the benefits of layout changes and also the advantages of the layout lock as its supporting synchronization mechanism for two data structures. In particular, we propose a concurrent binary search tree, and a concurrent array set, that benefit from concurrent layout modifications using the proposed layout lock. Experience demonstrates performance advantages and integration simplicity.


title: POSTER: IOGP: An Incremental Online Graph Partitioning for Large-Scale Distributed Graph Databases

authors:
Dong Dai
Wei Zhang
Yong Chen

abstract: Large-scale graphs are becoming critical in various domains such as social network, scientific application, knowledge discovery, and even system software, etc. Many of those use cases require large-scale high-performance graph databases, which are designed for serving continuous updates from the clients, and at the same time, answering complex queries towards the current graph in an on-line manner. Those operations in graph databases, also referred as OLTP (online transaction processing) operations, need specific design and implementation in graph partitioning algorithms. In this study, we designed an incremental online graph partitioning (IOGP), optimized for OLTP workloads. It is designed to achieve better locality, generate balanced partitions, and increase the parallelism for accessing hotspots of the graph. Our evaluation results on both real world and synthetic graphs in both simulation and real system confirm a better performance on graph queries (as much as 2X) with small overheads during graph insertion (less than 10%).


title: POSTER: Distributed Control: The Benefits of Eliminating Global Synchronization via Effective Scheduling

authors:
Jesun Sahariar Firoz
Thejaka Amila Kanewala
Marcin Zalewski
Martina Barnas
Andrew Lumsdaine

abstract: In distributed computing, parallel overheads such as \emph{synchronization overhead} may hinder performance. We introduce the idea of \emph{Distributed Control} (DC) where global synchronization is reduced to \emph{termination detection} and each worker proceeds ahead optimistically, based on the local knowledge of the global computation. To avoid "wasted'' work, \DC relies on local work prioritization. However, the work order obtained by local prioritization is susceptible to interference from the runtime. We show that employing effective scheduling policies and optimizations in the runtime, in conjunction with eliminating global barriers, improves performance in two graph applications: single-source shortest paths and connected components.


title: Combining SIMD and Many/Multi-core Parallelism for Finite State Machines with Enumerative Speculation

authors:
Peng Jiang
Gagan Agrawal

abstract: Finite State Machine (FSM) is the key kernel behind many popular applications, including regular expression matching, text tokenization, and Huffman decoding. Parallelizing FSMs is extremely difficult because of the strong dependencies and unpredictable memory accesses. Previous efforts have largely focused on multi-core parallelization, and used different approaches, including {\em speculative} and {\em enumerative} execution, both of which have been effective but also have limitations. With increasing width and improving flexibility in SIMD instruction sets, this paper focuses on combining SIMD and multi/many-core parallelism for FSMs. We have developed a novel strategy, called {\em enumerative speculation}. Instead of speculating on a single state as in speculative execution or enumerating all possible states as in enumerative execution, our strategy speculates transitions from several possible states, reducing the prediction overheads of speculation approach and the large amount of redundant work in the enumerative approach. A simple lookback approach produces a set of guessed states to achieve high speculation success rates in our enumerative speculation. We evaluate our method with four popular FSM applications: Huffman decoding, regular expression matching, HTML tokenization, and Div7. We obtain up to 2.5x speedup using SIMD on one core and up to 95x combining SIMD with 60 cores of an Intel Xeon Phi. On a single core, we outperform the best single-state speculative execution version by an average of 1.6x, and in combining SIMD and many-core parallelism, outperform enumerative execution by an average of 2x.


title: Grammar-aware Parallelization for Scalable XPath Querying

authors:
Lin Jiang
Zhijia Zhao

abstract: Semi-structured data emerge in many domains, especially in web analytics and business intelligence. However, querying such data is inherently sequential due to the nested structure of input data. Existing solutions pessimistically enumerate all execution paths to circumvent dependencies, yielding sub-optimal performance and limited scalability.


title: POSTER: MAPA: An Automatic Memory Access Pattern Analyzer for GPU Applications

authors:
Gangwon Jo
Jaehoon Jung
Jiyoung Park
Jaejin Lee

abstract: Various existing optimization and memory consistency management techniques for GPU applications rely on memory access patterns of kernels. However, they suffer from poor practicality because they require explicit user interventions to extract kernel memory access patterns. This paper proposes an automatic memory-access-pattern analysis framework called MAPA. MAPA is based on a source-level analysis technique derived from traditional symbolic analyses and a run-time pattern selection technique. The experimental results show that MAPA properly analyzes 116 real-world OpenCL kernels from Rodinia and Parboil.


title: Thread Data Sharing in Cache: Theory and Measurement

authors:
Hao Luo
Pengcheng Li
Chen Ding

abstract: On modern multi-core processors, independent workloads often interfere with each other by competing for shared cache space. However, for multi-threaded workloads, where a single copy of data can be accessed by multiple threads, the threads can cooperatively share cache. Because data sharing consolidates the collective working set of threads, the effective size of shared cache becomes larger than it would have been when data are not shared. This paper presents a new theory of data sharing. It includes (1) a new metric called the shared footprint to mathematically compute the amount of data shared by any group of threads in any size cache, and (2) a linear-time algorithm to measure shared footprint by scanning the memory trace of a multi-threaded program. The paper presents the practical implementation and evaluates the new theory using 14 PARSEC and SPEC OMP benchmarks, including an example use of shared footprint in program optimization.


title: A Multicore Path to Connectomics-on-Demand

authors:
Alexander Matveev
Yaron Meirovitch
Hayk Saribekyan
Wiktor Jakubiuk
Tim Kaler
Gergely Ódor
David M. Budden
Aleksandar Zlateski
Nir Shavit

abstract: The current design trend in large scale machine learning is to use distributed clusters of CPUs and GPUs with MapReduce-style programming. Some have been led to believe that this type of horizontal scaling can reduce or even eliminate the need for traditional algorithm development, careful parallelization, and performance engineering. This paper is a case study showing the contrary: that the benefits of algorithms, parallelization, and performance engineering, can sometimes be so vast that it is possible to solve "cluster-scale" problems on a single commodity multicore machine.


title: POSTER: Automated Load Balancer Selection Based on Application Characteristics

authors:
Harshitha Menon
Kavitha Chandrasekar
Laxmikant V. Kalé

abstract: Many HPC applications require dynamic load balancing to achieve high performance and system utilization. Different applications have different characteristics and hence require different load balancing strategies. Invocation of a suboptimal load balancing strategy can lead to inefficient execution. We propose Meta-Balancer, a framework to automatically decide the best load balancing strategy. It employs randomized decision forests, a machine learning method, to learn a model for choosing the best load balancing strategy for an application represented by a set of features that capture the application characteristics.


title: Function Call Re-Vectorization

authors:
Rubens E. A. Moreira
Caroline Collange
Fernando Magno Quintão Pereira

abstract: Programming languages such as C for CUDA, OpenCL or ISPC have contributed to increase the programmability of SIMD accelerators and graphics processing units. However, these languages still lack the flexibility offered by low-level SIMD programming on explicit vectors. To close this expressiveness gap while preserving performance, this paper introduces the notion of \ourinvention{} (CREV). CREV allows changing the dimension of vectorization during the execution of a kernel, exposing it as a nested parallel kernel call. CREV affords programmability close to dynamic parallelism, a feature that allows the invocation of kernels from inside kernels, but at much lower cost. In this paper, we present a formal semantics of CREV, and an implementation of it on the ISPC compiler. We have used CREV to implement some classic algorithms, including string matching, depth first search and Bellman-Ford, with minimum effort. These algorithms, once compiled by ISPC to Intel-based vector instructions, are as fast as state-of-the-art implementations, yet much simpler. Thus, CREV gives developers the elegance of dynamic programming, and the performance of explicit SIMD programming.


title: POSTER: A GPU-Friendly Skiplist Algorithm

authors:
Nurit Moscovici
Nachshon Cohen
Erez Petrank

abstract: We propose a design for a fine-grained lock-based skiplist optimized for Graphics Processing Units (GPUs). While GPUs are often used to accelerate streaming parallel computations, it remains a significant challenge to efficiently offload concurrent computations with more complicated data-irregular access and fine-grained synchronization. Natural building blocks for such computations would be concurrent data structures, such as skiplists, which are widely used in general purpose computations. Our design utilizes array-based nodes which are accessed and updated by warp-cooperative functions, thus taking advantage of the fact that GPUs are most efficient when memory accesses are coalesced and execution divergence is minimized. The proposed design has been implemented, and measurements demonstrate improved performance of up to 2.6x over skiplist designs for the GPU existing today.


title: Checking Concurrent Data Structures Under the C/C++11 Memory Model

authors:
Peizhao Ou
Brian Demsky

abstract: Concurrent data structures often provide better performance on multi-core processors but are significantly more difficult to design and test than their sequential counterparts. The C/C++11 standard introduced a weak memory model with support for low-level atomic operations such as compare and swap (CAS). While low-level atomic operations can significantly improve the performance of concurrent data structures, they introduce non-intuitive behaviors that can increase the difficulty of developing code.


title: Simple, Accurate, Analytical Time Modeling and Optimal Tile Size Selection for GPGPU Stencils

authors:
Nirmal Prajapati
Waruna Ranasinghe
Sanjay V. Rajopadhye
Rumen Andonov
Hristo N. Djidjev
Tobias Grosser

abstract: Stencil computations are an important class of compute and data intensive programs that occur widely in scientific and engineeringapplications. A number of tools use sophisticated tiling, parallelization, and memory mapping strategies, and generate code that relies on vendor-supplied compilers. This code has a number of parameters, such as tile sizes, that are then tuned via empirical exploration.


title: Optimizing the Four-Index Integral Transform Using Data Movement Lower Bounds Analysis

authors:
Samyam Rajbhandari
Fabrice Rastello
Karol Kowalski
Sriram Krishnamoorthy
P. Sadayappan

abstract: The four-index integral transform is a fundamental and computationally demanding calculation used in many computational chemistry suites such as NWChem. It transforms a four-dimensional tensor from one basis to another. This transformation is most efficiently implemented as a sequence of four tensor contractions that each contract a four- dimensional tensor with a two-dimensional transformation matrix. Differing degrees of permutation symmetry in the intermediate and final tensors in the sequence of contractions cause intermediate tensors to be much larger than the final tensor and limit the number of electronic states in the modeled systems.


title: POSTER: Poor Man's URCU

authors:
Pedro Ramalhete
Andreia Correia

abstract: RCU is, among other things, a well known mechanism for memory reclamation that is meant to be used in languages without an automatic Garbage Collector, unfortunately, it requires operating system support, which is currently provided only in Linux. An alternative is to use Userspace RCU (URCU) which has two variants that can be deployed on other operating systems, named \emph{Memory Barrier} and \emph{Bullet Proof}.


title: POSTER: A Wait-Free Queue with Wait-Free Memory Reclamation

abstract: Queues are a widely deployed data structure. They are used extensively in many multi threaded applications, or as a communication mechanism between threads or processes. We propose a new linearizable multi-producer-multi-consumer queue we named Turn queue, with wait-free progress bounded by the number of threads, and with wait-free bounded memory reclamation. Its main characteristics are: a simple algorithm that does no memory allocation apart from creating the node that is placed in the queue, a new wait-free consensus algorithm using only the atomic instruction compare-and-swap (CAS), and is easy to plugin with other algorithms for either enqueue or dequeue methods.


title: Exploiting Vector and Multicore Parallelism for Recursive, Data- and Task-Parallel Programs

authors:
Bin Ren
Sriram Krishnamoorthy
Kunal Agrawal
Milind Kulkarni

abstract: 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.


title: Model-based Iterative CT Image Reconstruction on GPUs

authors:
Amit Sabne
Xiao Wang
Sherman J. Kisner
Charles A. Bouman
Anand Raghunathan
Samuel P. Midkiff

abstract: Computed Tomography (CT) Image Reconstruction is an important technique used in a variety of domains, including medical imaging, electron microscopy, non-destructive testing and transportation security. Model-based Iterative Reconstruction (MBIR) using Iterative Coordinate Descent (ICD) is a CT algorithm that produces state-of-the-art results in terms of image quality. However, MBIR is highly computationally intensive and challenging to parallelize, and has traditionally been viewed as impractical in applications where reconstruction time is critical. We present the first GPU-based algorithm for ICD-based MBIR. The algorithm leverages the recently-proposed concept of SuperVoxels, and efficiently exploits the three levels of parallelism available in MBIR to better utilize the GPU hardware resources. We also explore data layout transformations to obtain more coalesced accesses and several GPU-specific optimizations for MBIR that boost performance. Across a suite of 3200 test cases, our GPU implementation obtains a geometric mean speedup of 4.43X over a state-of-the-art multi-core implementation on a 16-core iso-power CPU.


title: Noise Injection Techniques to Expose Subtle and Unintended Message Races

authors:
Kento Sato
Dong H. Ahn
Ignacio Laguna
Gregory L. Lee
Martin Schulz
Christopher M. Chambreau

abstract: Debugging intermittently occurring bugs within MPI applications is challenging, and message races, a condition in which two or more sends race to match with a receive, are one of the common root causes. Many debugging tools have been proposed to help programmers resolve them, but their runtime interference perturbs the timing such that subtle races often cannot be reproduced with debugging tools. We present novel noise injection techniques to expose message races even under a tool's control. We first formalize this race problem in the context of non-deterministic parallel applications and use this analysis to determine an effective noise-injection strategy to uncover them. We codified these techniques in NINJA (Noise INJection Agent) that exposes these races without modification to the application. Our evaluations on synthetic cases as well as a real-world bug in Hypre-2.10.1 show that NINJA significantly helps expose races.


title: Tapir: Embedding Fork-Join Parallelism into LLVM's Intermediate Representation

authors:
Tao B. Schardl
William S. Moses
Charles E. Leiserson

abstract: This paper explores how fork-join parallelism, as supported by concurrency platforms such as Cilk and OpenMP, can be embedded into a compiler's intermediate representation (IR). Mainstream compilers typically treat parallel linguistic constructs as syntactic sugar for function calls into a parallel runtime. These calls prevent the compiler from performing optimizations across parallel control constructs. Remedying this situation is generally thought to require an extensive reworking of compiler analyses and code transformations to handle parallel semantics.


title: Isoefficiency in Practice: Configuring and Understanding the Performance of Task-based Applications

authors:
Sergei Shudler
Alexandru Calotoiu
Torsten Hoefler
Felix Wolf

abstract: Task-based programming offers an elegant way to express units of computation and the dependencies among them, making it easier to distribute the computational load evenly across multiple cores. However, this separation of problem decomposition and parallelism requires a sufficiently large input problem to achieve satisfactory efficiency on a given number of cores. Unfortunately, finding a good match between input size and core count usually requires significant experimentation, which is expensive and sometimes even impractical. In this paper, we propose an automated empirical method for finding the isoefficiency function of a task-based program, binding efficiency, core count, and the input size in one analytical expression. This allows the latter two to be adjusted according to given (realistic) efficiency objectives. Moreover, we not only find (i) the actual isoefficiency function but also (ii) the function one would yield if the program execution was free of resource contention and (iii) an upper bound that could only be reached if the program was able to maintain its average parallelism throughout its execution. The difference between the three helps to explain low efficiency, and in particular, it helps to differentiate between resource contention and structural conflicts related to task dependencies or scheduling. The insights gained can be used to co-design programs and shared system resources.


title: It's Time for a New Old Language

abstract: The most popular programming language in computer science has no compiler or interpreter. Its definition is not written down in any one place. It has changed a lot over the decades, and those changes have introduced ambiguities and inconsistencies. Today, dozens of variations are in use, and its complexity has reached the point where it needs to be re-explained, at least in part, every time it is used. Much effort has been spent in hand-translating between this language and other languages that do have compilers. The language is quite amenable to parallel computation, but this fact has gone unexploited.


title: Using Butterfly-Patterned Partial Sums to Draw from Discrete Distributions

authors:
Guy L. Steele Jr.
Jean-Baptiste Tristan

abstract: We describe a SIMD technique for drawing values from multiple discrete distributions, such as sampling from the random variables of a mixture model, that avoids computing a complete table of partial sums of the relative probabilities. A table of alternate ("butterfly-patterned") form is faster to compute, making better use of coalesced memory accesses; from this table, complete partial sums are computed on the fly during a binary search. Measurements using CUDA 7.5 on an NVIDIA Titan Black GPU show that this technique makes an entire machine-learning application that uses a Latent Dirichlet Allocation topic model with 1024 topics about about 13% faster (when using single-precision floating-point data) or about 35% faster (when using double-precision floating-point data) than doing a straightforward matrix transposition after using coalesced accesses.


title: POSTER: STAR (Space-Time Adaptive and Reductive) Algorithms for Real-World Space-Time Optimality

authors:
Yuan Tang
Ronghui You

abstract: It's important to hit a space-time balance for a real-world algorithm to achieve high performance on modern shared-memory multi-core or many-core systems. However, a large class of dynamic programs with more than $O(1)$ dependency achieve optimality either in space or time, but not both. In the literature, the problem is known as the fundamental space-time tradeoff. By exploiting properly on the runtime system, we show that our STAR (Space-Time Adaptive and Reductive) technique can help these dynamic programs to achieve sublinear parallel time bounds while still maintaining work-, space-, and cache-optimality in a processor- and cache-oblivious fashion.


title: Self-Checkpoint: An In-Memory Checkpoint Method Using Less Space and Its Practice on Fault-Tolerant HPL

authors:
Xiongchao Tang
Jidong Zhai
Bowen Yu
Wenguang Chen
Weimin Zheng

abstract: Fault tolerance is increasingly important in high performance computing due to the substantial growth of system scale and decreasing system reliability. In-memory/diskless checkpoint has gained extensive attention as a solution to avoid the IO bottleneck of traditional disk-based checkpoint methods. However, applications using previous in-memory checkpoint suffer from little available memory space. To provide high reliability, previous in-memory checkpoint methods either need to keep two copies of checkpoints to tolerate failures while updating old checkpoints or trade performance for space by flushing in-memory checkpoints into disk.


title: Processor-Oblivious Record and Replay

authors:
Robert Utterback
Kunal Agrawal
I-Ting Angelina Lee
Milind Kulkarni

abstract: 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.


title: SC-Haskell: Sequential Consistency in Languages That Minimize Mutable Shared Heap

authors:
Michael Vollmer
Ryan G. Scott
Madanlal Musuvathi
Ryan R. Newton

abstract: A core, but often neglected, aspect of a programming language design is its memory (consistency) model. Sequential consistency~(SC) is the most intuitive memory model for programmers as it guarantees sequential composition of instructions and provides a simple abstraction of shared memory as a single global store with atomic read and writes. Unfortunately, SC is widely considered to be impractical due to its associated performance overheads.


title: Eunomia: Scaling Concurrent Search Trees under Contention Using HTM

authors:
Xin Wang
Weihua Zhang
Zhaoguo Wang
Ziyun Wei
Haibo Chen
Wenyun Zhao

abstract: While hardware transactional memory (HTM) has recently been adopted to construct efficient concurrent search tree structures, such designs fail to deliver scalable performance under contention. In this paper, we first conduct a detailed analysis on an HTM-based concurrent B+Tree, which uncovers several reasons for excessive HTM aborts induced by both false and true conflicts under contention. Based on the analysis, we advocate Eunomia, a design pattern for search trees which contains several principles to reduce HTM aborts, including splitting HTM regions with version-based concurrency control to reduce HTM working sets, partitioned data layout to reduce false conflicts, proactively detecting and avoiding true conflicts, and adaptive concurrency control. To validate their effectiveness, we apply such designs to construct a scalable concurrent B+Tree using HTM. Evaluation using key-value store benchmarks on a 20-core HTM-capable multi-core machine shows that Eunomia leads to 5X-11X speedup under high contention, while incurring small overhead under low contention.


title: Silent Data Corruption Resilient Two-sided Matrix Factorizations

authors:
Panruo Wu
Nathan DeBardeleben
Qiang Guan
Sean Blanchard
Jieyang Chen
Dingwen Tao
Xin Liang
Kaiming Ouyang
Zizhong Chen

abstract: This paper presents an algorithm based fault tolerance method to harden three two-sided matrix factorizations against soft errors: reduction to Hessenberg form, tridiagonal form, and bidiagonal form. These two sided factorizations are usually the prerequisites to computing eigenvalues/eigenvectors and singular value decomposition. Algorithm based fault tolerance has been shown to work on three main one-sided matrix factorizations: LU, Cholesky, and QR, but extending it to cover two sided factorizations is non-trivial because there are no obvious \textit{offline, problem} specific maintenance of checksums. We thus develop an \textit{online, algorithm} specific checksum scheme and show how to systematically adapt the two sided factorization algorithms used in LAPACK and ScaLAPACK packages to introduce the algorithm based fault tolerance.


title: POSTER: Recovering Performance for Vector-based Machine Learning on Managed Runtime

authors:
Mingyu Wu
Haibing Guan
Binyu Zang
Haibo Chen

abstract: No abstract available.


title: Pagoda: Fine-Grained GPU Resource Virtualization for Narrow Tasks

authors:
Tsung Tai Yeh
Amit Sabne
Putt Sakdhnagool
Rudolf Eigenmann
Timothy G. Rogers

abstract: Massively multithreaded GPUs achieve high throughput by running thousands of threads in parallel. To fully utilize the hardware, workloads spawn work to the GPU in bulk by launching large tasks, where each task is a kernel that contains thousands of threads that occupy the entire GPU.


title: POSTER: On the Problem of Consistency Exceptions in the Context of Strong Memory Models

authors:
Minjia Zhang
Swarnendu Biswas
Michael D. Bond

abstract: This work considers the problem of availability for memory models that throw consistency exceptions. We define a new memory model called RIx based on isolation of synchronization-free regions and a new approach called Avalon that provides RIx. Our evaluation shows that Avalon and RIx substantially reduce consistency exceptions, by 1-3 orders of magnitude and sometimes eliminate them completely. Furthermore, our exploration provides new, compelling points in the performance-availability tradeoff space.


title: Understanding the GPU Microarchitecture to Achieve Bare-Metal Performance Tuning

authors:
Xiuxia Zhang
Guangming Tan
Shuangbai Xue
Jiajia Li
Keren Zhou
Mingyu Chen

abstract: In this paper, we present a methodology to understand GPU microarchitectural features and improve performance for compute-intensive kernels. The methodology relies on a reverse engineering approach to crack the GPU ISA encodings in order to build a GPU assembler. An assembly microbenchmark suite correlates microarchitectural features with their performance factors to uncover instruction-level and memory hierarchy preferences. We use SGEMM as a running example to show the ways to achieve bare-metal performance tuning. The performance boost is achieved by tuning FFMA throughput by activating dual-issue, eliminating register bank conflicts, adding non-FFMA instructions with little penalty, and choosing proper width of global/shared load instructions. On NVIDIA Kepler K20m, we develop a faster SGEMM with 3.1Tflop/s performance and 88% efficiency; the performance is 15% higher than cuBLAS7.0. Applying these optimizations to convolution, the implementation gains 39%-62% performance improvement compared with cuDNN4.0. The toolchain is an attempt to automatically crack different GPU ISA encodings and build an assembler adaptively for the purpose of performance enhancements to applications on GPUs.


title: POSTER: An Infrastructure for HPC Knowledge Sharing and Reuse

authors:
Yue Zhao
Chunhua Liao
Xipeng Shen

abstract: This paper presents a prototype infrastructure for addressing the barriers for effective accumulation, sharing, and reuse of the various types of knowledge for high performance parallel computing.


title: Griffin: uniting CPU and GPU in information retrieval systems for intra-query parallelism

authors:
Yang Liu
Jianguo Wang
Steven Swanson

abstract: Interactive information retrieval services, such as enterprise search and document search, must provide relevant results with consistent, low response times in the face of rapidly growing data sets and query loads. These growing demands have led researchers to consider a wide range of optimizations to reduce response latency, including query processing parallelization and acceleration with co-processors such as GPUs. However, previous work runs queries either on GPU or CPU, ignoring the fact that the best processor for a given query depends on the query's characteristics, which may change as the processing proceeds.


title: Performance challenges in modular parallel programs

authors:
Umut A. Acar
Vitaly Aksenov
Arthur Charguéraud
Mike Rainey

abstract: Over the past decade, many programming languages and systems for parallel-computing have been developed, including Cilk, Fork/Join Java, Habanero Java, Parallel Haskell, Parallel ML, and X10. Although these systems raise the level of abstraction at which parallel code are written, performance continues to require the programmer to perform extensive optimizations and tuning, often by taking various architectural details into account. One such key optimization is granularity control, which requires the programmer to determine when and how parallel tasks should be sequentialized.


title: Harnessing epoch-based reclamation for efficient range queries

authors:
Maya Arbel-Raviv
Trevor Brown

abstract: Concurrent sets with range query operations are highly desirable in applications such as in-memory databases. However, few set implementations offer range queries. Known techniques for augmenting data structures with range queries (or operations that can be used to build range queries) have numerous problems that limit their usefulness. For example, they impose high overhead or rely heavily on garbage collection. In this work, we show how to augment data structures with highly efficient range queries, without relying on garbage collection. We identify a property of epoch-based memory reclamation algorithms that makes them ideal for implementing range queries, and produce three algorithms, which use locks, transactional memory and lock-free techniques, respectively. Our algorithms are applicable to more data structures than previous work, and are shown to be highly efficient on a large scale Intel system.


title: Reducing the burden of parallel loop schedulers for many-core processors

authors:
Mahwish Arif
Hans Vandierendonck

abstract: This work proposes a low-overhead half-barrier pattern to schedule fine-grain parallel loops and considers its integration in the Intel OpenMP and Cilkplus schedulers. Experimental evaluation demonstrates that the scheduling overhead of our techniques is 43% lower than Intel OpenMP and 12.1x lower than Cilk. We observe 22% speedup on 48 threads, with a peak of 2.8x speedup.


title: Graph partitioning applied to DAG scheduling to reduce NUMA effects

authors:
Isaac Sánchez Barrera
Marc Casas
Miquel Moretó
Eduard Ayguadé
Jesús Labarta
Mateo Valero

abstract: The complexity of shared memory systems is becoming more relevant as the number of memory domains increases, with different access latencies and bandwidth rates depending on the proximity between the cores and the devices containing the data. In this context, techniques to manage and mitigate non-uniform memory access (NUMA) effects consist in migrating threads, memory pages or both and are typically applied by the system software.


title: Juggler: a dependence-aware task-based execution framework for GPUs

authors:
Mehmet E. Belviranli
Seyong Lee
Jeffrey S. Vetter
Laxmi N. Bhuyan

abstract: Scientific applications with single instruction, multiple data (SIMD) computations show considerable performance improvements when run on today's graphics processing units (GPUs). However, the existence of data dependences across thread blocks may significantly impact the speedup by requiring global synchronization across multiprocessors (SMs) inside the GPU. To efficiently run applications with interblock data dependences, we need fine-granular task-based execution models that will treat SMs inside a GPU as stand-alone parallel processing units. Such a scheme will enable faster execution by utilizing all internal computation elements inside the GPU and eliminating unnecessary waits during device-wide global barriers.


title: Featherlight on-the-fly false-sharing detection

authors:
Milind Chabbi
Shasha Wen
Xu Liu

abstract: Shared-memory parallel programs routinely suffer from false sharing---a performance degradation caused by different threads accessing different variables that reside on the same CPU cacheline and at least one variable is modified. State-of-the-art tools detect false sharing via a heavyweight process of logging memory accesses and feeding the ensuing access traces to an offline cache simulator. We have developed Feather, a lightweight, on-the-fly false-sharing detection tool. Feather achieves low overhead by exploiting two hardware features ubiquitous in commodity CPUs: the performance monitoring units (PMU) and debug registers. Additionally, Feather is a first-of-its-kind tool to detect false sharing in multi-process applications that use shared memory. Feather allowed us to scale false-sharing detection to myriad codes. Feather detected several false-sharing cases in important multi-core and multi-process codes including previous PPoPP artifacts. Eliminating false sharing resulted in dramatic (up to 16x) speedups.