Real time multithreaded scheduler and scheduling method

• US 9,207,943 B2
• Filed: 03/17/2009
• Issued: 12/08/2015
• Est. Priority Date: 03/17/2009
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Plondke, Erich James, Codrescu, Lucian
• Primary Examiner(s): Partridge, William B
• Application Number:
  US12/405,271
• Publication Number:
  US 20100242041A1
• Time in Patent Office: 2,457 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/4812 by interrupt, e.g. masked
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

In a particular embodiment, a method is disclosed that includes receiving an interrupt at a first thread, the first thread including a lowest priority thread of a plurality of executing threads at a processor at a first time. The method also includes identifying a second thread, the second thread including a lowest priority thread of a plurality of executing threads at a processor at a second time. The method further includes directing a subsequent interrupt to the second thread.

Claims

1. A method comprising:

receiving an interrupt at a first thread of a multithreaded processor configured to schedule tasks among threads of a plurality of threads to enable execution of the tasks, the first thread executing a first task that is a lowest priority executing task at the multithreaded processor at a first time;

initiating an interrupt routine at the first thread;

identifying a second thread of the multithreaded processor, the second thread different from the first thread and identified based on comparing tasks executing at the plurality of threads, and determining that a second task at the second thread is the lowest priority executing task at the multithreaded processor at a second time occurring after the first time; and

setting a subsequent interrupt to be directed to the second thread.

2. The method of claim 1, wherein the interrupt indicates at least one task is ready to be executed.

3. The method of claim 1, wherein the multithreaded processor comprises an interleaved multithreaded processor.

4. The method of claim 1, wherein, at the first time, an idle task is assigned to the first thread.

5. The method of claim 1, wherein the first thread receives the interrupt and initiates the interrupt routine to select a highest priority ready task from a ready task list, wherein a first priority of the highest priority ready task from the ready task list is compared to a second priority of the lowest priority executing task from an executing task list, the executing task list configured to store tasks assigned to the plurality of threads of the multithreaded processor, and wherein tasks are swapped only when the first priority is higher than the second priority.

6. The method of claim 5, further comprising:

after swapping tasks to execute the highest priority ready task from the ready task list at the first thread and to add the first task previously assigned to the first thread to the ready task list, performing a determination of whether any ready tasks of the ready task list have a higher priority than a subsequent lowest priority executing task of a plurality of tasks assigned to the plurality of threads.

7. The method of claim 6, wherein performing the determination of whether any of the ready tasks of the ready task list have the higher priority comprises checking a schedule.

8. The method of claim 6, further comprising:

determining the subsequent lowest priority executing task of the plurality of tasks assigned to the plurality of threads; and

using the interrupt routine to set the subsequent interrupt to be directed to the second thread, wherein the second thread is executing the subsequent lowest priority executing task of the plurality of tasks assigned to the plurality of threads.

9. The method of claim 8, further comprising:

selectively setting the subsequent interrupt based on a result of checking a schedule to determine whether any ready task has a higher priority than the subsequent lowest priority executing task of the plurality of tasks assigned to the plurality of threads.

10. The method of claim 1, further comprising:

directing, by an interrupt controller of the multithreaded processor, threads of the plurality of threads other than the first thread to be masked from receiving the interrupt, wherein the first thread is not masked from receiving the interrupt.

26. The method of claim 1, wherein the multithreaded processor is included in a processing system, and wherein the processing system includes a plurality of instruction execution units.

11. A method comprising:

receiving an interrupt at a first thread of a set of threads of a multithreaded processor configured to schedule tasks among threads to enable execution of the tasks, the first thread identified based on comparing tasks executing at the set of threads and determining that a first task at the first thread is a lowest priority executing task at the multithreaded processor at a first time, wherein each thread of the set of threads executes a respective task of a set of executing tasks, and wherein each task of the set of executing tasks and each task of a set of ready tasks has a respective priority;

initiating an interrupt routine at the first thread, wherein, if a first priority of a highest priority ready task of the set of ready tasks is greater than a second priority of the first task, the first task is swapped with the highest priority ready task;

determining that a second task at a second thread different from the first thread is the lowest priority executing task at the multithreaded processor at a second time occurring after the first time; and

setting a subsequent interrupt to be directed to the second thread.

12. The method of claim 11, further comprising, after receiving the interrupt at the first thread, iteratively swapping the lowest priority executing task of the set of executing tasks with the highest priority ready task of the set of ready tasks until each task of the set of executing tasks has a priority that is greater than or equal to a priority of every task of the set of ready tasks, wherein each iteration of the iterative swapping includes, after swapping the lowest priority executing task of the set of executing asks with the highest priority ready task of the set of ready tasks:

determining a subsequent lowest priority executing task of the set of executing tasks; and

sending a subsequent interrupt to a particular thread executing the subsequent lowest priority executing task of the set of executing tasks to perform a next iteration of the iterative swapping when a subsequent lowest priority of the subsequent lowest priority executing task of the set of executing tasks is less than a subsequent highest priority of a subsequent highest priority ready task of the set of ready tasks.

