PARALLEL IMPLEMENTATION OF TREE SKELETONS

Trees are a useful data type, but they are not routinely included in p arallel programming systems, in part because their irregular structure makes partitioning and scheduling difficult. We present a method for algebraically constructing implementations of tree skeletons, high-lev el homomorphic operations that execute in parallel. Many computations on binary trees can be performed in O(log n) parallel time using n pro cessors, even taking account of communication costs. We extend these r esults to trees with arbitrary and variable degree. Then we show that it is possible to implement a distributed version of homomorphisms on binary trees, taking O(n/p + log(2)p) parallel time on p < n processor s, for trees of any skew and taking full account of communication cost s. Under slightly stronger restrictions on the underlying functions, t his can be improved to O(n/p + log p). Furthermore, the technique for deriving distributed versions is algebraic, allowing the automatic gen eration of code for SPMD and data-parallel architectures. (C) 1996 Aca demic Press, Inc.