title: On using connection-oriented vs. connection-less transport for performance and scalability of collective and one-sided operations: trade-offs and impact

authors:
Amith R. Mamidala
Sundeep Narravula
Abhinav Vishnu
Gopalakrishnan Santhanaraman
Dhabaleswar K. Panda

abstract: Communication subsystem plays a pivotal role in achieving scalable performance in clusters. The communication semantics employed are dictated by the programming model used by the application such as MPI, UPC, etc. Out of the gamut of communication primitives, collective and one-sided operations are especially significant and have to be designed harnessing the capabilities and features exposed by the underlying networks. In some cases, there is a direct match between the semantics of the operations and the underlying network primitives. InfiniBand provides two transport modes: (i)Connection-oriented Reliable connection (RC) supporting Memory and Channel semantics and (ii) Connection-less Unreliable Datagram (UD) supporting Channel semantics. Achieving good performance and scalability needs careful analysis and design of communication primitives based on these options.


venue: ppopp

title: Featherweight transactions: decoupling threads and atomic blocks

authors:
Virendra J. Marathe
Tim Harris
James R. Larus

abstract: No abstract available.


title: Efficient nonblocking software transactional memory

authors:
Virendra J. Marathe
Mark Moir

abstract: Foundational transactional memory research grew out of research into nonblocking concurrent data structures, which aim to overcome the many well-known software engineering, performance, and robustness problems associated with lock-based implementations. Recently, many researchers have developed blocking STMs, recognising that they are much easier to design and that the software engineering benefits of STM can be delivered even by a blocking STM. But hiding blocking from the application programmer does not eliminate all of its disadvantages, and in some cases blocking is unacceptable, for example if STM is to be used to coordinate between an interrupt handler and the interrupted thread.


title: A study of tracing overhead on a high-performance linux cluster

authors:
Kathryn Mohror
Karen L. Karavanic

abstract: Our goal in this work was to identify and quantify the overheads of tracing parallel applications. We investigate several different sources of overhead related to tracing: trace instrumentation, periodic writing of trace files to disk, differing trace buffer sizes, system changes, and increasing numbers of processors in the target application. We encountered overheads as large as 26.7% for writing the trace file to disk. We found that buffer sizes can make a difference in the overheads, and that differences in system software can also contribute to the level of the perturbation. Our results show that the overhead of instrumentation correlates strongly with the number of events, while the overhead of writing the trace buffer increases with increasing numbers of processors.


title: Fault detection in multi-threaded c++ server applications

authors:
Arndt Mühlenfeld
Franz Wotawa

abstract: This paper describes experiments with the freely available tool Helgrind, results obtained by using it for debugging a server application comprising 500 kLOC. We present improvements to the run time analysis of C++ programs that result in a dramatic reduction of false warnings.


title: Open nesting in software transactional memory

authors:
Yang Ni
Vijay Menon
Ali-Reza Adl-Tabatabai
Antony L. Hosking
Richard L. Hudson
J. Eliot B. Moss
Bratin Saha
Tatiana Shpeisman

abstract: Transactional memory (TM) promises to simplify concurrent programming while providing scalability competitive to fine-grained locking. Language-based constructs allow programmers to denote atomic regions declaratively and to rely on the underlying system to provide transactional guarantees along with concurrency. In contrast with fine-grained locking, TM allows programmers to write simpler programs that are composable and deadlock-free.


title: Implicit parallelism with ordered transactions

authors:
Christoph von Praun
Luis Ceze
Calin Cascaval

abstract: Implicit Parallelism with Ordered Transactions (IPOT) is an extension of sequential or explicitly parallel programming models to support speculative parallelization. The key idea is to specify opportunities for parallelization in a sequential program using annotations similar to transactions. Unlike explicit parallelism, IPOT annotations do not require the absence of data dependence, since the parallelization relies on runtime support for speculative execution. IPOT as a parallel programming model is determinate, i.e., program semantics are independent of the thread scheduling. For optimization, non-determinism can be introduced selectively.


title: MCSTL: the multi-core standard template library

authors:
Felix Putze
Peter Sanders
Johannes Singler

abstract: No abstract available.


title: Locality-aware connection management and rank assignment for wide-area MPI

authors:
Hideo Saito
Kenjiro Taura

abstract: We propose locality and application-aware connection management and rank assignment schemes for wide area message passing systems. Using our connection management scheme on 256 processors in 4 clusters, the NAS Parallel Benchmarks ran with no performance penalty with as few as 10% of the connections. Moreover, our rank assignment scheme wasable to find assignments that resulted in up to 160% better performance than locality and application-unaware assignments.


title: A theory of memory models

authors:
Vijay A. Saraswat
Radha Jagadeesan
Maged M. Michael
Christoph von Praun

abstract: A memory model for a concurrent imperative programming language specifies which writes to shared variables may be seen by reads performed by other threads. We present a simple mathematical framework for relaxed memory models for programming languages. To instantiate this framework for a specific language, the designer must choose the notion of atomic steps supported by the language (e.g. 32-bit reads and writes) and specify how a composite step may be broken into a sequence of atomic steps (the decomposition rule). This rule determines which sequence of intermediate writes (if any) are visible to concurrent reads by other threads. Different choices of the rule lead to models which permit a read to return any value if there is a concurrent write (race), or models which satisfy a "No Thin Air Read"property. The former is suitable for languages such as C++(programs with races have undefined behavior), and the latter for Java. Other intermediate models are possible, useful and interesting.


title: X10: concurrent programming for modern architectures

authors:
Vijay A. Saraswat
Vivek Sarkar
Christoph von Praun

abstract: Two major trends are converging to reshape the landscape of concurrent object-oriented programming languages. First, trends in modern architectures (multi-core, accelerators, high performance clusters such as Blue Gene) are making concurrency and distribution inescapable for large classes of OO programmers. Second, experience with first-generation concurrent OO languages (e.g. Java threads and synchronization) have revealed several drawbacks of unstructured threads with lock-based synchronization.


title: Conservative vs. optimistic parallelization of stateful network intrusion detection

authors:
Derek L. Schuff
Yung Ryn Choe
Vijay S. Pai

abstract: This paper presents two approaches to parallelizing the Snort network intrusion detection system (NIDS). One scheme parallelizes NIDS processing conservatively across independent network flows, while the other optimistically achieves intra-flow parallelism by exploiting the observation that certain intra-flow dependences are uncommon and may be ignored under certain circumstances. Both schemes achieve average speedup over 2 on four cores, with an average throughput over 1 Gbps on 5 traces tested.


title: Alert-on-update: a communication aid for shared memory multiprocessors

authors:
Michael F. Spear
Arrvindh Shriraman
Hemayet Hossain
Sandhya Dwarkadas
Michael L. Scott

abstract: No abstract available.


title: Speculations: providing fault-tolerance and improving performance of parallel applications

authors:
Cristian Tapus
Jason Hickey

abstract: Transactions are a simple and powerful mechanism for establishing fault-tolerance. To allow multiple processes to cooperate in a transaction we relax the isolation property and use message passing for communication. We call the new abstraction a speculation.


title: Expressing and exploiting concurrency in networked applications with aspen

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

abstract: This paper presents Aspen, a high-level programming language thattargets both high-productivity programming and runtime support formanaging resources needed by a computation. Programs in Aspen arerepresented as directed graphs, where the edges are well-definedunidirectional communication channels and the nodes are instances of computational modules that process the incoming data. The resulting representation of a program closely resembles a flow chart describing the flow of computation in a server application and exposing the communicationat a high level of abstraction. This strategy for program composition naturally allows parallelism and data sharing to be factored out of the core computational logic of a program, facilitating a division of labor between parallelism expertsand application experts and also easing code development and maintenance. Aspen automatically and transparently supports task-level parallelism among module instancesand data-level parallelism across different flows in an application or, in some cases, across different work items within a flow. Aspen automatically and adaptively allocates threads to modules according to the dynamic workload seen at those modules.


title: Disens: scalable distributed sensor network simulation

authors:
Ye Wen
Richard Wolski
Gregory Moore

abstract: Simulation is widely used for developing, evaluating and analyzing sensor network applications, especially when deploying a large scale sensor network remains expensive and labor intensive. However, due to its computation intensive nature, existent simulation tools have to make trade-offs between fidelity and scalability and thus offer limited capabilities as design and analysis tools. In this paper, we introduce DiSenS (DIstributed SENsor network Simulation) -- a highly scalable distributed simulation system for sensor networks. DiSenS does not only faithfully emulates an extensive set of sensor hardware and supports extensible radio/power models, so that sensor network applications can be simulated transparently with high fidelity, but also employs distributed-memory parallel cluster system to attack the complex simulation problem. Combining an efficient distributed synchronization protocol and a sophisticated node partitioning algorithm (based on existent research), DiSenS achieves greater scalability than even many discrete event simulators. On a small to medium size cluster (16-64 nodes), DiSenS is able to simulate hundreds of motes in realtime speed and scale to thousands in sub-realtime speed. To our knowledge, DiSenS is the first full-system sensor network simulator with such scalability.


title: Self-adaptive applications on the grid

authors:
Gosia Wrzesinska
Jason Maassen
Henri E. Bal

abstract: Grids are inherently heterogeneous and dynamic. One important problemin grid computing is resource selection, that is, finding anappropriate resource set for the application. Another problem is adaptation to the changing characteristics of the grid environment. Existing solutions to these two problems require that a performance model for an application is known. However, constructing such models is a complex task. In this paper, we investigate an approach that does not require performance models. We start an application on any set of resources. During the application run, we periodically collect the statistics about the application run and deduce application requirements from these statistics. Then, we adjustthe resource set to better fit the application needs. This approach allows us to avoid performance bottlenecks, such as overloaded WAN links or very slow processors, and therefore can yield significant performance improvements. We evaluate our approach in a number of scenarios typical for the Grid.


title: Barrier matching for programs with textually unaligned barriers

