EP0516266A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Merging sorted lists
Assignee: International Business Machines Corp
•
Filing: 1992-03-18
•
Granted: —
•
Expires: 2012-03-18
Abstract
Abstract In a system and method for merging a plurality of sorted lists using a multi-processing machine, the sorted lists are divided into a number of tasks equal to the number of processors. Pre-ordered lists which need no merging are removed initially in step 306. Search bounds are then determined in step 316 and an appropriate task size based upon the number of processors and the number of records is determined in step 308. The sorted lists are partitioned into the number of tasks equal to the number of processors in step 310. The tasks are then separately sorted in step 312 and concatenated to form a single sorted list in step 314. Advantage is taken of the multi-processing machine during the creation of the tasks, as well as the actual sorting.
Inventors
- 👤 Frank Gerard Bordonaro
- 👤 Glen Alan Brent
- 👤 Roger Joseph Edwards
- 👤 Joel Goldman
- 👤 David Bruce Lindquist
- 👤 Kushal Amrish Patel
- 👤 Peyton Randolph Williams, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-05 20:27
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F7/32; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
59 words
A merging device for merging a plurality of sorted lists, comprising means for dividing the plurality of sorted lists into a number of tasks, means for merging records in each task on a separate processor in a shared memory multi-processing system so that the records are sorted, and means for concatenating each task to form a single, sorted list.
Claim 2
Dependent Claim
321 words
A merging device for merging a plurality of sorted lists, wherein each sorted list has at least one record, comprising a random access memory (104), a plurality of independently operating processors (106) on a multi-processing machine, the processors sharing the random access memory, partition means (310) for selecting a portion of the sorted lists to be loaded into the random access memory and merged, thereby forming a selected portion of the sorted lists, wherein the number of records in the selected portion is related to the capacity of the random access memory, pre-order detection means (306) for determining whether any sorted list in the selected portion is a pre-ordered sorted list, such that each record in any of the sorted lists are either all greater or equal in value to each record in the pre-ordered sorted list or all less than or equal in value to each record in the pre-ordered sorted list, allocation means (310) for dividing the sorted lists in the selected portion into a plurality of tasks equal to the number of the independently operating processors, wherein an appropriate task size is determined based upon the number of records in the selected portion and the number of the independently operating processors, wherein the records of a specific task of the plurality of tasks are such that each record in any other of the plurality of tasks are either all greater or equal in value to each record in the specific task or all less than or equal in value to each record in the specific task, merge means (204) for merging the tasks in parallel, creating sorted tasks, and concatenation means (207) for concatenating the sorted tasks with each other, and with any pre-ordered lists to create a single sorted list, and for concatenating the single sorted list with other single sorted lists generated from previously selected portions of the sorted lists to form a final sorted list.
Claim 3
Dependent Claim
66 words
A device according to claim 2, wherein the sorted lists within the partition have an upper and a lower bound, and wherein the lower bound is set by analyzing each of the lowest records in each of the sorted lists within the partition and determining which record of the lowest records has a highest value, wherein the lower bound is set based upon the highest value.
Claim 4
Dependent Claim
26 words
A device according to claim 2 or 3, wherein the allocation means uses a binary search to divide the sorted lists into a number of tasks.
Claim 5
Dependent Claim
20 words
A device according to claim 4, wherein the allocation means divides the sorted lists to form a task in parallel.
Claim 6
Dependent Claim
56 words
A device according to claim 2, 3, 4 or 5, wherein the allocation means comprises breakpoint means for determining a breakpoint value in each of the sorted lists and for creating each of the number of tasks based upon the records in the sorted lists having a value equal to or greater than the breakpoint value.
Claim 7
Dependent Claim
21 words
A device according to claim 6, wherein the breakpoint values are determined in parallel by the plurality of independently operating processors.
Claim 8
Dependent Claim
49 words
A device according to claim 2, 3, 4, 5, 6 or 7, wherein the partition means includes means for forming the selected portion such that each record in the selected portion has a value greater or equal to any record remaining to be loaded into the random access memory.
Claim 9
Independent Claim
288 words
A method of merging a plurality of sorted lists each having at least one record, comprising the steps of: (1) selecting a portion of the sorted lists to be merged, thereby forming a selected portion; (2) loading the selected portion into a random access memory, wherein the number of records in the selected portion is related to the capacity of the random access memory; (3) determining whether any sorted list in the selected portion is a pre-ordered sorted list, such that each record in any of the sorted lists are either all greater or equal in value to each record in the pre-ordered sorted list or all less than or equal in value to each record in the pre-ordered sorted list; (4) dividing the sorted lists in the selected portion into a plurality of tasks equal to a number of independently operating processors; (5) determining an appropriate task size based upon the number of records in the selected portion and the number of the independently operating processors, wherein the records of a specific task are such that the records in any other task are either all greater or equal in value to each record in the specific task or all less than or equal in value to each record in the specific task; (6) merging the tasks in parallel, creating sorted tasks; (7) concatenating the sorted tasks with each other, and with any pre-ordered sorted lists to create a single sorted list; (8) re-executing the steps beginning at the step (1) if portions of the sorted lists have not been loaded into the random access memory, creating a plurality of single sorted lists; and (9) concatenating the plurality of single sorted list to form a final sorted list.
Claim 10
Dependent Claim
28 words
A method according to claim 9, wherein the step (4) comprises the step of using a binary search to divide the sorted lists into a number of tasks.
Claim 11
Dependent Claim
27 words
A method according to claim 10, including the step of using the independently operating processors to divide the sorted lists into a number of tasks in parallel.
Claim 12
Dependent Claim
56 words
A method according to claim 9, 10 or 11, wherein the step (1) of forming the selected portion comprises the step of analyzing each record in the selected portion and ensuring that each record has a value greater or equal to any record remaining to be loaded into said random access memory by the step (2).
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.