Two-pass linear complexity task scheduler
First Claim
Patent Images
1. A method for two-pass scheduling of a plurality of tasks, comprising the steps of:
- (A) assigning each of said tasks to a corresponding one or more of a plurality of processors in a first pass through said tasks using a circuit, wherein (i) said first pass is non-iterative and (ii) at least one of said tasks is assigned to run on two or more of said processors in parallel;
(B) reassigning said tasks among said processors to shorten a respective load on one or more of said processors in a second pass through said tasks, wherein said second pass (i) is non-iterative and (ii) begins after said first pass has completed; and
(C) generating a schedule in response to said assigning and said reassigning, wherein said schedule maps said tasks to said processors,wherein said reassigning of said tasks in said second pass changes at least one of said tasks from being mapped to a single one of said processors to being mapped to at least two of said processors.
4 Assignments
0 Petitions
Accused Products
Abstract
A method for two-pass scheduling of a plurality of tasks generally including steps (A) to (C). Step (A) may assign each of the tasks to a corresponding one or more of a plurality of processors in a first pass through the tasks. The first pass may be non-iterative. Step (B) may reassign the tasks among the processors to shorten a respective load on one or more of the processors in a second pass through the tasks. The second pass may be non-iterative and may begin after the first pass has completed. Step (C) may generate a schedule in response to the assigning and the reassigning. The schedule generally maps the tasks to the processors.
22 Citations
18 Claims
-
1. A method for two-pass scheduling of a plurality of tasks, comprising the steps of:
-
(A) assigning each of said tasks to a corresponding one or more of a plurality of processors in a first pass through said tasks using a circuit, wherein (i) said first pass is non-iterative and (ii) at least one of said tasks is assigned to run on two or more of said processors in parallel; (B) reassigning said tasks among said processors to shorten a respective load on one or more of said processors in a second pass through said tasks, wherein said second pass (i) is non-iterative and (ii) begins after said first pass has completed; and (C) generating a schedule in response to said assigning and said reassigning, wherein said schedule maps said tasks to said processors, wherein said reassigning of said tasks in said second pass changes at least one of said tasks from being mapped to a single one of said processors to being mapped to at least two of said processors. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. An apparatus comprising:
-
a memory configured to buffer a plurality of tasks; and a circuit configured to (i) assign each of said tasks to a corresponding one or more of a plurality of processors in a first pass through said tasks, wherein (a) said first pass is non-iterative and (b) at least one of said tasks is assigned to run on two or more of said processors in parallel, (ii) reassign said tasks among said processors to shorten a respective load on one or more of said processors in a second pass through said tasks, wherein said second pass (a) is non-iterative and (b) begins after said first pass has completed, and (iii) generate a schedule in response to said assign and said reassign, wherein said schedule maps said tasks to said processors, wherein said reassigning of said tasks in said second pass changes at least one of said tasks from being mapped to a single one of said processors to being mapped to at least two of said processors. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. An apparatus comprising:
-
means for assigning each of a plurality of tasks to a corresponding one or more of a plurality of processors in a first pass through said tasks, wherein (i) said first pass is non-iterative and (ii) at least one of said tasks is assigned to run on two or more of said processors in parallel; means for reassigning said tasks among said processors to shorten a respective load on one or more of said processors in a second pass through said tasks, wherein said second pass (i) is non-iterative and (ii) begins after said first pass has completed; and means for generating a schedule in response to said assigning and said reassigning, wherein said schedule maps said tasks to said processors, wherein said reassigning of said tasks in said second pass changes at least one of said tasks from being mapped to a single one of said processors to being mapped to at least two of said processors.
-
Specification