Parallel sorting system to reduce the amount of communication be

Details Parallel sorting system to reduce the amount of communication be Parallel sorting system to reduce the amount of communication be

1995-07-14

1997-04-15

Lall, Parshotam S.

Boots, shoes, and leggings

395800, 364DIG1, 364DIG2, G06F 930

Patent

active

056219083

ABSTRACT:
A parallel sorting system is disclosed, having N (=2.sup.n) processing devices, each of which comprises a sort element storing unit, an inner sorting unit, a transposing unit, and a comparing and substituting unit. In the sort element storing unit, sort elements/N are stored. Sorting process is performed for n stages. In each stage, the inner sorting unit sorts the sort elements, and the transposing unit exchanges sorted elements at a transposing position with another processing device through a network. Thereafter, the comparing and substituting unit compares the two sets of sorts elements. This process sequence is repeated for all stages. And, after the transposing process and the inner sorting process are performed, the sorting process are completed. In this system, the number of communication times is reduced to 2n.

REFERENCES:
patent: 4567572 (1986-01-01), Morris et al.
patent: 4899334 (1990-02-01), Shimizu
patent: 5084815 (1992-01-01), Mazzario
patent: 5121494 (1992-01-01), Dias et al.
patent: 5179699 (1993-01-01), Iyer et al.
patent: 5216420 (1993-06-01), Munter
patent: 5220664 (1993-06-01), Lee
patent: 5307485 (1994-04-01), Bordonaro et al.
patent: 5406556 (1995-04-01), Widjaja
patent: 5440553 (1995-08-01), Widjaja
patent: 5475856 (1995-12-01), Kogge
Bitonic sort on a mesh-connected parallel computer, by Sahni et al. IEEE Jan. 1979, pp. (2-7).
A Parallel Sorting Algorithm on an Eight-Neighbor Processor Array by Takeda et al, IEEE 1992 Publication pp.-456-468.
Sorting in Mesh Connected Multiprocessors by Scherson et al, IEEE 1992 pp.-626-632.
Sorting with Linear Speedup on a Pipelined Hypercube by Doshi et al, 1992 pp. 97-103.
Bitonic sort on a mesh-connected parallel computer, by Sahni et al. IEEE Jan. 1979, pp. (2-7).
Proceedings of the 1991 International Conference on Parallel Processors Aug. 12-16, 1991 by Dr. Wu pp.-I-443-I-450.
An Efficient Multiprocessor Merge Algorithm by Haderle et al IEEE 1990 276-283.
Parallel Sorting of Large Arrays on the MasPar MP-1+ by Smith et al, IEEE 1990 pp. 59-64.
K-Way Bitonic Sort by Nakatani et al, IEEE 1989 pp.-283-288.

Affiliated with

Also associated with

Rating

Parallel sorting system to reduce the amount of communication be does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Parallel sorting system to reduce the amount of communication be, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel sorting system to reduce the amount of communication be will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-369536