title: The pilot library for novice MPI programmers

authors:
John D. Carter
William B. Gardner
Gary Gréwal

abstract: The Pilot library is a new method for programming MPI-enabled clusters in C, targeted at novice parallel programmers. Formal elements from Communicating Sequential Processes (CSP) are used to realize a process/channel model of parallel computation that reduces opportunities for deadlock and other communication errors. This simple model, plus an application programming inter-face (API) styled after C's formatted I/O, are designed to make the library easy to learn. The Pilot library exists as a thin layer on top of any standard Message Passing Interface (MPI) implementation, preserving MPI's portability and efficiency, with little per-formance overhead arising as result of Pilot's additional features.


venue: ppopp

title: Scaling LAPACK panel operations using parallel cache assignment

authors:
Anthony M. Castaldo
R. Clint Whaley

abstract: In LAPACK many matrix operations are cast as block algorithms which iteratively process a panel using an unblocked algorithm and then update a remainder matrix using the high performance Level 3 BLAS. The Level~3 BLAS have excellent weak scaling, but panel processing tends to be bus bound, and thus scales with bus speed rather than the number of processors (p). Amdahl's law therefore ensures that as p grows, the panel computation will become the dominant cost of these LAPACK routines. Our contribution is a novel parallel cache assignment approach which we show scales well with p. We apply this general approach to the QR and LU panel factorizations on two commodity 8-core platforms with very different cache structures, and demonstrate superlinear panel factorization speedups on both machines. Other approaches to this problem demand complicated reformulations of the computational approach, new kernels to be tuned, new mathematics, an inflation of the high-order flop count, and do not perform as well. By demonstrating a straight-forward alternative that avoids all of these contortions and scales with p, we address a critical stumbling block for dense linear algebra in the age of massive parallelism.


title: Supporting lock-free composition of concurrent data objects

authors:
Daniel Cederman
Philippas Tsigas

abstract: Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks and convoying and, more importantly, being highly concurrent. But they share a common disadvantage in that the operations they provide are difficult to compose into larger atomic operations while still guaranteeing lock-freedom. We present a lock-free methodology for composing highly concurrent linearizable objects together by unifying their linearization points. This makes it possible to relatively easily introduce atomic lock-free move operations to a wide range of concurrent objects. Experimental evaluation has shown that the operations originally supported by the data objects keep their performance behavior under our methodology.


title: New abstractions for effective performance analysis of STM programs

abstract: We present the design and implementation of a dynamic conflict graph annotated with fine grain transaction characteristics and show that this is important information for effective performance analysis of a software transactional memory (STM) program. We show how to implement the necessary support in a compiler and an STM with minimal perturbation of the original behavior of the application.


title: Applying the concurrent collections programming model to asynchronous parallel dense linear algebra

authors:
Aparna Chandramowlishwaran
Kathleen Knobe
Richard W. Vuduc

abstract: This poster is a case study on the application of a novel programming model, called Concurrent Collections (CnC), to the implementation of an asynchronous-parallel algorithm for computing the Cholesky factorization of dense matrices. In CnC, the programmer expresses her computation in terms of application-specific operations, partially-ordered by semantic scheduling constraints. We demonstrate the performance potential of CnC in this poster, by showing that our Cholesky implementation nearly matches or exceeds competing vendor-tuned codes and alternative programming models. We conclude that the CnC model is well-suited for expressing asynchronous-parallel algorithms on emerging multicore systems.


title: Model-driven autotuning of sparse matrix-vector multiply on GPUs

authors:
JeeWhan Choi
Amik Singh
Richard W. Vuduc

abstract: We present a performance model-driven framework for automated performance tuning (autotuning) of sparse matrix-vector multiply (SpMV) on systems accelerated by graphics processing units (GPU). Our study consists of two parts.


title: GAMBIT: effective unit testing for concurrency libraries

authors:
Katherine E. Coons
Sebastian Burckhardt
Madanlal Musuvathi

abstract: As concurrent programming becomes prevalent, software providers are investing in concurrency libraries to improve programmer productivity. Concurrency libraries improve productivity by hiding error-prone, low-level synchronization from programmers and providing higher-level concurrent abstractions. Testing such libraries is difficult, however, because concurrency failures often manifest only under particular scheduling circumstances. Current best testing practices are often inadequate: heuristic-guided fuzzing is not systematic, systematic schedule enumeration does not find bugs quickly, and stress testing is neither systematic nor fast.


title: NOrec: streamlining STM by abolishing ownership records

authors:
Luke Dalessandro
Michael F. Spear
Michael L. Scott

abstract: Drawing inspiration from several previous projects, we present an ownership-record-free software transactional memory (STM) system that combines extremely low overhead with unusually clean semantics. While unlikely to scale to hundreds of active threads, this "NOrec" system offers many appealing features: very low fast-path latency--as low as any system we know of that admits concurrent updates; publication and privatization safety; livelock freedom; a small, constant amount of global metadata, and full compatibility with existing data structure layouts; no false conflicts due to hash collisions; compatibility with both managed and unmanaged languages, and both static and dynamic compilation; and easy acccommodation of closed nesting, inevitable (irrevocable) transactions, and starvation avoidance mechanisms. To the best of our knowledge, no extant STM system combines this set of features.


title: Symbolic prefetching in transactional distributed shared memory

authors:
Alokika Dash
Brian Demsky

abstract: We present a static analysis for the automatic generation of symbolic prefetches in a transactional distributed shared memory. A symbolic prefetch specifies the first object to be prefetched followed by a list of field offsets or array indices that define a path through the heap. We also provide an object caching framework and language extensions to support our approach. To our knowledge, this is the first prefetching approach that can prefetch objects whose addresses have not been computed or predicted.


title: SLAW: a scalable locality-aware adaptive work-stealing scheduler for multi-core systems

authors:
Yi Guo
Yisheng Zhao
Vincent Cavé
Vivek Sarkar

abstract: This poster introduces SLAW, a Scalable Locality-aware Adaptive Work-stealing scheduler. The SLAW features an adaptive task scheduling algorithm combined with a locality-aware scheduling framework.


title: Scalable communication protocols for dynamic sparse data exchange

authors:
Torsten Hoefler
Christian Siebert
Andrew Lumsdaine

abstract: Many large-scale parallel programs follow a bulk synchronous parallel (BSP) structure with distinct computation and communication phases. Although the communication phase in such programs may involve all (or large numbers) of the participating processes, the actual communication operations are usually sparse in nature. As a result, communication phases are typically expressed explicitly using point-to-point communication operations or collective operations. We define the dynamic sparse data-exchange (DSDE) problem and derive bounds in the well known LogGP model. While current approaches work well with static applications, they run into limitations as modern applications grow in scale, and as the problems that are being solved become increasingly irregular and dynamic.


title: Application heartbeats for software performance and health

authors:
Henry Hoffmann
Jonathan Eastep
Marco D. Santambrogio
Jason E. Miller
Anant Agarwal

abstract: Adaptive, or self-aware, computing has been proposed to help application programmers confront the growing complexity of multicore software development. However, existing approaches to adaptive systems are largely ad hoc and often do not manage to incorporate the true performance goals of the applications they are designed to support. This paper presents an enabling technology for adaptive computing systems: Application Heartbeats. The Application Heartbeats framework provides a simple, standard programming interface that applications can use to indicate their performance and system software (and hardware) can use to query an application's performance. The PARSEC benchmark suite is instrumented with Application Heartbeats to show the broad applicability of the interface and an external resource scheduler demonstrates the use of the interface by assigning cores to an application to maintain a designated performance goal.


title: Load balancing on speed

authors:
Steven Hofmeyr
Costin Iancu
Filip Blagojevic

abstract: To fully exploit multicore processors, applications are expected to provide a large degree of thread-level parallelism. While adequate for low core counts and their typical workloads, the current load balancing support in operating systems may not be able to achieve efficient hardware utilization for parallel workloads. Balancing run queue length globally ignores the needs of parallel applications where threads are required to make equal progress. In this paper we present a load balancing technique designed specifically for parallel applications running on multicore systems. Instead of balancing run queue length, our algorithm balances the time a thread has executed on ``faster'' and ``slower'' cores. We provide a user level implementation of speed balancing on UMA and NUMA multi-socket architectures running Linux and discuss behavior across a variety of workloads, usage scenarios and programming models. Our results indicate that speed balancing when compared to the native Linux load balancing improves performance and provides good performance isolation in all cases considered. Speed balancing is also able to provide comparable or better performance than DWRR, a fair multi-processor scheduling implementation inside the Linux kernel. Furthermore, parallel application performance is often determined by the implementation of synchronization operations and speed balancing alleviates the need for tuning the implementations of such primitives.


title: Data transformations enabling loop vectorization on multithreaded data parallel architectures

authors:
Byunghyun Jang
Perhaad Mistry
Dana Schaa
Rodrigo Dominguez
David R. Kaeli

abstract: Loop vectorization, a key feature exploited to obtain high performance on Single Instruction Multiple Data (SIMD) vector architectures, is significantly hindered by irregular memory access patterns in the data stream. This paper describes data transformations that allow us to vectorize loops targeting massively multithreaded data parallel architectures. We present a mathematical model that captures loop-based memory access patterns and computes the most appropriate data transformations in order to enable vectorization. Our experimental results show that the proposed data transformations can significantly increase the number of loops that can be vectorized and enhance the data-level parallelism of applications. Our results also show that the overhead associated with our data transformations can be easily amortized as the size of the input data set increases. For the set of high performance benchmark kernels studied, we achieve consistent and significant performance improvements (up to 11.4X) by applying vectorization using our data transformation approach.


title: Featherweight X10: a core calculus for async-finish parallelism

authors:
Jonathan K. Lee
Jens Palsberg

abstract: We present a core calculus with two of X10's key constructs for parallelism, namely async and finish. Our calculus forms a convenient basis for type systems and static analyses for languages with async-finish parallelism, and for tractable proofs of correctness. For example, we give a short proof of the deadlock-freedom theorem of Saraswat and Jagadeesan. Our main contribution is a type system that solves the open problem of context-sensitive may-happen-in-parallel analysis for languages with async-finish parallelism. We prove the correctness of our type system and we report experimental results of performing type inference on 13,000 lines of X10 code. Our analysis runs in polynomial time, takes a total of 28 seconds on our benchmarks, and produces a low number of false positives, which suggests that our analysis is a good basis for other analyses such as race detectors.


title: A symbolic verifier for CUDA programs

authors:
Guodong Li
Ganesh Gopalakrishnan
Robert M. Kirby
Daniel J. Quinlan

abstract: We present a preliminary automated verifier based on mechanical decision procedures which is able to prove functional correctness of CUDA programs and guarantee to detect bugs such as race conditions. We also employ a symbolic partial order reduction (POR) technique to mitigate the interleaving explosion problem.


title: Improving parallelism and locality with asynchronous algorithms

authors:
Lixia Liu
Zhiyuan Li

abstract: As multicore chips become the main building blocks for high performance computers, many numerical applications face a performance impediment due to the limited hardware capacity to move data between the CPU and the off-chip memory. This is especially true for large computing problems solved by iterative algorithms because of the large data set typically used. Loop tiling, also known as loop blocking, was shown previously to be an effective way to enhance data locality, and hence to reduce the memory bandwidth pressure, for a class of iterative algorithms executed on a single processor. Unfortunately, the tiled programs suffer from reduced parallelism because only the loop iterations within a single tile can be easily parallelized. In this work, we propose to use the asynchronous model to enable effective loop tiling such that both parallelism and locality can be attained simultaneously. Asynchronous algorithms were previously proposed to reduce the communication cost and synchronization overhead between processors. Our new discovery is that carefully controlled asynchrony and loop tiling can significantly improve the performance of parallel iterative algorithms on multicore processors due to simultaneously attained data locality and loop-level parallelism. We present supporting evidence from experiments with three well-known numerical kernels.


title: Towards scalable and transparent parallelization of multiplayer games using transactional memory support

authors:
Daniel Lupei
Bogdan Simion
Don Pinto
Matthew Misler
Mihai Burcea
William Krick
Cristiana Amza

abstract: This work addresses the problem of parallelizing multiplayer games using software Transactional Memory (STM) support. Using a realistic high impact application, we show that STM provides not only ease of programming, but also better performance than that achievable with state-of-the-art lock-based programming.


title: Scheduling support for transactional memory contention management

authors:
Walther Maldonado
Patrick Marlier
Pascal Felber
Adi Suissa
Danny Hendler
Alexandra Fedorova
Julia L. Lawall
Gilles Muller

abstract: Transactional Memory (TM) is considered as one of the most promising paradigms for developing concurrent applications. TM has been shown to scale well on >multiple cores when the data access pattern behaves "well," i.e., when few conflicts are induced. In contrast, data patterns with frequent write sharing, with long transactions, or when many threads contend for a smaller number of cores, result in numerous conflicts. Until recently, TM implementations had little control of transactional threads, which remained under the supervision of the kernel's transaction-ignorant scheduler. Conflicts are thus traditionally resolved by consulting an STM-level contention manager. Consequently, the contention managers of these "conventional" TM implementations suffer from a lack of precision and often fail to ensure reasonable performance in high-contention workloads.


title: Compiler aided selective lock assignment for improving the performance of software transactional memory

authors:
Sandya Mannarswamy
Dhruva R. Chakrabarti
Kaushik Rajan
Sujoy Saraswati

abstract: Atomic sections have been recently introduced as a language construct to improve the programmability of concurrent software. They simplify programming by not requiring the explicit specification of locks for shared data. Typically atomic sections are supported in software either through the use of optimistic concurrency by using transactional memory or through the use of pessimistic concurrency using compiler-assigned locks. As a software transactional memory (STM) system does not take advantage of the specific memory access patterns of an application it often suffers from false conflicts and high validation overheads. On the other hand, the compiler usually ends up assigning coarse grain locks as it relies on whole program points-to analysis which is conservative by nature. This adversely affects performance by limiting concurrency. In order to mitigate the disadvantages associated with STM's lock assignment scheme, we propose a hybrid approach which combines STM's lock assignment with a compiler aided selective lock assignment scheme (referred to as SCLA-STM). SCLA-STM overcomes the inefficiencies associated with a purely compile-time lock assignment approach by (i) using the underlying STM for shared variables where only a conservative analysis is possible by the compiler (e.g., in the presence of may-alias points to information) and (ii) being selective about the shared data chosen for the compiler-aided lock assignment. We describe our prototype SCLA-STM scheme implemented in the hp-ux IA-64 C/C++ compiler, using TL2 as our STM implementation. We show that SCLA-STM improves application performance for certain STAMP benchmarks from 1.68% to 37.13%.


title: Effective communication and computation overlap with hybrid MPI/SMPSs

authors:
Vladimir Marjanovic
Jesús Labarta
Eduard Ayguadé
Mateo Valero

abstract: Communication overhead is one of the dominant factors affecting performance in high-performance computing systems. To reduce the negative impact of communication, programmers overlap communication and computation by using asynchronous communication primitives. This increases code complexity, requiring more development effort and making less readable programs. This paper presents the hybrid use of MPI and SMPSs (SMP superscalar, a task-based shared-memory programming model) that allows the programmer to easily introduce the asynchrony necessary to overlap communication and computation. We demonstrate the hybrid use of MPI/SMPSs with the high-performance LINPACK benchmark (HPL), and compare it to the pure MPI implementation, which uses the look-ahead technique to overlap communication and computation. The hybrid MPI/SMPSs version significantly improves the performance of the pure MPI version, getting close to the asymptotic performance at medium problem sizes and still getting significant benefits at small/large problem sizes.


title: Structure-driven optimizations for amorphous data-parallel programs

authors:
Mario Méndez-Lojo
Donald Nguyen
Dimitrios Prountzos
Xin Sui
Muhammad Amber Hassaan
Milind Kulkarni
Martin Burtscher
Keshav Pingali

abstract: Irregular algorithms are organized around pointer-based data structures such as graphs and trees, and they are ubiquitous in applications. Recent work by the Galois project has provided a systematic approach for parallelizing irregular applications based on the idea of optimistic or speculative execution of programs. However, the overhead of optimistic parallel execution can be substantial. In this paper, we show that many irregular algorithms have structure that can be exploited and present three key optimizations that take advantage of algorithmic structure to reduce speculative overheads. We describe the implementation of these optimizations in the Galois system and present experimental results to demonstrate their benefits. To the best of our knowledge, this is the first system to exploit algorithmic structure to optimize the execution of irregular programs.


title: Intra-application shared cache partitioning for multithreaded applications

authors:
Sai Prashanth Muralidhara
Mahmut T. Kandemir
Padma Raghavan

abstract: In this paper, we address the problem of partitioning a shared cache when the executing threads belong to the same application.


title: KRASH: reproducible CPU load generation on many cores machines

authors:
Swann Perarnau
Guillaume Huard

abstract: In this article we present KRASH, a tool for reproducible generation of system-level CPU load. This tool is intended for use in shared memory machines equipped with multiple CPU cores which are usually exploited concurrently by several users. The objective of KRASH is to enable parallel application developers to validate their resources use strategies on a partially loaded machine by replaying an observed load in concurrence with their application. To reach this objective, we present a method for CPU load generation which behaves as realistically as possible: the resulting load is similar to the load that would be produced by concurrent processes run by other users. Nevertheless, contrary to a simple run of a CPU-intensive application, KRASH is not sensitive to system scheduling decisions. The main benefit brought by KRASH is this reproducibility: no matter how many processes are present in the system the load generated by our tool strictly respects a given load profile. To our knowledge, KRASH is the only tool that implements the generation of a dynamic load profile (a load varying with time). When used to generate a constant load, KRASH result is among the most realistic ones. Furthermore, KRASH provides more flexibility than other tools.


title: Modeling transactional memory workload performance

authors:
Donald E. Porter
Emmett Witchel

abstract: Transactional memory promises to make parallel programming easier than with fine-grained locking, while performing just as well. This performance claim is not always borne out because an application may violate a common-case assumption of the TM designer or because of external system effects. In order to help programmers assess the suitability of their code for transactional memory, this work introduces a formal model of transactional memory as well as a tool, called Syncchar. Syncchar can predict the speedup of a conversion from locks to transactions within 25% for the STAMP benchmarks. Because getting good performance from transactions is more difficult than commonly appreciated, developers need tools to tune transactional performance.


title: Thread to strand binding of parallel network applications in massive multi-threaded systems

authors:
Petar Radojkovic
Vladimir Cakarevic
Javier Verdú
Alex Pajuelo
Francisco J. Cazorla
Mario Nemirovsky
Mateo Valero

abstract: In processors with several levels of hardware resource sharing,like CMPs in which each core is an SMT, the scheduling process becomes more complex than in processors with a single level of resource sharing, such as pure-SMT or pure-CMP processors. Once the operating system selects the set of applications to simultaneously schedule on the processor (workload), each application/thread must be assigned to one of the hardware contexts(strands). We call this last scheduling step the Thread to Strand Binding or TSB. In this paper, we show that the TSB impact on the performance of processors with several levels of shared resources is high. We measure a variation of up to 59% between different TSBs of real multithreaded network applications running on the UltraSPARC T2 processor which has three levels of resource sharing. In our view, this problem is going to be more acute in future multithreaded architectures comprising more cores, more contexts per core, and more levels of resource sharing.


