Metrics
2 readers on Mendeley
Journal article
Optimal Parallel Prefix on Mesh Architectures
Parallel algorithms and applications, Vol.1(3), pp.191-209
01/01/1993
Metrics
46 Record Views
Abstract
Algorithms for efficient implementation of computation of prefix produce on mesh-connected processor arrays are presented. Assuming that an arithmetic operation takes unit time and communication/computation ratio for a single input item is τ, we show that the prefixes of n items can be computed in time 2τ√n + O(log n) on a square mesh with n processors. If n processors are configured as a disc with respect to the Manhattan metric, then the parallel time for the problem becomes √2τ√n + O(√τ
4
√n. We show that both of these algorithms are asymptotically optimal.
Related links
Details
- Title
- Optimal Parallel Prefix on Mesh Architectures
- Publication Details
- Parallel algorithms and applications, Vol.1(3), pp.191-209
- Resource Type
- Journal article
- Publisher
- Taylor & Francis Group
- Copyright
- © Taylor & Francis
- Identifiers
- 99380178126506600
- Academic Unit
- Computer Science; Hal Marcus College of Science and Engineering
- Language
- English