authors:
Yuan Zhang
Evelyn Duesterwald

abstract: Barriers, a common synchronization primitive in SPMD-style programs, are used to partition a program into a sequence of parallel phases. Popular parallel programming models, such as MPI and OpenMP, allow barriers to be textually unaligned. Textually unaligned barriers make it difficult for the programmer to understand the synchronization phases in the program, and they can easily lead to synchronization errors. In this paper, we present an interprocedural analysis for matching barriers in a program in order to detect synchronization errors, or, if no such errors exist, to determine the synchronization phases of the program. Our analysis uses a combination of path expressions and interprocedural program slicing to match synchronizing barrier statements. If the barrier matching succeeds, the analysis determines the sets of barrier statements that synchronize together. A matching failure indicates the presence of a synchronization error and the analysis constructs a counter example to illustrate the error. We have implemented the analysis in an MPI checker tool for programs written in C and successfully analyzed the synchronization structure of several MPI benchmarks.


title: Optimized lock assignment and allocation: a method for exploiting concurrency among critical sections

authors:
Yuan Zhang
Vugranam C. Sreedhar
Weirong Zhu
Vivek Sarkar
Guang R. Gao

abstract: No abstract available.


title: Supporting fault-tolerance in streaming grid applications

authors:
Qian Zhu
Liang Chen
Gagan Agrawal

abstract: No abstract available.


title: Nested parallelism in transactional memory

authors:
Kunal Agrawal
Jeremy T. Fineman
Jim Sukha

abstract: This paper investigates adding transactions with nested parallelism and nested transactions to a dynamically multithreaded parallel programming language that generates only series-parallel programs. We describe XConflict, a data structure that facilitates conflict detection for a software transactional memory system which supports transactions with nested parallelism and unbounded nesting depth. For languages that use a Cilk-like work-stealing scheduler, XConflict answers concurrent conflict queries in O(1) time and can be maintained efficiently. In particular, for a program with T1 work and a span (or critical-path length) of T∞, the running time on p processors of the program augmented with XConflict is only O(T1/p + pT∞).


title: Safer open-nested transactions through ownership

authors:
Kunal Agrawal
I-Ting Angelina Lee
Jim Sukha

abstract: No abstract available.


title: Compilers and parallel computing systems

abstract: Increasing the delivered performance of computers by running programs in parallel is an old idea with a new urgency. Multi cores (multi processors) on chips have emerged as a way to increase performance wherever chips are used. The talk will focus on the role programming languages and compilers must play in delivering parallel performance to users and applications. The speaker's personal experiences with languages and compilers for high performance systems will provide the basis for her observations. The talk is intended to encourage the exploration of new approaches.


title: Experiences using adaptive concurrency in transactional memory with Lee's routing algorithm

authors:
Mohammad Ansari
Christos Kotselidis
Kim Jarvis
Mikel Luján
Chris C. Kirkham
Ian Watson

abstract: Experience in profiling Lee's routing algorithm, a new complex TM application, showed that transactional applications may exhibit dynamic exploitable parallelism, i.e. the amount of useful parallelism available at any point in time varies during the execution of the application. Obviously, executing too many transactions at times when the available parallelism is low will lead to high contention and wasted computation in aborted transactions, and vice versa. Current Transactional Memory (TM) implementations do not account for this behavior.


title: Semantics-based distributed I/O for mpiBLAST

authors:
Pavan Balaji
Wu-chun Feng
Jeremy S. Archuleta
Heshan Lin
Rajkumar Kettimuthu
Rajeev Thakur
Xiaosong Ma

abstract: BLAST is a widely used software toolkit for genomic sequence search. mpiBLAST is a freely available, open-source parallelization of BLAST that uses database segmentation to allow different worker processes to search (in parallel) unique segments of the database. After searching, the workers write their output to a filesystem. While mpiBLAST has been shown to achieve high performance in clusters with fast local filesystems, its I/O processing remains a concern for scalability, especially in systems having limited I/O capabilities such as distributed filesystems spread across a wide-area network. Thus, we present ParaMEDIC---a novel environment that uses application-specific semantic information to compress I/O data and improve performance in distributed environments. Specifically, for mpiBLAST, ParaMEDIC partitions worker processes into compute and I/O workers. Compute workers, instead of directly writing the output to the filesystem, the workers process the output using semantic knowledge about the application to generate metadata and write the metadata to the filesystem. I/O workers, which physically reside closer to the actual storage, then process this metadata to re-create the actual output and write it to the filesystem. This approach allows ParaMEDIC to reduce I/O time, thus accelerating mpiBLAST by as much as 25-fold.


title: Automatic data movement and computation mapping for multi-level parallel architectures with explicitly managed memories

authors:
Muthu Manikandan Baskaran
Uday Bondhugula
Sriram Krishnamoorthy
J. Ramanujam
Atanas Rountev
P. Sadayappan

abstract: Several parallel architectures such as GPUs and the Cell processor have fast explicitly managed on-chip memories, in addition to slow off-chip memory. They also have very high computational power with multiple levels of parallelism. A significant challenge in programming these architectures is to effectively exploit the parallelism available in the architecture and manage the fast memories to maximize performance.


title: Software transactional memory for large scale clusters

authors:
Robert L. Bocchino Jr.
Vikram S. Adve
Bradford L. Chamberlain

abstract: While there has been extensive work on the design of software transactional memory (STM) for cache coherent shared memory systems, there has been no work on the design of an STM system for very large scale platforms containing potentially thousands of nodes. In this work, we present Cluster-STM, an STM designed for high performance on large-scale commodity clusters. Our design addresses several novel issues posed by this domain, including aggregating communication, managing locality, and distributing transactional metadata onto the nodes. We also re-evaluate several STM design choices previously studied for cache-coherent machines and conclude that, in some cases, different choices are appropriate on clusters. Finally, we show that our design scales well up to 512 processors. This is because on a cluster, the main barrier to STM scalability is the remote communication overhead imposed by the STM operations, and our design aggregates most of that communication with the communication of the underlying data.


title: Practical experiences with Java software transactional memory

authors:
Evgueni Brevnov
Yuri Dolgov
Boris Kuznetsov
Dmitry Yershov
Vyacheslav Shakin
Dong-yuan Chen
Vijay Menon
Suresh Srinivas

abstract: In this paper, we evaluate the emerging Transactional Memory (TM) area by developing a set of Java transactional memory workloads and studying their performance under a Java Software Transactional Memory (STM) system and comparing them to their lock based counterparts. We provide a detailed performance and memory consumption analysis of the overheads of software transactional memory and transactional workloads within a production quality open source Java Runtime system. Additionally, we detail the impact of the various performance optimizations in both workloads and the underlying runtime system to improving both single thread performance and scalability.


title: Compiler-enhanced incremental checkpointing for OpenMP applications

authors:
Greg Bronevetsky
Daniel Marques
Keshav Pingali
Radu Rugina
Sally A. McKee

abstract: As modern supercomputing systems reach peta-flop performance they grow in both size and complexity, becoming increasingly vulnerable to failures. Checkpointing is a popular technique for tolerating such failures. Although a variety of automated system-level checkpointing solutions are currently available to HPC users, manual application-level checkpointing remains more popular due to its superior performance. This paper improves performance of automated checkpointing by presenting a compiler analysis for incremental checkpointing. This analysis, which works with both sequential and OpenMP applications, significantly reduces checkpoint sizes and enables asynchronous checkpointing.


title: A case study in SIMD text processing with parallel bit streams: UTF-8 to UTF-16 transcoding

abstract: High performance SIMD text processing using the method of parallel bit streams is introduced with a case study of UTF-8 to UTF-16 transcoding. A forward transform converts byte-oriented character stream data into eight parallel bit streams. Decoding, validation and computation of UTF-8 indexed UTF-16 bit streams are performed using bit-parallel logic and shifting operations. Conversion from UTF-8 indexing to UTF-16 indexing is performed using parallel bit deletion. The inverse transform is applied to yield high and low UTF-16 byte streams which are then merged. Combined with optimization techniques for blocks of ASCII data, speed-ups of 3 to 25 times are achieved on commodity processors compared with optimized byte-at-a-time code. Further applications of the method of parallel bit streams to bulk text processing applications are briefly discussed along with future prospects for the combination of intraregister and intrachip parallelism on multicore processors.


title: SuperMatrix: a multithreaded runtime scheduling system for algorithms-by-blocks

authors:
Ernie Chan
Field G. Van Zee
Paolo Bientinesi
Enrique S. Quintana-Ortí
Gregorio Quintana-Ortí
Robert A. van de Geijn

abstract: This paper describes SuperMatrix, a runtime system that parallelizes matrix operations for SMP and/or multi-core architectures. We use this system to demonstrate how code described at a high level of abstraction can achieve high performance on such architectures while completely hiding the parallelism from the library programmer. The key insight entails viewing matrices hierarchically, consisting of blocks that serve as units of data where operations over those blocks are treated as units of computation. The implementation transparently enqueues the required operations, internally tracking dependencies, and then executes the operations utilizing out-of-order execution techniques inspired by superscalar microarchitectures. This separation of concerns allows library developers to implement algorithms without concerning themselves with the parallelization aspect of the problem. Different heuristics for scheduling operations can be implemented in the runtime system independent of the code that enqueues the operations. Results gathered on a 16 CPU ccNUMA Itanium2 server demonstrate excellent performance.


title: Type inference for locality analysis of distributed data structures

authors:
Satish Chandra
Vijay A. Saraswat
Vivek Sarkar
Rastislav Bodík

abstract: In languages with distributed heap data structures, the type system typically conveys only coarse locality information: whether a reference is local or possibly remote. Often, of interest to the optimizing compiler or the user is a more fine-grain information, such as whether two remote references point to objects in the same partition of the distributed heap.


title: Scalable packet classification using interpreting: a cross-platform multi-core solution