title: The LOFAR correlator: implementation and performance analysis

authors:
John W. Romein
P. Chris Broekema
Jan David Mol
Rob van Nieuwpoort

abstract: LOFAR is the first of a new generation of radio telescopes.Rather than using expensive dishes, it forms a distributed sensor network that combines the signals from many thousands of simple antennas. Its revolutionary design allows observations in a frequency range that has hardly been studied before.


title: Is transactional programming actually easier?

authors:
Christopher J. Rossbach
Owen S. Hofmann
Emmett Witchel

abstract: Chip multi-processors (CMPs) have become ubiquitous, while tools that ease concurrent programming have not. The promise of increased performance for all applications through ever more parallel hardware requires good tools for concurrent programming, especially for average programmers. Transactional memory (TM) has enjoyed recent interest as a tool that can help programmers program concurrently.


title: CUDAlign: using GPU to accelerate the comparison of megabase genomic sequences

authors:
Edans Flavius de Oliveira Sandes
Alba Cristina Magalhaes Alves de Melo

abstract: Biological sequence comparison is a very important operation in Bioinformatics. Even though there do exist exact methods to compare biological sequences, these methods are often neglected due to their quadratic time and space complexity. In order to accelerate these methods, many GPU algorithms were proposed in the literature. Nevertheless, all of them restrict the size of the smallest sequence in such a way that Megabase genome comparison is prevented. In this paper, we propose and evaluate CUDAlign, a GPU algorithm that is able to compare Megabase biological sequences with an exact Smith-Waterman affine gap variant. CUDAlign was implemented in CUDA and tested in two GPU boards, separately. For real sequences whose size range from 1MBP (Megabase Pairs) to 47MBP, a close to uniform GCUPS (Giga Cells Updates per Second) was obtained, showing the potential scalability of our approach. Also, CUDAlign was able to compare the human chromosome 21 and the chimpanzee chromosome 22. This operation took 21 hours on GeForce GTX 280, resulting in a peak performance of 20.375 GCUPS. As far as we know, this is the first time such huge chromosomes are compared with an exact method.


title: Composable thread coloring

authors:
Dean F. Sutherland
William L. Scherlis

abstract: This paper introduces the language-independent concept of ``thread usage policy.'' Many multi-threaded software systems contain policies that regulate associations among threads, executable code, and potentially shared state. A system, for example, may constrain which threads are permitted to execute particular code segments, usually as a means to constrain those threads from accessing or writing particular elements of state. These policies ensure properties such as state confinement or reader/writer constraints, often without recourse to locking or transaction discipline.


title: Analyzing lock contention in multithreaded applications

authors:
Nathan R. Tallent
John M. Mellor-Crummey
Allan Porterfield

abstract: Many programs exploit shared-memory parallelism using multithreading. Threaded codes typically use locks to coordinate access to shared data. In many cases, contention for locks reduces parallel efficiency and hurts scalability. Being able to quantify and attribute lock contention is important for understanding where a multithreaded program needs improvement.


title: Extreme scale computing: challenges and opportunities

authors:
Josep Torrellas
Bill Gropp
Jaime H. Moreno
Kunle Olukotun
Vivek Sarkar

abstract: No abstract available.


title: Lazy binary-splitting: a run-time adaptive work-stealing scheduler

authors:
Alexandros Tzannes
George C. Caragea
Rajeev Barua
Uzi Vishkin

abstract: We present Lazy Binary Splitting (LBS), a user-level scheduler of nested parallelism for shared-memory multiprocessors that builds on existing Eager Binary Splitting work-stealing (EBS) implemented in Intel's Threading Building Blocks (TBB), but improves performance and ease-of-programming. In its simplest form (SP), EBS requires manual tuning by repeatedly running the application under carefully controlled conditions to determine a stop-splitting-threshold (sst)for every do-all loop in the code. This threshold limits the parallelism and prevents excessive overheads for fine-grain parallelism. Besides being tedious, this tuning also over-fits the code to some particular dataset, platform and calling context of the do-all loop, resulting in poor performance portability for the code. LBS overcomes both the performance portability and ease-of-programming pitfalls of a manually fixed threshold by adapting dynamically to run-time conditions without requiring tuning.


title: Using data structure knowledge for efficient lock generation and strong atomicity

authors:
Gautam Upadhyaya
Samuel P. Midkiff
Vijay S. Pai

abstract: To achieve high-performance on multicore systems, sharedmemory parallel languages must efficiently implement atomic operations. The commonly used and studied paradigms for atomicity are fine-grained locking, which is both difficult to program and error-prone; optimistic software transactions, which require substantial overhead to detect and recover from atomicity violations; and compiler-generation of locks from programmer-specified atomic sections, which leads to serialization whenever imprecise pointer analysis suggests the mere possibility of a conflicting operation. This paper presents a new strategy for compiler-generated locking that uses data structure knowledge to facilitate more precise alias and lock generation analyses and reduce unnecessary serialization. Implementing and evaluating these ideas in the Java language shows that the new strategy achieves eight-thread speedups of 0.83 to 5.9 for the five STAMP benchmarks studied, outperforming software transactions on all but one benchmark, and nearly matching programmer-specified fine-grained locks on all but one benchmark. The results also indicate that compiler knowledge of data structures improves the effectiveness of compiler analysis, boosting eight-thread performance by up to 300%. Further, the new analysis allows for software support of strong atomicity with less than 1% overhead for two benchmarks and less than 20% for three others.The strategy also nearly matches the performance of programmer-specified fine-grained locks for the SPECjbb2000 benchmark, which has traditionally not been amenable to static analyses.


title: An optimizing compiler for GPGPU programs with input-data sharing

authors:
Yi Yang
Ping Xiang
Jingfei Kong
Huiyang Zhou

abstract: Developing high performance GPGPU programs is challenging for application developers since the performance is dependent upon how well the code leverages the hardware features of specific graphics processors. To solve this problem and relieve application developers of low-level hardware-specific optimizations, we introduce a novel compiler to optimize GPGPU programs. Our compiler takes a naive GPU kernel function, which is functionally correct but without any consideration for performance optimization. The compiler then analyzes the code, identifies memory access patterns, and generates optimized code. The proposed compiler optimizations target at one category of scientific and media processing algorithms, which has the characteristics of input-data sharing when computing neighboring output pixels/elements. Many commonly used algorithms, such as matrix multiplication, convolution, etc., share such characteristics. For these algorithms, novel approaches are proposed to enforce memory coalescing and achieve effective data reuse. Data prefetching and hardware-specific tuning are also performed automatically with our compiler framework. The experimental results based on a set of applications show that our compiler achieves very high performance, either superior or very close to the highly fine-tuned library, NVIDIA CUBLAS 2.1.


title: PHANTOM: predicting performance of parallel applications on large-scale parallel machines using a single node

authors:
Jidong Zhai
Wenguang Chen
Weimin Zheng

abstract: For designers of large-scale parallel computers, it is greatly desired that performance of parallel applications can be predicted at the design phase. However, this is difficult because the execution time of parallel applications is determined by several factors, including sequential computation time in each process, communication time and their convolution. Despite previous efforts, it remains an open problem to estimate sequential computation time in each process accurately and efficiently for large-scale parallel applications on non-existing target machines.


title: Fast tridiagonal solvers on the GPU

authors:
Yao Zhang
Jonathan Cohen
John D. Owens

abstract: We study the performance of three parallel algorithms and their hybrid variants for solving tridiagonal linear systems on a GPU: cyclic reduction (CR), parallel cyclic reduction (PCR) and recursive doubling (RD). We develop an approach to measure, analyze, and optimize the performance of GPU programs in terms of memory access, computation, and control overhead. We find that CR enjoys linear algorithm complexity but suffers from more algorithmic steps and bank conflicts, while PCR and RD have fewer algorithmic steps but do more work each step. To combine the benefits of the basic algorithms, we propose hybrid CR+PCR and CR+RD algorithms, which improve the performance of PCR, RD and CR by 21%, 31% and 61% respectively. Our GPU solvers achieve up to a 28x speedup over a sequential LAPACK solver, and a 12x speedup over a multi-threaded CPU solver.


title: Continuous speculative program parallelization in software

authors:
Chao Zhang
Chen Ding
Xiaoming Gu
Kirk Kelsey
Tongxin Bai
Xiaobing Feng

abstract: This paper addresses the problem of extracting coarse-grained parallelism from large sequential code. It builds on BOP, a system for software speculative parallelization. BOP lets a user to mark possibly parallel regions (PPR) in a program and at run-time speculatively executes PPR instances using Unix processes. This short paper presents a new run-time support called continuous speculation, which fully utilizes available parallelism to tolerate differences in PPR task size and processor speed.


title: Does cache sharing on modern CMP matter to the performance of contemporary multithreaded programs?

authors:
Eddy Z. Zhang
Yunlian Jiang
Xipeng Shen

abstract: Most modern Chip Multiprocessors (CMP) feature shared cache on chip. For multithreaded applications, the sharing reduces communication latency among co-running threads, but also results in cache contention.


title: Debugging programs that use atomic blocks and transactional memory

authors:
Ferad Zyulkyarov
Tim Harris
Osman S. Unsal
Adrián Cristal
Mateo Valero

abstract: With the emergence of research prototypes, programming using atomic blocks and transactional memory (TM) is becoming more attractive. This paper describes our experience building and using a debugger for programs written with these abstractions. We introduce three approaches: (i) debugging at the level of atomic blocks, where the programmer is shielded from implementation details (such as exactly what kind of TM is used, or indeed whether lock inference is used instead), (ii) debugging at the level of transactions, where conflict rates, read sets, write sets, and other TM internals are visible, and (iii) debug-time transactions, which let the programmer manipulate synchronization from within the debugger - e.g., enlarging the scope of an atomic block to try to identify a bug.


title: Programming the memory hierarchy revisited: supporting irregular parallelism in sequoia

authors:
Michael Bauer
John Clark
Eric Schkufza
Alex Aiken

abstract: We describe two novel constructs for programming parallel machines with multi-level memory hierarchies: call-up, which allows a child task to invoke computation on its parent, and spawn, which spawns a dynamically determined number of parallel children until some termination condition in the parent is met. Together we show that these constructs allow applications with irregular parallelism to be programmed in a straightforward manner, and furthermore these constructs complement and can be combined with constructs for expressing regular parallelism. We have implemented spawn and call-up in Sequoia and we present an experimental evaluation on a number of irregular applications.


title: Automatic safety proofs for asynchronous memory operations

authors:
Matko Botincan
Mike Dodds
Alastair F. Donaldson
Matthew J. Parkinson

abstract: We present a work-in-progress proof system and tool, based on separation logic, for analysing memory safety of multicore programs that use asynchronous memory operations. Categories and Subject Descriptors F.3.1 [Logics and Meanings


title: Copperhead: compiling an embedded data parallel language

authors:
Bryan Catanzaro
Michael Garland
Kurt Keutzer

abstract: Modern parallel microprocessors deliver high performance on applications that expose substantial fine-grained data parallelism. Although data parallelism is widely available in many computations, implementing data parallel algorithms in low-level languages is often an unnecessarily difficult task. The characteristics of parallel microprocessors and the limitations of current programming methodologies motivate our design of Copperhead, a high-level data parallel language embedded in Python. The Copperhead programmer describes parallel computations via composition of familiar data parallel primitives supporting both flat and nested data parallel computation on arrays of data. Copperhead programs are expressed in a subset of the widely used Python programming language and interoperate with standard Python modules, including libraries for numeric computation, data visualization, and analysis. In this paper, we discuss the language, compiler, and runtime features that enable Copperhead to efficiently execute data parallel code. We define the restricted subset of Python which Copperhead supports and introduce the program analysis techniques necessary for compiling Copperhead code into efficient low-level implementations. We also outline the runtime support by which Copperhead programs interoperate with standard Python modules. We demonstrate the effectiveness of our techniques with several examples targeting the CUDA platform for parallel programming on GPUs. Copperhead code is concise, on average requiring 3.6 times fewer lines of code than CUDA, and the compiler generates efficient code, yielding 45-100% of the performance of hand-crafted, well optimized CUDA code.


title: A domain-specific approach to heterogeneous parallelism

authors:
Hassan Chafi
Arvind K. Sujeeth
Kevin J. Brown
HyoukJoong Lee
Anand R. Atreya
Kunle Olukotun

abstract: Exploiting heterogeneous parallel hardware currently requires mapping application code to multiple disparate programming models. Unfortunately, general-purpose programming models available today can yield high performance but are too low-level to be accessible to the average programmer. We propose leveraging domain-specific languages (DSLs) to map high-level application code to heterogeneous devices. To demonstrate the potential of this approach we present OptiML, a DSL for machine learning. OptiML programs are implicitly parallel and can achieve high performance on heterogeneous hardware with no modification required to the source code. For such a DSL-based approach to be tractable at large scales, better tools are required for DSL authors to simplify language creation and parallelization. To address this concern, we introduce Delite, a system designed specifically for DSLs that is both a framework for creating an implicitly parallel DSL as well as a dynamic runtime providing automated targeting to heterogeneous parallel hardware. We show that OptiML running on Delite achieves single-threaded, parallel, and GPU performance superior to explicitly parallelized MATLAB code in nearly all cases.


title: Algorithm-based recovery for HPL

authors:
Teresa Davies
Zizhong Chen
Christer Karlsson
Hui Liu

abstract: When more processors are used for a calculation, the probability that one will fail during the calculation increases. Fault tolerance is a technique for allowing a calculation to survive a failure, and includes recovering lost data. A common method of recovery is diskless checkpointing. However, it has high overhead when a large amount of data is involved, as is the case with matrix operations. A checksum-based method allows fault tolerance of matrix operations with lower overhead. This technique is applicable to the LU decomposition in the benchmark HPL.


title: Two examples of parallel programming without concurrency constructs (PP-CC)

abstract: No abstract available.


title: ULCC: a user-level facility for optimizing shared cache performance on multicores

authors:
Xiaoning Ding
Kaibo Wang
Xiaodong Zhang

abstract: Scientific applications face serious performance challenges on multicore processors, one of which is caused by access contention in last level shared caches from multiple running threads. The contention increases the number of long latency memory accesses, and consequently increases application execution times. Optimizing shared cache performance is critical to reduce significantly execution times of multi-threaded programs on multicores. However, there are two unique problems to be solved before implementing cache optimization techniques on multicores at the user level. First, available cache space for each running thread in a last level cache is difficult to predict due to access contention in the shared space, which makes cache conscious algorithms for single cores ineffective on multicores. Second, at the user level, programmers are not able to allocate cache space at will to running threads in the shared cache, thus data sets with strong locality may not be allocated with sufficient cache space, and cache pollution can easily happen. To address these two critical issues, we have designed ULCC (User Level Cache Control), a software runtime library that enables programmers to explicitly manage and optimize last level cache usage by allocating proper cache space for different data sets of different threads. We have implemented ULCC at the user level based on a page-coloring technique for last level cache usage management. By means of multiple case studies on an Intel multicore processor, we show that with ULCC, scientific applications can achieve significant performance improvements by fully exploiting the benefit of cache optimization algorithms and by partitioning the cache space accordingly to protect frequently reused data sets and to avoid cache pollution. Our experiments with various applications show that ULCC can significantly improve application performance by nearly 40%.


title: SCRATCH: a tool for automatic analysis of dma races

authors:
Alastair F. Donaldson
Daniel Kroening
Philipp Rümmer

abstract: We present the SCRATCH tool, which uses bounded model checking and k-induction to automatically analyse software for multicore processors such as the Cell BE, in order to detect DMA races.


title: Auto-tuning of fast fourier transform on graphics processors

authors:
Yuri Dotsenko
Sara S. Baghsorkhi
Brandon Lloyd
Naga K. Govindaraju

abstract: We present an auto-tuning framework for FFTs on graphics processors (GPUs). Due to complex design of the memory and compute subsystems on GPUs, the performance of FFT kernels over the range of possible input parameters can vary widely. We generate several variants for each component of the FFT kernel that, for different cases, are likely to perform well. Our auto-tuner composes variants to generate kernels and selects the best ones. We present heuristics to prune the search space and profile only a small fraction of all possible kernels. We compose optimized kernels to improve the performance of larger FFT computations. We implement the system using the NVIDIA CUDA API and compare its performance to the state-of-the-art FFT libraries. On a range of NVIDIA GPUs and input sizes, our auto-tuned FFTs outperform the NVIDIA CUFFT 3.0 library by up to 38x and deliver up to 3x higher performance compared to a manually-tuned FFT.


title: SpiceC: scalable parallelism via implicit copying and explicit commit

authors:
Min Feng
Rajiv Gupta
Yi Hu

abstract: In this paper we present an approach to parallel programming called SpiceC. SpiceC simplifies the task of parallel programming through a combination of an intuitive computation model and SpiceC directives. The SpiceC parallel computation model consists of multiple threads where every thread has a private space for data and all threads share data via a shared space. Each thread performs computations using its private space thus offering isolation which allows for speculative computations. SpiceC provides easy to use SpiceC compiler directives using which the programmers can express different forms of parallelism. It allows developers to express high level constraints on data transfers between spaces while the tedious task of generating the code for the data transfers is performed by the compiler. SpiceC also supports data transfers involving dynamic data structures without help from developers. SpiceC allows developers to create clusters of data to enable parallel data transfers. SpiceC programs are portable across modern chip multiprocessor based machines that may or may not support cache coherence. We have developed implementations of SpiceC for shared memory systems with and without cache coherence. We evaluate our implementation using seven benchmarks of which four are parallelized speculatively. Our compiler generated implementations achieve speedups ranging from 2x to 18x on a 24 core system.


title: Lock-free and scalable multi-version software transactional memory

authors:
Sergio Miguel Fernandes
João P. Cachopo

abstract: Software Transactional Memory (STM) was initially proposed as a lock-free mechanism for concurrency control. Early implementations had efficiency limitations, and soon obstruction-free proposals appeared, to tackle this problem, often simplifying STM implementation. Today, most of the modern and top-performing STMs use blocking designs, relying on locks to ensure an atomic commit operation. This approach has revealed better in practice, in part due to its simplicity. Yet, it may have scalability problems when we move into many-core computers, requiring fine-tuning and careful programming to avoid contention. In this paper we present and discuss the modifications we made to a lock-based multi-version STM in Java, to turn it into a lock-free implementation that we have tested to scale at least up to 192 cores, and which provides results that compete with, and sometimes exceed, some of today's top-performing lock-based implementations. The new lock-free commit algorithm allows write transactions to proceed in parallel, by allowing them to run their validation phase independently of each other, and by resorting to helping from threads that would otherwise be waiting to commit, during the write-back phase. We also present a new garbage collection algorithm to dispose of old unused object versions that allows for asynchronous identification of unnecessary versions, which minimizes its interference with the rest of the transactional system.


title: Symbolically modeling concurrent MCAPI executions

authors:
Topher Fischer
Eric Mercer
Neha Rungta

abstract: Improper use of Inter-Process Communication (IPC) within concurrent systems often creates data races which can lead to bugs that are challenging to discover. Techniques that use Satisfiability Modulo Theories (SMT) problems to symbolically model possible executions of concurrent software have recently been proposed for use in the formal verification of software. In this work we describe a new technique for modeling executions of concurrent software that use a message passing API called MCAPI. Our technique uses an execution trace to create an SMT problem that symbolically models all possible concurrent executions and follows the same sequence of conditional branch outcomes as the provided execution trace. We check if there exists a satisfying assignment to the SMT problem with respect to specific safety properties. If such an assignment exists, it provides the conditions that lead to the violation of the property. We show how our method models behaviors of MCAPI applications that are ignored in previously published techniques.


title: Evaluating graph coloring on GPUs

authors:
Andre Vincent Pascal Grosset
Peihong Zhu
Shusen Liu
Suresh Venkatasubramanian
Mary W. Hall

abstract: This paper evaluates features of graph coloring algorithms implemented on graphics processing units (GPUs), comparing coloring heuristics and thread decompositions. As compared to prior work on graph coloring for other parallel architectures, we find that the large number of cores and relatively high global memory bandwidth of a GPU lead to different strategies for the parallel implementation. Specifically, we find that a simple uniform block partitioning is very effective on GPUs and our parallel coloring heuristics lead to the same or fewer colors than prior approaches for distributed-memory cluster architecture. Our algorithm resolves many coloring conflicts across partitioned blocks on the GPU by iterating through the coloring process, before returning to the CPU to resolve remaining conflicts. With this approach we get as few color (if not fewer) than the best sequential graph coloring algorithm and performance is close to the fastest sequential graph coloring algorithms which have poor color quality.


title: Ordered vs. unordered: a comparison of parallelism and work-efficiency in irregular algorithms

authors:
Muhammad Amber Hassaan
Martin Burtscher
Keshav Pingali

abstract: Outside of computational science, most problems are formulated in terms of irregular data structures such as graphs, trees and sets. Unfortunately, we understand relatively little about the structure of parallelism and locality in irregular algorithms. In this paper, we study multiple algorithms for four such problems: discrete-event simulation, single-source shortest path, breadth-first search, and minimal spanning trees. We show that the algorithms can be classified into two categories that we call unordered and ordered, and demonstrate experimentally that there is a trade-off between parallelism and work efficiency: unordered algorithms usually have more parallelism than their ordered counterparts for the same problem, but they may also perform more work. Nevertheless, our experimental results show that unordered algorithms typically lead to more scalable implementations, demonstrating that less work-efficient irregular algorithms may be better for parallel execution.


title: Accelerating CUDA graph algorithms at maximum warp

authors:
Sungpack Hong
Sang Kyun Kim
Tayo Oguntebi
Kunle Olukotun

abstract: Graphs are powerful data representations favored in many computational domains. Modern GPUs have recently shown promising results in accelerating computationally challenging graph problems but their performance suffers heavily when the graph structure is highly irregular, as most real-world graphs tend to be. In this study, we first observe that the poor performance is caused by work imbalance and is an artifact of a discrepancy between the GPU programming model and the underlying GPU architecture. We then propose a novel virtual warp-centric programming method that exposes the traits of underlying GPU architectures to users. Our method significantly improves the performance of applications with heavily imbalanced workloads, and enables trade-offs between workload imbalance and ALU underutilization for fine-tuning the performance. Our evaluation reveals that our method exhibits up to 9x speedup over previous GPU algorithms and 12x over single thread CPU execution on irregular graphs. When properly configured, it also yields up to 30 % improvement over previous GPU algorithms on regular graphs. In addition to performance gains on graph algorithms, our programming method achieves 1.3x to 15.1x speedup on a set of GPU benchmark applications. Our study also confirms that the performance gap between GPUs and other multi-threaded CPU graph implementations is primarily due to the large difference in memory bandwidth.


title: OoOJava: software out-of-order execution

authors:
James Christopher Jenista
Yong Hun Eom
Brian Demsky

abstract: Developing parallel software using current tools can be challenging. Even experts find it difficult to reason about the use of locks and often accidentally introduce race conditions and deadlocks into parallel software. OoOJava is a compiler-assisted approach that leverages developer annotations along with static analysis to provide an easy-to-use deterministic parallel programming model. OoOJava extends Java with a task annotation that instructs the compiler to consider a code block for out-of-order execution. OoOJava executes tasks as soon as their data dependences are resolved and guarantees that the execution of an annotated program preserves the exact semantics of the original sequential program. We have implemented OoOJava and achieved an average speedup of 16.6x on our ten benchmarks.


title: Kremlin: like gprof, but for parallelization

authors:
Donghwan Jeon
Saturnino Garcia
Christopher M. Louie
Sravanthi Kota Venkata
Michael Bedford Taylor

abstract: This paper overviews Kremlin, a software profiling tool designed to assist the parallelization of serial programs. Kremlin accepts a serial source code, profiles it, and provides a list of regions that should be considered in parallelization. Unlike a typical profiler, Kremlin profiles not only work but also parallelism, which is accomplished via a novel technique called hierarchical critical path analysis. Our evaluation demonstrates that Kremlin is highly effective, resulting in a parallelized program whose performance sometimes outperforms, and is mostly comparable to, manual parallelization. At the same time, Kremlin would require that the user parallelize significantly fewer regions of the program. Finally, a user study suggests Kremlin is effective in improving the productivity of programmers.


title: Thread contracts for safe parallelism

authors:
Rajesh K. Karmani
P. Madhusudan
Brandon M. Moore

abstract: We build a framework of thread contracts, called Accord, that allows programmers to annotate their concurrency co-ordination strategies. Accord annotations allow programmers to declaratively specify the parts of memory that a thread may read or write into, and the locks that protect them, reflecting the concurrency co-ordination among threads and the reason why the program is free of data-races. We provide automatic tools to check if the concurrency co-ordination strategy ensures race-freedom, using constraint-solvers (SMT solvers). Hence programmers using Accord can both formally state and prove their co-ordination strategies ensure race freedom. The programmer's implementation of the co-ordination strategy may however be correct or incorrect. We show how the formal Accord contracts allow us to automatically insert runtime assertions that serve to check, during testing, whether the implementation conforms to the contract. Using a large class of data-parallel programs that share memory in intricate ways, we show that natural and simple contracts suffice to document the co-ordination strategy amongst threads, and that the task of showing that the strategy ensures race-freedom can be handled efficiently and automatically by an existing SMT solver (Z3). While co-ordination strategies can be proved race-free in our framework, failure to prove the co-ordination strategy race-free, accompanied by counter-examples produced by the solver, indicates the presence of races. Using such counterexamples, we report hitherto undiscovered data-races that we found in the long-tested applu_l benchmark in the Spec OMP2001 suite.


title: Achieving a single compute device image in OpenCL for multiple GPUs

authors:
Jungwon Kim
Honggyu Kim
Joo Hwan Lee
Jaejin Lee

abstract: In this paper, we propose an OpenCL framework that combines multiple GPUs and treats them as a single compute device. Providing a single virtual compute device image to the user makes an OpenCL application written for a single GPU portable to the platform that has multiple GPU devices. It also makes the application exploit full computing power of the multiple GPU devices and the total amount of GPU memories available in the platform. Our OpenCL framework automatically distributes at run-time the OpenCL kernel written for a single GPU into multiple CUDA kernels that execute on the multiple GPU devices. It applies a run-time memory access range analysis to the kernel by performing a sampling run and identifies an optimal workload distribution for the kernel. To achieve a single compute device image, the runtime maintains virtual device memory that is allocated in the main memory. The OpenCL runtime treats the memory as if it were the memory of a single GPU device and keeps it consistent to the memories of the multiple GPU devices. Our OpenCL-C-to-C translator generates the sampling code from the OpenCL kernel code and OpenCL-C-to-CUDA-C translator generates the CUDA kernel code for the distributed OpenCL kernel. We show the effectiveness of our OpenCL framework by implementing the OpenCL runtime and two source-to-source translators. We evaluate its performance with a system that contains 8 GPUs using 11 OpenCL benchmark applications.


title: Wait-free queues with multiple enqueuers and dequeuers

authors:
Alex Kogan
Erez Petrank

abstract: The queue data structure is fundamental and ubiquitous. Lock-free versions of the queue are well known. However, an important open question is whether practical wait-free queues exist. Until now, only versions with limited concurrency were proposed. In this paper we provide a design for a practical wait-free queue. Our construction is based on the highly efficient lock-free queue of Michael and Scott. To achieve wait-freedom, we employ a priority-based helping scheme in which faster threads help the slower peers to complete their pending operations. We have implemented our scheme on multicore machines and present performance measurements comparing our implementation with that of Michael and Scott in several system configurations.


title: CSX: an extended compression format for spmv on shared memory systems

authors:
Kornilios Kourtis
Vasileios Karakasis
Georgios I. Goumas
Nectarios Koziris

abstract: The Sparse Matrix-Vector multiplication (SpMV) kernel scales poorly on shared memory systems with multiple processing units due to the streaming nature of its data access pattern. Previous research has demonstrated that an effective strategy to improve the kernel's performance is to drastically reduce the data volume involved in the computations. Since the storage formats for sparse matrices include metadata describing the structure of non-zero elements within the matrix, we propose a generalized approach to compress metadata by exploiting substructures within the matrix. We call the proposed storage format Compressed Sparse eXtended (CSX). In our implementation we employ runtime code generation to construct specialized SpMV routines for each matrix. Experimental evaluation on two shared memory systems for 15 sparse matrices demonstrates significant performance gains as the number of participating cores increases. Regarding the cost of CSX construction, we propose several strategies which trade performance for preprocessing cost making CSX applicable both to online and offline preprocessing.


title: Programming the cloud

abstract: Client + cloud computing is a disruptive, new computing platform, combining diverse client devices -- PCs, smartphones, sensors, and single-function and embedded devices -- with the unlimited, on-demand computation and data storage offered by cloud computing services such as Amazon's AWS or Microsoft's Windows Azure. As with every advance in computing, programming is a fundamental challenge as client + cloud computing combines many difficult aspects of software development. Systems built for this world are inherently parallel and distributed, run on unreliable hardware, and must be continually available -- a challenging programming model for even the most skilled programmers. How then do ordinary programmers develop software for the Cloud? This talk presents one answer, Orleans, a software framework for building client + cloud applications. Orleans encourages use of simple concurrency patterns that are easy to understand and implement correctly, building on an actor-like model with declarative specification of persistence, replication, and consistency and using lightweight transactions to support the development of reliable and scalable client + cloud software.


title: Communicating memory transactions

authors:
Mohsen Lesani
Jens Palsberg

abstract: Many concurrent programming models enable both transactional memory and message passing. For such models, researchers have built increasingly efficient implementations and defined reasonable correctness criteria, while it remains an open problem to obtain the best of both worlds. We present a programming model that is the first to have opaque transactions, safe asynchronous message passing, and an efficient implementation. Our semantics uses tentative message passing and keeps track of dependencies to enable undo of message passing in case a transaction aborts. We can program communication idioms such as barrier and rendezvous that do not deadlock when used in an atomic block. Our experiments show that our model adds little overhead to pure transactions, and that it is significantly more efficient than Transactional Events. We use a novel definition of safe message passing that may be of independent interest.


title: Transaction communicators: enabling cooperation among concurrent transactions

authors:
Victor Luchangco
Virendra J. Marathe

abstract: In this paper, we propose to extend transactional memory with transaction communicators, special objects through which concurrent transactions can communicate: changes by one transaction to a communicator can be seen by concurrent transactions before the first transaction commits. Although isolation of transactions is compromised by such communication, we constrain the effects of this compromise by tracking dependencies among transactions, and preventing any transaction from committing unless every transaction whose changes it saw also commits. In particular, mutually dependent transactions must commit or abort together, and transactions that do not communicate remain isolated. To help programmers synchronize accesses to communicators, we also provide special communicator-isolating transactions, which ensure isolation even for accesses to communicators. We propose language features to help programmers express the communicator constructs. We implemented a novel communicators-enabled STM runtime in the Maxine VM. Our preliminary evaluation demonstrates that communicators can be used in diverse settings to improve the performance of transactional programs, and to empower programmers with the ability to safely express within transactions important programming idioms that fundamentally require compromise of transaction isolation (e.g., CSP-style synchronous communication).


title: How's the parallel computing revolution going?

abstract: Two trends changed the computing landscape over the past decade: (1) hardware vendors started delivering chip multiprocessors (CMPs) instead of uniprocessors, and (2) software developers increasingly chose managed languages instead of native languages. Unfortunately, the former change is disrupting the virtuous-cycle between performance improvements and software innovation. Establishing a new parallel performance virtuous cycle for managed languages will require scalable applications executing on scalable Virtual Machine (VM) services, since the VM schedules, monitors, compiles, optimizes, garbage collects, and executes together with the application. This talk describes current progress, opportunities, and challenges for scalable VM services. The parallel computing revolution urgently needs more innovations.


title: Compact data structure and scalable algorithms for the sparse grid technique

authors:
Alin Florindor Murarasu
Josef Weidendorfer
Gerrit Buse
Daniel Butnaru
Dirk Pflüger

abstract: The sparse grid discretization technique enables a compressed representation of higher-dimensional functions. In its original form, it relies heavily on recursion and complex data structures, thus being far from well-suited for GPUs. In this paper, we describe optimizations that enable us to implement compression and decompression, the crucial sparse grid algorithms for our application, on Nvidia GPUs. The main idea consists of a bijective mapping between the set of points in a multi-dimensional sparse grid and a set of consecutive natural numbers. The resulting data structure consumes a minimum amount of memory. For a 10-dimensional sparse grid with approximately 127 million points, it consumes up to 30 times less memory than trees or hash tables which are typically used. Compared to a sequential CPU implementation, the speedups achieved on GPU are up to 17 for compression and up to 70 for decompression, respectively. We show that the optimizations are also applicable to multicore CPUs.


title: Inferring ownership transfer for efficient message passing

authors:
Stas Negara
Rajesh K. Karmani
Gul A. Agha

abstract: One of the more popular paradigms for concurrent programming is the Actor model of message passing; it has been adopted in one form or another by a number of languages and frameworks. By avoiding a shared local state and instead relying on message passing, the Actor model facilitates modular programming. An important challenge for message passing languages is to transmit messages efficiently. This requires retaining the pass-by-value semantics of messages while avoiding making a deep copy on sequential or shared memory multicore processors. A key observation is that many messages have an ownership transfer semantics; such messages can be sent efficiently using pointers without introducing shared state between concurrent objects. We propose a conservative static analysis algorithm which infers if the content of a message is compatible with an ownership transfer semantics. Our tool, called SOTER (for Safe Ownership Transfer enablER) transforms the program to avoid the cost of copying the contents of a message whenever it can infer the content obeys the ownership transfer semantics. Experiments using a range of programs suggest that our conservative static analysis method is usually able to infer ownership transfer. Performance results demonstrate that the transformed programs execute up to an order of magnitude faster than the original programs.


title: QoS aware storage cache management in multi-server environments

authors:
Ramya Prabhakar
Shekhar Srikantaiah
Rajat Garg
Mahmut T. Kandemir

abstract: In this paper, we propose a novel two-step approach to the management of the storage caches to provide predictable performance in multi-server storage architectures: (1) An adaptive QoS decomposition and optimization step uses max-flow algorithm to determine the best decomposition of application-level QoS to sub-QoSs such that the application performance is optimized, and (2) A storage cache allocation step uses feedback control theory to allocate shared storage cache space such that the specified QoSs are satisfied throughout the execution.


title: Weak atomicity under the x86 memory consistency model

authors:
Amitabha Roy
Steven Hand
Tim Harris

abstract: We consider the problem of building a weakly atomic Software Transactional Memory (STM), that provides Single (Global) Lock Atomicity (SLA) while adhering to the x86 memory consistency model (x86-MM).


title: Lifeline-based global load balancing

authors:
Vijay A. Saraswat
Prabhanjan Kambadur
Sreedhar B. Kodali
David Grove
Sriram Krishnamoorthy

abstract: On shared-memory systems, Cilk-style work-stealing has been used to effectively parallelize irregular task-graph based applications such as Unbalanced Tree Search (UTS). There are two main difficulties in extending this approach to distributed memory. In the shared memory approach, thieves (nodes without work) constantly attempt to asynchronously steal work from randomly chosen victims until they find work. In distributed memory, thieves cannot autonomously steal work from a victim without disrupting its execution. When work is sparse, this results in performance degradation. In essence, a direct extension of traditional work-stealing to distributed memory violates the work-first principle underlying work-stealing. Further, thieves spend useless CPU cycles attacking victims that have no work, resulting in system inefficiencies in multi-programmed contexts. Second, it is non-trivial to detect active distributed termination (detect that programs at all nodes are looking for work, hence there is no work). This problem is well-studied and requires careful design for good performance. Unfortunately, in most existing languages/frameworks, application developers are forced to implement their own distributed termination detection.


title: Automatic formal verification of MPI-based parallel programs

authors:
Stephen F. Siegel
Timothy K. Zirkel

abstract: The Toolkit for Accurate Scientific Software (TASS) is a suite of tools for the formal verification of MPI-based parallel programs used in computational science. TASS can verify various safety properties as well as compare two programs for functional equivalence. The TASS front end takes an integer n ≥ 1 and a C/MPI program, and constructs an abstract model of the program with n processes. Procedures, structs, (multi-dimensional) arrays, heap-allocated data, pointers, and pointer arithmetic are all representable in a TASS model. The model is then explored using symbolic execution and explicit state space enumeration. A number of techniques are used to reduce the time and memory consumed. A variety of realistic MPI programs have been verified with TASS, including Jacobi iteration and manager-worker type programs, and some subtle defects have been discovered. TASS is written in Java and is available from http://vsl.cis.udel.edu/tass under the Gnu Public License.


title: A wait-free NCAS library for parallel applications with timing constraints

authors:
Philippe Stellwag
Fabian Scheler
Jakob Krainz
Wolfgang Schröder-Preikschat

abstract: We introduce our major ideas of a wait-free, linearizable, and disjoint access parallel NCAS library, called rtNCAS. It focuses the construction of wait-free data structure operations (DSO) in real-time circumstances. rtNCAS is able to conditionally swap multiple independent words (NCAS) in an atomic manner. It allows us, furthermore, to implement arbitrary DSO by means of their sequential specification.


title: Time skewing made simple

authors:
Robert Strzodka
Mohammed Shaheen
Dawid Pajak

abstract: Time skewing and loop tiling has been known for a long time to be a highly \nbeneficial acceleration technique for nested loops especially on bandwidth \nhungry multi-core processors, but it is little used in practice because \nefficient implementations utilize complicated code and simple or abstract ones \nshow much smaller gains over naive nested loops. We break this dilemma with an \nessential time skewing scheme that is both compact and fast.


title: The STAPL parallel container framework

authors:
Gabriel Tanase
Antal A. Buss
Adam Fidel
Harshvardhan
Ioannis Papadopoulos
Olga Pearce
Timmie G. Smith
Nathan L. Thomas
Xiabing Xu
Nedal Mourad
Jeremy Vu
Mauro Bianco
Nancy M. Amato
Lawrence Rauchwerger

abstract: The Standard Template Adaptive Parallel Library (STAPL) is a parallel programming infrastructure that extends C++ with support for parallelism. It includes a collection of distributed data structures called pContainers that are thread-safe, concurrent objects, i.e., shared objects that provide parallel methods that can be invoked concurrently. In this work, we present the STAPL Parallel Container Framework (PCF), that is designed to facilitate the development of generic parallel containers. We introduce a set of concepts and a methodology for assembling a pContainer from existing sequential or parallel containers, without requiring the programmer to deal with concurrency or data distribution issues. The PCF provides a large number of basic parallel data structures (e.g., pArray, pList, pVector, pMatrix, pGraph, pMap, pSet). The PCF provides a class hierarchy and a composition mechanism that allows users to extend and customize the current container base for improved application expressivity and performance. We evaluate STAPL pContainer performance on a CRAY XT4 massively parallel system and show that pContainer methods, generic pAlgorithms, and different applications provide good scalability on more than 16,000 processors.


title: Enhanced speculative parallelization via incremental recovery

authors:
Chen Tian
Changhui Lin
Min Feng
Rajiv Gupta

abstract: The widespread availability of multicore systems has led to an increased interest in speculative parallelization of sequential programs using software-based thread level speculation. Many of the proposed techniques are implemented via state separation where non-speculative computation state is maintained separately from the speculative state of threads performing speculative computations. If speculation is successful, the results from speculative state are committed to non-speculative state. However, upon misspeculation, discard-all scheme is employed in which speculatively computed results of a thread are discarded and the computation is performed again. While this scheme is simple to implement, one disadvantage of discard-all is its inability to tolerate high misspeculation rates due to its high runtime overhead. Thus, it is not suitable for use in applications where misspeculation rates are input dependent


title: COREMU: a scalable and portable parallel full-system emulator

authors:
Zhaoguo Wang
Ran Liu
Yufei Chen
Xi Wu
Haibo Chen
Weihua Zhang
Binyu Zang

abstract: This paper presents the open-source COREMU, a scalable and portable parallel emulation framework that decouples the complexity of parallelizing full-system emulators from building a mature sequential one. The key observation is that CPU cores and devices in current (and likely future) multiprocessors are loosely-coupled and communicate through well-defined interfaces. Based on this observation, COREMU emulates multiple cores by creating multiple instances of existing sequential emulators, and uses a thin library layer to handle the inter-core and device communication and synchronization, to maintain a consistent view of system resources. COREMU also incorporates lightweight memory transactions, feedback-directed scheduling, lazy code invalidation and adaptive signal control to provide scalable performance. To make COREMU useful in practice, we also provide some preliminary tools and APIs that can help programmers to diagnose performance problems and (concurrency) bugs. A working prototype, which reuses the widely-used QEMU as the sequential emulator, is with only 2500 lines of code (LOCs) changes to QEMU. It currently supports x64 and ARM platforms, and can emulates up to 255 cores running commodity OSes with practical performance, while QEMU cannot scale above 32 cores. A set of performance evaluation against QEMU indicates that, COREMU has negligible uniprocessor emulation overhead, performs and scales significantly better than QEMU. We also show how COREMU could be used to diagnose performance problems and concurrency bugs of both OS kernel and parallel applications.


title: Active pebbles: a programming model for highly parallel fine-grained data-driven computations

authors:
Jeremiah Willcock
Torsten Hoefler
Nicholas Gerard Edmonds
Andrew Lumsdaine

abstract: A variety of programming models exist to support large-scale, distributed memory, parallel computation. These programming models have historically targeted coarse-grained applications with natural locality such as those found in a variety of scientific simulations of the physical world. Fine-grained, irregular, and unstructured applications such as those found in biology, social network analysis, and graph theory are less well supported. We propose Active Pebbles, a programming model which allows these applications to be expressed naturally; an accompanying execution model ensures performance and scalability.


title: ScalaExtrap: trace-based communication extrapolation for spmd programs

authors:
Xing Wu
Frank Mueller

abstract: Performance modeling for scientific applications is important for assessing potential application performance and systems procurement in high-performance computing (HPC). Recent progress on communication tracing opens up novel opportunities for communication modeling due to its lossless yet scalable trace collection. Estimating the impact of scaling on communication efficiency still remains non-trivial due to execution-time variations and exposure to hardware and software artifacts. This work contributes a fundamentally novel modeling scheme. We synthetically generate the application trace for large numbers of nodes by extrapolation from a set of smaller traces. We devise an innovative approach for topology extrapolation of single program, multiple data (SPMD) codes with stencil or mesh communication. The extrapolated trace can subsequently be (a) replayed to assess communication requirements before porting an application, (b) transformed to auto-generate communication benchmarks for various target platforms, and (c) analyzed to detect communication inefficiencies and scalability limitations. To the best of our knowledge, rapidly obtaining the communication behavior of parallel applications at arbitrary scale with the availability of timed replay, yet without actual execution of the application at this scale is without precedence and has the potential to enable otherwise infeasible system simulation at the exascale level.


title: All-window profiling and composable models of cache sharing

authors:
Xiaoya Xiang
Bin Bao
Tongxin Bai
Chen Ding
Trishul M. Chilimbi

abstract: As multi-core processors become commonplace and cloud computing is gaining acceptance, more applications are run in a shared cache environment. Cache sharing depends on a concept called footprint, which depends on all cache accesses not just cache misses. Previous work has recognized the importance of footprint but has not provided a method for accurate measurement, mainly because the complete measurement requires counting data access in all execution windows, which takes time quadratic in the length of a trace. The paper first presents an algorithm efficient enough for off-line use to approximately measure the footprint with a guaranteed precision. The cost of the analysis can be adjusted by changing the precision. Then the paper presents a composable model. For a set of programs, the model uses the all-window footprint of each program to predict its cache interference with other programs without running these programs together. The paper evaluates the efficiency of all-window profiling using the SPEC 2000 benchmarks and compares the footprint interference model with a miss-rate based model and with exhaustive testing.


title: Cooperative reasoning for preemptive execution

authors:
Jaeheon Yi
Caitlin Sadowski
Cormac Flanagan

abstract: We propose a cooperative methodology for multithreaded software, where threads use traditional synchronization idioms such as locks, but additionally document each point of potential thread interference with a "yield" annotation. Under this methodology, code between two successive yield annotations forms a serializable transaction that is amenable to sequential reasoning. This methodology reduces the burden of reasoning about thread interleavings by indicating only those interference points that matter. We present experimental results showing that very few yield annotations are required, typically one or two per thousand lines of code. We also present dynamic analysis algorithms for detecting cooperability violations, where thread interference is not documented by a yield, and for yield annotation inference for legacy software.


title: GRace: a low-overhead mechanism for detecting data races in GPU programs

authors:
Mai Zheng
Vignesh T. Ravi
Feng Qin
Gagan Agrawal

abstract: In recent years, GPUs have emerged as an extremely cost-effective means for achieving high performance. Many application developers, including those with no prior parallel programming experience, are now trying to scale their applications using GPUs. While languages like CUDA and OpenCL have eased GPU programming for non-graphical applications, they are still explicitly parallel languages. All parallel programmers, particularly the novices, need tools that can help ensuring the correctness of their programs. Like any multithreaded environment, data races on GPUs can severely affect the program reliability. Thus, tool support for detecting race conditions can significantly benefit GPU application developers. Existing approaches for detecting data races on CPUs or GPUs have one or more of the following limitations: 1) being illsuited for handling non-lock synchronization primitives on GPUs; 2) lacking of scalability due to the state explosion problem; 3) reporting many false positives because of simplified modeling; and/or 4) incurring prohibitive runtime and space overhead. In this paper, we propose GRace, a new mechanism for detecting races in GPU programs that combines static analysis with a carefully designed dynamic checker for logging and analyzing information at runtime. Our design utilizes GPUs memory hierarchy to log runtime data accesses efficiently. To improve the performance, GRace leverages static analysis to reduce the number of statements that need to be instrumented. Additionally, by exploiting the knowledge of thread scheduling and the execution model in the underlying GPUs, GRace can accurately detect data races with no false positives reported. Based on the above idea, we have built a prototype of GRace with two schemes, i.e., GRace-stmt and GRace-addr, for NVIDIA GPUs. Both schemes are integrated with the same static analysis. We have evaluated GRace-stmt and GRace-addr with three data race bugs in three GPU kernel functions and also have compared them with the existing approach, referred to as B-tool. Our experimental results show that both schemes of GRace are effective in detecting all evaluated cases with no false positives, whereas Btool reports many false positives for one evaluated case. On the one hand, GRace-addr incurs low runtime overhead, i.e., 22-116%, and low space overhead, i.e., 9-18MB, for the evaluated kernels. On the other hand, GRace-stmt offers more help in diagnosing data races with larger overhead.


title: Optimizing remote accesses for offloaded kernels: application to high-level synthesis for FPGA

authors:
Christophe Alias
Alain Darte
Alexandru Plesco

abstract: In the context of the high-level synthesis (HLS) of regular kernels offloaded to FPGA and communicating with an external DDR memory, we show how to automatically generate adequate communicating processes for optimizing the transfer of remote data. This requires a generalized form of communication coalescing where data can be transferred from the external memory even when this memory is not fully up-to-date. Experiments with Altera HLS tools demonstrate that this automatization, based on advanced polyhedral code analysis and code generation techniques, can be used to efficiently map C kernels to FPGA, by generating, entirely at C level, all the necessary glue (the communication processes), which is compiled with the same HLS tool as for the computation kernel.


title: Programming parallel embedded and consumer applications in OpenMP superscalar

authors:
Michael Andersch
Chi Ching Chi
Ben H. H. Juurlink

abstract: In this paper, we evaluate the performance and usability of the parallel programming model OpenMP Superscalar (OmpSs), apply it to 10 different benchmarks and compare its performance with corresponding POSIX threads implementations.


title: Efficient performance evaluation of memory hierarchy for highly multithreaded graphics processors

authors:
Sara S. Baghsorkhi
Isaac Gelado
Matthieu Delahaye
Wen-mei W. Hwu

