Compiler-based scheduling optimization hints for user-level threads

• US 8,205,200 B2
• Filed: 11/29/2005
• Issued: 06/19/2012
• Est. Priority Date: 11/29/2005
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Liao, Shih-wei, Rakvic, Ryan N., Hankins, Richard A., Wang, Hong, Wu, Gansha, Lueh, Guei-Yuan, Tian, Xinmin, Petersen, Paul M., Shah, Sanjiv, Diep, Trung, Shen, John, Chinya, Gautham
• Primary Examiner(s): Wu, Qing
• Application Number:
  US11/289,803
• Publication Number:
  US 20070124732A1
• Time in Patent Office: 2,394 Days
• Field of Search: 718/103
• US Class Current: 718/102
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Method, apparatus and system embodiments to schedule user-level OS-independent “shreds” without intervention of an operating system. For at least one embodiment, the shred is scheduled for execution by a scheduler routine rather than the operating system. The scheduler routine may receive compiler-generated hints from a compiler. The compiler hints may be generated by the compiler without user-provided pragmas, and may be passed to the scheduler routine via an API-like interface. The interface may include a scheduling hint data structure that is maintained by the compiler. Other embodiments are also described and claimed.

Claims

1. A machine-implemented method comprising:

receiving from a compiler scheduling hint information associated with an operating system independent user-level thread, the scheduling hint information configurable to include parallelism information associated with the user-level thread, wherein said receiving further comprises receiving the scheduling hint information via an application programming interface between the compiler and the scheduler, wherein said interface further comprises an attribute table; and

electively taking the associated scheduling hint information into account to perform dynamic run-time scheduling for the user-level thread, wherein said scheduling for said operating system independent user-level thread is performed by a scheduler in user space.

2. The method of claim 1, wherein:

said receiving further comprises receiving scheduling hint information for a plurality of user-level threads; and

said interface further comprises an attribute table for each of the user-level threads.

3. The method of claim 1, wherein:

said scheduler is to schedule said user-level thread for execution without intervention of operating system scheduling logic.

4. The method of claim 1, wherein said scheduling hint information further comprises:

an indication that the user-level thread may be scheduled as an independent unit of execution.

5. The method of claim 4, wherein said utilizing further comprises:

utilizing the scheduling hint information to schedule the user-level thread on a physical sequencer so as to increase parallelism of an original program.

6. The method of claim 1, wherein said scheduling hint further comprises:

an indication that the user-level thread may be fused with another user-level thread without violating dependence constraints.

7. The method of claim 6, wherein said taking said scheduling hint information into account further comprises:

scheduling the user-level thread and the other user-level thread for execution on a same sequencer.

8. The method of claim 6, wherein said taking said scheduling hint information into account further comprises:

scheduling the user-level thread and the other user-level thread for execution on sequencers that are topologically adjacent to each other.

9. The method of claim 6, wherein said taking said scheduling hint information into account further comprises:

scheduling the user-level thread and the other user-level thread for execution on two different physical sequencers that share a single cache.

10. The method of claim 1, wherein said scheduling hint information further comprises:

an indication of the degree of locality for the user-level thread.

11. The method of claim 10, wherein said taking said scheduling hint information into account further comprises:

scheduling another user-level thread with the same degree of locality on a same sequencer as the user-level thread.

12. The method of claim 1, wherein said scheduling hint information further comprises:

a degree of computation indicator.

13. The method of claim 1, wherein the scheduling hint information further comprises:

indication of a hot spot.

14. The method of claim 13, wherein said utilizing further comprises:

utilizing the scheduling hint information to schedule the user-level thread on a physical sequencer so as to reduce the latency of the user-level thread.

15. The method of claim 1, wherein:

said scheduling hint information is independently generated by the compiler without user input.

16. The method of claim 1, wherein:

said taking said scheduling hint information into account further comprises determining whether a performance benefit can be gained if said information is used to guide scheduling decisions; and

if not, disregarding the scheduling hint information when performing said scheduling.

17. A system, comprising:

a memory;

a runtime scheduler to schedule one or more operating system independent user-level threads, said scheduler residing in user space of said memory;

one or more thread execution units to execute said one or more operating system independent user-level threads; and

an interface to pass a compiler-generated scheduling hint associated with at least one of the operating system independent user-level threads from a compiler to the scheduler, the scheduler configured to electively utilize the scheduling hint, wherein said scheduling hint information is received via an application programming interface between a compiler and a scheduler, wherein said interface further comprises an attribute table.

18. The system of claim 17, wherein runtime scheduler is further to:

utilize the scheduling hint in order to select one of the thread execution units to execute the at least one user-level thread.

19. A machine-implemented method, comprising:

performing dependence analysis on a program that includes operating system independent user-level threads;

decomposing the program into independent units of work associated with the operating system independent user-level threads; and

statically generating, without utilizing user-provided pragmatic information, one or more scheduling hints to be associated with at least one of the independent units of work, and

providing the scheduling hints to a runtime scheduler configured to electively utilize provided scheduling hints, wherein said scheduling hint information is received via an application programming interface between a compiler and a scheduler, wherein said interface further comprises an attribute table.

20. The method of claim 19, further comprising:

generating code to update at least one of the scheduling hints during execution of the program.

21. An article comprising a non-transitory machine-accessible medium having a plurality of machine accessible instructions, wherein, when the instructions are executed by a processor, the instructions cause the processor to perform a method, comprising:

performing dependence analysis on a program that includes operating system independent user-level threads;

decomposing the program into independent units of work associated with the operating system independent user-level threads; and

statically generating, without utilizing user-provided pragmatic information, one or more scheduling hints to be associated with at least one of the independent units of work, and

generating compiled code for the program that includes instructions to provide the scheduling hints to a runtime scheduler configurable to electively utilize the scheduling hints, wherein said scheduling hint information is received via an application programming interface between a compiler and a scheduler, wherein said interface further comprises an attribute table.

22. The article of claim 21, further comprising additional machine accessible instructions, wherein, when the instructions are executed by a processor, the instructions further cause the processor to:

generate a graph to represent locality among the independent units of work.

23. A method for a machine having an associated operating system, comprising:

receiving from a compiler static scheduling hint information associated with a user-level thread invisible to the operating system, the static scheduling hint information configurable to include parallelism information associated with the user-level thread, wherein said scheduling hint information is received via an application programming interface between a compiler and a scheduler, wherein said interface further comprises an attribute table; and

electively taking the associated static scheduling hint information into account to perform dynamic run-time scheduling for the user-level thread invisible to the operating system by a scheduler operating in user space.

24. The method of claim 23 wherein the user-level thread invisible to the operating system comprises a shred.