authors:
Haipeng Cheng
Zheng Chen
Bei Hua
Xinan Tang

abstract: Packet classification is an enabling technology to support advanced Internet services. It is still a challenge for a software solution to achieve 10Gbps (line-rate) classification speed. This paper presents a classification algorithm that can be efficiently implemented on a multi-core architecture with or without cache. The algorithm embraces the holistic notion of exploiting application characteristics, considering the capabilities of the CPU and the memory hierarchy, and performing appropriate data partitioning. The classification algorithm adopts two stages: searching on a reduction tree and searching on a list of ranges. This decision is made based on a classification heuristic: the size of the range list is limited after the first stage search. Optimizations are then designed to speed up the two-stage execution. To exploit the speed gap (1) between the CPU and external memory; (2) between internal memory (cache) and external memory, an interpreter is used to trade the CPU idle cycles with demanding memory access requirements. By applying the CISC style of instruction encoding to compress the range expressions, it not only significantly reduces the total memory requirement but also makes effective use of the internal memory (cache) bandwidth. We show that compressing data structures is an effective optimization across the multi-core architectures.


title: High performance dense linear algebra on a spatially distributed processor

authors:
Jeffrey R. Diamond
Behnam Robatmili
Stephen W. Keckler
Robert A. van de Geijn
Kazushige Goto
Doug Burger

abstract: As technology trends have limited the performance scaling of conventional processors, industry and academic research has turned to parallel architectures on a single chip, including distributed uniprocessors and multicore chips. This paper examines how to extend the archtypical operation of dense linear algebra, matrix multiply, to an emerging class of uniprocessor architectures characterized by a large number of independent functional units, register banks, and cache banks connected by a 2-D on-chip network. We extend the well known algorithm for matrix multiplication by Goto to this spatially distributed class of uniprocessor and describe the optimizations of the innermost kernel, a systolic-like algorithm running on a general purpose uniprocessor. The resulting implementation yields the first demonstration of high-performance in an application executing on the TRIPS processor hardware, a next-generation distributed processor core. We show that such processors are indeed capable of substantial improvements in single threaded performance provided their spatial topography is taken into account.


title: All-window profiling of concurrent executions

authors:
Chen Ding
Trishul M. Chilimbi

abstract: This paper first demonstrates the need for all-window profiling in a concurrent execution, then presents an approximate algorithm, and finally discusses related work.


title: Matrix product on heterogeneous master-worker platforms

authors:
Jack J. Dongarra
Jean-Francois Pineau
Yves Robert
Frédéric Vivien

abstract: This paper is focused on designing efficient parallel matrix-product algorithms for heterogeneous master-worker platforms. While matrix-product is well-understood for homogeneous 2D-arrays of processors (e.g., Cannon algorithm and ScaLAPACK outer product algorithm), there are three key hypotheses that render our work original and innovative:


title: Dynamic performance tuning of word-based software transactional memory

authors:
Pascal Felber
Christof Fetzer
Torvald Riegel

abstract: The current generation of software transactional memories has the advantage of being simple and efficient. Nevertheless, there are several parameters that affect the performance of a transactional memory, for example the locality of the application and the cache line size of the processor. In this paper, we investigate dynamic tuning mechanisms on a new time-based software transactional memory implementation. We study in extensive measurements the performance of our implementation and exhibit the benefits of dynamic tuning. We compare our results with TL2, which is currently one of the fastest word-based software transactional memories.


title: Massive parallel LDPC decoding on GPU

authors:
Gabriel Falcão Paiva Fernandes
Leonel Sousa
Vítor Manuel Mendes da Silva

abstract: Low-Density Parity-Check (LDPC) codes are powerful error correcting codes (ECC). They have recently been adopted by several data communication standards such as DVB-S2 and WiMax. LDPCs are represented by bipartite graphs, also called Tanner graphs, and their decoding demands very intensive computation. For that reason, VLSI dedicated architectures have been investigated and developed over the last few years. This paper proposes a new approach for LDPC decoding on graphics processing units (GPUs). Efficient data structures and an new algorithm are proposed to represent the Tanner graph and to perform LDPC decoding according to the stream-based computing model. GPUs were programmed to efficiently implement the proposed algorithms by applying data-parallel intensive computing. Experimental results show that GPUs perform LDPC decoding nearly three orders of magnitude faster than modern CPUs. Moreover, they lead to the conclusion that GPUs with their tremendous processing power can be considered as a consistent alternative to state-of-the-art hardware LDPC decoders.


title: FastForward for efficient pipeline parallelism: a cache-optimized concurrent lock-free queue

authors:
John Giacomoni
Tipp Moseley
Manish Vachharajani

abstract: Low overhead core-to-core communication is critical for efficient pipeline-parallel software applications. This paper presents FastForward, a cache-optimized single-producer/single-consumer concurrent lock-free queue for pipeline parallelism on multicore architectures, with weak to strongly ordered consistency models. Enqueue and dequeue times on a 2.66 GHz Opteron 2218 based system are as low as 28.5 ns, up to 5x faster than the next best solution. FastForward's effectiveness is demonstrated for real applications by applying it to line-rate soft network processing on Gigabit Ethernet with general purpose commodity hardware.


title: Design and implementation of a high-performance MPI for C# and the common language infrastructure

authors:
Douglas P. Gregor
Andrew Lumsdaine

abstract: As high-performance computing enters the mainstream, parallel programming mechanisms (including the Message Passing Interface, or MPI) must be supported in new environments such as C# and the Common Language Infrastructure (CLI). Making effective use of MPI with the CLI requires an interface that reflects the high-level object-oriented nature of C# and that also supports its programming idioms. However, for performance reasons, this high-level functionality must ultimately be mapped to low-level native MPI libraries. In addition to abstraction penalty concerns, avoiding unwanted overhead in this mapping process is significantly complicated by the safety and portability features of the CLI virtual machine, such as garbage collection and just-in-time compilation. In this paper, we describe our approach to using features of C# and the CLI---such as reflection, unsafe code regions, and run-time code generation---to realize an elegant, yet highly efficient, C# interface to MPI. Experimental results demonstrate that there is no appreciable overhead introduced by our approach when compared to the native MS-MPI library.


title: On the correctness of transactional memory

authors:
Rachid Guerraoui
Michal Kapalka

abstract: Transactional memory (TM) is perceived as an appealing alternative to critical sections for general purpose concurrent programming. Despite the large amount of recent work on TM implementations, however, very little effort has been devoted to precisely defining what guarantees these implementations should provide. A formal description of such guarantees is necessary in order to check the correctness of TM systems, as well as to establish TM optimality results and inherent trade-offs.


title: Programming with tiles

authors:
Jia Guo
Ganesh Bikshandi
Basilio B. Fraguela
María Jesús Garzarán
David A. Padua

abstract: The importance of tiles or blocks in scientific computing cannot be overstated. Many algorithms, both iterative and recursive, can be expressed naturally if tiles are represented explicitly. From the point of view of performance, tiling, either as a code or a data layout transformation, is one of the most effective ways to exploit locality, which is a must to achieve good performance in current computers because of the significant difference in speed between processor and memory. Furthermore, tiles are also useful to express data distribution in parallel computations. However, despite the importance of tiles, most languages do not support them directly. This gives place to bloated programs populated with numerous subscript expressions which make the code difficult to read and coding mistakes more likely.


title: Transactional boosting: a methodology for highly-concurrent transactional objects

authors:
Maurice Herlihy
Eric Koskinen

abstract: We describe a methodology for transforming a large class of highly-concurrent linearizable objects into highly-concurrent transactional objects. As long as the linearizable implementation satisfies certain regularity properties (informally, that every method has an inverse), we define a simple wrapper for the linearizable implementation that guarantees that concurrent transactions without inherent conflicts can synchronize at the same granularity as the original linearizable implementation.


title: A portable runtime interface for multi-level memory hierarchies

authors:
Mike Houston
Ji Young Park
Manman Ren
Timothy J. Knight
Kayvon Fatahalian
Alex Aiken
William J. Dally
Pat Hanrahan

abstract: We present a platform independent runtime interface for moving data and computation through parallel machines with multi-level memory hierarchies. We show that this interface can be used as a compiler target and can be implemented easily and efficiently on a variety of platforms. The interface design allows us to compose multiple runtimes, achieving portability across machines with multiple memory levels. We demonstrate portability of programs across machines with two memory levels with runtime implementations for multi-core/SMP machines, the STI Cell Broadband Engine, a distributed memory cluster, and disk systems. We also demonstrate portability across machines with multiple memory levels by composing runtimes and running on a cluster of SMP nodes, out-of-core algorithms on a Sony Playstation 3 pulling data from disk, and a cluster of Sony Playstation 3's. With this uniform interface, we achieve good performance for our applications and maximize bandwidth and computational resources on these system configurations.


title: ZOID: I/O-forwarding infrastructure for petascale architectures

authors:
Kamil Iskra
John W. Romein
Kazutomo Yoshii
Peter H. Beckman

abstract: The ZeptoOS project is developing an open-source alternative to the proprietary software stacks available on contemporary massively parallel architectures. The aim is to enable computer science research on these architectures, enhance community collaboration, and foster innovation. In this paper, we introduce a component of ZeptoOS called ZOID---an I/O-forwarding infrastructure for architectures such as IBM Blue Gene that decouple file and socket I/O from the compute nodes, shipping those functions to dedicated I/O nodes. Through the use of optimized network protocols and data paths, as well as a multithreaded daemon running on I/O nodes, ZOID provides greater performance than does the stock infrastructure. We present a set of benchmark results that highlight the improvements. Crucially, the flexibility of our infrastructure is a vast improvement over the stock infrastructure, allowing users to forward data using custom-designed application interfaces, through an easy-to-use plug-in mechanism. This capability is used for real-time telescope data transfers, extensively discussed in the paper. Plug-in--specific threads implement prefetching of data obtained over sockets from an input cluster and merge results from individual compute nodes before sending them out, significantly reducing required network bandwidth. This approach allows a ZOID version of the application to handle a larger number of subbands per I/O node, or even to bypass the input cluster altogether, plugging the input from remote receiver stations directly into the I/O nodes. Using the resources more efficiently can result in considerable savings.


