Scheduling optimizations for user-level threads

• US 20070074217A1
• Filed: 09/26/2005
• Published: 03/29/2007
• Est. Priority Date: 09/26/2005
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Shen, John, Bigbee, Bryant, Wang, Hong, Chinya, Gautham, Kaushik, Shivnandan, Petersen, Paul, Patel, Baiju, Diep, Trung, Hankins, Richard, Rakvic, Ryan, Tain, Xinmin, Armstrong, Douglas, Shah, Sanjiv
• Application Number:
  US11/235,865
• Publication Number:
  US 20070074217A1
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/3009 Thread control instructions
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• 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 resides in user space and may be part of a runtime library. The library may also include monitoring logic that monitors execution of a shredded program and provides scheduling hints, based on shred dependence information, to the scheduler. In addition, the scheduler may further optimize shred scheduling by taking into account information about a system'"'"'s configuration of thread execution hardware. Other embodiments are also described and claimed.

Claims

1. A method comprising:

recording dependence information for a plurality of user-level threads of a software program; and

utilizing the dependence information to perform scheduling for the user-level threads, wherein said scheduling for said user-level threads is performed by a scheduler that resides in user space;

wherein said scheduler is to schedule said user-level threads for execution without intervention of an operating system.

2. The method of claim 1, further comprising:

wherein at least two of said plurality of user-level threads share an application image with an OS-controlled thread; and

wherein said scheduler is further to schedule said at least two user-level threads to execute concurrently with each other.

3. The method of claim 1, wherein said recording further comprises:

determining an identifier for a dependent user-level thread responsive to a thread creation instruction in a first user-level thread.

4. The method of claim 3, wherein said recording further comprises:

determining a time stamp associated with creation of the dependent user-level thread.

5. The method of claim 1, wherein said recording further comprises:

determining an identifier for a dependent user-level thread responsive to a synchronization instruction in a first user-level thread.

6. The method of claim 5, wherein said recording further comprises:

determining a time stamp associated with execution of the dependent user-level thread.

7. The method of claim 1, wherein said recording further comprises:

generating a directed graph to represent said dependence information.

8. The method of claim 7, wherein:

said directed graph includes a node for each unique instance of execution for the user-level threads.

9. The method of claim 8, wherein:

each edge between a first and second of said nodes represents a dependence relationship between said first node and said second node.

10. The method of claim 8, wherein:

said directed graph includes a time stamp corresponding to an execution latency for each node.

11. The method of claim 1, wherein said utilizing further comprises:

determining a system critical path that includes one or more of the user-level threads, and

assigning to the user-level threads on the critical path a higher scheduling priority than the remaining user-level threads.

12. The method of claim 1, wherein said utilizing further comprises:

determining a recurring pattern of sequentially-executed user-level threads, and

scheduling the sequentially-executed user-level threads to execute on a single thread execution unit.

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

determining a system critical path that includes one or more of the user-level threads, and

assigning those of the user-level threads that are not on the system critical path to run on one or more low-power thread execution units.

14. A system, comprising:

a first thread execution unit;

a second thread execution unit; and

scheduler logic to schedule a first user-level thread for execution on said first thread execution unit and to schedule a second user-level thread for concurrent execution on said second execution unit;

wherein said scheduler is to perform said scheduling based on dependence information about said first and second user-level threads and is further to perform said scheduling without intervention of an operating system.

15. The system of claim 14, wherein:

said scheduler is further to base said scheduling on hardware allocation information associated with said first and second thread execution units.

16. The system of claim 14, further comprising:

one or more additional thread execution units on which said scheduler is to schedule one or more additional user-level threads for concurrent execution.

17. The system of claim 14, wherein:

said scheduler is to receive said dependence information during an execution pass of a software program, and is further to dynamically consider said dependence information during said same execution pass.

18. The system of claim 14, wherein:

said scheduler is to receive said dependence information during an execution pass of a software program, and is further to consider said dependence information during a subsequent execution pass of the software program.

19. A multi-sequencer multithreading system comprising:

a memory system;

a first sequencer;

a second sequencer coupled to said first sequencer and to said memory system; and

scheduling logic, stored in user space of the memory system, the scheduling logic including one or more instructions to concurrently schedule one or more user-level threads associated with a single application image, wherein said concurrent scheduling is based on feedback about dependencies among user-level threads.

20. The system of claim 19, wherein:

the scheduling logic further includes logic to place a descriptor for a pending user-level thread into a work queue.

21. The system of claim 19, wherein:

said first sequencer is of a first sequencer type and said second sequencer is of a second sequencer type.

22. The system of claim 19, wherein:

the scheduling logic further includes logic to monitor said feedback during execution of a software program.

23. An article comprising a 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:

recording dependence information for a plurality of user-level threads of a software program; and

utilizing the dependence information to perform scheduling for the user-level threads, wherein said scheduling for said user-level threads is performed by a scheduler routine;

wherein said scheduler routine is to schedule said user-level threads for execution without intervention of an operating system.

24. The article of claim 23, wherein:

at least two of said plurality of user-level threads share an application image with an OS-controlled thread; and

said scheduler routine is further to schedule said at least two user-level threads to execute concurrently with each other.

25. The article of claim 23, wherein said instructions that provide for said recording further comprise instructions that provide for, when executed by a processor:

determining an identifier for a dependent user-level thread responsive to a thread creation instruction in a first user-level thread.

26. The article of claim 23, wherein said instructions that provide for said recording further comprise instructions that provide for, when executed by a processor:

determining a time stamp associated with creation of the dependent user-level thread.

27. The article of claim 23, wherein said instructions that provide for said recording further comprise instructions that provide for, when executed by a processor:

generating a directed graph to represent said dependence information.

28. The article of claim 27, wherein:

said directed graph includes a node for each unique instance of execution for the user-level threads.

29. The article of claim 28, wherein:

each edge between a first and second of said nodes represents a dependence relationship between said first node and said second node.

30. The article of claim 28, wherein:

said directed graph includes a time stamp corresponding to an execution latency for each node.

31. The article of claim 23, wherein said instructions that provide for said utilizing further comprise instructions that provide for, when executed by a processor:

determining a system critical path that includes one or more of the user-level threads, and

assigning to the user-level threads on the critical path a higher scheduling priority than the remaining user-level threads.

32. The article of claim 23, wherein said instructions that provide for said utilizing further comprise instructions that provide for, when executed by a processor:

determining a recurring pattern of sequentially-executed user-level threads, and

scheduling the sequentially-executed user-level threads to execute on the same thread execution unit.

33. The article of claim 23, wherein said instructions that provide for said utilizing further comprise instructions that provide for, when executed by a processor:

determining a system critical path that includes one or more of the user-level threads, and

assigning those of the user-level threads that are not on the system critical path to run on one or more low-power thread execution units.