ANU Computer Science Technical Reports

TR-CS-98-05

M. Manzur Murshed.
Optimal computation of the contour of maximal elements on constrained reconfigurable meshes.
May 1998.

[POSTSCRIPT (145291 bytes)] [PDF (249177 bytes)] [EPrints archive]

Abstract: The Reconfigurable Mesh (RM) attracted criticism for its key assumption that a message can be broadcast in constant time independent of bus length. To account for this limit Beresford-Smith et al. have recently proposed k-constrained RM where buses of length at most k, a constant, are allowed to be formed. Straightforward simulations of optimal RM algorithms on this constrained RM model are found to be non-optimal. This paper presents two optimal algorithms to compute the contour of maximal elements of a set of planar points. The first algorithm solves this problem of size p in O(p/k) time on an k-constrained RM of size k × p, k <= p, and the second algorithm solves this problem of size n in O(q/k) time on an k-constrained RM of size p × q, p <= q, and pq = kn.

Technical Reports <Technical-DOT-Reports-AT-cs-DOT-anu.edu.au>

Last modified: Tue May 31 12:56:00 EST 2011