US6434590B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for scheduling parallel processors
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-04-01
•
Granted: 2002-08-13
•
Expires: 2018-04-01
Abstract
Abstract A parallel processing method involves the steps of determining a sequential ordering of tasks for processing, assigning priorities to available tasks on the basis of the earliest and then later in the sequential ordering, selecting a number of tasks greater than a total number of available parallel processing elements from all available tasks having the highest priorities, partitioning the selected tasks into a number of groups equal to the available number of parallel processing elements, and executing the tasks in the groups in the parallel processing elements. The determining step establishes an ordering with a specific predetermined sequential schedule that is independent of the parallel execution, and the assigning step assigns priorities for parallel execution on the basis of the sequential schedule that is independent of the parallel execution.
Inventors
- 👤 Guy E. Blelloch
- 👤 Phillip B. Gibbons
- 👤 Yossi Matias
- 👤 Girija J. Narlikar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 23:38
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5061; G06F9/5066; G06F2209/00; G06F2209/50; G06F2209/5021
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
158 words
A method of parallel processing, comprising: selecting, in an assignment manager, a sequential schedule to determine priorities for processing; assigning, in the assignment manager, live tasks available for scheduling according to priorities on the basis of the sequential schedule; making, in the assignment manager, the highest priority live tasks that are available for scheduling available for processing by parallel processing elements; extracting, by said processing elements, available tasks for processing into each of said processing elements; and executing tasks from the extracted tasks in each of the processing elements; said sequential schedule and determining of priorities being independent of the execution of the extracted tasks in the processing elements; choosing, in the assignment manager, an operating criterion for execution of the extracted tasks in the processing elements; and said executing of tasks in each of said processing elements including executing extracted tasks until the criterion is reached and then feeding information concerning the execution to the assignment manager.
Claim 2
Independent Claim
158 words
A method of parallel processing, comprising: selecting, in an assignment manager, a sequential schedule to determine priorities for processing; assigning, in the assignment manager, live tasks available for scheduling according to priorities on the basis of the sequential schedule; making, in the assignment manager, the highest priority live tasks that are available for scheduling available for processing by parallel processing elements; extracting, by said processing elements, available tasks for processing into each of said processing elements; and executing tasks from the extracted tasks in each of the processing elements; said sequential schedule and determining of priorities being independent of the execution of the extracted tasks in the processing elements; choosing, in the assignment manager, an operating criterion for execution of the extracted tasks in the processing elements; and said executing of tasks in each of said processing elements including executing extracted tasks until the criterion is reached and then feeding information concerning the execution to the assignment manager.
Claim 3
Dependent Claim
28 words
A method as in claim 1 , wherein tasks are spawned during executing of tasks and the tasks are given priorities on the basis of the sequential scheduling.
Claim 4
Dependent Claim
16 words
A method as in claim 1 , wherein said sequential ordering is a Depth-first (DF) schedule.
Claim 5
Dependent Claim
30 words
A method as in claim 1 , further comprising placing information on completed tasks in the assignment manager and new live tasks generated by execution into a task in queue.
Claim 6
Dependent Claim
38 words
A method as in claim 4 , further comprising fetching information on completed tasks and new live tasks from the task in queue and updating to remove records of completed tasks and include records of new live tasks.
Claim 7
Dependent Claim
21 words
A method as in claim 4 , further comprising placing in the task queue notification that the parallel program has completed.
Claim 8
Dependent Claim
24 words
A method as in claim 1 , wherein the assignment manager selects a depth first order as the sequential schedule used to determine priorities.
Claim 9
Dependent Claim
29 words
A method as in claim 1 , wherein the assignment manager places the live tasks in a depth first order, and places records that mark these tasks as unblocked.
Claim 10
Dependent Claim
21 words
A method as in claim 1 , wherein the assignment manager determines which tasks are available for scheduling and not blocked.
Claim 11
Dependent Claim
53 words
A method as in claim 1 , wherein the assignment manager removes records of completed tasks and includes records of new live tasks, marks said tasks awaiting a flag as blocked awaiting a flag and otherwise marks said tasks as unblocked, and marks as unblocked any tasks awaiting any of the new flags.
Claim 12
Dependent Claim
13 words
A method as in claim 1 , wherein the criterion is time elapsed.
Claim 13
Dependent Claim
13 words
A method as in claim 1 , wherein the criterion is used memory.
Claim 14
Dependent Claim
16 words
A method as in claim 1 , wherein the criterion is the number of operations completed.
Claim 15
Dependent Claim
16 words
A method as in claim 1 , wherein the criterion is the number of tasks completed.
Claim 16
Dependent Claim
28 words
A method as in claim 1 , wherein the processing elements feed information concerning the execution to the assignment manager no later than when the criterion is reached.
Claim 17
Dependent Claim
26 words
A method as in claim 1 , wherein the processing elements feeding information concerning the execution to the assignment manager then extract available tasks for processing.
Claim 18
Independent Claim
159 words
An apparatus for parallel processing, comprising: an assignment manager having coded therein a sequential schedule to determine priorities for processing; the assignment manager being responsive to live tasks available for scheduling according to priorities on the basis of the sequential schedule; the assignment manager being responsive to the highest priority live tasks that are available for scheduling available for processing; a plurality of task-extracting and task-executing processing elements respectively responsive to available tasks so that said processing elements execute tasks from the tasks extracted into each of the processing elements; said sequential schedule for determining of priorities in said assignment manager being independent of the execution of the executed tasks in the processing elements; said assignment manager having an operating criterion for governing execution of the extracted tasks in the processing elements; and said task-extracting and task-executing processing elements being responsive to said criterion and including a status feedback arrangement to said assignment manager in response to said criterion.
Claim 19
Independent Claim
159 words
An apparatus for parallel processing, comprising: an assignment manager having coded therein a sequential schedule to determine priorities for processing; the assignment manager being responsive to live tasks available for scheduling according to priorities on the basis of the sequential schedule; the assignment manager being responsive to the highest priority live tasks that are available for scheduling available for processing; a plurality of task-extracting and task-executing processing elements respectively responsive to available tasks so that said processing elements execute tasks from the tasks extracted into each of the processing elements; said sequential schedule for determining of priorities in said assignment manager being independent of the execution of the executed tasks in the processing elements; said assignment manager having an operating criterion for governing execution of the extracted tasks in the processing elements; and said task-extracting and task-executing processing elements being responsive to said criterion and including a status feedback arrangement to said assignment manager in response to said criterion.
Claim 20
Dependent Claim
64 words
A method as in claim 1 , wherein said selecting and assigning and making by the assignment manager overlap said extracting and executing by the processing elements, and neither the assignment manager nor the processing elements need wait for the other to become idle before the selecting and assigning and making by the assignment manager and said extracting and executing by the processing elements.
Claim 21
Dependent Claim
36 words
An apparatus as in claim 17 , wherein in said processing elements spawn tasks during executing of extracted tasks and the tasks are given priorities in said assignment manager on the basis of the sequential scheduling.
Claim 22
Dependent Claim
20 words
An apparatus as in claim 17 , wherein said assignment manager includes the sequential ordering in a depth-first (DF) schedule.
Claim 23
Dependent Claim
33 words
An apparatus as in claim 17 , wherein said feedback arrangement places information on completed tasks in the assignment manager and on new live tasks generated by execution into a task in queue.
Claim 24
Dependent Claim
41 words
An apparatus as in claim 19 , wherein said assignment manager responds to information on completed tasks and new live tasks in a task in queue and updates to remove records of completed tasks and include records of new live tasks.
Claim 25
Dependent Claim
23 words
An apparatus as in claim 19 , wherein said feedback arrangement places in the task queue notification that the parallel program has completed.
Claim 26
Dependent Claim
24 words
An apparatus as in claim 17 , wherein the assignment manager selects a depth first order as the sequential schedule used to determine priorities.
Claim 27
Dependent Claim
28 words
An apparatus as in claim 17 , wherein the assignment manager places the live tasks a depth first order, and places records that mark these tasks as unblocked.
Claim 28
Dependent Claim
21 words
An apparatus as in claim 17 , wherein the assignment manager determines which tasks are available for scheduling and not blocked.
Claim 29
Dependent Claim
53 words
An apparatus as in claim 17 , wherein the assignment manager removes records of completed tasks and Includes records of new live tasks, marks said tasks awaiting a flag as blocked awaiting a flag and otherwise marks said tasks as unblocked, and marks as unblocked any tasks awaiting any of the new flags.
Claim 30
Dependent Claim
13 words
An apparatus as in claim 17 , wherein thus criterion is time elapsed.
Claim 31
Dependent Claim
13 words
An apparatus as in claim 17 , wherein the criterion is used memory.
Claim 32
Dependent Claim
16 words
An apparatus as in claim 17 , wherein the criterion is the number of operations completed.
Claim 33
Dependent Claim
16 words
An apparatus as in claim 17 , wherein the criterion is the number of tasks completed.
Claim 34
Dependent Claim
28 words
An apparatus as in claim 17 , wherein the processing elements feed information concerning the execution to the assignment manager no later than when the criterion is reached.
Claim 35
Dependent Claim
26 words
An apparatus as in claim 17 , wherein the processing elements feeding information concerning the execution to the assignment manager then extract available tasks for processing.
Claim 36
Dependent Claim
37 words
An apparatus as in claim 17 , wherein the assignment manager responses overlap said processing elements responses, and neither the assignment manager nor the processing elements wait for the other to become idle before executing the tasks.
References Cited (Backward Citations)
US4521874A
Cited
US5241677A
Cited
US5155858A
Cited
US5481747A
Cited
US5349656A
Cited
US5325525A
Cited
US5392429A
Cited
US5347654A
Cited
US5325526A
Cited
US5442792A
Cited
US5768594A
Cited
US5889989A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-08-12 | 2006-02-11 | 2006-08-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-08-12 | 2010-02-11 | 2010-08-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-08-12 | 2014-02-11 | 2014-08-13 | $7700.00 | Window Closed / Lapsed |