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 ...
| 第一著者: | |
|---|---|
| フォーマット: | Journal article |
| 言語: | English |
| 出版事項: |
1996
|
| _version_ | 1826286477635485696 |
|---|---|
| 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-07T01:44:21Z |
| format | Journal article |
| id | oxford-uuid:97eaeb3d-ee8c-41c7-b8dc-00cb9120e865 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:44:21Z |
| publishDate | 1996 |
| record_format | dspace |
| spelling | oxford-uuid:97eaeb3d-ee8c-41c7-b8dc-00cb9120e8652022-03-27T00:03:15ZComputing downwards accumulations on trees quicklyJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:97eaeb3d-ee8c-41c7-b8dc-00cb9120e865EnglishSymplectic Elements at Oxford1996Gibbons, 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 |