Mapping Divide-and-Conquer Algorithms to Parallel Architectures
Loading...
Date
1990-01-19
Authors
Lo, V.
Rajopadhye, S. V.
Gupta, S.
Keldsen, D.
Mohamed, M.
Telle, Jan
Journal Title
Journal ISSN
Volume Title
Publisher
University of Oregon
Abstract
In this paper, we identify the binomial tree as an ideal computation
structure for parallel divide-and-conquer algorithms. We show its superiority
to the classic full binary tree structure with respect to speedup
and efficiency. We also present elegant and efficient algorithms for mapping
the binomial tree to two interconnection networks commonly used in
multicomputers, namely the hypercube and the two-dimensional mesh.
Our mappings are optimal with respect to both average dilation and
link contention. We discuss the practical implications of these results for
message-passing architectures using store-and-forward routing vs. those
using wormhole routing.
Description
24 pages
Keywords
binomial tree, full binary tree structure, average dilation, link contention