Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Data Parallel Programming for Irregular Tree Computations

Leo A. Meyerovich, Todd Mytkowicz, and Wolfram Schulte

Abstract

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.

Details

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