Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!gatech!hubcap!fpst
From: fpst@hubcap.UUCP (Steve Stevenson)
Newsgroups: comp.parallel
Subject: Sort on a NxN Processor Array
Message-ID: <4259@hubcap.UUCP>
Date: 31 Jan 89 12:46:36 GMT
Organization: Clemson University, Clemson, SC
Lines: 65
Approved: parallel@hubcap.clemson.edu

>From: KOLOUTSAKIS%grcrvax1.bitnet@RELAY.CS.NET 
>
>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. The algorithm is an extension of the
>       so called "odd-even transposition sorting" (OETS) algorithm for a
>       sequence of N processors:
>
>       P <--> P <--> P <--> ... <--> P
>        0      1      2               N-1
>
> ...rest of the article...
>   
>        Michalis Kolountzakis,
>        Math. Dept, Univ. of Crete, Greece

 have made a list of some of the references that mention sorting on
a Mesh-Connected array of processors. I have no idea how these will 
work on a SIMD constrained system. If you can do something with 
odd -vs- even columns and rows, you may be able to do something with
the Shearsort article. I have seen the (OETS) algorithm called 
"Conways Algorithm" in a few journal articles dealing with formalism
in the form of parallel touring machines, but I cannot trace the
reference. If anyone has references to (OETS) or Conway, please send
it on.

Back to the references...

C. D. Thompson and H. T. Kung, "Sorting on a Mesh-Connected Parallel
Computer," Comm. ACM, V20 (Apr 1977), pp 263-271.

D. Nassimi. and S. Sahni, "Bitonic Sort on a Mesh-Connected
Parallel Computer," IEEE Trans. Comp., V27 #1 (Jan 1979).

P. Chen and M. Nussbaum, "Sorting with Systolic Architecture,"
IEEE Parallel Proc., (1985), pp 865-868.

H. Lang, M. Schimmler, H. Schmeck, and H. Schroder, "Systolic Sorting
on a Mesh-Connected Network," IEEE Trans. Comp., V34 #7 (July 1985),
pp 652-658.

Y. Ma, S. Sen, and I. D. Scherson, "The Distance bound on Mesh
-Connected Processor Arrays is Tight," IEEE Parallel Proc., (1986)
pp 255-263.

K. Sado and Y. Igarashi, "Some Parallel Sorts on a Mesh-Connected 
Processor Array and their Time Efficiency," J. Parallel & Dist. Compu.,
V3 (1986), pp 398-410.

C. P. Schnorr and A. Shamir, "An Optimal Sorting Algorithm For Mesh 
Connected Computers," ACM STOC conference (1986), pp 255-263.

Y. Choi adn M. Malek, "A Fault-Tolerant Systolic Sorter," IEEE Trans.
Comp., V37 #5 (May 1988), pp621-624.

I hope some of this helps.
David.

-- 
Steve Stevenson                            fpst@hubcap.clemson.edu
(aka D. E. Stevenson),                     steve@hubcap.clemson.csnet
Department of Computer Science,            comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell