Parallel algorithms for tree accumulations

doi:10.1016/j.jpdc.2004.09.001

2005-01-01

PRE

Fatih Erdoğan Sevilgen

Srinivas Aluru

DOI：10.1016/j.jpdc.2004.09.001

原文链接

原文求助

摘要

En 中文

Accumulations are abstract operations on trees useful in many applications involving trees. The upward accumulation problem is to aggregate data in the subtree under each node of the tree. The downward accumulation problem is to aggregate data at all the ancestors of each node. In this paper, we present parallel algorithms for these problems on coarse-grained distributed memory parallel computers. We first show that when the accumulation function and the set of possible values at nodes of the tree form an Abelian (commutative) group, this problem can be solved by a remarkably simple algorithm-Upward accumulation takes O ( n/p + taup + mun/p) time, where n is the number of nodes in the tree, p is the number of processors, T is the communication latency and p is the transfer time per unit message size. Downward accumulation takes O (n/p + (tau + mu) log P) time, making it very communication efficient. For the general case, p n we present upward and downward accumulation algorithms that run in O ( n/p log n + taup log n + mun/p log n) time. (C) 2004 Elsevier Inc. All rights reserved.

Keyword:

upward accumulation

downward accumulation

tree contraction

parallel prefix

AI总结

对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

Journal of Parallel and Distributed Computing

IF:

论文数:

3.8K

被引数:

4.8K

机构

暂无机构信息

引用论文

Detection of Superoxide Ions from Photoexcited Semiconductors in Non-Aqueous Solvents Using the ESR Spin-Trapping Technique

Bulletin of the Chemical Society of Japan

IF0

2006-08-16

PREAI

Hiroyuki Noda; Kazuo Oikawa; Hiroaki Ohya-Nishiguchi; Hitoshi Kamada

High-sensitivity Gd³⁺–Gd³⁺ EPR distance measurements that eliminate artefacts seen at short distances

Magnetic Resonance

IF0

2020-12-09

OAAI

Hassane EL Mkami; Robert I. Hunter; Paul A. S. Cruickshank; Michael J. Taylor; Janet E. Lovett; Akiva Feintuch; Mian Qi; Adelheid Godt; Graham M. Smith

Medial Olivocochlear-Induced Transient-Evoked Otoacoustic Emission Amplitude Shifts in Individual Subjects

Journal of the Association for Research in Otolaryngology

IF0

2013-08-28

OAAI

Shawn S. Goodman; Ian B. Mertes; James D. Lewis; Diana K. Weissbeck

Practical parallel list ranking

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING

IF4

1999-02-01

PREAI

Sibeyn, JF; Guillaume, F; Seidel, T