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).


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.


The result was improved in [191]. Related papers are [176, 184, 190, 195].

Go to next publication

Return to Richard Brent's index page