Methods and apparatus for processor task migration in a multi-processor system

• US 7,565,653 B2
• Filed: 02/20/2004
• Issued: 07/21/2009
• Est. Priority Date: 02/20/2004
• Status: Active Grant

• Current Assignee: Sony Computer Entertainment Incorporated (Sony Group Corp.)
• Original Assignee: Sony Computer Entertainment Incorporated (Sony Group Corp.)
• Inventors: Iwamoto, Tatsuya, Inoue, Keisuke
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): ARCOS, CAROLINE H
• Application Number:
  US10/783,238
• Publication Number:
  US 20050188372A1
• Time in Patent Office: 1,978 Days
• Field of Search: 718/100, 718/102, 718/103, 718/104, 718/105
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/4411 Configuring for operating with peripheral devices; Loading of device drivers
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

Methods and apparatus are provided for executing processor tasks on a multi-processing system. The multi-processing system includes a plurality of sub-processing units and a main processing unit that may access a shared memory. Each sub-processing unit includes an on-chip local memory separate from the shared memory. The methods and apparatus contemplate: providing that the processor tasks be copied from the shared memory into the local memory of the sub-processing units in order to execute them, and prohibiting the execution of the processor tasks from the shared memory; and migrating at least one processor task from one of the sub-processing units to another of the sub-processing units.

Claims

1. A method of executing processor tasks on a multi-processing system, the multi-processing system including a plurality of processing units coupled to and for accessing a shared memory, the method comprising:

providing that selected processor tasks for execution and having respective priorities be copied from the shared memory to one or more of the processing units, and that each of the selected tasks is executed at one of the processing units;

providing that the processing units select processor tasks from the shared memory for execution based on the priority levels of the processor tasks;

determining a second processing unit from the plurality of the processing units except for a first processing unit of the processing units, wherein the second processing unit is executing a processor task of lowest priority and having a lower priority than a first selected processor task being executed at the first processing unit;

migrating the first selected processor task being executed at the first processing unit from the first processing unit to the second processing unit; and

after the migrating, providing that the first processing unit run a processor task having a higher priority than the migrated first selected processor task.

2. The method of claim 1, further comprising prohibiting execution of the first selected processor task from the shared memory after copying of the first selected processor task to one or more of the processing units.

3. The method of claim 1, wherein the plurality of processing units comprises a main processor unit and a plurality of sub-processing units, each of the plurality of sub-processing units having a local memory, and wherein the processor tasks are copied to local memory and executed in local memory.

4. The method of claim 1, wherein migration of the first selected processor task is based on a condition.

5. The method of claim 4, wherein satisfaction of the condition and the initiating of the migration is not based on preemptive action.

6. The method of claim 3, further comprising:

requiring that the sub-processing units select processor tasks from the shared memory for execution based on their priority levels.

7. The method of claim 3, further comprising:

requiring that the sub-processing units select a processor task of higher priority before a processor task of lower priority from the shared memory.

8. The method of claim 3, further comprising:

selecting a first processor task of a first priority level from the shared memory for execution by a first sub-processing unit;

selecting a second processor task of a second priority level from the shared memory for execution by a second sub-processing unit; and

yielding the first sub-processing unit to a third processor task of a third priority level before completing the execution of the first processor task, the third processor task being selected because its priority level is higher than any other processor tasks that are ready to be executed.

9. A method of executing processor tasks on a multi-processing system, the multi-processing system including a plurality of processing units coupled to and for accessing a shared memory, the method comprising:

providing that selected processor tasks for execution and having respective priorities be copied from the shared memory to one or more of the processing units, and that each of the selected tasks is executed at one of the processing units;

providing that the processing units select processor tasks from the shared memory for execution based on the priority levels of the processor tasks;

determining a second processing unit from the plurality of the processing units except for a first processing unit of the processing units, wherein the second processing unit is running a processor task of lowest priority and having a lower priority than a first selected processor task running on the first processing unit;

migrating the first selected processor task running on the first processing unit from the first processing unit to the second processing unit; and

after the migrating, providing that the first processing unit run a processor task having a higher priority than the migrated first selected processor task.

10. The method of claim 9, further comprising prohibiting the execution of the first selected processor task from the shared memory after copying of the processor task to one or more of the processing units.

11. The method of claim 9, wherein the plurality of processing units comprises a main processor unit and a plurality of sub-processing units, each of the plurality of sub-processing units having a local memory, and wherein the processor tasks are copied to local memory and executed in local memory.

12. The method of claim 11, further comprising:

requiring that the sub-processing units select a processor task of higher priority before a processor task of lower priority from the shared memory.

13. The method of claim 11, further comprising:

selecting a plurality of processor tasks of associated priority levels from the shared memory, based on the priority levels, for execution by a number of sub-processing units;

Causing an n-th processor task in the shared memory having a given priority level to become ready for execution; and

determining whether the given priority level is higher than any of the priority levels of the plurality of processor tasks whose execution has not been completed.

14. The method of claim 13, wherein at least one of the sub-processing units is operable to perform the determination.

15. The method of claim 13, further comprising:

