Partitioning of sorted lists (containing duplicate entries) for multiprocessors sort and merge

• US 6,366,911 B1
• Filed: 09/28/1998
• Issued: 04/02/2002
• Est. Priority Date: 09/28/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Christy, Dan Allan
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Kindred, Alford W.
• Application Number:
  US09/161,788
• Time in Patent Office: 1,282 Days
• Field of Search: 707/1-7, 707/101, 707/102, 707/200, 707/205
• US Class Current: 707/737
• CPC Class Codes: G06F 7/36 Combined merging and sorting
• CPC Class Codes: Y10S 707/968 Partitioning
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

According to a preferred embodiment, a method of sorting a list of elements with duplicate entries using multiple processors is disclosed. Using “P” processors, a list of elements is split into P lists and each processor pre-sorts a list. All pre-sorted lists are lined up to form a partitioning table, with each pre-sorted list making up a column in the table, and the first element from each pre-sorted list making up the first row in the table, and the second element from each pre-sorted list making up the second row, etc. P−1 partition boundary lines are drawn through the partition table to create P equally sized partitions. Each partition boundary line is drawn such that every element below the line has a value larger than any element above the line, and every element above the line has a value smaller than any element below the line. Duplicate elements are uniquely “weighted” during the partitioning process. Thus, with respect to duplicate elements, each partition boundary lines is drawn such that every duplicate element below the line weighs more than any duplicate element above the line, and every duplicate element above the line weighs less than any duplicate element below the line. In this manner, tabularized pre-sorted lists are grouped into P partitions, which are merged and re-sorted into P sorted lists. Finally, the P sorted lists are simply strung together to provide a sorted list of all elements. Maximum use of P processors is obtained, and a near linear improvement in sort time is obtained when adding further processors.

Claims

1. An apparatus for partitioning multiple pre-sorted lists comprising:

at least one processor;

at least one memory coupled to said at least one processor, said at least one memory including a plurality of elements split into a plurality of lists and pre-sorted into a plurality of pre-sorted lists; and

a multi-processor sort application residing in the at least one memory, said multi-processor sort application weighting elements by data value and further uniquely weighting by position value duplicate elements with respect to each other in said plurality of elements and partitioning said plurality of pre-sorted lists based on weighting criteria and partition size criteria, such that said plurality of partitioned pre-sorted lists can be merged, re-sorted, and concatenated together into one sorted list including all elements in said plurality of elements.

2. The apparatus of claim 1 wherein said multi-processor sort application creates a plurality of ordered partitions, each ordered partition in said plurality of ordered partitions including elements that

sort before any non-duplicate elements in any of said plurality of ordered partitions that follow said each ordered partition,

weigh less than any duplicate elements in any of said plurality of ordered partitions that follow said each ordered partition,

sort after any non-duplicate elements in any of said plurality of ordered partitions that precede said each ordered partition, and

weigh more than any duplicate elements in any of said plurality of ordered partitions that precede said each ordered partition.

3. The apparatus of claim 1 wherein each of said duplicate elements in said plurality of elements is weighted uniquely according to which position said each of said duplicate elements occupy among said plurality of pre-sorted and according to what position said each of said duplicate elements occupies within one of said plurality of pre-sorted lists.

4. The apparatus of claim 3 wherein each of said duplicate elements in said plurality of elements is weighted uniquely first according to which position said each of said duplicate elements occupy among said plurality of pre-sorted lists and second according to what position said each of said duplicate elements occupies within one of said plurality of pre-sorted lists.

5. The apparatus of claim 3 wherein each of said duplicate elements in said plurality of elements is weighted uniquely first according to what position said each of said duplicate elements occupies within one of said plurality of pre-sorted lists, and second according to which position said each of said duplicate elements occupy among said plurality of pre-sorted lists.

6. The apparatus of claim 1 wherein each of said duplicate elements in said plurality of elements is weighted uniquely according to what column and row that said each of said duplicate elements occupies in a partitioning table.

7. The apparatus of claim 6 wherein each of said columns of said partitioning table comprises one of said plurality of pre-sorted lists and each of said rows of said partitioning table comprises at least one element from at least one of said plurality of pre-sorted lists.

8. An apparatus for partitioning multiple pre-sorted lists of elements comprising:

least one processor;

