Computing Downwards Accumulations on Trees Quickly
Jeremy Gibbons
Abstract
\em 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 \em 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 \em logarithm\/ of the depth of the tree, on a CREW PRAM machine.
Details
| Journal |
Theoretical Computer Science |
| Note |
Earlier version appeared in Proceedings of the 16th Australian Computer Science Conference‚ Brisbane‚ 1993 |
| Number |
1 |
| Pages |
67–80 |
| Volume |
169 |
| Year |
1996 |
Links
Related pages
|
People |
|
|
Activities |