Workshop Program

We characterize a general class of algorithms common in machine learning, scientific computing, and signal processing, whose computational dependencies are both sparse, and dynamically defined throughout execution. Existing parallel computing runtimes, like MapReduce and GraphLab, are a poor fit for this class because they assume statically defined dependencies for resource allocation and scheduling decisions. As a result, changing load characteristics and straggling compute units degrade performance significantly. However, we show that the sparsity of computational dependencies and these algorithms’ natural error tolerance can be exploited to implement a flexible execution model with large efficiency gains, using two simple primitives: selective push-pull and statistical barriers. With reconstruction for compressive time-lapse MRI as a motivating application, we deploy a large Orthogonal Matching Pursuit (OMP) computation on Amazon’s EC2 cluster to demonstrate a 19x speedup over current static execution models.

Constructing parallel software is, in essence, the process of associating ‘work’ with computational units. The definition of work is dependent upon the model of parallelism used, and our choice of model can have profound effects on both programmer productivity and run-time efficiency. Given that the movement of data is responsible for the majority of parallelism overhead, and accessing data is responsible for the majority of parallelism errors, data items should be the basis for describing parallel work. As data items rarely exist in isolation and are instead parts of larger collections, we argue that subsets of collections should be the basic unit of parallelism. This requires a semantically rich method of referring to these sub-collections. Sub-collections are not guaranteed to be disjoint, and so an efficient run-time mechanism is required to maintain correctness. With a focus on complex systems, we present some of the challenges inherent in this approach and describe how we are extending Synchronization via Scheduling (SvS) and other techniques to overcome these difficulties. We discuss our experiences incorporating these techniques into a modern video game engine used in an in-development title.

The rise of multi- and many-core architectures also gave birth to a plethora of new parallel programming models. Among these, the open industry standard OpenCL addresses this heterogeneity of programming environments by providing a unified programming framework. The price to pay, however, is that OpenCL requires additional low-level boilerplate code, when compared to vendor-specific solutions, even if only simple operations are to be performed. Also, the unified programming framework does not automatically provide any guarantees on performance portability of a particular implementation. Thus, device-specific compute kernels are still required for obtaining good performance across different hardware architectures.

We address both, the issue of programmability and portable performance, in this work: On the one hand, a high-level programming interface for linear algebra routines allows for the convenient specification of the operations of interest without having to go into the details of the underlying hardware. On the other hand, we discuss the underlying generator for device-specific OpenCL kernels at runtime, which is supplemented by an auto-tuning framework for portable performance as well as with work partitioning and task scheduling for multiple devices.

Our benchmark results show portable performance across hardware from major vendors. In all cases, at least 75 percent of the respective vendor-tuned library was obtained, while in some cases we even outperformed the reference. We further demonstrate the convenient and ecient use of our high-level interface in a multi-device setting with good scalability.

We present approximate data structures with construction algorithms that execute without synchronization. The data races present in these algorithms may cause them to drop inserted or appended elements. Nevertheless, the algorithms 1) do not crash and 2) may produce a data structure that is accurate enough for its clients to use successfully. We advocate an approach in which the approximate data structures are composed of basic tree and array building blocks with associated synchronization-free construction algorithms. This approach enables developers to reuse the construction algorithms, which have been engineered to execute successfully in parallel contexts despite the presence of data races, without having to understand the details of why they execute successfully.

We evaluate the end-to-end accuracy and performance consequences of our approach by building a space-subdivision tree for the Barnes-Hut N-body simulation out of our presented tree and array building blocks. The resulting approximate data structure construction algorithm eliminates synchronization overhead and anomalies such as excessive serialization and deadlock. The algorithm exhibits good performance (running 14 times faster on 16 cores than the sequential version) and good accuracy (the accuracy loss is four orders of magnitude less than the accuracy gain associated with increasing the accuracy of the Barnes-Hut center of mass approximation by 20%).

Parallelism in the cloud comes in two basic flavors: low-latency queries and batch processing. These flavors are both fundamental but quite different in their needs.  By separating the two we can build simpler systems that support both well. In particular, we cover the design of a new OS for cloud computing that brings these concepts all the way down to the metal, where the job shifts from virtualizing resources for typically local human users to more direct support for these two classes of parallelism under the remote control of a cluster-wide scheduler.

Future computers of all sizes, from cell phones to supercomputers, share challenges of power and programmability to realize their potential. The end of Dennard scaling has made all computing power limited, so that performance is determined by energy efficiency. With improvements in process technology offering little increase in efficiency, innovations in architecture and circuits are required to maintain the expected performance scaling. The large-scale parallelism and deep storage hierarchy of future machines poses programming challenges. This talk will discuss these challenges in more detail and introduce some of the technologies being developed to address them.

With the ubiquitous availability of parallel architectures, the burden falls on programmers’ shoulders to write correct parallel programs that have high performance and portability across different systems. One of the major issues that complicates this task is the intricacies involved with the underlying memory consistency models. Sequential Consistency (SC) is the simplest and most intuitive memory model. Therefore, programmers usually assume SC for writing parallel programs. However, various concurrency bugs can lead to violations of SC. These subtle bugs make the program difficult to reason about and virtually always lead to incorrectness. This paper provides the first (to the best of our knowledge) comprehensive characteristics study of SC violation bugs that appear in real world codebases.

We have carefully examined pattern, manifestation, effect, and fix strategy of 20 SC violation bugs. These bugs have been selected from randomly chosen 127 concurrency bugs from a variety of open source programs and libraries (e.g. Mozilla, Apache, MySQL, Gcc, Cilk, Java, and Splash2). Our study reveals interesting findings and provides useful guidance for future research in this area.

This paper presents property-driven partial logging, a novel information partition scheme that takes into account load balancing and shared variable properties to optimize the replay of Java concurrency bugs through partial log combination. Preliminary evaluation with standard benchmarks and a real-world application provides initial evidence of the feasibility of our approach.

Our accelerating computational demand and the rise of multicore hardware have made parallel programs, especially shared-memory multithreaded programs, increasingly pervasive and critical. Yet, these programs remain extremely difficult to write, test, analyze, debug, and verify. Conventional wisdom has attributed these difficulties to nondeterminism, and researchers have recently dedicated much effort to bringing determinism into multithreading. In this paper, we argue that determinism is not as useful as commonly perceived: it is neither sufficient nor necessary for reliability.We present our view on why multithreaded programs are difficult to get right, describe a promising approach we call stable multithreading to dramatically improve reliability, and summarize our last four years’ research on building and applying stable multithreading systems.

Non-volatile storage connected as memory (NVRAM) offers promising opportunities for simplifying and accelerating manipulation of persistent data. Load and store latency is potentially comparable to that of ordinary memory. The challenge is to ensure that the persisted data remains consistent if a failure occurs during execution, especially in a multithreaded programming environment. In this paper, we provide semantics for identifying a globally consistent state for a lock-based multithreaded program. We show how to conveniently ensure that programs are returned to such a globally consistent state after a crash. We discuss challenges and opportunities along the way, and explain why adding durability to transactional programs may be less expensive.