Data Parallel Programming for Irregular Tree Computations

Leo A. Meyerovich, Todd Mytkowicz, and Wolfram Schulte


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,



Publication typeInproceedings
Published inHotPAR
> Publications > Data Parallel Programming for Irregular Tree Computations