Technology trends suggest that future machines will rely
on parallelism to meet increasing performance requirements. To aid in programmer productivity and application performance, many
parallel programming models provide communication building
blocks called collective communication. These
operations, such as Broadcast, Scatter, Gather, and Reduce, abstract
common global data movement patterns behind a simple library
interface allowing the hardware and runtime system to optimize them for performance and scalability.
We consider the problem of optimizing collective communication in Partitioned Global Address Space (PGAS) languages. Rooted in traditional
shared memory programming models, they deliver the benefits of
sophisticated distributed data structures using language extensions
and one-sided communication.
One-sided communication allows one processor to directly read and
write memory associated with another.
Many popular PGAS language implementations share a common runtime
system called GASNet for implementing such communication. To provide a highly scalable
platform for our work, we present a new implementation of
GASNet for the IBM BlueGene/P, allowing GASNet to scale to tens of thousands of processors.
We demonstrate that PGAS languages are highly scalable and that
the one-sided communication within them is an efficient and
convenient platform for collective communication. We show how to use one-sided communication to achieve 3x improvements in the latency and
throughput of the collectives over standard message passing implementations.
Using a 3D FFT as a representative communication
bound benchmark, for example, we see a 17% increase in performance on 32,768
cores of the BlueGene/P and a 1.5x improvement on 1024 cores of the CrayXT4. We also show how the
automatically tuned collectives can deliver more than an order of
magnitude in performance over existing implementations on shared
There is no obvious
best algorithm that serves all machines and usage patterns
demonstrating the need for tuning and we thus build
an automatic tuning system in GASNet
that optimizes the collectives for a variety of large scale
supercomputers and novel multicore architectures. To understand the large search space, we
construct analytic performance models use them to minimize the
overhead of autotuning. We demonstrate that autotuning is
an effective approach to addressing performance optimizations on complex parallel systems.