title: Cache-aware iteration space partitioning

authors:
Arun Kejariwal
Alexandru Nicolau
Utpal Banerjee
Alexander V. Veidenbaum
Constantine D. Polychronopoulos

abstract: The need for high performance per watt has led to the development of multi-core systems such as the Intel Core 2 Duo processor and the Intel quad-core Kentsfield processor. Maximal exploitation of the hardware parallelism supported by such systems necessitates the development of concurrent software. This, in part, entails program parallelization and efficient mapping of the parallelized program onto the different cores. The latter affects the load balance between the different cores which in turn has a direct impact on performance. In light of the fact that parallel loops, such as a parallel DO loop in Fortran, account for a large percentage of the total execution time, we focus on the problem of how to efficiently partition the iteration space of (possibly) nested perfect/non-perfect parallel loops. In this regard, one of the key aspects is how to efficiently capture the cache behavior as the cache subsystem is often the main performance bottleneck in multi-core systems. In this paper, we present a novel profile-guided compiler technique for cache-aware partitioning of iteration spaces of parallel loops. We present a case study using a kernel from the industry-standard SPEC CPU benchmark suite.


title: Split hardware transactions: true nesting of transactions using best-effort hardware transactional memory

authors:
Yossi Lev
Jan-Willem Maessen

abstract: Transactional Memory (TM) is on its way to becoming the programming API of choice for writing correct, concurrent, and scalable programs. Hardware TM (HTM) implementations are expected to be significantly faster than pure software TM (STM); however, full hardware support for true closed and open nested transactions is unlikely to be practical.


title: Formal specification of the MPI-2.0 standard in TLA+

authors:
Guodong Li
Michael Delisi
Ganesh Gopalakrishnan
Robert M. Kirby

abstract: No abstract available.


title: Toward high performance nonblocking software transactional memory

authors:
Virendra J. Marathe
Mark Moir

abstract: Substantial advances in STM performance in recent years have mostly focused on blocking systems. We describe our work integrating the most important techniques and optimizations emerging from the recent work on blocking STMs into several variants of a nonblocking STM.


title: Concurrent GC leveraging transactional memory

authors:
Phil McGachey
Ali-Reza Adl-Tabatabai
Richard L. Hudson
Vijay Menon
Bratin Saha
Tatiana Shpeisman

abstract: We predict that the ever-growing number of cores on our desktops will require a re-examination of concurrent programming. Two technologies are likely to become mainstream in response: Transactional memory provides a superior programming model to traditional lock-based concurrency, while Concurrent GC can take advantage of multiple cores to eliminate perceptible pauses in desktop applications such as games or Internet telephony. This paper proposes a combination of the two technologies, producing a synergy that improves scalability while eliminating the annoyance of user-perceivable pauses.


title: Where will all the threads come from?

abstract: Today, multicore microprocessors are at the heart of systems ranging from laptops to supercomputers. The shift to multicore architectures has transformed the problem of improving program performance from a micro-architecture problem to a software problem, shifting the focus from instruction-level parallelism to thread-level parallelism. As the density of transistors on chips increases, technology roadmaps call for increasing the number of cores. A key challenge facing the community is how we will keep increasing numbers of cores busy with productive work. Of great interest are answers to the question, "Where will all the threads come from"


title: Quasi-static scheduling for safe futures

authors:
Armand Navabi
Xiangyu Zhang
Suresh Jagannathan

abstract: Migrating sequential programs to effectively utilize next generation multicore architectures is a key challenge facing application developers and implementors. Languages like Java that support complex control- and dataflow abstractions confound classical automatic parallelization techniques. On the other hand, introducing multithreading and concurrency control explicitly into programs can impose a high conceptual burden on the programmer, and may entail a significant rewrite of the original program.


title: Performance without pain = productivity: data layout and collective communication in UPC

authors:
Rajesh Nishtala
George Almási
Calin Cascaval

abstract: The next generations of supercomputers are projected to have hundreds of thousands of processors. However, as the numbers of processors grow, the scalability of applications will be the dominant challenge. This forces us to reexamine some of our fundamental ways that we approach the design and use of parallel languages and runtime systems.


title: Probabilistic advanced reservations for batch-scheduled parallel machines

authors:
Daniel Nurmi
Richard Wolski
John Brevik

abstract: No abstract available.


title: Enhancing the performance of MPI-IO applications by overlapping I/O, computation and communication

authors:
Christina M. Patrick
Seung Woo Son
Mahmut T. Kandemir

abstract: No abstract available.


title: Modeling optimistic concurrency using quantitative dependence analysis

authors:
Christoph von Praun
Rajesh Bordawekar
Calin Cascaval

abstract: This work presents a quantitative approach to analyze parallelization opportunities in programs with irregular memory access where potential data dependencies mask available parallelism. The model captures data and causal dependencies among critical sections as algorithmic properties and quantifies them as a density computed over the number of executed instructions. The model abstracts from runtime aspects such as scheduling, the number of threads, and concurrency control used in a particular parallelization.


title: Extracting coarse-grain parallelism in general-purpose programs

authors:
Sean Rul
Hans Vandierendonck
Koen De Bosschere

abstract: While the chip multiprocessor (CMP) has quickly become the predominant processor architecture, its continuing success largely depends on the parallelizability of complex programs. In the early 1990s great successes were obtained to extract parallelism from the inner loops of scientific computations. In this paper we show that significant amounts of coarse-grain parallelism exists in the outer program loops, even in general-purpose programs. This coarse-grain parallelism can be exploited efficiently on CMPs without additional hardware support.


title: Optimization principles and application performance evaluation of a multithreaded GPU using CUDA

authors:
Shane Ryoo
Christopher I. Rodrigues
Sara S. Baghsorkhi
Sam S. Stone
David Blair Kirk
Wen-mei W. Hwu

abstract: GPUs have recently attracted the attention of many application developers as commodity data-parallel coprocessors. The newest generations of GPU architecture provide easier programmability and increased generality while maintaining the tremendous memory bandwidth and computational power of traditional GPUs. This opportunity should redirect efforts in GPGPU research from ad hoc porting of applications to establishing principles and strategies that allow efficient mapping of computation to graphics hardware. In this work we discuss the GeForce 8800 GTX processor's organization, features, and generalized optimization strategies. Key to performance on this platform is using massive multithreading to utilize the large number of cores and hide global memory latency. To achieve this, developers face the challenge of striking the right balance between each thread's resource usage and the number of simultaneously active threads. The resources to manage include the number of registers and the amount of on-chip memory used per thread, number of threads per multiprocessor, and global memory bandwidth. We also obtain increased performance by reordering accesses to off-chip memory to combine requests to the same or contiguous memory locations and apply classical optimizations to reduce the number of executed operations. We apply these strategies across a variety of applications and domains and achieve between a 10.5X to 457X speedup in kernel codes and between 1.16X to 431X total application speedup.


title: Assertional reasoning about data races in relaxed memory models

authors:
Beverly A. Sanders
KyungHee Kim

abstract: We describe the ideas behind a method to use assertional reasoning to statically show that all sequentially consistent executions of a concurrent program are free from data races.


title: Experience on optimizing irregular computation for memory hierarchy in manycore architecture

authors:
Guangming Tan
Dongrui Fan
Junchao Zhang
Andrew Russo
Guang R. Gao

abstract: No abstract available.


title: An adaptive memory conscious approach for mining frequent trees: implications for multi-core architectures

authors:
Shirish Tatikonda
Srinivasan Parthasarathy

abstract: We consider the problem of frequent tree mining and present algorithms targeting emerging single-chip multiprocessor (CMP) architectures. We explore algorithmic designs that improve the memory performance of such algorithms, both in terms of alleviating latency to memory as well as in terms of reducing the off-chip traffic. We then explore adaptive task-parallel and data-parallel design strategies which facilitate effective parallelization even in the presence of data and workload skew while minimizing parallelization overheads. We show that our optimized algorithms achieve orders of magnitude improvement both in run time and memory usage, when compared to state-of-the-art algorithms. Also, we show that our adaptive parallelization strategy achieves near-linear speedups on a modern dual quad-core system.


title: ISP: a tool for model checking MPI programs

authors:
Sarvani S. Vakkalanka
Subodh Sharma
Ganesh Gopalakrishnan
Robert M. Kirby

abstract: No abstract available.


title: Automated application-level checkpointing based on live-variable analysis in MPI programs

authors:
Panfeng Wang
Xuejun Yang
Hongyi Fu
Yunfei Du
Zhiyun Wang
Jia Jia

abstract: This paper proposes an optimization method of data saving for application-level checkpointing based on the live-variable analysis method for MPI programs. We presents the implementation of a source-to-source precompiler (CAC) for automating applicationlevel checkpointing based on the optimization method. The experiment shows that CAC is capable of automating application-level checkpointing correctly and reducing checkpoint data effectively.


title: Compiler optimizations for parallelizing general-purpose applications under thread-level speculation

authors:
Antonia Zhai
Shengyue Wang
Pen-Chung Yew
Guojin He

abstract: No abstract available.


title: Transactional memory with strong atomicity using off-the-shelf memory protection hardware

authors:
Martín Abadi
Tim Harris
Mojtaba Mehrara

