Flattening Trees

Gabriele Keller and Manuel M. T. Chakravarty

In David Pritchard and Jeff Reeve, editors, Euro-Par'98, Parallel Processing, pp 709-719, LNCS 1470, Springer-Verlag, 1998.

Nested data-parallelism can be efficiently implemented by mapping it to flat parallelism using Blelloch & Sabot's flattening transformation. So far, the only dynamic data structure supported by flattening are vectors. We extend it with support for user-defined recursive types, which allow parallel tree structures to be defined. Thus, important parallel algorithms can be implemented more clearly and efficiently.

PostScript version (10 pages).

This page is part of Manuel Chakravarty's WWW-stuff.