Accelerating Graph Applications on Parallel Heterogeneous Architectures

#parallel #computing #graph #algorithms #performance

How will computing power increase in the future?  We need to use parallelism more effectively.

Innovative parallel system designs like GPUs and the TPU have achieved significant performance improvements.  However, a closer look will reveal that these gains have largely been achieved on “dense” computations, in which data is accessed in regular, predictable patterns.  But we also need to achieve improvements in “sparse” graph computations, because these computations are a natural way to represent and analyze important data structures, such as social networks and consumer behaviors.

This talk will present some of the current work at Princeton on parallel heterogeneous systems – and how to use them to accelerate graph applications.  One part of this effort has aimed at optimizing graph applications for a prevalent existing system: the CPU/GPU SoC.  A domain specific language and an optimizing compiler have been created to conduct a large empirical study on a range of GPU systems.  This talk will present some key results of the study, including significant speedups, horrible slowdowns, and a new robust definition of performance portability. 

Another part of the research program is the design of a new parallel heterogeneous architecture, with reconfigurable and programmable communication structures tailored for graph computations.  This system addresses key memory bottlenecks by pairing up the simple cores of a many-core system in a producer/consumer relationship.  Simulation results show that our design is significantly more efficient (up to 20x) than existing processors.