Hardware support for thread scheduling on multi-core processors

• US 20110088041A1
• Filed: 10/09/2009
• Published: 04/14/2011
• Est. Priority Date: 10/09/2009
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Alameldeen, Alaa R., Chishti, Zeshan A.
• Granted Patent: US 8,276,142 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 2209/501 Performance criteria
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A method, device, and system are disclosed. In one embodiment the method includes scheduling a thread to run on first core of a multi-core processor. The determination as to which core the thread is scheduled on uses one or more processes. These processes may include ranking all of the cores specific to a workload of the thread, establishing a current utilization of each core of the multi-core processor, and calculating an inter-core migration cost for the thread.

Claims

1. A method, comprising:

scheduling a first thread to run on a first core of a multi-core processor, wherein the determination as to which core of the multi-core processor is the first core the first thread is scheduled on employs one or more of

ranking all cores of the multi-core processor specific to a workload of the first thread,

establishing a current utilization of each core of the multi-core processor, and

calculating an inter-core migration cost for the first thread.

2. The method of claim 1, wherein ranking includes pre-establishing a ranked list of all cores in the multi-core processor, wherein the ranked list is based on a first metric.

3. The method of claim 1, wherein establishing the current utilization includes counting a first activity for the first core dynamically during operation of the multi-core processor.

4. The method of claim 3, further comprising counting at least two activities and calculating a metric using the at least two activities, the calculated metric determining the current utilization.

5. The method of claim 3, further comprising:

receiving a thread scheduling query from an operating system;

sampling an activity count of the first core in response to the thread scheduling query;

reporting the activity count to the operating system; and

resetting the activity count.

6. The method of claim 1, wherein calculating the inter-core migration cost for the first thread includes tracking an individual cost of each of a plurality of inter-core migrations for the first thread and averaging cost among the plurality of migrations.

7. The method of claim 6, wherein the cost includes an average number of clock cycles elapsed between a beginning of the inter-core migration of the first thread until the first thread begins executing on a new core.

8. The method of claim 7, wherein the cost is calculated separately for every thread running in the multi-core processor.

9. The method of claim 1, further comprising:

determining a benefit obtained by the first thread from migrating from a first core in the multi-core processor to a second core in the multi-core processor;

determining a cost imposed on the first thread from migrating from the first core to the second core; and

migrating the first thread from the first core to the second core if the benefit outweighs the cost.

10. The method of claim 9, further comprising:

determining the benefit and cost associated with migrating the first thread from the first core separately to each of the one or more other cores in the multi-core processor; and

migrating the first thread from the first core to a one other core of the one or more other cores, the one other core having the greatest difference of the benefit being greater than the cost.

11. The method of claim 1, further comprising:

determining a benefit obtained by a second thread from running on the first core in the multi-core processor versus running on a second core in the multi-core processor;

determining a cost imposed on the first thread currently running on the first core from migrating from the first core to the second core; and

if the benefit outweighs the cost, migrating the first thread from the first core to the second core and scheduling the second thread on the first core.

12. A multi-core processor, comprising:

a first thread of a plurality of threads to run in the multi-core processor;

a core rank map to rank all cores of the multi-core processor specific to one or more thread workloads;

one or more usage counters to determine a current utilization of each core of the multi-core processor;

a thread migration cost counter to calculate an inter-core migration cost for the first thread; and

scheduling logic to schedule the first thread to run on a single core of the multi-core processor, the scheduling logic to employ at least the core rank map, first of the one or more usage counters, and the thread migration cost counter to determine which core in the multi-core processor will be the single core to schedule the thread on.

13. The multi-core processor of claim 12, wherein the core rank map includes first pre-established ranked list of all cores in the multi-core processor, wherein the first ranked list is based on a first metric.

14. The multi-core processor of claim 12, wherein the one or more usage counters are further operable to count a first activity for the first core dynamically during operation of the multi-core processor.

15. The multi-core processor of claim 14, wherein the one or more usage counters are further operable to count at least two activities and the scheduling logic is further operable to calculate a metric using at least two activities, the calculated metric to determine the current utilization.

16. The multi-core processor of claim 14, wherein the scheduling logic is further operable to:

receive a thread scheduling query from an operating system;

sample an activity count of the first core by reading a current count from first of the one or more usage counters in response to the thread scheduling query;

report the activity count to the operating system; and

reset the current count of the first of the one or more usage counters.

17. The multi-core processor of claim 12, wherein the thread migration cost counter is further operable to:

calculate the inter-core migration cost for the first thread by tracking an individual cost of each of a plurality of inter-core migrations for the first thread and averaging the cost among the plurality of migrations.

18. The multi-core processor of claim 17, wherein the cost includes an average number of clock cycles elapsed between a beginning of the inter-core migration of the first thread until the first thread begins to execute on a new core.

19. The multi-core processor of claim 18, wherein the thread migration cost counter is further operable to calculate the cost separately for every thread running in the multi-core processor.

20. The multi-core processor of claim 12, wherein the scheduling logic is further operable to:

determine a benefit obtained by the first thread from migrating from a first core in the multi-core processor to a second core in the multi-core processor;

determine a cost imposed on the first thread from migrating from the first core to the second core; and

migrate the first thread from the first core to the second core if the benefit outweighs the cost.

21. The multi-core processor of claim 20, wherein the scheduling logic is further operable to:

determine the benefit and cost associated with migrating the first thread from the first core separately to each of the one or more other cores in the multi-core processor; and

migrate the first thread from the first core to a one other core of the one or more other cores, the one other core having the greatest difference of the benefit being greater than the cost.

22. The multi-core processor of claim 12, wherein the scheduling logic is further operable to:

determine a benefit obtained by a second thread from running on the first core in the multi-core processor versus running on a second core in the multi-core processor;

determine a cost imposed on the first thread currently running on the first core from migrating from the first core to the second core; and

if the benefit outweighs the cost, migrate the first thread from the first core to the second core and schedule the second thread on the first core.

23. A system, comprising:

a bus;

a system memory coupled to the bus;

a multi-core processor coupled to the bus;

a first thread of a plurality of threads to run in the multi-core processor;

a core rank map to rank all cores of the multi-core processor specific to one or more thread workloads, wherein the core rank map includes first pre-established ranked list of all cores in the multi-core processor, wherein the first ranked list is based on a first metric;

one or more usage counters to determine a current utilization of each core of the multi-core processor, wherein the one or more usage counters are operable to count a first activity for the first core dynamically during operation of the multi-core processor;

a thread migration cost counter to calculate an inter-core migration cost for the first thread; and

scheduling logic to schedule the first thread to run on a single core of the multi-core processor, the scheduling logic to employ at least the core rank map, first of the one or more usage counters, and the thread migration cost counter to determine which core in the multi-core processor will be the single core to schedule the thread on.

24. The system of claim 23, wherein the scheduling logic is further operable to:

determine a benefit obtained by the first thread from migrating from a first core in the multi-core processor to a second core in the multi-core processor;

determine a cost imposed on the first thread from migrating from the first core to the second core; and

migrate the first thread from the first core to the second core if the benefit outweighs the cost.

25. The system of claim 23, wherein the scheduling logic is further operable to:

determine a benefit obtained by a second thread from running on the first core in the multi-core processor versus running on a second core in the multi-core processor;

determine a cost imposed on the first thread currently running on the first core from migrating from the first core to the second core; and

if the benefit outweighs the cost, migrate the first thread from the first core to the second core and schedule the second thread on the first core.