TWO-PASS LINEAR COMPLEXITY TASK SCHEDULER

• US 20120284731A1
• Filed: 11/07/2011
• Published: 11/08/2012
• Est. Priority Date: 05/05/2011
• Status: Active Grant

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Shutkin, Yurii S., Aliseychik, Pavel A., Gasanov, Elyar E., Neznanov, Ilya V., Sokolov, Andrey P., Panteleev, Pavel A.
• Granted Patent: US 8,850,437 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

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.

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, wherein said first pass is non-iterative;

(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.

2. The method according to claim 1, wherein a complexity of scheduling said tasks is linear in response to both a number of said tasks and a number of said processors.

3. The method according to claim 1, further comprising the step of:

generating a list of said tasks prior to said first pass, wherein said list is sorted by a plurality of respective lengths of said tasks.

4. The method according to claim 3, wherein said assigning of said tasks to said processors in said first pass is performed in an order defined by said list.

5. The method according to claim 4, wherein a longest of said tasks is assigned first and a shortest of said tasks is assigned last.

6. The method according to claim 1, wherein during said first pass (i) said tasks having a corresponding length shorter than a first threshold are assigned to a single one of said processors and (ii) said tasks having said corresponding length greater than a second threshold are assigned to all of said processors.

7. The method according to claim 1, 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.

8. The method according to claim 1, wherein said schedule comprises a plurality of threads, wherein each of said threads (i) corresponds to a respective one of said tasks and (ii) identifies said one or more processors that process said respective task.

9. The method according to claim 1, wherein said schedule adjoins said tasks mapped to a given one of said processors such that no gaps exist in processing said adjoining tasks.

10. 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 said first pass is non-iterative, (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 (i) is non-iterative and (ii) 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.

11. The apparatus according to claim 10, wherein a complexity of scheduling said tasks is linear in response to both a number of said tasks and a number of said processors.

12. The apparatus according to claim 10, wherein (i) said circuit is further configured to generate a list of said tasks prior to said first pass and (ii) said list is sorted by a plurality of respective lengths of said tasks.

13. The apparatus according to claim 12, wherein said assigning of said tasks to said processors in said first pass is performed in an order defined by said list.

14. The apparatus according to claim 13, wherein a longest of said tasks is assigned first and a shortest of said tasks is assigned last.

15. The apparatus according to claim 10, wherein during said first pass (i) said tasks having a corresponding length shorter than a first threshold are assigned to a single one of said processors and (ii) said tasks having said corresponding length greater than a second threshold are assigned to all of said processors.

16. The apparatus according to claim 10, 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.

17. The apparatus according to claim 10, wherein said schedule comprises a plurality of threads, wherein each of said threads (i) corresponds to a respective one of said tasks and (ii) identifies said one or more processors that process said respective task.

18. The apparatus according to claim 10, wherein said circuit and said processors form a decoder.

19. The apparatus according to claim 11, wherein said apparatus is implemented as one or more integrated circuits.

20. 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 said first pass is non-iterative;

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.