abstract: This paper introduces a new way to provide strong atomicity in an implementation of transactional memory. Strong atomicity lets us offer clear semantics to programs, even if they access the same locations inside and outside transactions. It also avoids differences between hardware-implemented transactions and software-implemented ones. Our approach is to use off-the-shelf page-level memory protection hardware to detect conflicts between normal memory accesses and transactional ones. This page-level mechanism ensures correctness but gives poor performance because of the costs of manipulating memory protection settings and receiving notifications of access violations. However, in practice, we show how a combination of careful object placement and dynamic code update allows us to eliminate almost all of the protection changes. Existing implementations of strong atomicity in software rely on detecting conflicts by conservatively treating some non-transactional accesses as short transactions. In contrast, our page-level mechanism lets us be less conservative about how non-transactional accesses are treated; we avoid changes to non-transactional code until a possible conflict is detected dynamically, and we can respond to phase changes where a given instruction sometimes generates conflicts and sometimes does not. We evaluate our implementation with C# versions of many of the STAMP benchmarks, and show how it performs within 25% of an implementation with weak atomicity on all the benchmarks we have studied. It avoids pathological cases in which other implementations of strong atomicity perform poorly.


title: Safe open-nested transactions through ownership

authors:
Kunal Agrawal
I-Ting Angelina Lee
Jim Sukha

abstract: Researchers in transactional memory (TM) have proposed open nesting as a methodology for increasing the concurrency of transactional programs. The idea is to ignore ``low-level'' memory operations of an open-nested transaction when detecting conflicts for its parent transaction, and instead perform abstract concurrency control for the ``high-level'' operation that the nested transaction represents. To support this methodology, TM systems use an open-nested commit mechanism that commits all changes performed by an open-nested transaction directly to memory, thereby avoiding low-level conflicts. Unfortunately, because the TM runtime is unaware of the different levels of memory, unconstrained use of open-nested commits can lead to anomalous program behavior.


title: Serialization sets: a dynamic dependence-based parallel execution model

authors:
Matthew D. Allen
Srinath Sridharan
Gurindar S. Sohi

abstract: This paper proposes a new parallel execution model where programmers augment a sequential program with pieces of code called serializers that dynamically map computational operations into serialization sets of dependent operations. A runtime system executes operations in the same serialization set in program order, and may concurrently execute operations in different sets. Because serialization sets establish a logical ordering on all operations, the resulting parallel execution is predictable and deterministic.


title: Compiler-assisted dynamic scheduling for effective parallelization of loop nests on multicore processors

authors:
Muthu Manikandan Baskaran
Nagavijayalakshmi Vydyanathan
Uday Bondhugula
J. Ramanujam
Atanas Rountev
P. Sadayappan

abstract: Recent advances in polyhedral compilation technology have made it feasible to automatically transform affine sequential loop nests for tiled parallel execution on multi-core processors. However, for multi-statement input programs with statements of different dimensionalities, such as Cholesky or LU decomposition, the parallel tiled code generated by existing automatic parallelization approaches may suffer from significant load imbalance, resulting in poor scalability on multi-core systems. In this paper, we develop a completely automatic parallelization approach for transforming input affine sequential codes into efficient parallel codes that can be executed on a multi-core system in a load-balanced manner. In our approach, we employ a compile-time technique that enables dynamic extraction of inter-tile dependences at run-time, and dynamic scheduling of the parallel tiles on the processor cores for improved scalable execution. Our approach obviates the need for programmer intervention and re-writing of existing algorithms for efficient parallel execution on multi-cores. We demonstrate the usefulness of our approach through comparisons using linear algebra computations: LU and Cholesky decomposition.


title: Topology aware task mapping techniques: an api and case study

authors:
Abhinav Bhatele
Eric J. Bohm
Laxmikant V. Kalé

abstract: Optimal network performance is critical to efficient parallel scaling for communication-bound applications on large machines. With wormhole routing, no-load latencies do not increase significantly with number of hops traveled. Yet, we, and others have recently shown that in presence of contention, message latencies can grow substantially large. Hence task mapping strategies should take the topology of the machine into account on large machines. This poster presents a uniform API which provides topology information on 3D tori like IBM Blue Gene and Cray XT machines. We present techniques to use this API to improve performance. The API can be used by user-level codes to obtain information about allocated partitions at runtime which is essential for mapping.We motivate why it is important to consider network topology, using a simple 3D Stencil kernel. We then present mapping strategies for a production code, OpenAtom, running on three-dimensional torus and mesh topologies. OpenAtom presents complex communication scenarios of interaction between multiple groups of objects. Results are presented in the context of 3D Stencil and OpenAtom on up to 16,384 processors of Blue Gene/L, 8,192 processors of Blue Gene/P and 2,048 processors of Cray XT3.


title: Efficient, portable implementation of asynchronous multi-place programs

authors:
Ganesh Bikshandi
José G. Castaños
Sreedhar B. Kodali
V. Krishna Nandivada
Igor Peshansky
Vijay A. Saraswat
Sayantan Sur
Pradeep Varma
Tong Wen

abstract: The X10 programming language is organized around the notion of places (an encapsulation of data and activities operating on the data), partitioned global address space (PGAS), and asynchronous computation and communication.


title: Parallel thinking

abstract: Assuming that the multicore revolution plays out the way the microprocessor industry expects, it seems that within a decade most programming will involve parallelism at some level. One needs to ask how this affects the the way we teach computer science, or even how we have people think about computation. With regards to teaching there seem to be three basic choices: (1) we only train a small number of experts in parallel computation who develop a collection of libraries, and everyone else just uses them; (2) we leave our core curriculum pretty much as is, but add some advanced courses on parallelism or perhaps tack on a few lectures at the end of existing courses; or (3) we start teaching parallelism from the start and embed it throughout the curriculum with the idea of getting students to think about parallelism as the most natural form of computation and sequential computation as a special case.


title: Software transactional distributed shared memory

authors:
Alokika Dash
Brian Demsky

abstract: We have developed a transaction-based approach to distributed shared memory(DSM) that supports object caching and generates path expression prefetches. A path expression specifies a path through the heap that traverses the objects to be prefetched. To our knowledge, this is the first prefetching approach that can prefetch objects whose addresses have not been computed or predicted. Our DSM uses both prefetching and caching of remote objects to hide network latency while relying on the two-phase transaction commit mechanism to preserve the simple transactional consistency model that we present to the developer. We have evaluated this approach on a matrix multiply benchmark. We have found that our approach enables to effectively utilize multiple machines in a cluster and also benefit from prefetching and caching of objects.


title: How to build programmable multi-core chips

abstract: The arrival of multi-core chips has heightened interest in the discipline of parallel programming, a topic that has received much attention for many years. Computer architects have much to learn from sound principles for structuring software and expressing parallel computation. This talk will cover principles for the design of computer systems to support composable parallel software - the idea that any parallel program is usable, without change, as a component of larger parallel programs. By following these principles, a revolution in the ease of building robust and high-performance parallel software can be achieved. The principles suggest interesting directions for computer architecture; the tools to experiment with new architecture concepts are ready and waiting for the savvy and ambitious researcher


title: Preliminary results on nb-feb, a synchronization primitive for parallel programming

authors:
Phuong Hoai Ha
Philippas Tsigas
Otto J. Anshus

abstract: We introduce a non-blocking full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on may-core architectures. We show that the NB-FEB primitive is universal, scalable and feasible. NB-FEB, together with registers, can solve the consensus problem for an arbitrary number of processes (universality). NB-FEB is combinable, namely its memory requests to the same memory location can be combined into only one memory request, which consequently mitigates performance degradation due to synchronization "hot spots" (scalability). Since NB-FEB is a variant of the original full/empty bit that always returns a value instead of waiting for a conditional flag, it is as feasible as the original full/empty bit, which has been implemented in many computer systems (feasibility).


title: Opportunities beyond single-core microprocessors

abstract: Designers of future hardware and software face many challenges. Performance scaling of sequential cores is not what it once was. The best architectures for many cores, or equivalents, are not clear. Software, especially on clients, does not make abundant parallelism clear. Computer use and disposal is not so green. Smarter phones must not burn your pocket. Transistors and wires are getting less reliable. CMOS may run out of steam for technical or economic reasons. And the list goes on.


title: Backtracking-based load balancing

authors:
Tasuku Hiraishi
Masahiro Yasugi
Seiji Umatani
Taiichi Yuasa

abstract: High-productivity languages for parallel computing become more important as parallel environments including multicores become more common. Cilk is such a language. It provides good load balancing for many applications including irregular ones; that is, it keeps all workers busy by creating plenty of "logical" threads and adopting the oldest-first work stealing strategy. This paper proposes a "logical thread"-free framework called Tascell, which achieves a higher performance and supports a wider range of parallel environments including clusters without loss of productivity. A Tascell worker spawns a "real" task only when requested by another idle worker. The worker performs the spawning by temporarily "backtracking" and restoring its oldest task-spawnable state. Our approach eliminates the cost of spawning/managing logical threads. It also promotes the reuse of workspaces and improves the locality of reference since it does not need to prepare a workspace for each concurrently runnable logical thread. Furthermore, Tascell enables elegant and highly-efficient backtrack search algorithms with delayed workspace copying. For instance, our 16-queens problem solver is 1.86 times faster than Cilk on a system with two dual-core processors. Our approach also enables a single program to run in both shared and distributed memory environments with reasonable efficiency and scalability.


title: Exploiting global optimizations for openmp programs in the openuh compiler

authors:
Lei Huang
Deepak Eachempati
Marcus W. Hervey
Barbara M. Chapman

abstract: The advent of new parallel architectures has increased the need for parallel optimizing compilers to assist developers in creating efficient code. OpenUH is a state-of-the-art optimizing compiler, but it only performs a limited set of optimizations for OpenMP programs due to its conservative assumptions of shared memory programming. These limitations may prevent some OpenMP applications from being fully optimized to the extent of its sequential counterpart. This paper describes our design and implementation of a parallel data flow framework, consisting of a Parallel Control Flow Graph (PCFG) and a Parallel SSA (PSSA) representation in OpenUH, to model data flow for OpenMP programs. This framework enables the OpenUH compiler to perform all classical scalar optimizations for OpenMP programs, in addition to conducting OpenMP specific optimizations.


title: An efficient transactional memory algorithm for computing minimum spanning forest of sparse graphs

authors:
Seunghwa Kang
David A. Bader

abstract: Due to power wall, memory wall, and ILP wall, we are facing the end of ever increasing single-threaded performance. For this reason, multicore and manycore processors are arising as a new paradigm to pursue. However, to fully exploit all the cores in a chip, parallel programming is often required, and the complexity of parallel programming raises a significant concern. Data synchronization is a major source of this programming complexity, and Transactional Memory is proposed to reduce the difficulty caused by data synchronization requirements, while providing high scalability and low performance overhead.


title: Parallelization spectroscopy: analysis of thread-level parallelism in hpc programs

authors:
Arun Kejariwal
Calin Cascaval

abstract: In this paper, we present a method - parallelization spectroscopy - for analyzing the thread-level parallelism available in production High Performance Computing (HPC) codes.We survey a number of techniques that are commonly used for parallelization and classify all the loops in the case study presented using a sensitivity metric: how likely is a particular technique is successful in parallelizing the loop.


title: Petascale computing with accelerators

authors:
Michael Kistler
John A. Gunnels
Daniel A. Brokenshire
Brad Benton

abstract: A trend is developing in high performance computing in which commodity processors are coupled to various types of computational accelerators. Such systems are commonly called hybrid systems. In this paper, we describe our experience developing an implementation of the Linpack benchmark for a petascale hybrid system, the LANL Roadrunner cluster built by IBM for Los Alamos National Laboratory. This system combines traditional x86-64 host processors with IBM PowerXCell™ 8i1 accelerator processors. The implementation of Linpack we developed was the first to achieve a performance result in excess of 1.0 PFLOPS, and made Roadrunner the #1 system on the Top500 list in June 2008. We describe the design and implementation of hybrid Linpack, including the special optimizations we developed for this hybrid architecture. We then present actual results for single node and multi-node executions. From this work, we conclude that it is possible to achieve high performance for certain applications on hybrid architectures when careful attention is given to efficient use of memory bandwidth, scheduling of data movement between the host and accelerator memories, and proper distribution of work between the host and accelerator processors.


title: How much parallelism is there in irregular applications?

authors:
Milind Kulkarni
Martin Burtscher
Rajasekhar Inkulu
Keshav Pingali
Calin Cascaval

abstract: Irregular programs are programs organized around pointer-based data structures such as trees and graphs. Recent investigations by the Galois project have shown that many irregular programs have a generalized form of data-parallelism called amorphous data-parallelism. However, in many programs, amorphous data-parallelism cannot be uncovered using static techniques, and its exploitation requires runtime strategies such as optimistic parallel execution. This raises a natural question: how much amorphous data-parallelism actually exists in irregular programs?


title: Turbocharging boosted transactions or: how i learnt to stop worrying and love longer transactions

authors:
Chinmay Eishan Kulkarni
Osman S. Unsal
Adrián Cristal
Eduard Ayguadé
Mateo Valero

abstract: Boosted transactions offer an attractive method that enables programmers to create larger transactions that scale well and offer deadlock-free guarantees. However, as boosted transactions get larger, they become more susceptible to conflicts and aborts. We describe a linear-time algorithm to detect transactions that cannot make progress, which transactions need to be aborted, and when. The algorithm guarantees zero false positives with minimal aborts. Our proposals, as implemented in DSTM2, increase the transactional throughput of the system, often by more than 30%.


title: OpenMP to GPGPU: a compiler framework for automatic translation and optimization

authors:
Seyong Lee
Seung-Jai Min
Rudolf Eigenmann

abstract: GPGPUs have recently emerged as powerful vehicles for general-purpose high-performance computing. Although a new Compute Unified Device Architecture (CUDA) programming model from NVIDIA offers improved programmability for general computing, programming GPGPUs is still complex and error-prone. This paper presents a compiler framework for automatic source-to-source translation of standard OpenMP applications into CUDA-based GPGPU applications. The goal of this translation is to further improve programmability and make existing OpenMP applications amenable to execution on GPGPUs. In this paper, we have identified several key transformation techniques, which enable efficient GPU global memory access, to achieve high performance. Experimental results from two important kernels (JACOBI and SPMUL) and two NAS OpenMP Parallel Benchmarks (EP and CG) show that the described translator and compile-time optimizations work well on both regular and irregular applications, leading to performance improvements of up to 50X over the unoptimized translation (up to 328X over serial).


title: Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin

authors:
Tong Li
Dan P. Baumberger
Scott Hahn

abstract: Fairness is an essential requirement of any operating system scheduler. Unfortunately, existing fair scheduling algorithms are either inaccurate or inefficient and non-scalable for multiprocessors. This problem is becoming increasingly severe as the hardware industry continues to produce larger scale multi-core processors. This paper presents Distributed Weighted Round-Robin (DWRR), a new scheduling algorithm that solves this problem. With distributed thread queues and small additional overhead to the underlying scheduler, DWRR achieves high efficiency and scalability. Besides conventional priorities, DWRR enables users to specify weights to threads and achieve accurate proportional CPU sharing with constant error bounds. DWRR operates in concert with existing scheduler policies targeting other system attributes, such as latency and throughput. As a result, it provides a practical solution for various production OSes. To demonstrate the versatility of DWRR,we have implemented it in Linux kernels 2.6.22.15 and 2.6.24, which represent two vastly different scheduler designs. Our evaluation shows that DWRR achieves accurate proportional fairness and high performance for a diverse set of workloads.


title: Architectural support for cilk computations on many-core architectures

authors:
Guoping Long
Dongrui Fan
Junchao Zhang

abstract: No abstract available.


title: A compiler and runtime system for enabling data mining applications on gpus

authors:
Wenjing Ma
Gagan Agrawal

abstract: With increasing need for accelerating data mining and scientific data analysis on large data sets, and less chance to improve processor performance by simply increasing clock frequencies, multi-core architectures and accelerators like FPGAs and GPUs have become popular. A recent development in using GPU for general computing has been the release of CUDA (Compute Unified Device Architecture) by NVIDIA. CUDA allows GPU programming with Clanguage-like features, thus easing the development of non-graphics applications on a GPU. However, several challenges still remain in programming the GPUs with CUDA, because CUDA involves explicit parallel programming and management of its complex memory hierarchy, as well as allocating device memory, moving data between CPU anddevice memory, and specification of thread grid configurations.


title: Towards concurrency refactoring for x10

authors:
Shane Markstrum
Robert M. Fuhrer
Todd D. Millstein

abstract: In this poster, we present our vision of refactoring support for languages with a partitioned global address space memory model as embodied in the X10 programming language. We examine a novel refactoring, extract concurrent, that introduces additional concurrency within a loop by arranging for some user-selected code in the loop body to run in parallel with other iterations of the loop. We discuss the mechanisms and challenges for implementing this refactoring and how development of this refactoring provides insight for designing future refactorings.


title: Idempotent work stealing

authors:
Maged M. Michael
Martin T. Vechev
Vijay A. Saraswat

abstract: Load balancing is a technique which allows efficient parallelization of irregular workloads, and a key component of many applications and parallelizing runtimes. Work-stealing is a popular technique for implementing load balancing, where each parallel thread maintains its own work set of items and occasionally steals items from the sets of other threads.


title: Techniques for efficient placement of synchronization primitives

authors:
Alexandru Nicolau
Guangqiang Li
Arun Kejariwal

abstract: Harnessing the hardware parallelism of the emerging multi-cores systems necessitates concurrent software. Unfortunately, most of the existing mainstream software is sequential in nature. Although one could auto-parallelize a given program, the efficacy of this is largely limited to floating-point codes. One of the ways to alleviate the above limitation is to parallelize programs, which cannot be auto-parallelized, via explicit synchronization. In this regard, efficient placement of the synchronization primitives - say, post, wait - plays a key role in achieving high degree of thread-level parallelism (TLP). In this paper, we propose novel compiler techniques for the above. Specifically, given a control flow graph (CFG), the proposed techniques place a post as early as possible and place a wait as late as possible in the CFG, subject to dependences. We demonstrate the efficacy of our techniques, on a real machine, using real codes, specifically, from the industry-standard SPEC CPU benchmarks, the Linux kernel and other widely used open source codes. Our results show that the proposed techniques yield significantly higher levels of TLP than the state-of-the-art.


title: Multi-core demands multi-interfaces

abstract: The challenge for the microarchitect has always been (with very few notable domain-specific exceptions) how to translate the continually increasing processing power provided by Moore's Law into increased performance, or more recently into similar performance at lower cost in energy. The mechanisms in the past (almost entirely) kept the interface intact and used the increase in transistor count to improve the performance of the microarchitecture of the uniprocessor. When that became too hard, we went to larger and larger on-chip caches. Both are consistent with the notion that abstractions are good. At some point, we got overwhelmed with too many transistors; predictably, multi-core was born. As the transistor count continues to skyrocket, we are faced with two questions: what should be on the chip, and how should the software interface to it. If we expect to continue to take advantage of what process technology is providing, I think we need to do several things, starting with rethinking the notion of abstraction and providing multiple interfaces for the programmer.


title: Solving dense linear systems on platforms with multiple hardware accelerators

authors:
Gregorio Quintana-Ortí
Francisco D. Igual
Enrique S. Quintana-Ortí
Robert A. van de Geijn

abstract: In a previous PPoPP paper we showed how the FLAME methodology, combined with the SuperMatrix runtime system, yields a simple yet powerful solution for programming dense linear algebra operations on multicore platforms. In this paper we provide further evidence that this approach solves the programmability problem for this domain by targeting a more complex architecture, composed of a multicore processor and multiple hardware accelerators (GPUs, Cell B.E., etc.), each with its own local memory, resulting in a platform more reminiscent of a heterogeneous distributed-memory system. In particular, we show that the FLAME programming model accommodates this new situation effortlessly so that no significant change needs to be made to the codebase. All complexity is hidden inside the SuperMatrix runtime scheduling mechanism, which incorporates software implementations of standard cache/memory coherence techniques in computer architecture to improve the performance. Our experimental evaluation on a Intel Xeon 8-core host linked to an NVIDIA Tesla S870 platform with four GPUs delivers peak performances around 550 and 450 (single-precision) GFLOPS for the matrix-matrix product and the Cholesky factorization, respectively, which we believe to be the best performance numbers posted on this new architecture for such operations.


