Adaptive AT2 optimal algorithms on reconfigurable meshes
186. M. M. Murshed and R. P. Brent,
Adaptive AT2
optimal algorithms on reconfigurable meshes,
J. Parallel Computing 26 (2000), 1447-1458.
Preliminary version in
Proc. Tenth IASTED Conference on Parallel and Distributed Computing
and Systems, Las Vegas, Nevada, Oct. 1998, 190-195.
Extended version available as
Technical Report TR-CS-98-02,
Computer Sciences Lab, ANU, March 1998, 15 pp.
Paper:
pdf (129K),
ps (94K).
Preliminary version:
pdf (87K),
ps (76K).
Technical Report:
pdf (213K),
ps (163K).
Abstract
Recently self-simulation algorithms have been developed to execute
algorithms on a reconfigurable mesh (RM) of size smaller than recommended
in those algorithms. Optimal slowdown, in self-simulation, has been
achieved with the compromise that the resultant algorithms fail to remain
AT2 optimal. In this paper we introduce, for the first time,
the idea of an adaptive algorithm which runs on RM of variable
sizes without compromising the AT2 optimality. We support our
idea by developing adaptive algorithms for sorting items and computing
the contour of maximal elements of a set of planar points on RM.
Comments
The result was improved in [191].
Related papers are
[176,
184,
190,
195].
Go to next publication
Return to Richard Brent's index page