ISSN:
1573-7640
Keywords:
Parallel algorithms
;
clustering
;
transitive closure
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Practical parallel algorithms, based on classical sequential Union-Find algorithms for computing transitive closures of binary relations, are described and implemented for both shared memory and distributed memory parallel computers. By practical algorithms, we mean algorithms that are efficient for parallel systems with bounded numbers of processors as opposed to algorithms where the number of processors grows with the problem size. Transitive closures are useful for decomposing many applications problems into independent subproblems. The implementations were on an ENCORE Multimax shared memory machine and an NCUBE hypercube. Our implementations indicate that transitive closure computations are intrinsically difficult for distributed memory parallel machines because of the need for global information. By contrast, our results for shared memory machines exhibited excellent speedups.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01383882
Permalink