at least one memory coupled to said at least one processor;

said at least one memory including a plurality elements including at least one set of duplicate elements, said plurality of elements divided into a plurality of lists and pre-sorted into a plurality of pre-sorted lists; and

a multi-processor sort application residing in said at least one memory, said multi-processor sort application uniquely weighting each duplicate element in said at least one set of duplicate elements, and partitioning said plurality of pre-sorted lists into a plurality of ordered partitions, such that said plurality of ordered partitions can be merged, re-sorted, and concatenated into one sorted list of elements, each ordered partition in said plurality of ordered partition including elements that

sort before any non-duplicate elements in any of said plurality of ordered partitions that follow said each ordered partition,

weigh less than any duplicate elements in any of said plurality of ordered partitions that follow said each ordered partition,

sort after any non-duplicate elements in any of said plurality of ordered partitions that precede said each ordered partition, and

weigh more than any duplicate elements in any of said plurality of ordered partitions that precede said each ordered partition.

9. The apparatus of claim 8 wherein each of said at least one set of duplicate elements is weighted uniquely:

first according to which one of said plurality of pre-sorted lists that said each of said duplicate elements exists; and

second according to what position said each of said duplicate elements occupies within said one of said plurality of pre-sorted lists.

10. The apparatus of claim 8 wherein each of said at least one set of duplicate elements is weighted uniquely:

first according to what position each of said duplicate elements occupies within said one of said plurality of pre-sorted lists; and

second according to which one of said plurality of pre-sorted lists that said each of said duplicate elements exists.

11. A method of partitioning a plurality of elements comprising the steps of:

a) pre-sorting said plurality of elements into a plurality of pre-sorted lists;

b) uniquely weighting each element in each group of duplicate elements with respect to other said duplicate elements in each said group of duplicate elements in said plurality of elements;

c) weighting each non-duplicate element in said plurality of elements by data value; and

d) partitioning said plurality of pre-sorted lists into an upper partition and a lower partition, said upper partition having a predetermined percentage of elements from said plurality of elements, and such that any element in said group of duplicate elements in said upper partition weighs less than any element in said group of duplicate elements in said lower partition and weighs less than any said non-duplicate element in said lower partition.

12. The method of claim 11 wherein the step of partitioning said plurality of elements into an upper and lower partition comprises partitioning said plurality of elements such that:

each element in said upper partition sorts before elements in said lower partition that do not duplicate said each element in said upper partition;

each element in said upper partition weighs less than elements in said lower partition that duplicate said each element in said upper partition;

each element in said lower partition sorts after elements in said upper partition that do not duplicate said each element in said lower partition; and

each element in said lower partition weighs more than elements in said upper partition that duplicate said each element in said lower partition.

13. The method of claim 11 wherein the step of partitioning said plurality of elements into an upper partition and a lower partition comprises the step of drawing a partition boundary line through said plurality of pre-sorted lists such that a predetermined percentage of said elements in said plurality of elements exists in said upper partition.

14. The method of claim 11 wherein the step of uniquely weighting elements in said plurality of elements having duplicate values comprises creating a partition table from said plurality of pre-sorted lists, assigning a row and column number to each element in said partition table, and weighting said duplicate elements with respect to each other in said partition table according to said row and column numbers and globally weighting said non-duplicate elements according to the data value of the element.

15. The method of claim 11 wherein the step of partitioning said plurality of elements into an upper partition and a lower partition comprises the steps of:

a) calculating a magnitude requirement, said magnitude requirement equaling a number of elements that must be moved from said lower partition to said upper partition in order for all non-duplicate elements in said upper partition to sort before non-duplicate elements in said lower partition and for duplicate elements in said upper partition to weigh less than duplicate elements in said lower partition;

b) calculating a partition requirement, said partition requirement equaling a number of elements that must be moved from said lower partition to said upper partition, or from said upper partition to said lower partition, in order for said predetermined percentage of elements to exist in said upper partition; and

c) moving elements between said upper and lower partitions, when moving any of said elements complies with said magnitude requirement and said partition requirement.

16. The method of claim 15 wherein the step of moving elements between said upper and lower partitions comprises:

a) moving a number of elements equal to said magnitude requirement from said lower partition to said upper partition, such elements sorting first amongst all elements in said lower partition, and if there are duplicate elements that sort first to be chosen from in moving said number of elements equal to said magnitude requirement, moving duplicate elements that weigh less than other duplicate elements in said lower partition;

b) moving a number of elements equal to the difference between said magnitude requirement and said partition requirement from said upper partition to said lower partition, if said magnitude requirement exceeds said partition requirement, such elements sorting last amongst all elements in said upper partition and if there are duplicate elements that sort last to be chosen from in moving said number of elements equal to the difference between said magnitude requirement and said partition requirement from said upper partition to said lower partition, moving duplicate elements that weigh more than other duplicate elements in said upper partition; and

c) moving a number of elements equal to the difference between said partition requirement and said magnitude requirement from said lower partition to said upper partition, if said partition requirement exceeds said magnitude requirement, such elements sorting first amongst all elements in said lower partition and if there are duplicate elements that sort first to be chosen from in moving said number of elements equal to the difference between said partition requirement and said magnitude requirement from said lower partition to said upper partition, moving duplicate elements that weigh less than other duplicate elements in said lower partition.

17. A method of partitioning a plurality of pre-sorted elements comprising the steps of:

a) obtaining a fraction of said plurality of pre-sorted elements to assign to an upper partition;

b) obtaining at least one element to be under consideration from said plurality of pre-sorted elements;

c) partitioning said at least one element under consideration into an upper partition and a lower partition, such that said upper partition includes said fraction of said at least one element under consideration, and such that

each element in said upper partition sorts before any element in said lower partition that is not a duplicate of said each element in said upper partition,

each element in said upper partition weighs less than any element in said lower partition that is a duplicate of said each element in said upper partition,

each element in said lower partition sorts after any element in said upper partition that is not a duplicate of said each element in said lower partition, and

each element in said lower partition weighs more than any element in said upper partition that is a duplicate of said each element in said lower partition;

d) obtaining at least one additional element to be under consideration from said plurality of pre-sorted elements; and

e) repeating steps c) and d) until all elements from said plurality of pre-sorted elements have been considered in partitioning said plurality of pre-sorted elements.

18. The method of claim 17 wherein the step of obtaining at least one element to be under consideration from said plurality of pre-sorted elements comprises obtaining at least one element from an initial row of elements in a partitioning table comprised of said plurality of pre-sorted elements.

19. The method of claim 17 wherein the step of partitioning said at least one element under consideration into an upper partition and a lower partition, such that said upper partition includes said fraction of said at least one element under consideration comprises the steps of:

a) calculating a magnitude requirement, said magnitude requirement equaling a number of said at least one element under consideration that must be moved from said lower partition to said upper partition in order for all of said at least one element under consideration in said upper partition to sort before non-duplicate elements in said lower partition and weigh less than duplicate elements in said lower partition;

b) calculating a partition requirement, said partition requirement equaling a number of said at least one element under consideration that must be moved from said lower partition to said upper partition, or from said upper partition to said lower partition, in order for said fraction of elements under consideration to exist in said upper partition; and

c) moving said at least one element under consideration between said upper and lower partitions, when moving any of said at least one element under consideration complies with said magnitude requirement and said partition requirement.

20. The method of claim 19 wherein the step of moving said at least one element under consideration between said upper and lower partitions comprises:

a) moving a number of elements equal to said magnitude requirement from said lower partition to said upper partition, such elements sorting first amongst all elements in said lower partition, and if there are duplicate elements that sort first to be chosen from in moving said number of elements equal to said magnitude requirement, moving duplicate elements that weigh less than other duplicate elements in said lower partition;

b) moving a number of elements equal to the difference between said magnitude requirement and said partition requirement from said upper partition to said lower partition, if said magnitude requirement exceeds said partition requirement, such elements sorting last amongst all elements in said upper partition and if there are duplicate elements that sort last to be chosen from in moving said number of elements equal to the difference between said magnitude requirement and said partition requirement from said upper partition to said lower partition, moving duplicate elements that weigh more than other duplicate elements in said upper partition; and

c) moving a number of elements equal to the difference between said partition requirement and said magnitude requirement from said lower partition to said upper partition, if said partition requirement exceeds said magnitude requirement, such elements sorting first amongst all elements in said lower partition and if there are duplicate elements that sort first to be chosen from in moving said number of elements equal to the difference between said partition requirement and said magnitude requirement from said lower partition to said upper partition, moving duplicate elements that weigh less than other duplicate elements in said lower partition.

