US5852826A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel merge sort method and apparatus
Assignee: International Business Machines Corp
•
Filing: 1996-01-26
•
Granted: 1998-12-22
•
Expires: 2016-01-26
Abstract
Abstract A parallel sorting technique for external and internal sorting which maximizes the use of multiple processes to sort records from an input data set. Performance of the sort linearly scales with the number of processors because multiple processors can perform every step of the technique. To begin, the records of a data set to be sorted are read from an input file and written into multiple buffers in memory so long as memory is available. The records within each buffer are then simultaneously sorted to create runs therein. A merge tree is constructed with the runs as stream elements into leaf nodes of the tree, where the stream elements are merged. The stream elements at each node are then merged by multiple processes working simultaneously at the node, thereby generating an output stream of elements for merging at a higher node. For an internal sort, the run that results from all of the merging is immediately written to an output device. For an external sort, the run is an intermediate run, written to secondary storage along with other intermediate runs. A forecast structure provides a forecast of the order of the run blocks from the multiple intermediate runs. These blocks are read in the forecasted order from secondary storage, written into memory and merged through a merge tree to form an ordered record stream that is a complete run for the data set. The ordered record stream is then written to the output device.
Inventors
- 👤 Gary Graunke
- 👤 Leonard D. Shapiro
- 👤 Sujata Ramamoorthy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 17:53
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F7/36; G06F16/00; G06F16/20; G06F16/28; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
245 words
A method of sorting records with a multiprocessor computer system having memory and a set of processes running in parallel, comprising: a) repeating the following steps a.1-a.5 until the records to be sorted are read from an input device and stored in secondary storage: a.1) reading blocks of records from the input device and writing the blocks to memory; a.2) sorting the records within each block simultaneously to create a run; a.3) constructing a merge tree in memory for merging the runs into an intermediate run that is output by the tree, the merge tree having nodes where two runs are merged to form another run; a.4) simultaneously merging the runs throughout the merge tree to form the intermediate run; and a.5) writing the intermediate run to secondary storage; b) after the records to be sorted are stored in intermediate runs in secondary storage: b.1) determining an order in which run blocks of the intermediate runs will be read from secondary storage; b.2) constructing a merge tree for merging the run blocks into a complete run that is output by the tree, the merge tree having nodes where two runs are merged to form another run; b.3) reading the run blocks from the secondary storage and writing the run blocks to memory in the determined order for merging in the merge tree; b.4) simultaneously merging runs throughout the merge tree to form the complete run; and b.5) writing the complete run to an output device.
Claim 2
Independent Claim
245 words
A method of sorting records with a multiprocessor computer system having memory and a set of processes running in parallel, comprising: a) repeating the following steps a.1-a.5 until the records to be sorted are read from an input device and stored in secondary storage: a.1) reading blocks of records from the input device and writing the blocks to memory; a.2) sorting the records within each block simultaneously to create a run; a.3) constructing a merge tree in memory for merging the runs into an intermediate run that is output by the tree, the merge tree having nodes where two runs are merged to form another run; a.4) simultaneously merging the runs throughout the merge tree to form the intermediate run; and a.5) writing the intermediate run to secondary storage; b) after the records to be sorted are stored in intermediate runs in secondary storage: b.1) determining an order in which run blocks of the intermediate runs will be read from secondary storage; b.2) constructing a merge tree for merging the run blocks into a complete run that is output by the tree, the merge tree having nodes where two runs are merged to form another run; b.3) reading the run blocks from the secondary storage and writing the run blocks to memory in the determined order for merging in the merge tree; b.4) simultaneously merging runs throughout the merge tree to form the complete run; and b.5) writing the complete run to an output device.
Claim 3
Dependent Claim
56 words
The method of claim 1 wherein the input device is adapted for simultaneous reading at multiple locations and the step of reading blocks of records from the input device and writing the blocks to memory comprises simultaneously reading blocks of records from the multiple locations of the input device and simultaneously writing the blocks to memory.
Claim 4
Dependent Claim
37 words
The method of claim 1 wherein the step of sorting the records within each block comprises: forming a vector of record addresses for blocks of records within memory; and sorting the addresses within the record address vectors.
Claim 5
Dependent Claim
58 words
The method of claim 1 wherein the step of constructing a merge tree comprises pairing up runs at a node at one level and merging at the node a number of sorted records from the paired runs to form a third run, the third run then paired with a fourth run at a node at a higher level.
Claim 6
Dependent Claim
48 words
The method of claim 1 wherein the step of simultaneously merging the runs throughout the merge tree comprises: having more than two processes reserve portions of the two runs for merging at a node; and having the processes simultaneously merge their portions of the runs at the node.
Claim 7
Dependent Claim
35 words
The method of claim 1 wherein the step of writing the intermediate run to secondary storage comprises having at least two processes simultaneously write records of the run to multiple locations of the secondary storage.
Claim 8
Dependent Claim
28 words
The method of claim 1 wherein the step of writing the intermediate run to secondary storage includes making an entry for each run block into a forecast structure.
Claim 9
Dependent Claim
68 words
The method of claim 1 wherein the step of determining an order in which run blocks of the intermediate runs will be read from secondary storage comprises: making an entry for each run block into a forecast structure including the key of the first record in the run block; and sorting the entries in the forecast structure by the key of the first record of each run block.
Claim 10
Dependent Claim
24 words
The method of claim 1 wherein reading the run blocks from the secondary storage comprises reading multiple run blocks in the same read access.
Claim 11
Dependent Claim
56 words
The method of claim 1 wherein the step of reading the run blocks from the secondary storage and writing the blocks to memory in the determined order is performed simultaneously with the steps of merging runs to form a complete run and writing the complete run to the output device and freeing memory for more reading.
Claim 12
Dependent Claim
59 words
The method of claim 1 wherein the step of simultaneously merging the runs throughout the merge tree comprises: having several processes reserve consecutive portions of the two runs for merging at a node; and having the several processes simultaneously merge their portions of the runs at the node by performing a binary search on only one of the runs.
Claim 13
Dependent Claim
43 words
The method of claim 1 wherein the step of constructing a merge tree for merging the runs into an intermediate run includes merging records at a lower level node to provide additional records at a higher level node for continuing the tree construction.
Claim 14
Dependent Claim
31 words
The method of claim 12 wherein merging records at a lower level includes selecting a lower level node whose data will be needed next for merging at the higher level node.
Claim 15
Dependent Claim
17 words
A computer-readable medium for storing a computer program comprising instructions for executing the method of claim 1.
Claim 16
Independent Claim
128 words
A method of sorting records with a multiprocessor computer system having memory and a set of processes running in parallel, comprising: reading blocks of records from an input device and writing the blocks to memory; sorting the records within each block simultaneously to create a run therein; constructing a merge tree for merging the runs into a larger run that is output by the tree, the merge tree having nodes where two runs are merged; simultaneously merging the runs throughout the merge tree to form the larger run by having more than two processes reserve portions of the two runs for merging at each node and having the processes simultaneously merge their portions of the runs at each node; and writing the larger run to an output device.
Claim 17
Independent Claim
128 words
A method of sorting records with a multiprocessor computer system having memory and a set of processes running in parallel, comprising: reading blocks of records from an input device and writing the blocks to memory; sorting the records within each block simultaneously to create a run therein; constructing a merge tree for merging the runs into a larger run that is output by the tree, the merge tree having nodes where two runs are merged; simultaneously merging the runs throughout the merge tree to form the larger run by having more than two processes reserve portions of the two runs for merging at each node and having the processes simultaneously merge their portions of the runs at each node; and writing the larger run to an output device.
Claim 18
Independent Claim
97 words
A method of merging records stored in shorter runs into a larger run, the method comprising the following steps: providing a forecast structure, the structure having entries containing a key of a predetermined record in each run block of each run and a run block address; sorting the entries in the forecast structure by the key of the predetermined record of each run block; reading a number of the sorted run blocks from secondary storage into memory; and merging the run blocks in memory through a merge tree having a root node to produce a longer run.
Claim 19
Independent Claim
97 words
A method of merging records stored in shorter runs into a larger run, the method comprising the following steps: providing a forecast structure, the structure having entries containing a key of a predetermined record in each run block of each run and a run block address; sorting the entries in the forecast structure by the key of the predetermined record of each run block; reading a number of the sorted run blocks from secondary storage into memory; and merging the run blocks in memory through a merge tree having a root node to produce a longer run.
Claim 20
Dependent Claim
51 words
The method of claim 16 wherein the sorting step comprises: making an entry for each run block into a forecast structure including the key of the first record in the run block; and sorting the entries in the forecast structure by the key of the first record of each run block.
Claim 21
Dependent Claim
48 words
The method of claim 16 including: creating for each shorter run a forecast stream of the sorted run blocks that can be read from secondary storage and written to memory; and referring to the forecast streams to determine which run blocks to read from secondary storage into memory.
Claim 22
Dependent Claim
24 words
The method of claim 18 including reading multiple run blocks appearing in the same forecast stream from the secondary storage in a single access.
Claim 23
Dependent Claim
26 words
The method of claim 16 including reading the key of the first record of a run block to avoid a deadlock in merging the run blocks.
Claim 24
Dependent Claim
22 words
The method of claim 16 including merging all records available at a node to avoid a deadlock in merging the run blocks.
Claim 25
Dependent Claim
64 words
The method of claim 16 including: writing the longer run to an output device; freeing the memory used by run blocks that have been written to the output device for receiving additional sorted run blocks; and repeating the steps of reading, merging, writing and freeing until the shorter runs have been read from secondary storage into memory and merged to produce the longer run.
Claim 26
Dependent Claim
21 words
The method of claim 22 in which the steps of reading, merging, writing and freeing are performed simultaneously by several processes.
Claim 27
Dependent Claim
213 words
Apparatus for sorting records with a multiprocessor computer system having memory and a set of processes running in parallel, comprising: means for reading blocks of records from an input device and writing the blocks to memory; means for sorting the records within each block simultaneously to create a run therein; means for constructing a merge tree for merging the runs into an intermediate run that is output by the tree, the merge tree having nodes where two runs are merged to form another run; means for simultaneously merging the runs throughout the merge tree to form the intermediate run; means for writing intermediate runs to secondary storage; means for determining an order in which run blocks of the intermediate runs will be read from secondary storage; means for constructing a merge tree for merging the run blocks into a complete run that is output by the tree, the merge tree having nodes where two runs are merged to form another run; means for reading the run blocks from the secondary storage and writing the run blocks to memory in the determined order for merging in the merge tree; means for simultaneously merging runs throughout the merge tree to form the complete run; and means for writing the complete run to an output device.
Claim 28
Dependent Claim
213 words
Apparatus for sorting records with a multiprocessor computer system having memory and a set of processes running in parallel, comprising: means for reading blocks of records from an input device and writing the blocks to memory; means for sorting the records within each block simultaneously to create a run therein; means for constructing a merge tree for merging the runs into an intermediate run that is output by the tree, the merge tree having nodes where two runs are merged to form another run; means for simultaneously merging the runs throughout the merge tree to form the intermediate run; means for writing intermediate runs to secondary storage; means for determining an order in which run blocks of the intermediate runs will be read from secondary storage; means for constructing a merge tree for merging the run blocks into a complete run that is output by the tree, the merge tree having nodes where two runs are merged to form another run; means for reading the run blocks from the secondary storage and writing the run blocks to memory in the determined order for merging in the merge tree; means for simultaneously merging runs throughout the merge tree to form the complete run; and means for writing the complete run to an output device.
Claim 29
Dependent Claim
51 words
A multiprocessor computer system for sorting records comprising: memory; multiple processors programmed to run merge processes in parallel in memory, at least several of the merge processes performing each of the following tasks as needed: constructing a merge tree in memory; and merging of records at a tree node into runs.
Claim 30
Dependent Claim
51 words
A multiprocessor computer system for sorting records comprising: memory; multiple processors programmed to run merge processes in parallel in memory, at least several of the merge processes performing each of the following tasks as needed: constructing a merge tree in memory; and merging of records at a tree node into runs.
Claim 31
Dependent Claim
26 words
The computer system of claim 25 wherein the several merge processes also perform each of the following tasks as needed: sorting records at a tree node.
Claim 32
Dependent Claim
34 words
The computer system of claim 25 wherein the several merge processes also perform each of the following tasks as needed: inputting of records into memory for sorting; and outputting of runs to secondary storage.
Claim 33
Dependent Claim
17 words
A computer-readable medium for storing a computer program comprising instructions for executing the method of claim 15.
Claim 34
Dependent Claim
17 words
A computer-readable medium for storing a computer program comprising instructions for executing the method of claim 16.
References Cited (Backward Citations)
US5179699A
Cited
US5414842A
Cited
US5210870A
Cited
US5307485A
Cited
US5519860A
Cited
US5421007A
Cited
US5621908A
Cited
US5487164A
Cited
US5640554A
Cited
US5619693A
Cited
US5487166A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-21 | 2002-06-22 | 2002-12-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-21 | 2006-06-22 | 2006-12-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-21 | 2010-06-22 | 2010-12-22 | $7700.00 | Window Closed / Lapsed |