Constant time algorithms for computing the contour of maximal elements
on the reconfigurable mesh
174. M. Manzur
Murshed and R. P. Brent,
Constant time algorithms for computing the contour of maximal elements
on the reconfigurable mesh,
Parallel Processing Letters 8 (1998), 351-361.
A shorter version
appeared in Proc. ICPADS'97,
Seoul, Korea, Dec. 1997, 172-177.
Preliminary version available as
Technical Report TR-CS-97-09,
Computer Sciences Laboratory, ANU, May 1997, 9 pp.
Paper:
pdf (196K),
ps (78K).
Conference Proceedings:
pdf (163K),
ps (69K).
Technical Report:
pdf (274K),
ps (131K).
Abstract
There has recently been an interest in the introduction of reconfigurable
buses to existing parallel architectures. Among them the
Reconfigurable Mesh (RM) draws much attention because
of its simplicity. This paper presents three constant time algorithms
to compute the contour of the maximal elements of N planar
points on the RM. The first algorithm employs an RM of size
N x N while the second one uses a 3-D RM of
size
N1/2 x
N1/2 x
N1/2.
We generalise the result to a k-D RM of size
N1/(k-1) x
N1/(k-1) x ... x
N1/(k-1).
Comments
Related papers are
[171,
176,
184,
186,
190,
191,
195].
Go to next publication
Return to Richard Brent's index page