US5179699A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Partitioning of sorted lists for multiprocessors sort and merge
Assignee: International Business Machines Corp
•
Filing: 1989-01-13
•
Granted: 1993-01-12
•
Expires: 2009-01-13
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 R. Iyer
- 👤 Gary R. Ricard
- 👤 Peter J. Varman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 03:12
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
258 words
A computer implemented method of partitioning P sorted lists by L-1 processors into L partitions, where each of the processors has access to storage containing the sorted lists and 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 computer implemented method comprising the steps of: a) accessing said storage to obtain at least one row of elements from the sorted lists for consideration, the accessing step being performed by each of the processors; b) fixing a partition boundary within the sorted lists, the partition boundary being fixed based on the number of processors that are to perform the partitioning, the fixing step being performed by each of the processors; c) determining the maximum value of all the elements under consideration above the partition boundary, the determining the maximum value step being performed by each of the processors; d) determining the elements under consideration below the partition boundary that have a value which is less than the maximum value, the determining the elements step being performed by each of the processors; e) moving the elements about the partition boundary based on the size of the partition and the values of the elements under consideration, the moving step being performed by each of the processors; and f) repeating steps a, c, d, and e until all successive rows have been considered, and the partitions each contain substantially the same number of elements.
Claim 2
Dependent Claim
258 words
A computer implemented method of partitioning P sorted lists by L-1 processors into L partitions, where each of the processors has access to storage containing the sorted lists and 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 computer implemented method comprising the steps of: a) accessing said storage to obtain at least one row of elements from the sorted lists for consideration, the accessing step being performed by each of the processors; b) fixing a partition boundary within the sorted lists, the partition boundary being fixed based on the number of processors that are to perform the partitioning, the fixing step being performed by each of the processors; c) determining the maximum value of all the elements under consideration above the partition boundary, the determining the maximum value step being performed by each of the processors; d) determining the elements under consideration below the partition boundary that have a value which is less than the maximum value, the determining the elements step being performed by each of the processors; e) moving the elements about the partition boundary based on the size of the partition and the values of the elements under consideration, the moving step being performed by each of the processors; and f) repeating steps a, c, d, and e until all successive rows have been considered, and the partitions each contain substantially the same number of elements.
Claim 3
Dependent Claim
34 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 sorted 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
46 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 boundary that are below the maximum value.
Claim 7
Dependent Claim
37 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 partition boundary to above the partition boundary.
Claim 8
Dependent Claim
88 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 partition boundary to above the partition 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 partition boundary to below the partition boundary.
Claim 9
Dependent Claim
88 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 partition boundary to above the partition 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 partition boundary to above the partition boundary.
Claim 10
Dependent Claim
159 words
A computer implemented method of sorting a list of N elements using P processors, where P is an integer greater than 2, and wherein the processors, each having access to storage containing the list, cooperate in parallel to provide the sorted list, the computer implemented method comprising the steps of: a) accessing the list from said storage; b) dividing the accessed list into P sub-lists of approximately N/P elements, the sub-lists residing in said storage; c) each processor accessing and sorting one of the sub-lists, the sorted sub-lists residing in said storage, d) each processor accessing the sorted sub-lists upon completion of the sorting step; e) defining P-1 partition boundaries, each of the partition boundaries being defined by one of P-1 of the processors, said partition boundaries dividing the lists into nearly equal partitions of elements having values less than all of the elements of a succeeding partition; and f) each of the processors merging one of the partitions.
Claim 11
Dependent Claim
159 words
A computer implemented method of sorting a list of N elements using P processors, where P is an integer greater than 2, and wherein the processors, each having access to storage containing the list, cooperate in parallel to provide the sorted list, the computer implemented method comprising the steps of: a) accessing the list from said storage; b) dividing the accessed list into P sub-lists of approximately N/P elements, the sub-lists residing in said storage; c) each processor accessing and sorting one of the sub-lists, the sorted sub-lists residing in said storage, d) each processor accessing the sorted sub-lists upon completion of the sorting step; e) defining P-1 partition boundaries, each of the partition boundaries being defined by one of P-1 of the processors, said partition boundaries dividing the lists into nearly equal partitions of elements having values less than all of the elements of a succeeding partition; and f) each of the processors merging one of the partitions.
Claim 12
Dependent Claim
206 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 accessing said storage to obtain said presorted lists; means for selectively and iteratively adding elements from said presorted lists to a partitioning list, said means for selectively and iteratively adding being coupled with said means for accessing; means for selecting an initial partition boundary for said partitioning list, said means for selecting being coupled with said means for accessing; 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, said means for determining a size modifier being coupled with said means for accessing; 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, said means for determining a magnitude modifier being coupled with said means for accessing; and means for modifying the partition boundary as a function of said size modifier and said magnitude modifier following each iterative addition of elements, said means for modifying being coupled with said means for accessing.
Claim 13
Dependent Claim
206 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 accessing said storage to obtain said presorted lists; means for selectively and iteratively adding elements from said presorted lists to a partitioning list, said means for selectively and iteratively adding being coupled with said means for accessing; means for selecting an initial partition boundary for said partitioning list, said means for selecting being coupled with said means for accessing; 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, said means for determining a size modifier being coupled with said means for accessing; 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, said means for determining a magnitude modifier being coupled with said means for accessing; and means for modifying the partition boundary as a function of said size modifier and said magnitude modifier following each iterative addition of elements, said means for modifying being coupled with said means for accessing.
Claim 14
Dependent Claim
160 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 accessing said storage to obtain said presorted lists; means for selectively and iteratively adding elements from said presorted lists to a partitioning list, said means for selectively and iteratively adding being coupled with said means for accessing; means for selecting an initial partition boundary for the partitioning list, said means for selecting being coupled with said means for accessing; means for determining a size modifier, said means for determining a size modifier being coupled with said means for accessing; means for determining a magnitude modifier, said means for determining a magnitude modifier being coupled with said means for accessing; and means for modifying the partition boundary as a function of the size modifier and magnitude modifier following each iterative addition of elements, said means for modifying being coupled with said means for accessing.
Claim 15
Dependent Claim
160 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 accessing said storage to obtain said presorted lists; means for selectively and iteratively adding elements from said presorted lists to a partitioning list, said means for selectively and iteratively adding being coupled with said means for accessing; means for selecting an initial partition boundary for the partitioning list, said means for selecting being coupled with said means for accessing; means for determining a size modifier, said means for determining a size modifier being coupled with said means for accessing; means for determining a magnitude modifier, said means for determining a magnitude modifier being coupled with said means for accessing; and means for modifying the partition boundary as a function of the size modifier and magnitude modifier following each iterative addition of elements, said means for modifying being coupled with said means for accessing.
Claim 16
Dependent Claim
87 words
The apparatus of claim 11 and further comprising: means for identifying the movement of elements about the partition 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 partition 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 partition 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 form 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
47 words
The apparatus of claim 11 wherein the rows of elements based on an index are added to said 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 presorted list.
Claim 19
Dependent Claim
50 words
The method 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 method of claim 14 wherein each iteration of adding rows, results in the addition of rows of elements which lie halfway between the rows of elements previously considered.
References Cited (Backward Citations)
US4210961A
Cited
US4210961B1
Cited
US4030077A
Cited
US4595995A
Cited
US4575798A
Cited
US4799152A
Cited
US4794521A
Cited
US4797815A
Cited
US4862356A
Cited
US4951193A
Cited
US4843542A
Cited
US4991134A
Cited
US4920487A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-01-12 | 1996-07-13 | 1997-01-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-01-12 | 2000-07-13 | 2001-01-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-01-12 | 2004-07-13 | 2005-01-12 | $7700.00 | Window Closed / Lapsed |