Abstract |
---|
Blelloch & Sabot's flattening transformation reduces nesteddata-parallelism to flat parallelism; therefore, it is a key technique forthe efficient implementation of nested parallelism on a wide range ofparallel machines. So far, the only dynamic data structure supported byflattening are vectors. This paper extends flattening with support foruser-defined recursive types, which allow to define parallel treestructures. As a result, important parallel algorithms can be implementedmore clearly and efficiently. We formalize flattening as a programtransformation and provide empirical evidence for the efficiency of ourproposal. |
Contact |
Gabriele Keller Institute of Information Sciences and Electronics,Tennoudai 1-1-1,University of Tsukuba,Tsukuba, Ibaraki 305-8573,Japan, keller@greyarea.is.tsukuba.ac.jp |