title: Committing conflicting transactions in an STM

authors:
Hany E. Ramadan
Indrajit Roy
Maurice Herlihy
Emmett Witchel

abstract: Dependence-aware transactional memory (DATM) is a recently proposed model for increasing concurrency of memory transactions without complicating their interface. DATM manages dependences between conflicting, uncommitted transactions so that they commit safely.


title: Industrial perspectives panel

abstract: This year, we have a different format for HPCA's industrial session. We will have an "industrial perspectives panel" with practitioners from industry presenting their perspectives on interesting future technical challenges and opportunities for research. We have panelists from IBM, Microsoft, NVIDIA, and Sun exploring a spectrum of interesting areas from consumer to enterprise markets including "hot" topics around multicores, graphics accelerators, and solid-state memory.


title: Detecting and tolerating asymmetric races

authors:
Paruj Ratanaworabhan
Martin Burtscher
Darko Kirovski
Benjamin G. Zorn
Rahul Nagpal
Karthik Pattabiraman

abstract: Because data races represent a hard-to-manage class of errors in concurrent programs, numerous approaches to detect them have been proposed and evaluated. We specifically consider asymmetric races, a subclass of all race conditions, where a programmer’s thread correctly acquires and releases a lock for a given variable, while another thread causes a race by improperly accessing this variable. We introduce ToleRace, a runtime system that allows programs to either tolerate or detect asymmetric races based on local replication of shared state. ToleRace provides an approximation of atomicity in critical sections by creating local copies of shared variables when a critical section is entered and propagating the appropriate copy when the critical section is exited. We characterize the possible interleavings that can cause races and precisely describe the effect of ToleRace in each case. We study the theoretical aspects of an oracle that knows exactly what type of interleaving has occurred. Then, we present a software implementation of ToleRace on top of a dynamic instrumentation tool. We evaluate our implementation on multithreaded applications from the SPLASH2 and PARSEC suites and show that its overhead is acceptable, i.e., a factor of two on average.


title: A comparison of programming models for multiprocessors with explicitly managed memory hierarchies

authors:
Scott Schneider
Jae-Seung Yeom
Benjamin Rose
John C. Linford
Adrian Sandu
Dimitrios S. Nikolopoulos

abstract: On multiprocessors with explicitly managed memory hierarchies (EMM), software has the responsibility of moving data in and out of fast local memories. This task can be complex and error-prone even for expert programmers. Before we can allow compilers to handle this complexity for us, we must identify the abstractions that are general enough to allow us to write applications with reasonable effort, yet specific enough to exploit the vast on-chip memory bandwidth of EMM multi-processors. To this end, we compare two programming models against hand-tuned codes on the STI Cell, paying attention to programmability and performance. The first programming model, Sequoia, abstracts the memory hierarchy as private address spaces, each corresponding to a parallel task. The second, Cellgen, is a new framework which provides OpenMP-like semantics and the abstraction of a shared address space divided into private and shared data. We compare three applications programmed using these models against their hand-optimized counterparts in terms of abstractions, programming complexity, and performance.


title: A tunable holistic resiliency approach for high-performance computing systems

authors:
Stephen L. Scott
Christian Engelmann
Geoffroy Vallée
Thomas J. Naughton
Anand Tikotekar
George Ostrouchov
Chokchai Leangsuksun
Nichamon Naksinehaboon
Raja Nassar
Mihaela Paun
Frank Mueller
Chao Wang
Arun Babu Nagarajan
Jyothish Varma

abstract: In order to address anticipated high failure rates, resiliency characteristics have become an urgent priority for next-generation extreme-scale high-performance computing (HPC) systems. This poster describes our past and ongoing efforts in novel fault resilience technologies for HPC. Presented work includes proactive fault resilience techniques, system and application reliability models and analyses, failure prediction, transparent process- and virtual-machine-level migration, and trade-off models for combining preemptive migration with checkpoint/restart. This poster summarizes our work and puts all individual technologies into context with a proposed holistic fault resilience framework.


title: A compiler-directed data prefetching scheme for chip multiprocessors

authors:
Seung Woo Son
Mahmut T. Kandemir
Mustafa Karaköy
Dhruva R. Chakrabarti

abstract: Data prefetching has been widely used in the past as a technique for hiding memory access latencies. However, data prefetching in multi-threaded applications running on chip multiprocessors (CMPs) can be problematic when multiple cores compete for a shared on-chip cache (L2 or L3). In this paper, we (i) quantify the impact of conventional data prefetching on shared caches in CMPs. The experimental data collected using multi-threaded applications indicates that, while data prefetching improves performance in small number of cores, its benefits reduce significantly as the number of cores is increased, that is, it is not scalable; (ii) identify harmful prefetches as one of the main contributors for degraded performance with a large number of cores; and (iii) propose and evaluate a compiler-directed data prefetching scheme for shared on-chip cache based CMPs. The proposed scheme first identifies program phases using static compiler analysis, and then divides the threads into groups within each phase and assigns a customized prefetcher thread (helper thread) to each group of threads. This helps to reduce the total number of prefetches issued, prefetch overheads, and negative interactions on the shared cache space due to data prefetches, and more importantly, makes compiler-directed prefetching a scalable optimization for CMPs. Our experiments with the applications from the SPEC OMP benchmark suite indicate that the proposed scheme improves overall parallel execution latency by 18.3% over the no-prefetch case and 6.4% over the conventional data prefetching scheme (where each core prefetches its data independently), on average, when 12 cores are used. The corresponding average performance improvements with 24 cores are 16.4% (over the no-prefetch case) and 11.7% (over the conventional prefetching case). We also demonstrate that the proposed scheme is robust under a wide range of values of our major simulation parameters, and the improvements it achieves come very close to those that can be achieved using an optimal scheme.


title: A comprehensive strategy for contention management in software transactional memory

authors:
Michael F. Spear
Luke Dalessandro
Virendra J. Marathe
Michael L. Scott

abstract: In Software Transactional Memory (STM), contention management refers to the mechanisms used to ensure forward progress--to avoid livelock and starvation, and to promote throughput and fairness. Unfortunately, most past approaches to contention management were designed for obstruction-free STM frameworks, and impose significant constant-time overheads. Priority-based approaches in particular typically require that reads be visible to all transactions, an expensive property that is not easy to support in most STM systems.


title: Effective performance measurement and analysis of multithreaded applications

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

abstract: Understanding why the performance of a multithreaded program does not improve linearly with the number of cores in a shared-memory node populated with one or more multicore processors is a problem of growing practical importance. This paper makes three contributions to performance analysis of multithreaded programs. First, we describe how to measure and attribute parallel idleness, namely, where threads are stalled and unable to work. This technique applies broadly to programming models ranging from explicit threading (e.g., Pthreads) to higher-level models such as Cilk and OpenMP. Second, we describe how to measure and attribute parallel overhead -- when a thread is performing miscellaneous work other than executing the user's computation. By employing a combination of compiler support and post-mortem analysis, we incur no measurement cost beyond normal profiling to glean this information. Using idleness and overhead metrics enables one to pinpoint areas of an application where concurrency should be increased (to reduce idleness), decreased (to reduce overhead), or where the present parallelization is hopeless (where idleness and overhead are both high). Third, we describe how to measure and attribute arbitrary performance metrics for high-level multithreaded programming models, such as Cilk. This requires bridging the gap between the expression of logical concurrency in programs and its realization at run-time as it is adaptively partitioned and scheduled onto a pool of threads. We have prototyped these ideas in the context of Rice University's HPCToolkit performance tools. We describe our approach, implementation, and experiences applying this approach to measure and attribute work, idleness, and overhead in executions of Cilk programs.


title: Formal verification of practical MPI programs

authors:
Anh Vo
Sarvani S. Vakkalanka
Michael Delisi
Ganesh Gopalakrishnan
Robert M. Kirby
Rajeev Thakur

abstract: This paper considers the problem of formal verification of MPI programs operating under a fixed test harness for safety properties without building verification models. In our approach, we directly model-check the MPI/C source code, executing its interleavings with the help of a verification scheduler. Unfortunately, the total feasible number of interleavings is exponential, and impractical to examine even for our modest goals. Our earlier publications formalized and implemented a partial order reduction approach that avoided exploring equivalent interleavings, and presented a verification tool called ISP. This paper presents algorithmic and engineering innovations to ISP, including the use of OpenMP parallelization, that now enables it to handle practical MPI programs, including: (i) ParMETIS- a widely used hypergraph partitioner, and (ii) MADRE- a Memory Aware Data Re-distribution Engine, both developed outside our group. Over these benchmarks, ISP has automatically verified up to 14K lines of MPI/C code, producing error traces of deadlocks and assertion violations within seconds.


title: NePalTM: design and implementation of nested parallelism for transactional memory systems

authors:
Haris Volos
Adam Welc
Ali-Reza Adl-Tabatabai
Tatiana Shpeisman
Xinmin Tian
Ravi Narayanaswamy

abstract: We present the programming model, design and implementation of NePalTM; a transactional memory system where atomic blocks can be used for concurrency control at an arbitrary level of nested parallelism.


title: Mapping parallelism to multi-cores: a machine learning based approach

authors:
Zheng Wang
Michael F. P. O'Boyle