21. A program product comprising:

a multi-processor sort application operating on data elements in a plurality of pre-sorted lists, uniquely weighting non-duplicate elements based on data value and further weighting any duplicate elements with respect to each other based on position value among and/or within in said pre-sorted lists and partitioning said plurality of pre-sorted lists based on weighting criteria and partition size criteria, such that said plurality of partitioned pre-sorted lists can be merged, re-sorted, and concatenated together into one sorted list including all elements in said plurality of elements; and

signal bearing media bearing said multi-processor sort application.

22. The program product of claim 21 wherein the signal bearing media comprises transmission media.

23. The program product of claim 21 wherein the signal bearing media comprises recordable media.

24. The program product of claim 21 wherein said multi-processor sort application creates a plurality of ordered partitions, each ordered partition in said plurality of ordered partitions including elements that

sort before any non-duplicate elements in any of said plurality of ordered partitions that follow said each ordered partition,

weigh less than any duplicate elements in any of said plurality of ordered partitions that follow said each ordered partition,

sort after any non-duplicate elements in any of said plurality of ordered partitions that precede said each ordered partition, and

weigh more than any duplicate elements in any of said plurality of ordered partitions that precede said each ordered partition.

25. The program product of claim 21 wherein each of said duplicate elements in said plurality of elements is weighted uniquely according to which position each of said duplicate elements occupies among said plurality of pre-sorted lists and according to what position said each of said duplicate elements occupies within one of said plurality of pre-sorted lists.

26. The program product of claim 25 wherein each of said duplicate elements in said plurality of elements is weighted uniquely first according to which position each of said duplicate elements occupies among said plurality of pre-sorted lists and second according to what position said each of said duplicate elements occupies within one of said plurality of pre-sorted lists.

27. The program product of claim 25 wherein each of said duplicate elements in said plurality of elements is weighted uniquely first according to what position said each of said duplicate elements occupies in one of said plurality of pre-sorted lists, and second according to which position each of said duplicate elements occupies among said plurality of pre-sorted lists.

28. The program product of claim 21 wherein each of said duplicate elements in said plurality of elements is weighted uniquely according to what column and row that said each of said duplicate elements occupies in a partitioning table.

29. The program product of claim 28 wherein each of said columns of said partitioning table comprises one of said plurality of pre-sorted lists and each of said rows of said partitioning table comprises at least one element from at least one of said plurality of pre-sorted lists.

30. A program product comprising:

a multi-processor sort application operating on data elements in a plurality of pre-sorted lists, said multi-processor sort application uniquely weighting non-duplicate elements based on data value and further weighting each duplicate element in at least one set of duplicate elements with respect to each other based on position value among and/or within said pre-sorted lists, and partitioning said plurality of pre-sorted lists based on weighting criteria and partition size criteria into a plurality of ordered partitions, such that said plurality of ordered partitions can be merged, re-sorted, and concatenated into one sorted list of elements, each ordered partition in said plurality of ordered partition including elements that

sort before any non-duplicate elements in any of said plurality of ordered partitions that follow said each ordered partition,

weigh less than any duplicate elements in any of said plurality of ordered partitions that follow said each ordered partition,

sort after any non-duplicate elements in any of said plurality of ordered partitions that precede said each ordered partition, and

weigh more than any duplicate elements in any of said plurality of ordered partitions that precede said each ordered partition; and

signal bearing media bearing the at least one signal provider.

31. The program product of claim 30 wherein the signal bearing media comprises transmission media.

32. The program product of claim 30 wherein the signal bearing media comprises recordable media.

33. The program product of claim 30 wherein each of said at least one set of duplicate elements is weighted uniquely:

first according to which position each of said duplicate elements occupy among said plurality of pre-sorted lists; and

second according to what position said each of said duplicate elements occupies within said one of said plurality of pre-sorted lists.

34. The program product of claim 30 wherein each of said at least one set of duplicate elements is weighted uniquely:

first according to what position each of said duplicate elements occupies within said one of said plurality of pre-sorted lists; and

second according to which position each of said duplicate elements occupies among said plurality of pre-sorted lists.