preemptively replacing one of the plurality of processor tasks of lower priority level than the given priority level with the n-th processor task.

16. The method of claim 15, wherein a first of the sub-processing units is operable to at least initiate the replacement and cause another of the plurality of sub-processing units to yield execution of a processor task of lower priority level.

17. The method of claim 16, further comprising:

providing that the initiating first sub-processing unit issues an interrupt to the yielding, another sub-processing unit in order to initiate the replacement of the processor task of lower priority level.

18. The method of claim 16, further comprising:

providing that the yielding sub-processing unit writes the processor task of lower priority from its local memory back into the shared memory.

19. The method of claim 16, further comprising:

providing that the yielding sub-processing unit copies the n-th processor task of higher priority from the shared memory into its local memory for execution.

20. A method of executing processor tasks on a multi-processing system, the multi-processing system including a plurality of sub-processing units and a main processing unit coupled to and for accessing a shared memory, each sub-processing unit including an on-chip local memory separate from the shared memory, the method comprising:

providing that the processor tasks for execution and having respective priorities be copied from the shared memory into the local memory of the sub-processing units and that each of the tasks is executed at one of the sub-processing units, and prohibiting the execution of the processor tasks from the shared memory after the copying into the local memory of the sub-processing units;

selecting a plurality of processor tasks of associated priority levels from the shared memory for execution by one or more of the sub-processing units;

providing that the sub-processing units select processor tasks from the shared memory for execution based on the priority levels of the processor tasks;

providing that the sub-processing units determine whether an n-th processor task in the shared memory having a given priority level has a higher priority level than any of the priority levels of the plurality of processor tasks;

determining a second sub-processing unit from the plurality of the sub-processing units except for a first sub-processing unit of the sub-processing units, wherein the second sub-processing unit is executing a processor task of lowest priority and having a lower priority than a first selected processor task being executed on the first sub-processing unit;

migrating the first processor task being executed at the first sub-processing unit from the first sub-processing unit to the second sub-processing unit; and

after the migrating, providing that the first sub-processing unit run a processor task having a higher priority than the migrated first processor task.

21. The method of claim 20, further comprising:

providing that a processor task of lower priority running on one of the sub-processing units is preemptively replaced with a processor task of higher priority.

22. The method of claim 20, further comprising:

providing that the sub-processing units use a shared task priority table in determining whether the n-th processor task is of a higher priority level than the plurality of processor tasks.

23. The method of claim 22, wherein:

the shared task priority table includes entry pairs of sub-processing unit identifiers and processor task priority identifiers; and

each entry includes a sub-processing unit identifier and priority identifier pair that indicate a priority level of a given processor task running on an associated sub-processing unit.

24. The method of claim 20, further comprising:

providing that a sub-processing unit, when seeking to determine whether the n-th processor task is of a higher priority level than the plurality of processor tasks, searches the shared task priority table to find an entry pair indicating a lower priority level.

25. A method of executing processor tasks on a multi-processing system, the multi-processing system including a plurality of sub-processing units and a main processing unit coupled to and for accessing a shared memory, each processing unit including an on-chip local memory separate from the shared memory, the method comprising:

providing that the processor tasks for execution and having respective priorities be copied from the shared memory into the local memory of the sub-processing units and that each of the tasks is executed at one of the sub-processing units, and prohibiting the execution of the processor tasks from the shared memory after the copying into the local memory of the sub-processing units;

providing that the sub-processing units select processor tasks from the shared memory for execution based on priority levels of the processor tasks;

determining a second sub-processing unit from the plurality of the sub-processing units except for a first sub-processing unit of the sub-processing units, wherein the second sub-processing unit is executing a processor task of lowest priority and having a lower priority than a first selected processor task running on the first sub-processing unit;

migrating the first selected processor task running on the first sub-processing units to the second sub-processing unit in response to an interrupt received by the first sub-processing unit; and

after the migrating, providing that the first sub-processing unit runs a processor task having a higher priority than the migrated first selected processor task.

26. A multi-processor apparatus, comprising:

a plurality of processing units, each processing unit including local memory in which to execute processor tasks; and

a shared memory operable to store processor tasks that are ready to be executed and have respective priorities, wherein;

the processor tasks are copied from the shared memory into the local memory of the processing units for execution of the processor tasks by the processing units,

the processing units select processor tasks from the shared memory for execution based on the priority levels of the processor tasks, and

a first selected processor task being executed at a first processing unit of the processing units is migrated from the first processing unit to a second processing unit of the processing units for providing that, after the migrating, the first processing unit run a processor task having a higher priority than the migrated first selected processor task, wherein the second processing unit is determined from the plurality of the processing units except for the first processing unit, and wherein the second processing unit is executing a processor task of lowest priority and having a lower priority than the first selected processor task.

27. The apparatus of claim 26, further comprising prohibiting the execution of the first processor selected task from the shared memory after the copying of the first selected processor task to the local memory of one or more of the processing units.

28. The apparatus of claim 26, wherein the plurality of processing units comprises a main processor unit and a plurality of sub-processing units, each of the plurality of sub-processing units having a local memory, and wherein the processor tasks are copied to the local memory and executed in the local memory.

