𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parallel Implementation of Tree Skeletons

✍ Scribed by D.B. Skillicorn

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
277 KB
Volume
39
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

Trees are a useful data type, but they are not routinely included in parallel programming systems, in part because their irregular structure makes partitioning and scheduling difficult. We present a method for algebraically constructing implementations of tree skeletons, high-level homomorphic operations that execute in parallel. Many computations on binary trees can be performed in O(log n) parallel time using n processors, even taking account of communication costs. We extend these results to trees with arbitrary and variable degree. Then we show that it is possible to implement a distributed version of homomorphisms on binary trees, taking O(n/p ؉ log 2 p) parallel time on p Ͻ n processors, for trees of any skew and taking full account of communication costs. Under slightly stronger restrictions on the underlying functions, this can be improved to O(n/p ؉ log p). Furthermore, the technique for deriving distributed versions is algebraic, allowing the automatic generation of code for SPMD and data-parallel architectures.

📜 SIMILAR VOLUMES

Parallel Shortcutting of Rooted Trees
Parallel Shortcutting of Rooted Trees
✍ Mikkel Thorup 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 305 KB

First it is shown that for any rooted tree T with n vertices, and parameter m G n, there is a ''shortcutting'' set S of at most m arcs from the transitive closure Ž . T\* of T such for any ¨, w g T \*, there is a dipath in T j S from ¨to w of length Ž Ž .. Ž O ␣ m, n . An equivalent result has been

Towards a complete framework for paralle
Towards a complete framework for parallel implementation of logic languages: the data parallel implementation of SEL
✍ Succi, Giancarlo; Uhrik, Carl 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 784 KB

Although logic languages, due to their nnn-declarative nature, are widely proclaimed to be conducive in theory to parallel implementation, in fact there appears to be insufficient practical evidence to stimulate further developments in this field. The paper puts forward various complications which a

A Faster Implementation of a Parallel Tr
A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs
✍ Sun-yuan Hsieh; Chin-Wen Ho; Tsan-sheng Hsu; Ming-Tat Ko; Gen-Huey Chen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 261 KB

We consider a parallel tree contraction scheme which in each contraction phase Ž . Ž . removes leaves and nodes in the maximal chains. Let T n and P n denote the time and processor complexity required to compute the all nearest smaller values Ž . ANSV and the minimum of n values for input elements d

Parallel implementation of the ADI-FDTD
Parallel implementation of the ADI-FDTD method
✍ T. Stefański; T. D. Drysdale 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB

## Abstract We present a parallel implementation of the three‐dimensional alternating direction implicit finite‐difference time‐domain (ADI‐FDTD) method in Cartesian coordinates using the message passing interface (MPI) library. Parallel implementations not only speed up computations but also incre

Uniform Generation of Binary Trees in Pa
Uniform Generation of Binary Trees in Parallel
✍ M.D. Atkinson; J.R. Sack 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 245 KB

An unbiased random generator for binary trees is developed for a CREW-PRAM. The generator is capable of generating a binary tree on \(n\) nodes in time \(O(\log n)\), space \(O(n)\), with \(O(n)\) processors; it is also capable of generating various related combinatorial objects. O 1994 Academic Pre