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 `manip...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Published: |
1996
|
| _version_ | 1826297763203121152 |
|---|---|
| author | Gibbons, J |
| author_facet | Gibbons, J |
| author_sort | Gibbons, J |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T04:36:37Z |
| format | Journal article |
| id | oxford-uuid:d0253f1e-4ebb-4a68-bef2-b2e7bece61eb |
| institution | University of Oxford |
| last_indexed | 2024-03-07T04:36:37Z |
| publishDate | 1996 |
| record_format | dspace |
| spelling | oxford-uuid:d0253f1e-4ebb-4a68-bef2-b2e7bece61eb2022-03-27T07:47:53ZComputing Downwards Accumulations on Trees QuicklyJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d0253f1e-4ebb-4a68-bef2-b2e7bece61ebDepartment of Computer Science1996Gibbons, JDownwards 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. |
| spellingShingle | Gibbons, J Computing Downwards Accumulations on Trees Quickly |
| title | Computing Downwards Accumulations on Trees Quickly |
| title_full | Computing Downwards Accumulations on Trees Quickly |
| title_fullStr | Computing Downwards Accumulations on Trees Quickly |
| title_full_unstemmed | Computing Downwards Accumulations on Trees Quickly |
| title_short | Computing Downwards Accumulations on Trees Quickly |
| title_sort | computing downwards accumulations on trees quickly |
| work_keys_str_mv | AT gibbonsj computingdownwardsaccumulationsontreesquickly |