Balanced Trees Inhabiting Functional Parallel Programming

摘要

Divide-and-conquer is an important technique in parallel programming. However, algebraic data structures do not fit divide-and-conquer parallelism. For example, the usual pointer-based implementation of lists cannot efficiently be divided at their middle, which prevents us from developing list-iterating divide-and-conquer parallel programs. Tree-iterating programs possibly face a similar problem, because trees might be ill-balanced and list-like shapes. This paper examines parallel programming based on balanced trees: we consider balanced-tree structures and develop recursive functions on them. By virtue of their balancing nature, either bottom-up or top-down recursive functions exploit divide-and-conquer parallelism. Our main contribution is to demonstrate the promise of this approach. We propose a way of systematically developing balanced trees from parallel algorithms, and then, we show that efficient parallel programs on them can be developed by equational reasoning powered by Reynolds' relational parametric-ity. We consider functions that operate either lists or binary trees, and show that our methods can uniformly deal with both cases. The developed parallel programs are purely functional, correct by construction, and sometimes even simpler than known algorithms.