## 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
*N*^{1/2} x
*N*^{1/2} x
*N*^{1/2}.
We generalise the result to a *k*-D RM of size
*N*^{1/(k-1)} x
*N*^{1/(k-1)} x ... x
*N*^{1/(k-1)}.

## Comments

Related papers are
[171,
176,
184,
186,
190,
191,
195].
Go to next publication

Return to Richard Brent's index page