abstract: The efficient mapping of program parallelism to multi-core processors is highly dependent on the underlying architecture. This paper proposes a portable and automatic compiler-based approach to mapping such parallelism using machine learning. It develops two predictors: a data sensitive and a data insensitive predictor to select the best mapping for parallel programs. They predict the number of threads and the scheduling policy for any given program using a model learnt off-line. By using low-cost profiling runs, they predict the mapping for a new unseen program across multiple input data sets. We evaluate our approach by selecting parallelism mapping configurations for OpenMP programs on two representative but different multi-core platforms (the Intel Xeon and the Cell processors). Performance of our technique is stable across programs and architectures. On average, it delivers above 96% performance of the maximum available on both platforms. It achieve, on average, a 37% (up to 17.5 times) performance improvement over the OpenMP runtime default scheme on the Cell platform. Compared to two recent prediction models, our predictors achieve better performance with a significant lower profiling cost.


title: MPIWiz: subgroup reproducible replay of mpi applications

authors:
Ruini Xue
Xuezheng Liu
Ming Wu
Zhenyu Guo
Wenguang Chen
Weimin Zheng
Zheng Zhang
Geoffrey M. Voelker

abstract: Message Passing Interface (MPI) is a widely used standard for managing coarse-grained concurrency on distributed computers. Debugging parallel MPI applications, however, has always been a particularly challenging task due to their high degree of concurrent execution and non-deterministic behavior. Deterministic replay is a potentially powerful technique for addressing these challenges, with existing MPI replay tools adopting either data-replay or order-replay approaches. Unfortunately, each approach has its tradeoffs. Data-replay generates substantial log sizes by recording every communication message. Order-replay generates small logs, but requires all processes to be replayed together. We believe that these drawbacks are the primary reasons that inhibit the wide adoption of deterministic replay as the critical enabler of cyclic debugging of MPI applications.


title: Stack-based parallel recursion on graphics processors

authors:
Ke Yang
Bingsheng He
Qiong Luo
Pedro V. Sander
Jiaoying Shi

abstract: Recent research has shown promising results on using graphics processing units (GPUs) to accelerate general-purpose computation. However, today's GPUs do not support recursive functions. As a result, for inherently recursive algorithms such as tree traversal, GPU programmers need to explicitly use stacks to emulate the recursion. Parallelizing such stack-based implementation on the GPU increases the programming difficulty; moreover, it is unclear how to improve the efficiency of such parallel implementations. As a first step to address both ease of programming and efficiency issues, we propose three parallel stack implementation alternatives that differ in the granularity of stack sharing. Taking tree traversals as an example, we study the performance tradeoffs between these alternatives and analyze their behaviors in various situations. Our results could be useful to both GPU programmers and GPU compiler writers.


title: Comparability graph coloring for optimizing utilization of stream register files in stream processors

authors:
Xuejun Yang
Li Wang
Jingling Xue
Yu Deng
Ying Zhang

abstract: A stream processor executes an application that has been decomposed into a sequence of kernels that operate on streams of data elements. During the execution of a kernel, all streams accessed must be communicated through the SRF (Stream Register File), a non-bypassing software-managed on-chip memory. Therefore, optimizing utilization of the SRF is crucial for good performance. The key insight is that the interference graphs formed by the streams in stream applications tend to be comparability graphs or decomposable into a set of multiple comparability graphs. We present a compiler algorithm that can find optimal or near-optimal colorings in stream IGs, thereby improving SRF utilization than the First-Fit


title: Application-aware management of parallel simulation collections

authors:
Siu Yau
Vijay Karamcheti
Denis Zorin
Kostadin Damevski
Steven G. Parker

abstract: This paper presents a system deployed on parallel clusters to manage a collection of parallel simulations that make up a computational study. It explores how such a system can extend traditional parallel job scheduling and resource allocation techniques to incorporate knowledge specific to the study.


title: Atomic quake: using transactional memory in an interactive multiplayer game server

authors:
Ferad Zyulkyarov
Vladimir Gajinov
Osman S. Unsal
Adrián Cristal
Eduard Ayguadé
Tim Harris
Mateo Valero

abstract: Transactional Memory (TM) is being studied widely as a new technique\nfor synchronizing concurrent accesses to shared memory data\nstructures for use in multi-core systems. Much of the initial work\non TM has been evaluated using microbenchmarks and application\nkernels; it is not clear whether conclusions drawn from these\nworkloads will apply to larger systems. In this work we make the\nfirst attempt to develop a large, complex, application that uses TM\nfor all of its synchronization. We describe how we have taken an\nexisting parallel implementation of the Quake game server and\nrestructured it to use transactions. In doing so we have encountered\nexamples where transactions simplify the structure of the program.\nWe have also encountered cases where using transactions\noccludes the structure of the existing code. Compared with existing\nTM benchmarks, our workload exhibits non-block-structured\ntransactions within which there are I/O operations and system call\ninvocations. There are long and short running transactions (200–\n1.3M cycles) with small and large read and write sets (a few bytes\nto 1.5MB). There are nested transactions reaching up to 9 levels\nat runtime. There are examples where error handling and recovery\noccurs inside transactions. There are also examples where data\nchanges between being accessed transactionally and accessed nontransactionally.\nHowever, we did not see examples where the kind\nof access to one piece of data depended on the value of another.


title: Exascale computing: the challenges and opportunities in the next decade

abstract: Supercomputing systems have made great strides in recent years as the extensive computing needs of cutting-edge engineering work and scientific discovery have driven the development of more powerful systems. In 2008, the first petaflop machine was released, and historic trends indicate that in ten years, we should be at the exascale level. Indeed, various agencies are targeting a computer system capable of 1 Exaop (10**18 ops) of computation within the next decade. We believe that applications in many industries will be materially transformed by exascale computers.


title: Helper locks for fork-join parallel programming

authors:
Kunal Agrawal
Charles E. Leiserson
Jim Sukha

abstract: Helper locks allow programs with large parallel critical sections, called parallel regions, to execute more efficiently by enlisting processors that might otherwise be waiting on the helper lock to aid in the execution of the parallel region. Suppose that a processor p is executing a parallel region A after having acquired the lock L protecting A. If another processor p′ tries to acquire L, then instead of blocking and waiting for p to complete A, processor p′ joins p to help it complete A. Additional processors not blocked on L may also help to execute A.


title: Input-driven dynamic execution prediction of streaming applications

authors:
Farhana Aleen
Monirul Sharif
Santosh Pande

abstract: Streaming applications are promising targets for effectively utilizing multicores because of their inherent amenability to pipelined parallelism. While existing methods of orchestrating streaming programs on multicores have mostly been static, real-world applications show ample variations in execution time that may cause the achieved speedup and throughput to be sub-optimal. One of the principle challenges for moving towards dynamic orchestration has been the lack of approaches that can predict or accurately estimate upcoming dynamic variations in execution efficiently, well before they occur.


title: Modeling advanced collective communication algorithms on cell-based systems

authors:
Qasim Ali
Samuel P. Midkiff
Vijay S. Pai

abstract: This paper presents and validates performance models for a varietyvof high-performance collective communication algorithms for systems with Cell processors. The systems modeled include a single Cell processor, two Cell chips on a Cell Blade, and a cluster of Cell Blades. The models extend PLogP, the well-known point-topoint performance model, by accounting for the unique hardware characteristics of the Cell (e.g., heterogeneous interconnects and DMA engines) and by applying the model to collective communication. This paper also presents a micro-benchmark suite to accurately measure the extended PLogP parameters on the Cell Blade and then uses these parameters to model different algorithms for the barrier, broadcast, reduce, all-reduce, and all-gather collective operations. Out of 425 total performance predictions, 398 of them see less than 10% error compared to the actual execution time and all of them see less than 15%.


title: Is hardware innovation over?

abstract: My colleagues, promotion committees, research funding agencies and business people often wonder if there is need for any architecture research. There seems to be no room to dislodge Intel IA-32. Even the number of new Application-Specific Integrated Circuits (ASICs) seems to be declining each year, because of the ever-increasing development cost.


title: An adaptive performance modeling tool for GPU architectures

authors:
Sara S. Baghsorkhi
Matthieu Delahaye
Sanjay J. Patel
William D. Gropp
Wen-mei W. Hwu

abstract: This paper presents an analytical model to predict the performance of


title: Leveraging parallel nesting in transactional memory

authors:
João Pedro Barreto
Aleksandar Dragojevic
Paulo Ferreira
Rachid Guerraoui
Michal Kapalka

abstract: Exploiting the emerging reality of affordable multi-core architectures goes through providing programmers with simple abstractions that would enable them to easily turn their sequential programs into concurrent ones that expose as much parallelism as possible. While transactional memory promises to make concurrent programming easy to a wide programmer community, current implementations either disallow nested transactions to run in parallel or do not scale to arbitrary parallel nesting depths. This is an important obstacle to the central goal of transactional memory, as programmers can only start parallel threads in restricted parts of their code.


title: A practical concurrent binary search tree

authors:
Nathan Grasso Bronson
Jared Casper
Hassan Chafi
Kunle Olukotun

abstract: We propose a concurrent relaxed balance AVL tree algorithm that is fast, scales well, and tolerates contention. It is based on optimistic techniques adapted from software transactional memory, but takes advantage of specific knowledge of the the algorithm to reduce overheads and avoid unnecessary retries. We extend our algorithm with a fast linearizable clone operation, which can be used for consistent iteration of the tree. Experimental evidence shows that our algorithm outperforms a highly tuned concurrent skip list for many access patterns, with an average of 39% higher single-threaded throughput and 32% higher multi-threaded throughput over a range of contention levels and operation mixes.


title: A distributed placement service for graph-structured and tree-structured data

authors:
Gregory Buehrer
Srinivasan Parthasarathy
Shirish Tatikonda

abstract: Effective data placement strategies can enhance the performance of data-intensive applications implemented on high end computing clusters. Such strategies can have a significant impact in localizing the computation, in minimizing synchronization (communication) costs, in enhancing reliability (via strategic replication policies), and in ensuring a balanced workload or enhancing the available bandwidth from massive storage devices (e.g. disk arrays).