Data Parallel Programming for Irregular Tree Computations

  • Leo A. Meyerovich ,
  • Todd Mytkowicz ,
  • Wolfram Schulte

HotPAR |

Published by USENIX

The adoption of data parallel primitives to increase
multicore utilization presents an opportunity for aggressive
compiler optimization. We examine computations
over the tree abstract datatype (ADT) in particular.
For better utilization than approaches like flattening,
we argue that transformations should specialize for common
data and computation regularities. For example,
we demonstrate a novel pattern that exploits regularity in
node labeling as a SIMD parallelism opportunity, which
we call SIMTask parallelism. For better applicability, we
argue for better linguistic support of irregularity. For example,
we show how the future primitive might be used
to tolerate occasional data dependencies in an otherwise
associative computation.
We validate our approach on two tree computations:
RepMin, popular in the functional programming community,
and intrinsic widths, a stage of webpage layout in a
prototype web browser. We show speedups over traditional
versions of these computations of 124X and 10X,
respectively.