27. The method of claim 11, wherein the multithreaded processor comprises an interleaved multithreaded processor.

13. A system comprising a multithreaded processor configured to schedule tasks among threads of a plurality of threads to enable execution of the tasks such that the plurality of threads are executing highest priority tasks, wherein the multithreaded processor is configured to:

identify a particular thread of the plurality of threads, the particular thread identified based on comparing tasks executing at the plurality of threads and determining that a first task at the particular thread is a lowest priority executing task at the multithreaded processor at a first time;

direct an interrupt to the particular thread of the plurality of threads, wherein the particular thread of the plurality of threads receives the interrupt and launches an interrupt routine;

swap the first task with a highest priority ready task;

determine that a second task at a second thread different from the particular thread is the lowest priority executing task at the multithreaded processor at a second time occurring after the first time; and

set a subsequent interrupt to be directed to the second thread.

14. The system of claim 13, wherein the multithreaded processor is configured such that the interrupt does not impact performance of at least one thread executing a highest priority task.

15. The system of claim 13, wherein the multithreaded processor is configured such that the interrupt routine selects the highest priority ready task from a ready task list after receiving the interrupt.

16. The system of claim 13, wherein the multithreaded processor is configured such that, after swapping the first task with the highest priority ready task, a schedule is checked to determine whether any ready task of a ready task list has a higher priority than any executing task assigned to the plurality of threads.

17. The system of claim 13, wherein the multithreaded processor is configured such that tasks assigned to the plurality of threads are updated using a minimum possible number of swaps of tasks of the tasks assigned to the plurality of threads and ready tasks so that each task of the tasks assigned to the plurality of threads has a corresponding priority at least as high as a highest priority of the ready tasks.

18. The system of claim 13, further comprising:

a first data structure including a prioritized executing task list of tasks assigned to the plurality of threads; and

a second data structure including a prioritized ready task list of tasks ready to be assigned to the plurality of threads.

19. The system of claim 18, further comprising an interrupt controller configured to set the subsequent interrupt to be directed to the second thread.

20. The system of claim 18, wherein an interrupt mask is configured to set the interrupt to be directed to the particular thread of the plurality of threads.

21. The system of claim 19, further comprising a scheduler configured to:

move the highest priority ready task from the prioritized ready task list of the second data structure to the prioritized executing task list of the first data structure to associate the highest priority ready task with the particular thread; and

check a schedule to determine whether any ready tasks in the second data structure have a higher priority than the lowest priority executing task in the first data structure.

22. The system of claim 21, wherein the particular thread of the plurality of threads is an idle thread associated with an idle task.

23. A non-transitory computer-readable medium containing computer executable instructions that are executable to cause a computer including a multithreaded processor to:

identify a particular thread of a plurality of threads of the multithreaded processor, wherein the multithreaded processor is configured to schedule tasks among the plurality of threads to enable execution of the tasks, the particular thread identified based on comparing tasks executing at the plurality of threads and determining that a first task at the particular thread is a lowest priority executing task at the multithreaded processor at a first time;

set an interrupt to be directed to the particular thread of the plurality of threads, wherein the interrupt indicates at least one task is ready to be executed, and wherein the particular thread of the plurality of threads receives the interrupt and initiates an interrupt routine that selects a highest priority ready task from a ready task list based on comparing a first priority of the highest priority ready task to a second priority of the first task;

determine that a second task at a second thread different from the particular thread is the lowest priority executing task at the multithreaded processor at a second time occurring after the first time; and

set a subsequent interrupt to be directed to the second thread.

24. The non-transitory computer-readable medium of claim 23, wherein the computer executable instructions are further executable to cause the computer to:

after selecting the highest priority ready task from the ready task list, check a schedule to determine whether any ready task has a higher priority than any executing task; and

selectively issue the subsequent interrupt based on a result of checking the schedule to determine whether any ready task has a higher priority than any executing task.

25. An apparatus comprising:

means for receiving an interrupt at a first thread of a set of threads of a multithreaded processor, wherein the multithreaded processor is configured to schedule tasks among threads of the set of threads to enable execution of the tasks, the first thread identified based on comparing tasks executing at the set of threads and determining that a first task at the first thread is a lowest priority executing task at the multithreaded processor at a first time, wherein each thread of the set of threads executes a respective task of a set of executing tasks, and wherein each task of the set of executing tasks and each task of a set of ready tasks has a respective priority;

means for initiating an interrupt routine at the first thread;

means for iteratively swapping, based on the interrupt, a lowest priority executing task of the set of executing tasks with a highest priority task of the set of ready tasks until each task of the set of executing tasks has a priority that is greater than or equal to a priority of every task of the set of ready tasks;

means for determining that a second task at a second thread different from the first thread is the lowest priority executing task at the multithreaded processor at a second time occurring after the first time; and

means for setting a subsequent interrupt to be directed to the second thread.