Parallel Program = Operator + Schedule + Parallel Data Structures
Big Data Analytics
Programming Models & Languages
System Software & Runtime Systems
TimeWednesday, June 27th2:51pm - 3:13pm
DescriptionMulticore and manycore processors are now ubiquitous, but
parallel programming remains as difficult as it was 30-40
years ago. During this time, our community has explored
many promising approaches including functional and dataflow
languages, logic programming, and automatic parallelization
using program analysis and restructuring, but none of these
approaches has succeeded except in a few niche application
In this talk, I will argue that these problems arise largely
from the computation-centric foundations and abstractions
that we currently use to think about parallelism. In their
place, I will propose a novel data-centric foundation for
parallel programming called the operator formulation in which
algorithms are described in terms of actions on data.
The operator formulation shows that a generalized form of
data-parallelism called amorphous data-parallelism is ubiquitous
even in complex, irregular applications such as mesh
generation/refinement/partitioning and SAT solvers.
Regular algorithms emerge as a special case of irregular ones,
and many application-specific optimization
techniques can be generalized to a broader context.
The operator formulation also leads to a structural analysis
of algorithms called TAO-analysis that provides implementation
guidelines for exploiting parallelism efficiently.
Finally, I will describe a system called Galois based on these ideas for
exploiting amorphous data-parallelism on multicores and GPUs.