abstract: With the emergence of highly multithreaded architectures, performance monitoring techniques face new challenges in efficiently locating sources of performance discrepancies in the program source code. For example, the state-of-the-art performance counters in highly multithreaded graphics processing units (GPUs) report only the overall occurrences of microarchitecture events at the end of program execution. Furthermore, even if supported, any fine-grained sampling of performance counters will distort the actual program behavior and will make the sampled values inaccurate. On the other hand, it is difficult to achieve high resolution performance information at low sampling rates in the presence of thousands of concurrently running threads. In this paper, we present a novel software-based approach for monitoring the memory hierarchy performance in highly multithreaded general-purpose graphics processors. The proposed analysis is based on memory traces collected for snapshots of an application execution. A trace-based memory hierarchy model with a Monte Carlo experimental methodology generates statistical bounds of performance measures without being concerned about the exact inter-thread ordering of individual events but rather studying the behavior of the overall system. The statistical approach overcomes the classical problem of disturbed execution timing due to fine-grained instrumentation. The approach scales well as we deploy an efficient parallel trace collection technique to reduce the trace generation overhead and a simple memory hierarchy model to reduce the simulation time. The proposed scheme also keeps track of individual memory operations in the source code and can quantify their efficiency with respect to the memory system. A cross-validation of our results shows close agreement with the values read from the hardware performance counters on an NVIDIA Tesla C2050 GPU. Based on the high resolution profile data produced by our model we optimized memory accesses in the sparse matrix vector multiply kernel and achieved speedups ranging from 2.4 to 14.8 depending on the characteristics of the input matrices.