29. The apparatus of claim 28, wherein migration of the first selected processor task is based on a condition.

30. The apparatus of claim 29, wherein satisfaction of the condition and the initiating of the migration is not based on preemptive action.

31. The apparatus of claim 29, wherein the sub-processing units are operable to select processor tasks from the shared memory for execution based on their priority levels.

32. The apparatus of claim 28, wherein the sub-processing units are operable to select a processor task of higher priority before a processor task of lower priority from the shared memory.

33. The apparatus of claim 29, wherein:

a first sub-processing unit is operable to select a first processor task of a first priority level from the shared memory for execution;

a second sub-processing unit is operable to select a second processor task of a second priority level from the shared memory for execution; and

the first sub-processing unit is operable to yield to a third processor task of a third priority level before completing the execution of the first processor task, the third processor task being selected because its priority level is higher than any other processor tasks that a ready to be executed.

34. The apparatus of claim 28, wherein the sub-processing units are operable to:

select a plurality of processor tasks of associated priority levels from the shared memory for execution; and

determine whether an n-th processor task in the shared memory having a given priority level that has become ready for execution at one of the sub-processing units has a higher level priority than any of the priority levels of the plurality of processor tasks whose execution has not been completed.

35. The apparatus of claim 34, wherein at least one of the sub-processing units is operable to perform the determination.

36. The apparatus of claim 34, wherein at least one of the sub-processing units is operable to preemptively replace one of the plurality of processor tasks of lower priority level than the given priority level with the n-th processor task.

37. The apparatus of claim 36, wherein a first of the sub-processing units is operable to at least initiate the replacement and cause another of the plurality of sub-processing units to yield execution of a processor task of lower priority level.

38. The apparatus of claim 37, wherein the initiating sub-processing unit is operable to issue an interrupt to the yielding sub-processing unit in order to initiate the replacement of the processor task of lower priority level.

39. The apparatus of claim 37, wherein the yielding sub-processing unit is operable to write the processor task of lower priority from its local memory back into the shared memory.

40. The apparatus of claim 37, wherein the yielding sub-processing unit is operable to copy the n-th processor task of higher priority from the shared memory into its local memory for execution.

41. A multi-processor apparatus, comprising:

a plurality of sub-processing units, each sub-processing unit including an on-chip local memory and for executing processor tasks; and

a shared memory operable to store processor tasks having respective priorities and that are ready to be executed, wherein;

the processor tasks are copied from the shared memory into the local memory of the sub-processing units for execution by the sub-processing units, and the processor tasks are not executed from the shared memory,

the sub-processing units are operable to select processor tasks from the shared memory for execution based on the priority levels of the processor tasks; and

at least a first sub-processing unit of the sub-processing units is operable to migrate a first selected processor task running on the first sub-processing units to a second processing unit of the sub-processing units in response to an interrupt received by the first sub-processing unit for providing that, after the migrating, the first sub-processing unit runs a processor task having a higher priority than the migrated first selected processor task, wherein the second sub-processing unit is determined from the plurality of the sub-processing units except for the first sub-processing unit, and wherein the second processing unit is running a second processor task of lowest priority and having a lower priority than the first selected processor task.

42. The apparatus of claim 41, wherein the sub-processing units are operable to select a processor task of higher priority before a processor task of lower priority from the shared memory.

43. The apparatus of claim 41, wherein the sub-processing units are operable to:

select a plurality of processor tasks of associated priority levels from the shared memory for execution; and

determine which of the plurality of processor tasks running on the sub-processing units has a lowest priority level that is lower than the priority level of the first selected processor task running on the first sub-processing unit.

44. The apparatus of claim 43, wherein the first sub-processing unit is operable to perform the determination.

45. The apparatus of claim 43, wherein the first selected processor task is migrated to the second sub-processing unit running the second processor task and replaces the second processor task at the second sub-processing unit.

46. The apparatus of claim 45, wherein the first sub-processing unit is operable to at least initiate the migration and cause the second sub-processing unit running the second processor task to yield execution to the first selected processor task.

47. The apparatus of claim 46, wherein the first sub-processing unit is operable to issue an interrupt to the second sub-processing unit in order to initiate the replacement of the second processor task.

48. The apparatus of claim 46, wherein the second sub-processing unit is operable to write the second processor task from its local memory back into the shared memory.

49. The apparatus of claim 43, wherein the second sub-processing unit is operable to copy the first selected processor task from the local memory of the first sub-processing unit into its local memory for execution.

50. The apparatus of claim 41, wherein the first sub-processing unit is operable to use a shared task priority table in determining which processor task is of the lowest priority level.

51. The apparatus of claim 50, wherein:

the shared task priority table includes entry pairs of sub-processing unit identifiers and processor task priority identifiers; and

each entry includes a sub-processing unit identifier and priority identifier pair that indicate a priority level of a given processor task running on an associated sub-processing unit.

52. The apparatus of claim 51, wherein the first sub-processing unit is operable to search the shared task priority table to find an entry pair indicating a lowest priority level.

53. The apparatus of claim 51, wherein the sub-processing units are operable to modify the shared task priority table such that the entry pairs are current.