EP0378038A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Partitioning of sorted lists for multiprocessor sort and merge
Assignee: International Business Machines Corp
•
Filing: 1989-12-06
•
Granted: —
•
Expires: 2009-12-06
Abstract
Abstract Any number of sorted lists are efficiently partitioned into P lists, where P represents the number of processors available to sort the resulting lists. When given a large list to sort, the list is initially divided into P lists, and each processor sorts one of these lists. The lists are then exactly partitioned so that each of the elements in the new consecutive partitioned lists have values no smaller than any of the elements in the lists before it, nor larger than any of the elements in the list following it. Partitioning is done by P-1 processors. Each of the processors successively considers selected rows of elements from the sorted lists, and moves a partition boundary based on an element magnitude requirement and a partition size requirement. The new partitioned lists are then merged by the P processors, and simply strung together to provide a sorted list of all the ;elements.
Inventors
- 👤 Balakrishna Raghavendra Iyer
- 👤 Gary Ross Ricard
- 👤 Peter Joseph Varman
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-31 20:20
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F7/36; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
161 words
A method of partitioning P sorted lists by L-1 processors into L partitions, where P is greater than 2 and L is greater than or equal to 2, and each successive partition of elements contains only elements having a value greater than all the elements of the preceding partition, the method comprising the steps at each processor of: a) selecting at least one row of elements from the lists for consideration; b) fixing a partition boundary near the middle row of elements; c) determining the maximum value of all the elements under consideration above the partition boundary; d) determining the elements under consideration below the partition boundary that are less than the maximum value; e) moving elements about the boundary based on the size of the partition and the values of the elements under consideration; and f) repeating steps a, c, d, and e until successive rows have been considered, and the partitions each contain substantially the same number of elements.
Claim 2
Independent Claim
161 words
A method of partitioning P sorted lists by L-1 processors into L partitions, where P is greater than 2 and L is greater than or equal to 2, and each successive partition of elements contains only elements having a value greater than all the elements of the preceding partition, the method comprising the steps at each processor of: a) selecting at least one row of elements from the lists for consideration; b) fixing a partition boundary near the middle row of elements; c) determining the maximum value of all the elements under consideration above the partition boundary; d) determining the elements under consideration below the partition boundary that are less than the maximum value; e) moving elements about the boundary based on the size of the partition and the values of the elements under consideration; and f) repeating steps a, c, d, and e until successive rows have been considered, and the partitions each contain substantially the same number of elements.
Claim 3
Dependent Claim
33 words
The method of claim 1 wherein the first row of elements selected has an index which is the greatest integer power of 2 less than the number of elements in the longest list.
Claim 4
Dependent Claim
53 words
The method of claim 2 wherein the next elements selected for consideration when steps a, c, d, and e are repeated include the two rows having indexes halfway between the index of the first row and zero, and halfway between the index of the first row and the next higher power of two.
Claim 5
Dependent Claim
30 words
The method of claim 2 wherein each repetition of steps a, c, d, and e result in the selection of all elements which lie halfway between the elements previously considered.
Claim 6
Dependent Claim
45 words
The method of claim 1 wherein the elements are moved in three different ways, case 1, case 2, and case 3 dependent upon the relationship between the size of the partition and the number of elements below the partition that are below the maximum value.
Claim 7
Dependent Claim
35 words
The method of claim 5 wherein the movement of elements in case 1 occurs in the following steps: moving the number of elements determined in step d from below the boundary to above the boundary.
Claim 8
Dependent Claim
84 words
The method of claim 5 wherein the movement of elements in case 2 occurs in the following steps: moving the number of elements determined in step d from below the boundary to above the boundary; determining the number of elements which should be moved to make the partitions the correct size; and moving the number of elements determined in step d minus the number of elements to be moved to make the partitions the correct size from above the boundary to below the boundary.
Claim 9
Dependent Claim
84 words
The method of claim 5 wherein the movement of elements in case 3 occurs in the following steps: moving the number of elements determined in step d from below the boundary to above the boundary; determining the number of elements which should be moved to make the partitions the correct size; and moving the number of elements to be moved to make the partitions the correct size minus the number of elements determined in step d from below the boundary to above the boundary.
Claim 10
Independent Claim
103 words
A method of sorting a list of N elements using P processors, where P is an integer greater than 2, and wherein the processors cooperate in parallel to provide the sorted list, comprising the steps of: a) dividing the list into P sublists of approximately N/P elements; b) each processor sorting one of the sublists; c) defining P-1 partition boundaries. each boundary being defined by one of P-1 of the processors, said boundaries dividing the lists into nearly equal partitions of elements having values less than all of the elements of a succeeding partition; and d) each processor merging one of the partitions.
Claim 11
Independent Claim
103 words
A method of sorting a list of N elements using P processors, where P is an integer greater than 2, and wherein the processors cooperate in parallel to provide the sorted list, comprising the steps of: a) dividing the list into P sublists of approximately N/P elements; b) each processor sorting one of the sublists; c) defining P-1 partition boundaries. each boundary being defined by one of P-1 of the processors, said boundaries dividing the lists into nearly equal partitions of elements having values less than all of the elements of a succeeding partition; and d) each processor merging one of the partitions.
Claim 12
Dependent Claim
130 words
Apparatus for partitioning multiple presorted lists of elements comprising: a plurality of processors each having access to storage containing the presorted lists, each processor comprising: means for selectively and iteratively adding elements from the lists to a partitioning list; means for selecting an initial partition boundary for the partitioning list; means for determining a size modifier based on the desired number of elements above the partition boundary versus the actual number of elements above the partition boundary; means for determining a magnitude modifier based on the number of elements below the partition boundary which are less than the magnitude of the largest element above the partition boundary; and means for modifying the partition boundary as a function of the size modifier and magnitude modifier following each iterative addition of elements.
Claim 13
Dependent Claim
130 words
Apparatus for partitioning multiple presorted lists of elements comprising: a plurality of processors each having access to storage containing the presorted lists, each processor comprising: means for selectively and iteratively adding elements from the lists to a partitioning list; means for selecting an initial partition boundary for the partitioning list; means for determining a size modifier based on the desired number of elements above the partition boundary versus the actual number of elements above the partition boundary; means for determining a magnitude modifier based on the number of elements below the partition boundary which are less than the magnitude of the largest element above the partition boundary; and means for modifying the partition boundary as a function of the size modifier and magnitude modifier following each iterative addition of elements.
Claim 14
Dependent Claim
85 words
Apparatus for partitioning multiple presorted lists of elements comprising: a plurality of processors each having access to storage containing the presorted lists, each processor comprising: means for selectively and iteratively adding elements from the lists to a partitioning list; means for selecting an initial partition boundary for the partitioning list: means for determining a size modifier; means for determining a magnitude modifier; and means for modifying the partition boundary as a function of the size modifier and magnitude modifier following each iterative addition of elements.
Claim 15
Dependent Claim
85 words
Apparatus for partitioning multiple presorted lists of elements comprising: a plurality of processors each having access to storage containing the presorted lists, each processor comprising: means for selectively and iteratively adding elements from the lists to a partitioning list; means for selecting an initial partition boundary for the partitioning list: means for determining a size modifier; means for determining a magnitude modifier; and means for modifying the partition boundary as a function of the size modifier and magnitude modifier following each iterative addition of elements.
Claim 16
Dependent Claim
84 words
The apparatus of claim 11 and further comprising: means for identifying the movement of elements about the boundary as a case 1 situation when the magnitude modifier and the size modifier are equal; means for identifying the movement of elements about the boundary as a case 2 situation when the magnitude modifier is greater than the size modifier; and means for identifying the movement of elements about the boundary as a case 3 situation when the magnitude modifier is less than the size modifier.
Claim 17
Dependent Claim
117 words
The apparatus of claim 12 wherein the magnitude modifier is an integer s, and the size modifier is an integer n and wherein the apparatus further comprises: means for moving s elements from below the partition boundary to above the partition boundary in the event of case 1; means for moving s elements from below the partition boundary to above the partition boundary, and s-n elements from above the partition boundary to below the partition boundary in the event of case 2; and means for moving s elements from below the partition boundary to above the partition boundary, and n-s elements from below the partition boundary to above the partition boundary in the event of case 3.
Claim 18
Dependent Claim
46 words
The apparatus of claim 11 wherein the rows of elements based on an index are added to the partitioning list, and the first row added has an index which is the greatest integer power of 2 less than the number of elements in the longest list.
Claim 19
Dependent Claim
50 words
The apparatus of claim 14 wherein the next row of elements added for the second iteration comprise the two rows having indexes halfway between the index of the first row added and zero, and halfway between the index of the first row added and the next higher power of two.
Claim 20
Dependent Claim
29 words
The apparatus of claim 14 wherein each iteration of adding rows, result in the addition of rows of elements which lie halfway between the rows of elements previously considered.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.