title: Communication avoiding successive band reduction

authors:
Grey Ballard
James Demmel
Nicholas Knight

abstract: The running time of an algorithm depends on both arithmetic and communication (i.e., data movement) costs, and the relative costs of communication are growing over time. In this work, we present both theoretical and practical results for tridiagonalizing a symmetric band matrix: we present an algorithm that asymptotically reduces communication, and we show that it indeed performs well in practice.


title: Automatic communication optimizations through memory reuse strategies

authors:
Muthu Manikandan Baskaran
Nicolas Vasilache
Benoît Meister
Richard Lethin

abstract: Modern parallel architectures are emerging with sophisticated hardware consisting of hierarchically placed parallel processors and memories. The properties of memories in a system vary wildly, not only quantitatively (size, latency, bandwidth, number of banks) but also qualitatively (scratchpad, cache). Along with the emergence of such architectures comes the need for effectively utilizing the parallel processors and properly managing data movement across memories to improve memory bandwidth and hide data transfer latency. In this paper, we describe some of the high-level optimizations that are targeted at the improvement of memory performance in the R-Stream compiler, a high-level source-to-source automatic parallelizing compiler. We direct our focus in this paper on optimizing communications (data transfers) by improving memory reuse at various levels of an explicit memory hierarchy. This general concept is well-suited to the hardware properties of GPGPUs, which is the architecture that we concentrate on for this paper. We apply our techniques and obtain performance improvement on various stencil kernels including an important iterative stencil kernel in seismic processing applications where the performance is comparable to that of the state-of-the-art implementation of the kernel by a CUDA expert.


title: Internally deterministic parallel algorithms can be fast

authors:
Guy E. Blelloch
Jeremy T. Fineman
Phillip B. Gibbons
Julian Shun

abstract: The virtues of deterministic parallelism have been argued for decades and many forms of deterministic parallelism have been described and analyzed. Here we are concerned with one of the strongest forms, requiring that for any input there is a unique dependence graph representing a trace of the computation annotated with every operation and value. This has been referred to as internal determinism, and implies a sequential semantics---i.e., considering any sequential traversal of the dependence graph is sufficient for analyzing the correctness of the code. In addition to returning deterministic results, internal determinism has many advantages including ease of reasoning about the code, ease of verifying correctness, ease of debugging, ease of defining invariants, ease of defining good coverage for testing, and ease of formally, informally and experimentally reasoning about performance. On the other hand one needs to consider the possible downsides of determinism, which might include making algorithms (i) more complicated, unnatural or special purpose and/or (ii) slower or less scalable.


title: S: a scripting language for high-performance RESTful web services

authors:
Daniele Bonetta
Achille Peternier
Cesare Pautasso
Walter Binder

abstract: There is an urgent need for novel programming abstractions to leverage the parallelism in modern multicore machines. We introduce S, a new domain-specific language targeting the server-side scripting of high-performance RESTful Web services. S promotes an innovative programming model based on explicit (control-flow) and implicit (process-level) parallelism control, allowing the service developer to specify which portions of the control-flow should be executed in parallel. For each service, the choice of the best level of parallelism is left to the runtime system. We assess performance and scalability by implementing two non-trivial composite Web services in S. Experiments show that S-based Web services can handle thousands of concurrent client requests on a modern multicore machine.


title: Efficient deadlock avoidance for streaming computation with filtering

authors:
Jeremy D. Buhler
Kunal Agrawal
Peng Li
Roger D. Chamberlain

abstract: Parallel streaming computations have been studied extensively, and many languages, libraries, and systems have been designed to support this model of computation. In particular, we consider acyclic streaming computations in which individual nodes can choose to filter, or discard, some of their inputs in a data-dependent manner. In these applications, if the channels between nodes have finite buffers, the computation can deadlock. One method of deadlock avoidance is to augment the data streams between nodes with occasional dummy messages; however, for general DAG topologies, no polynomial time algorithm is known to compute the intervals at which dummy messages must be sent to avoid deadlock.


title: NDetermin: inferring nondeterministic sequential specifications for parallelism correctness

authors:
Jacob Burnim
Tayfun Elmas
George C. Necula
Koushik Sen

abstract: Nondeterministic Sequential (NDSeq) specifications have been proposed as a means for separating the testing, debugging, and verifying of a program's parallelism correctness and its sequential functional correctness. In this work, we present a technique that, given a few representative executions of a parallel program, combines dynamic data flow analysis and Minimum-Cost Boolean Satisfiability (MinCostSAT) solving for automatically inferring a likely NDSeq specification for the parallel program. For a number of Java benchmarks, our tool NDetermin infers equivalent or stronger NDSeq specifications than those previously written manually.


title: Performance analysis of parallel constraint-based local search

authors:
Yves Caniou
Daniel Diaz
Florian Richoux
Philippe Codognet
Salvador Abreu

abstract: We present a parallel implementation of a constraint-based local search algorithm and investigate its performance results for hard combinatorial optimization problems on two different platforms up to several hundreds of cores. On a variety of classical CSPs benchmarks, speedups are very good for a few tens of cores, and good up to a hundred cores. More challenging problems derived from reallife applications (Costas array) shows even better speedups, nearly optimal up to 256 cores.


title: PARRAY: a unifying array representation for heterogeneous parallelism

authors:
Yifeng Chen
Xiang Cui
Hong Mei

abstract: This paper introduces a programming interface called PARRAY (or Parallelizing ARRAYs) that supports system-level succinct programming for heterogeneous parallel systems like GPU clusters. The current practice of software development requires combining several low-level libraries like Pthread, OpenMP, CUDA and MPI. Achieving productivity and portability is hard with different numbers and models of GPUs. PARRAY extends mainstream C programming with novel array types of distinct features: 1) the dimensions of an array type are nested in a tree, conceptually reflecting the memory hierarchy; 2) the definition of an array type may contain references to other array types, allowing sophisticated array types to be created for parallelization; 3) threads also form arrays that allow programming in a Single-Program-Multiple-Codeblock (SPMC) style to unify various sophisticated communication patterns. This leads to shorter, more portable and maintainable parallel codes, while the programmer still has control over performance-related features necessary for deep manual optimization. Although the source-to-source code generator only faithfully generates low-level library calls according to the type information, higher-level programming and automatic performance optimization are still possible through building libraries of sub-programs on top of PARRAY. The case study on cluster FFT illustrates a simple 30-line code that 2x outperforms Intel Cluster MKL on the Tianhe-1A system with 7168 Fermi GPUs and 14336 CPUs.


title: A speculation-friendly binary search tree

authors:
Tyler Crain
Vincent Gramoli
Michel Raynal

abstract: We introduce the first binary search tree algorithm designed for speculative executions. Prior to this work, tree structures were mainly designed for their pessimistic (non-speculative) accesses to have a bounded complexity. Researchers tried to evaluate transactional memory using such tree structures whose prominent example is the red-black tree library developed by Oracle Labs that is part of multiple benchmark distributions. Although well-engineered, such structures remain badly suited for speculative accesses, whose step complexity might raise dramatically with contention.


title: Lock cohorting: a general technique for designing NUMA locks

authors:
David Dice
Virendra J. Marathe
Nir Shavit

abstract: Multicore machines are quickly shifting to NUMA and CC-NUMA architectures, making scalable NUMA-aware locking algorithms, ones that take into account the machines' non-uniform memory and caching hierarchy, ever more important. This paper presents lock cohorting, a general new technique for designing NUMA-aware locks that is as simple as it is powerful.


title: Scalable parallel debugging with statistical assertions

authors:
Minh Ngoc Dinh
David Abramson
Chao Jin
Andrew Gontarek
Bob Moench
Luiz De Rose

abstract: Traditional debuggers are of limited value for modern scientific codes that manipulate large complex data structures. This paper discusses a novel debug-time assertion, called a "Statistical Assertion", that allows a user to reason about large data structures, and the primitives are parallelised to provide an efficient solution. We present the design and implementation of statistical assertions, and illustrate the debugging technique with a molecular dynamics simulation. We evaluate the performance of the tool on a 12,000 cores Cray XE6.