Method and apparatus for improving processing performance of a multi-core processor

• US 9,063,796 B2
• Filed: 08/02/2012
• Issued: 06/23/2015
• 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: Giusto, Paolo, Lakshmanan, Karthik, Rajkumar, Ragunathan
• Primary Examiner(s): NGUYEN, VAN H
• Application Number:
  US13/564,804
• Publication Number:
  US 20140040904A1
• Time in Patent Office: 1,055 Days
• US Class Current: 1/1
• 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

Managing task execution in a multi-core processor may be achieved by employing a spinlock and a multi-processor priority ceiling protocol. The spinlock may be employed to effect a dynamically enforceable mutual exclusion constraint. The multi-processor priority ceiling protocol may be employed 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;

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, including executing global critical sections corresponding to a global mutex M_G when a task T acquires the global mutex M_G at a set priority.

2. The method of claim 1, 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 including executing global critical sections corresponding to a global mutex M_G when a task T acquires the global mutex M_G at a set priority further comprises the set priority being 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.

3. The method of claim 2, 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.

4. 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;

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, including executing global critical sections corresponding to a global mutex when a task acquires the global mutex at a set priority.

5. 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;

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 priority ceiling, including executing global critical sections corresponding to a global mutex M_G when a task T acquires the global mutex M_G at a set priority.

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

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

8. The method of claim 5, wherein employing the global priority ceiling to preempt tasks having selected mutual exclusion constraints by a task having a mutual exclusion constraint with a higher priority ceiling, including executing global critical sections corresponding to a global mutex M_G when a task T acquires the global mutex M_G at a set priority further comprises the set priority being 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.

9. The method of claim 8, 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.

10. The method of claim 5, 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.

11. The method of claim 10, 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.

12. The method of claim 11, 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.

13. The method of claim 12, 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.

14. The method of claim 13, 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.

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

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