Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!gatech!hubcap!landman
From: landman@Sun.COM (Howard A. Landman)
Newsgroups: comp.parallel
Subject: Re: Sorting on NxN Mesh.
Message-ID: <4241@hubcap.UUCP>
Date: 30 Jan 89 13:03:43 GMT
Sender: fpst@hubcap.UUCP
Lines: 30
Approved: parallel@hubcap.clemson.edu

In article <4196@hubcap.UUCP> KOLOUTSAKIS%grcrvax1.bitnet@RELAY.CS.NET (Math Dept U of Crete Greece Michalis Kolountzakis) writes:
>I would appreciate any suggestions, references or solutions for the following
>problem:
>        We have a SIMD, 4-connected, NxN Mesh Connected Computer (MCC) and
>        the following
>        algorithm for sorting on it. ...
>	It is almost obvious that OETS is a sorting algorithm
>        for the sequence of processors but it takes some time to prove that it
>        is linear in N.

However, proving the lower bound is trivial.  If we assume the reverse-ordered
case as input, the sum of the distances from initial to final position is
quadratic in the number of processors, and the rate of decrease in this sum
is at best linear in the number of processors; so the run time must be at best
linear.

>        It is obvious again that it is a sorting algorithm but what is its
>        time complexity? Is it linear ? is the question. I suspect it is not,
>        because if it were no other sorting alg. for the NxN mesh should have
>        been invented; this seems far simpler than any other I have seen.

It's pretty clear that this is no worse than the previous algorithm.  And,
when we attempt the above lower bound, we find that since the sum may decrease
by as much as N*sqrt(N), we can only establish a lower bound of order sqrt(N).
(This bound, by the way, applies to ANY CONCEIVABLE algorithm on the MCC,
not just this one.)  I suspect that 2D OETS actually achieves this lower
bound complexity, which would make it SUB-linear in N.

	Howard A. Landman
	landman@hanami.sun.com