Maximal contour algorithms on constrained reconfigurable meshes
190.
M. Manzur Murshed and R. P. Brent,
Maximal contour algorithms on constrained reconfigurable meshes,
Proc. 1999 International Conference on Parallel and Distributed
Processing Techniques and Applications
(Las Vegas, Nevada),
CSREA Press, Vol. 4, 1999, 2238-2244.
Paper:
pdf (110K),
ps (98K).
Abstract
The Reconfigurable Mesh (RM) has attracted criticism for its
key assumption that a message can be broadcast in constant time
independent of bus length. To account for this limit,
Beresford-Smith et al have recently proposed the
k-constrained RM model where buses of length at most
k, a constant, are allowed to be formed. Straightforward
simulations of optimal RM algorithms on this constrained RM model
are found to be non-optimal.
This paper presents two optimal algorithms to compute the contour of
maximal elements of a set of planar points on the k-constrained
RM. The first algorithm solves this problem of size p
in O(p/k) time on a k-constrained RM of size
k×p, where k < p.
The second algorithm solves the same problem of size n
in O(q/k) time on a k-constrained RM of size
p×q, where p < q,
and pq = kn.
Comments
Related papers are
[171,
174,
176,
184,
186,
191,
195].
Go to next publication
Return to Richard Brent's index page