US5765146A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of performing a parallel relational database query in a multiprocessor environment
Assignee: International Business Machines Corp
•
Filing: 1993-11-04
•
Granted: 1998-06-09
•
Expires: 2013-11-04
Abstract
Abstract A method of performing a parallel join operation on a pair of relations R1 and R2 in a system containing P processors organized into Q clusters of P/Q processors each. The system contains disk storage for each cluster, shared by the processors of that cluster, together with a shared intermediate memory (SIM) accessible by all processors. The relations R1 and R2 to be joined are first sorted on the join column. The underlying domain of the join column is then partitioned into P ranges of equal size. Each range is further divided into M subranges of progressively decreasing size to create MP tasks T m ,p, the subranges of a given range being so sized relative to one another that the estimated completion time for task T m ,p is a predetermined fraction that of task T m-1 ,p. Tasks T m ,p with larger time estimates are assigned (and the corresponding tuples shipped) to the cluster to which processor p belongs, while tasks with smaller time estimates are assigned to the SIM, which is regarded as a universal cluster (cluster 0). The actual task-to-processor assignments are determined dynamically during the join phase in accordance with the dynamic longest processing time first (DLPT) algorithm. Each processor within a cluster picks its next task at any given decision point to be the one with the largest time estimate which is owned by that cluster or by cluster 0.
Inventors
- 👤 Joel Leonard Wolf
- 👤 Philip Shi-lung Yu
- 👤 John Joseph Edward Turek
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 18:10
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24532; G06F16/24534; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
247 words
In a system having a plurality of processors, a plurality of partially shared storage facilities, and a universal storage facility, each of said partially shared storage facilities being shared by a particular subset of said plurality of processors, each of said processors sharing at least one of said partially shared storage facilities, said universal storage facility being shared by all of said processors, a method of performing a parallel operation on a data set comprising the steps of: (a) partitioning said operation into a plurality of independent tasks having different estimated completion times, each of said tasks being restricted to a corresponding subset of said data set; (b) assigning a predetermined subset of said plurality of tasks having smaller estimated completion times to said universal storage facility; (c) assigning the remaining tasks of said plurality of tasks to said partially shared storage facilities, said remaining tasks having larger estimated completion times; (d) initially assigning each of said processors a task from a partially shared storage facility shared by said processor for performance of said operation thereon; (e) upon the completion of a task by one of said processors, assigning that processor an awaiting task from a partially shared storage facility shared by said processor if any awaiting tasks remain in said partially shared storage facility, otherwise, assigning said processor an awaiting task from the universal storage facility; and (f) repeating the preceding step (e) until each of said tasks has been assigned to one of said processors.
Claim 2
Dependent Claim
247 words
In a system having a plurality of processors, a plurality of partially shared storage facilities, and a universal storage facility, each of said partially shared storage facilities being shared by a particular subset of said plurality of processors, each of said processors sharing at least one of said partially shared storage facilities, said universal storage facility being shared by all of said processors, a method of performing a parallel operation on a data set comprising the steps of: (a) partitioning said operation into a plurality of independent tasks having different estimated completion times, each of said tasks being restricted to a corresponding subset of said data set; (b) assigning a predetermined subset of said plurality of tasks having smaller estimated completion times to said universal storage facility; (c) assigning the remaining tasks of said plurality of tasks to said partially shared storage facilities, said remaining tasks having larger estimated completion times; (d) initially assigning each of said processors a task from a partially shared storage facility shared by said processor for performance of said operation thereon; (e) upon the completion of a task by one of said processors, assigning that processor an awaiting task from a partially shared storage facility shared by said processor if any awaiting tasks remain in said partially shared storage facility, otherwise, assigning said processor an awaiting task from the universal storage facility; and (f) repeating the preceding step (e) until each of said tasks has been assigned to one of said processors.
Claim 3
Dependent Claim
46 words
The method of claim 1 wherein upon the completion of a task by one of said processors, that processor is assigned an awaiting task from a partially shared storage facility shared by said processor or from the universal storage facility having the longest estimated completion time.
Claim 4
Dependent Claim
20 words
The method of claim 1 wherein each of said partially shared storage facilities is shared by a plurality of processors.
Claim 5
Dependent Claim
197 words
In a system having a plurality of processor clusters, each of said processor clusters containing one or more processors and a cluster storage facility shared by the processors of that cluster, and a universal cluster comprising a shared storage facility shared by all of said processors, a method of performing a parallel operation on a data set comprising the steps of: (a) partitioning said operation into a plurality of independent tasks, each of which is restricted to a corresponding subset of said data set; (b) assigning a predetermined subset of said plurality of independent tasks to said universal cluster; (c) assigning the remaining tasks of said plurality of independent tasks to said processor clusters; (d) initially assigning each of said processors a task from the corresponding processor cluster for performance of said operation thereon; (e) upon the completion of a task by one of said processors, assigning that processor an awaiting task from the corresponding processor cluster if any awaiting tasks remain in said processor cluster, otherwise, assigning the processor an awaiting task from the universal cluster; and (f) repeating the preceding step (f) until each of said tasks has been assigned to one of said processors.
Claim 6
Dependent Claim
197 words
In a system having a plurality of processor clusters, each of said processor clusters containing one or more processors and a cluster storage facility shared by the processors of that cluster, and a universal cluster comprising a shared storage facility shared by all of said processors, a method of performing a parallel operation on a data set comprising the steps of: (a) partitioning said operation into a plurality of independent tasks, each of which is restricted to a corresponding subset of said data set; (b) assigning a predetermined subset of said plurality of independent tasks to said universal cluster; (c) assigning the remaining tasks of said plurality of independent tasks to said processor clusters; (d) initially assigning each of said processors a task from the corresponding processor cluster for performance of said operation thereon; (e) upon the completion of a task by one of said processors, assigning that processor an awaiting task from the corresponding processor cluster if any awaiting tasks remain in said processor cluster, otherwise, assigning the processor an awaiting task from the universal cluster; and (f) repeating the preceding step (f) until each of said tasks has been assigned to one of said processors.
Claim 7
Dependent Claim
16 words
The method of claim 4 wherein each of said processor clusters contains a plurality of processors.
Claim 8
Dependent Claim
29 words
The method of claim 4 wherein said steps of assigning tasks to said clusters comprise the step of transferring the corresponding subsets of said data set to said clusters.
Claim 9
Dependent Claim
31 words
The method of claim 4 wherein tasks having smaller estimated completion times are assigned to said universal cluster while tasks having larger estimated completion times are assigned to said processor clusters.
Claim 10
Dependent Claim
18 words
The method of claim 4 wherein said processors are assigned awaiting tasks having the longest estimated completion times.
References Cited (Backward Citations)
US4497039A
Cited
US4769772A
Cited
US5043872A
Cited
GB2235798A
Cited
US5121494A
Cited
US5166674A
Cited
US5191578A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-08 | 2001-12-08 | 2002-06-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-08 | 2005-12-08 | 2006-06-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-08 | 2009-12-08 | 2010-06-09 | $7700.00 | Window Closed / Lapsed |