Computing downwards accumulations on trees quickly
Downwards passes on binary trees are essentially functions which pass information down a tree, from the root towards the leaves. Under certain conditions, a downwards pass is both 'efficient' (computable in a functional style in parallel time proportional to the depth of the tree) and ...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
1996
|
| Summary: | Downwards passes on binary trees are essentially functions which pass information down a tree, from the root towards the leaves. Under certain conditions, a downwards pass is both 'efficient' (computable in a functional style in parallel time proportional to the depth of the tree) and 'manipulable' (enjoying a number of distributivity properties useful in program construction); we call a downwards pass satisfying these conditions a downwards accumulation. In this paper, we show that these conditions do in fact yield a stronger conclusion: the accumulation can be computed in parallel time proportional to the logarithm of the depth of the tree, on a CREW PRAM machine. |
|---|