System for sorting in a multiprocessor environment
AssigneeCybersales, Inc.
InventorPaul S. Silver
Life of this patent
Estimating the term…
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.
Claims13
In a sorting network of the type employing a parallel processor configured to sort a set of data elements by mapping a shuffle-exchange network onto a Batcher network, said sorting network employing a control mask including a set of mask bits indicative of whether or not to exchange given pairs of said data elements, and said sorting network employing a number of redundant shuffle operations to obtain permutations of said data elements as required by said Batcher sorting network, the improvement comprising shuffling said control mask each time a redundant shuffle operation is performed on said data elements.
A method for sorting a data set of 2.sup.m keys in a parallel processing structure, wherein m is a nonzero positive integer, said parallel processing structure comprising, in combination, a computer system having operative units configured to simultaneously perform a plurality of data operations, and a memory shared by each of said operative units, said method comprising:
- (a) generating a control mask having a plurality of mask bits indicating whether to exchange said keys in each of a plurality of pairs of said keys;
- (b) applying a compare-exchange operation to each pair of said keys in a 1-apart permutation, to exchange said keys in each pair to the extent indicated by said mask bits;
- (c) updating said control mask;
- (d) for a first number of repetitions:
- (i) redundantly shuffling said keys, and
- (ii) redundantly shuffling said control mask;
- and
- (e) for a second number of repetitions:
- (i) shuffling said keys,
- (ii) shuffling said control mask, and
- (iii) applying said compare-exchange operation to a plurality of pairs of said keys, to exchange said keys in each pair as indicated by said mask bits.
A method for sorting a data set of 2.sup.m keys in a parallel processing structure, said parallel processing structure comprising, in combination, a computer system having operative units configured to simultaneously perform a plurality of data operations, and a memory shared by each of said operative units, said method comprising:
- (i) generating a control mask having a plurality of mask bits that indicate whether to exchange said keys in each of a plurality of pairs of said keys:
- (a) initiating a control vector equal to 0, 1, 0, 1, . . . , 0, 1,
- (b) initiating a control mask equal to 0, 1, 0, 1, . . . , 0, 1, and
- (c) for m repetitions, modifying said control mask by XORing said control mask with said control vector and shuffling said control mask;
- (ii) applying a compare-exchange operation to each pair of said keys to exchange said keys in each pair as indicated by said mask bits;
- and
- (iii) performing the following for m-1 repetitions, each repetition defining a repetition number x:
- (a) shuffling said control vector,
- (b) modifying said control mask by XORing said control mask with said control vector,
- (c) for m-1-x repetitions, shuffling said keys and shuffling said control mask, and
- (d) for two repetitions, shuffling said keys, shuffling said control mask, and applying a compare-exchange operation to said keys.
A system for sorting a set of data elements, said system comprising, in combination,
- a parallel processor having operative units configured to simultaneously perform a plurality of data operations;
- a memory shared by each of said operative units;
- a control mask comprising a set of mask bits indicating whether to exchange said data elements in each of a plurality of pairs of said data elements;
- and
- a shuffle routine stored in said memory and executable by said parallel processor, said shuffle routine redundantly shuffling said data elements a number of times and redundantly shuffling said mask bits each time said data elements are redundantly shuffled.
An apparatus for sorting data set of 2.sup.m keys, said apparatus comprising:
- a parallel processing structure having a shared memory structure including a memory for storing a set of machine language instructions executable by said parallel processor;
- a control mask generation routine stored in said memory and executable by said microprocessor, for generating a control mask having a plurality of mask bits indicating whether to exchange said keys in each of a plurality of pairs of said keys;
- and
- a redundant shuffle routine stored in said memory and executable by said parallel processing structure, for redundantly shuffling said keys a number of times and for redundantly shuffling said mask bits each time said keys are redundantly shuffled.
An apparatus for sorting a data set of 2.sup.m keys, comprising:
- (i) a parallel processor having a shared memory structure including a memory for storing a set of machine language instructions executable by said parallel processor;
- (ii) a first routine stored in said memory and executable by said parallel processor for generating a control mask having a plurality of mask bits that indicate whether to exchange the keys in each of a plurality of pairs of said keys, said first routine initiating a control vector equal to 0, 1, 0, 1, . . . , 0, 1, initiating a control mask equal to 0, 1, 0, 1, . . . , 0, 1, and, for m repetitions, modifying said control mask by XORing said control mask with said control vector and shuffling said control mask;
- (iii) a second routine stored in said memory and executable by said parallel processor for applying a compare-exchange operation to each pair of said keys and thereby exchanging said keys in each pair to the extent indicated by said mask bits;
- and
- (iv) a third routine stored in said memory and executable by said processor for performing the following for m-1 repetitions, each repetition defining a repetition number x:
- (a) shuffling said control vector,
- (b) modifying said control mask by XORing said control mask with said control vector,
- (c) for m-1-x, shuffling said keys and shuffling said control mask, and
- (d) for two repetitions, shuffling said keys, shuffling said control mask, and applying a compare-exchange operation to said keys.
A computer readable medium having instructions stored thereon for causing a computer to perform a method for sorting a data set of 2.sup.m keys in a parallel processing structure, wherein m is a nonzero positive integer, said parallel processing structure comprising, in combination, a computer system having operative units configured to simultaneously perform a plurality of data operations, and a memory shared by each of said operative units, said method comprising:
- (a) generating a control mask having a plurality of mask bits indicating whether to exchange said keys in each of a plurality of pairs of said keys;
- (b) applying a compare-exchange operation to each pair of said keys in a 1-apart permutation, to exchange said keys in each pair to the extent indicated by said mask bits;
- (c) updating said control mask;
- (d) for a first number of repetitions:
- (i) redundantly shuffling said keys, and
- (ii) redundantly shuffling said control mask;
- and
- (e) for a second number of repetitions:
- (i) shuffling said keys,
- (ii) shuffling said control mask, and
- (iii) applying said compare-exchange operation to a plurality of pairs of said keys, to exchange said keys in each pair as indicated by said mask bits.
A computer readable medium having instructions stored thereon for causing a computer to perform a method for sorting a data set of 2.sup.m keys in a parallel processing structure, said parallel processing structure comprising, in combination, a computer system having operative units configured to simultaneously perform a plurality of data operations, and a memory shared by each of said operative units, said method comprising:
- (i) generating a control mask having a plurality of mask bits that indicate whether to exchange said keys in each of a plurality of pairs of said keys:
- (a) initiating a control vector equal to 0, 1, 0, 1, . . . , 0, 1,
- (b) initiating a control mask equal to 0, 1, 0, 1, . . . , 0, 1, and
- (c) for m repetitions, modifying said control mask by XORing said control mask with said control vector and shuffling said control mask;
- (ii) applying a compare-exchange operation to each pair of said keys to exchange said keys in each pair as indicated by said mask bits;
- and
- (iii) performing the following for m-1 repetitions, each repetition defining a repetition number x:
- (a) shuffling said control vector,
- (b) modifying said control mask by XORing said control mask with said control vector,
- (c) for m-1-x repetitions, shuffling said keys and shuffling said control mask, and
- (d) for two repetitions, shuffling said keys, shuffling said control mask, and applying a compare-exchange operation to said keys.
Dependencies are inferred from the claim text.