fpst@hubcap.UUCP (Steve Stevenson) (01/31/89)
>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
halldors@athos.rutgers.edu (Halldorsson) (02/01/89)
In article <4259@hubcap.UUCP> fpst@hubcap.UUCP (Steve Stevenson) writes: > 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. If you are referring to the aforementioned mesh version of OETS, then I'm very interested in seeing those. If you are referring to the plain OETS (also called "Brickwall sort"), then Knuth vol.III discusses it, but I believe it originates with Demuth: Demuth: "Electronic Data Sorting". Ph.D. Dissertation, 1956. Reprinted in IEEE TOC c-34,April 1985, pp.296 It is also discussed fairly well in these overview references: Akl: "Parallel Sorting Algorithms". (Wiley?) 1985 Lakshmivarahan et al: "Parallel Sorting Algorithms", in Advances in Computers, 1984. Kronsjo: "Computational Complexity of Sequential and Parallel Algorithms". Wiley 1985. > Back to the references... Good list of references. I can only add two more on mesh sorting: Kunde: "Routing&Sorting on Mesh-Connected Arrays", VLSI Algorithms & Architecture. Springer LNCS #319 Leighton: "Tight Bounds on the Complexity of Parallel Sorting". STOC '84 Also in IEEE TOC, c-34, 4, April 1985, pp.344 Magnus