System for sorting in a multiprocessor environment

Details System for sorting in a multiprocessor environment System for sorting in a multiprocessor environment

1997-03-27

2000-11-07

Maung, Zarni

Electrical computers and digital processing systems: multicomput

Distributed data processing

370411, G06F 1516, H04L 1228

Patent

active

061449865

ABSTRACT:
An improved system for sorting a data set of 2.sup.m keys in a parallel processor environment is disclosed. The system operatively maps a shuffle-exchange network onto a Batcher sorting network in order to produce a monotonically sorted output set. Complete and efficient sorting is achieved by shuffling a control mask applied to multiple compare-exchange elements when the data set is redundantly shuffled. A further improvement is achieved by employing an unshuffle operation to the data set and/or the control mask when the use of an unshuffle operation would be more expedient than use of a shuffle operation.

REFERENCES:
patent: 4064556 (1977-12-01), Edelberg et al.
patent: 4161036 (1979-07-01), Morris et al.
patent: 4425617 (1984-01-01), Sherwood
patent: 4567572 (1986-01-01), Morris et al.
patent: 4595995 (1986-06-01), Alles
patent: 4628483 (1986-12-01), Nelson
patent: 4727474 (1988-02-01), Batcher
patent: 4734877 (1988-03-01), Sakata et al.
patent: 4761780 (1988-08-01), Bingham et al.
patent: 4799152 (1989-01-01), Chuang
patent: 4905224 (1990-02-01), Lobjinski et al.
patent: 5146590 (1992-09-01), Lorie et al.
patent: 5179699 (1993-01-01), Iyer et al.
patent: 5185886 (1993-02-01), Edem et al.
patent: 5222235 (1993-06-01), Hintz et al.
patent: 5287466 (1994-02-01), Kodama
patent: 5307485 (1994-04-01), Bordonaro et al.
patent: 5319788 (1994-06-01), Canfield et al.
patent: 5392279 (1995-02-01), Taniguchi
patent: 5513371 (1996-04-01), Cypher et al.
patent: 5541914 (1996-07-01), Krishnamoorthy et al.
Batcher, K.E., "Low-cost Flexible Simulation with the Static Perfect Shuffle Network", Fourth Symposium on the Frontiers of Massively Parallel Computation (Cat. No. 92CH3185-6); Oct. 19-21, 1992., IEEE; NASA; McLean, VA, 434-440, (1992).
Batcher, K.E., "Sorting Networks and their Applications", The Proceeding of AFIPS 1968 SJCC, 307-314, (1968).
Stone, H.S., "Parallel Processing with the Perfect Shuffle", IEEE Transactions on Computers, C-20(2), 153-161, (Feb. 1971).

Affiliated with

Also associated with

Rating

System for sorting in a multiprocessor environment does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System for sorting in a multiprocessor environment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for sorting in a multiprocessor environment will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1651929