nyan@cs.UAlberta.CA (Nyan) (03/20/91)
Many people have expressed interest in the topic and below
are some of the papers :
** Shi, Hanmao, "Parallel Sorting on Multiprocessor
Computers", MSc Thesis, Dept of Comp Sci, U of Alberta.
A new algorithm called PSRS "Parallel Sorting
by Regular Sampling " is developed.(include coding)
Parallel Sorting Algorithm by Akl, S. G. 1985
The Design and Analysis of Parallel Algorithm - Akl
Fast Parallel Sorting Algm - Hirschberg, Comm of ACM
Vol 21, No 8 August 1978 pp. 657 - 661
Lakshmivarahan, S. , "Parallel Sorting Algorithm "
Advances in Computers, 1984 pp. 295 - 354
Preparata, "New Parallel Sorting Schemes "
IEEE Trans on Computers Vol C-27, 1978 pp. 669-673
Batcher K E, "Sorting networks and their application "
Proceedings of the AFIP 1968 pp. 307 - 314
Kumar M, "An Efficient Implementation of Batcher' Odd-Even
Merge Algorithm and Its Application in Parallel Sorting Schemes"
IEEE Trans on Computers Vol C-32, No 3 Mar 1983, pp 254-264.
Baudet G & Stevenson D, "Optimal Sorting Algorithms for Parallel
Computers", IEEE Trans on Computers Vol. C-27 No 1 Jan 1978 pp 84-87.
Wagar B, "Hyperquicksort : A fast Sorting Algorithm for Hypercubes"
Hypercube Multiprocessors, M. T. Heath, SIAM, pp 292 - 299 1987
Quinn M J "Parallel Sorting Algorithms for tightly coupled
Multiprocessor", Parallel computing 6, pp 349 - 357, 1988.
Rotem D & at el, "Distribyted Sorting " IEEE Trans on Computers
Vol 34 No 4 pp 372 - 375 , 1985
Evans D J & Yousif N Y "The Parallel Neighbour Sort and Two-way
Merge Algorithm", Parallel Computing, Vol 3, pp 85 -90, 1986.
** Parallel Quicksort. The result is that it demonstrates a successful linear
speedup parallel sort workable on parallel multiprocessors with a large number
of processors.
--
=========================== MODERATOR ==============================
Steve Stevenson {steve,fpst}@hubcap.clemson.edu
Department of Computer Science, comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabelldwns@doc.ic.ac.uk (David W N Sharp) (03/26/91)
In article 2281 a list of parallel sorting references was given.
Readers may also be interested in the massively parallel quicksort algorithm
described in
D.W.N. Sharp & M.D.Cripps, "A Parallel Implementation Strategy for Quicksort,"
Proc. 1989 IEE International Symposium on Computer Architecture and Digital
Signal Processing, Hong Kong, 11-14 October 1989, pp.305-309.
The algorithm is also explained (after a synthesis of it by
program transformation) in chapter 6 of
D.W.N Sharp, "Functional language Program Transformation For Parallel Computer
Architectures," Ph.D. thesis, Dept. of Computing, Imperial College, London,
Dec. 1990.
David Sharp.
dwns@uk.ac.ic.doc
--
=========================== MODERATOR ==============================
Steve Stevenson {steve,fpst}@hubcap.clemson.edu
Department of Computer Science, comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell