ANU Computer Science Technical Reports
TR-CS-98-02
M. Manzur Murshed and Richard P. Brent.
Adaptive AT^2 optimal algorithms on reconfigurable meshes.
March 1998.
[POSTSCRIPT (165401 bytes)] [PDF (290764 bytes)]
Abstract: Recently a few 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 AT^2 optimal. In this paper we have introduced,
for the first time, the idea of "adaptive" algorithm which runs on RM of
variable sizes without compromising the AT^2 optimality. We have supported
our idea by developing adaptive algorithms for sorting items and computing
the contour of maximal elements of a set of planar points on RM. We have also
conjectured that to obtain an AT^2 algorithm to solve a problem of size n
with I(n) information content on an RM of size p × q where pq =
kI(n), it is not necessary to form buses of length > k. This conjecture
has been supported by deriving a new algorithm, from our adaptive algorithm,
to compute the contour of maximal elements of n planar points on an
ordinary mesh of size sqrt(n) × sqrt(n).
Technical Reports <Technical-DOT-Reports-AT-cs-DOT-anu.edu.au>
Last modified: Tue May 31 12:56:00 EST 2011