Method and system for scheduling a thread in a multiprocessor system

• US 8,032,888 B2
• Filed: 10/17/2006
• Issued: 10/04/2011
• Est. Priority Date: 10/17/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Murphy, Declan J., Gitzenis, Savvas, Vengerov, David
• Primary Examiner(s): Puente; Emerson
• Assistant Examiner(s): Truong; Camquy
• Application Number:
  US11/581,917
• Publication Number:
  US 20110004882A1
• Time in Patent Office: 1,813 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 9/5033 considering data affinity
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A method for scheduling a thread on a plurality of processors that includes obtaining a first state of a first processor in the plurality of processors and a second state of a second processor in the plurality of processors, wherein the thread is last executed on the first processor, and wherein the first state of the first processor includes the state of a cache of the first processor, obtaining a first estimated instruction rate to execute the thread on the first processor using an estimated instruction rate function and the first state, obtaining a first estimated global throughput for executing the thread on the first processor using the first estimated instruction rate and the second state, obtaining a second estimated global throughput for executing the thread on the second processor using the second state, comparing the first estimated global throughput with the second estimated global throughput to obtain a comparison result, and executing the thread, based on the comparison result, on one selected from a group consisting of the first processor and the second processor, wherein the thread performs an operation on one of the plurality of processors.

Claims

1. A method for scheduling a thread on a plurality of processors comprising:

obtaining a first state of a first processor in the plurality of processors and a second state of a second processor in the plurality of processors, wherein the thread is last executed on the first processor, and wherein the first state of the first processor comprises a state of a cache of the first processor;

obtaining a first estimated instruction rate to execute the thread on the first processor using an estimated instruction rate function and the first state;

obtaining a second estimated instruction rate for the second processor using the estimated instruction rate function and the second state;

summing the second estimated instruction rate and the first estimated instruction rate to obtain a first estimated global throughput for executing the thread on the first processor;

obtaining a second estimated global throughput for executing the thread on the second processor using the second state;

comparing the first estimated global throughput with the second estimated global throughput to obtain a comparison result; and

executing the thread, based on the comparison result, on one selected from a group consisting of the first processor and the second processor, wherein the thread performs an operation on one of the plurality of processors.

2. The method of claim 1, wherein the state of the cache comprises a state variable that identifies an amount of cache used by currently executing threads of the first processor.

3. The method of claim 1, wherein the estimated instruction rate function is refined using reinforcement learning.

4. The method of claim 1, wherein the first state of the first processor comprises a state of a thread queue of the first processor.

5. The method of claim 4, wherein the state of the thread queue of the first processor comprises at least one selected from a group consisting of a number of threads in a processor queue, a number of newly executed threads in a processor queue of the first processor, and an execution rate of instructions by the first processor.

6. The method of claim 5, wherein instructions for memory access are excluded from the execution rate of instructions.

7. A method for scheduling a thread on a plurality of processors comprising:

obtaining a first state of a first processor in the plurality of processors and a second state of a second processor in the plurality of processors, wherein the thread is last executed on the first processor, and wherein the first state of the first processor comprises a state of a cache of the first processor;

obtaining a first estimated instruction rate to execute the thread on the first processor using an estimated instruction rate function and the first state;

obtaining a first estimated global throughput for executing the thread on the first processor using the first estimated instruction rate and the second state;

obtaining a second estimated instruction rate for the first processor using the estimated instruction rate function and the first state;

obtaining an estimated state of the second processor using the second state, wherein the estimated state reflects the presence of an additional thread on the second processor;

obtaining a third estimated instruction rate for the second processor using the estimated instruction rate function and the estimated state;

summing the second estimated instruction rate and the third estimated instruction rate to obtain a second estimated global throughput for executing the thread on the second processor;

comparing the first estimated global throughput with the second estimated global throughput to obtain a comparison result; and

executing the thread, based on the comparison result, on one selected from a group consisting of the first processor and the second processor, wherein the thread performs an operation on one of the plurality of processors.

8. The method of claim 7, wherein the second estimated global throughput comprises a total of the first estimated instruction rate, the second estimated instruction rate, and a load balancing parameter.

9. A system for scheduling a thread comprising:

a plurality of processors for executing the thread; and

a scheduler configured to;

obtain a first state of a first processor in the plurality of processors and a second state of a second processor in the plurality of processors, wherein the thread is last executed on the first processor, and wherein the first state of the first processor comprises a state of a cache of the first processor;

obtain a first estimated instruction rate to execute the thread on the first processor using an estimated instruction rate function and the first state;

obtain a second estimated instruction rate for the second processor using the estimated instruction rate function and the second state;

sum the second estimated instruction rate and the first estimated instruction rate to obtain a first estimated global throughput;

obtain a second estimated global throughput for executing the thread on the second processor using the second state;

compare the first estimated global throughput with the second estimated global throughput to obtain a comparison result; and

execute the thread, based on the comparison result, on one selected from the group consisting of the first processor and the second processor, wherein the thread performs an operation on one of the plurality of processors.

10. The system of claim 9, wherein the state of the cache comprises a state variable that identifies an amount of cache used by currently executing threads of the first processor.

11. The system of claim 9, wherein a state of a thread queue of the first processor comprises at least one selected from a group consisting of a number of threads in a processor queue, a number of newly executed threads in a processor queue of the first processor, and an execution rate of instructions by the first processor, and wherein instructions for memory access are excluded from the execution rate of instructions.

12. The system of claim 9, wherein obtaining the first estimated global throughput and the second estimated global throughput uses an estimated instruction rate function.

13. The system of claim 9, wherein the estimated instruction rate function is refined using reinforcement learning.

14. The system of claim 9, wherein obtaining the second estimated global throughput comprises:

obtaining the second estimated instruction rate for the first processor using the estimated instruction rate function and the first state;

obtaining an estimated state of the second processor using the second state, wherein the estimated state reflects a presence of an additional thread on the second processor;

obtaining a third estimated instruction rate for the second processor using the estimated instruction rate function and the estimated state; and

summing the second estimated instruction rate and the third estimated instruction rate to obtain the second estimated global throughput.

15. A distributed computer system for scheduling a thread on a plurality of processors comprising:

a plurality of nodes for;

obtaining a first state of a first processor in the plurality of processors and a second state of a second processor in the plurality of processors, wherein the thread is last executed on the first processor, and wherein the first state of the first processor comprises a state of a cache of the first processor;

obtaining a first estimated instruction rate to execute the thread on the first processor using an estimated instruction rate function and the first state;

obtaining a second estimated instruction rate for the second processor using the estimated instruction rate function and the second state;

summing the second estimated instruction rate and the first estimated instruction rate to obtain a first estimated global throughput;

obtaining a second estimated global throughput for executing the thread on the second processor using the second state;

comparing the first estimated global throughput with the second estimated global throughput to obtain a comparison result; and

executing the thread, based on the comparison result, on one selected from a group consisting of the first processor and the second processor, wherein the thread performs an operation on one of the plurality of processors,

wherein each node of the plurality of nodes comprises a hardware processor.

16. The distributed computer system of claim 15, wherein the state of the cache comprises a state variable that identifies an amount of cache used by currently executing threads of the first processor.

17. The distributed computer system of claim 15, wherein the estimated instruction rate function is refined using reinforcement learning.

18. The distributed computer system of claim 15, wherein the first state of the first processor comprises a state of a thread queue of the first processor.