METHOD AND APPARATUS FOR IMPROVING PROCESSING PERFORMANCE OF A MULTI-CORE PROCESSOR

• US 20140040904A1
• Filed: 08/02/2012
• Published: 02/06/2014
• Est. Priority Date: 08/02/2012
• Status: Active Grant

• Current Assignee: Carnegie Mellon University, GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: Carnegie Mellon University, GM Global Technology Operations LLC (General Motors Company)
• Inventors: Rajkumar, Ragunathan, Giusto, Paolo, Lakshmanan, Karthik
• Granted Patent: US 9,063,796 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for managing task execution in a multi-core processor includes employing a spinlock to effect a dynamically enforceable mutual exclusion constraint and employing a multi-processor priority ceiling protocol to effect the dynamically enforceable mutual exclusion constraint to synchronize a plurality of tasks executing in the first and second processing cores of the multi-core processor.

Claims

1. A method for managing task execution in a multi-core processor, comprising employing a spinlock to effect a dynamically enforceable mutual exclusion constraint and employing a multi-processor priority ceiling protocol to effect the dynamically enforceable mutual exclusion constraint to synchronize a plurality of tasks executing in the first and second processing cores of the multi-core processor.

2. The method of claim 1, wherein employing the multi-processor priority ceiling protocol comprises employing a global priority ceiling to preempt tasks having selected mutual exclusion constraints by a task having a mutual exclusion constraint having a higher remote priority ceiling.

3. The method of claim 2, wherein employing a global priority ceiling to preempt tasks having selected mutual exclusion constraints by a task having a mutual exclusion constraint having a higher remote priority ceiling comprises executing global critical sections corresponding to a global mutex M_G when a task T acquires the global mutex M_G at a priority that is set in accordance with the following relationship:

p(M_G)=p(G)+p(T0)

wherein p(M_G) is a priority ceiling for the global mutex M_G,

p(G) is a base priority level greater than another executing task in the system, and

p(T0) is the priority of a highest priority task T0 that can lock the global mutex M_G.

4. The method of claim 3, wherein the global mutex M_G is a mutex shared by tasks deployed in different ones of the first and second processing cores of the multi-core processor.

5. A method for managing task execution in a multi-core processor, comprising:

executing a runnable of a task in a first processing core of the multi-core processor including introducing a static offset for another runnable of a task executing in a second processing core of the multi-core processor to effect a statically defined mutual exclusion constraint across said runnables;

employing a spinlock to effect a dynamically enforceable mutual exclusion constraint and employing a multi-processor priority ceiling protocol to effect the dynamically enforceable mutual exclusion constraint to synchronize a plurality of tasks executing in the first and second processing cores of the multi-core processor.

6. The method of claim 5, wherein employing the multi-processor priority ceiling protocol to effect the dynamically enforceable mutual exclusion constraint comprises employing a global priority ceiling that allows for tasks having selected mutual exclusion constraints to be preempted by a mutual exclusion constraint with a higher remote priority ceiling.

7. A method for managing task execution in a multi-core processor, comprising:

executing a runnable of a task in a first processing core including introducing a static offset for another runnable of a task executing in a second processing core to effect a statically defined mutual exclusion constraint across said runnables; and

selectively employing spinlocks, set/wait events, and multi-processor priority ceiling protocols to effect mutual exclusion constraints to synchronize a plurality of tasks executing in the first and second processing cores.

8. The method of claim 7, wherein employing set/wait events statically enforce the mutual exclusion constraints.

9. The method of claim 7, wherein employing spinlocks and the multi-processor priority ceiling protocols dynamically enforce the mutual exclusion constraints.

10. The method of claim 7, wherein employing multi-processor priority ceiling protocols comprises employing a global priority ceiling to preempt tasks having selected mutual exclusion constraints by a task having a mutual exclusion constraint with a higher remote priority ceiling.

11. The method of claim 10, wherein employing the global priority ceiling to preempt tasks having selected mutual exclusion constraints comprises executing global critical sections corresponding to a global mutex M_G when a task T acquires the global mutex M_G at a priority that is set in accordance with the following relationship:

p(M_G)=p(G)+p(T0)

wherein p(M_G) is a priority ceiling for the global mutex M_G,

p(G) is a base priority level greater than another executing task in the system, and

p(T0) is the priority of a highest priority task T0 that can lock the global mutex M_G.

12. The method of claim 11, wherein the global mutex M_G is a mutex shared by tasks deployed in each of the first and second processing cores of the multi-core processor.

13. The method of claim 7, wherein employing the multi-processor priority ceiling protocols comprises assigning priority to a task within a global critical section guarded by a global mutex with a priority of the global critical section.

14. The method of claim 13, wherein employing the multi-processor priority ceiling protocols further comprises permitting a first task within the global critical section to preempt a second task within the global critical section when a priority of the first task is greater than a priority of the second task.

15. The method of claim 14, wherein employing the multi-processor priority ceiling protocols further comprises granting a global mutex to a task using an atomic transaction in shared memory of the multi-core processor when the global mutex is not held by another task.

16. The method of claim 15, wherein employing the multi-processor priority ceiling protocols further comprises adding a task to a prioritized queue on the global mutex before preempting the task when a request for a global mutex cannot be granted, wherein a priority for the task added to the prioritized queue is pre-assigned.

17. The method of claim 16, wherein employing the multi-processor priority ceiling protocols further comprises making a highest priority task eligible for execution in a host processing core for the highest priority task at the global critical section priority for the highest priority task when a task attempts to release the global mutex.

18. The method of claim 17, wherein employing the multi-processor priority ceiling protocols further comprises pre-assigning priorities to tasks outside global critical sections.

19. The method of claim 18, wherein employing the multi-processor priority ceiling protocols further comprises employing a single processor priority ceiling protocol for a request to a local mutex.