Many-core process scheduling to maximize cache usage

• US 9,417,935 B2
• Filed: 05/01/2012
• Issued: 08/16/2016
• Est. Priority Date: 05/01/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Gounares, Alexander G., Garrett, Charles D.
• Primary Examiner(s): Wai, Eric C
• Assistant Examiner(s): Lee, James J
• Application Number:
  US13/461,748
• Publication Number:
  US 20130117753A1
• Time in Patent Office: 1,568 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 2209/484 Precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A process scheduler for multi-core and many-core processors may place related executable elements that share common data on the same cores. When executed on a common core, sequential elements may store data in memory caches that are very quickly accessed, as opposed to main memory which may take many clock cycles to access the data. The sequential elements may be identified from messages passed between elements or other relationships that may link the elements. In one embodiment, a scheduling graph may be constructed that contains the executable elements and relationships between those elements. The scheduling graph may be traversed to identify related executable elements and a process scheduler may attempt to place consecutive or related executable elements on the same core so that commonly shared data may be retrieved from a memory cache rather than main memory.

Claims

1. A system comprising:

a plurality of processors;

an operating system executing on said plurality of processors;

an individual runnable queue for each of said processors, said each runnable queue comprising one or more executable elements ready for execution by a processor; and

a queue manager being part of said operating system, said queue manager being configured to perform at least the following;

receive a scheduling graph comprising a plurality of executable elements and relationships between said executable elements;

schedule a first executable element of the plurality of executable elements to execute on a first processor of the plurality of processors;

from said scheduling graph, identify a second executable element and a third executable element of the plurality of executable elements that have one or more generational dependent relationships with said first executable element, and place said second executable element and said third executable element on an idle queue as potential executable elements that may be executed;

based at least on determining that any other dependencies of said second executable element have been fulfilled and that said second executable element is ready to execute when the execution of said first executable element is complete, place said second executable element in said runnable queue for said first processor, said first processor being connected to a memory cache, said first executable element placing a memory object in said memory cache upon completion and said second executable element retrieving said memory object from said memory cache upon execution, wherein said first executable element and said second executable element are modified to perform a lightweight message passing based at least on determining that said second executable element is the only dependent element in said runnable queue for said first processor; and

based at least on executing said second executable element on said first processor, determine that said third executable element is no longer reachable from said second executable element, and remove said third executable element from said idle queue.

2. The system of claim 1, said relationships comprising message passing between executable elements.

3. The system of claim 2, said message passing being based on at least one of explicit message passing and implicit message passing.

4. The system of claim 1, said first executable element and said second executable element being functional blocks defined using a functional programming mechanism.

5. The system of claim 4, said functional blocks being originally defined in a functional programming language.

6. The system of claim 1, said queue manager being a function within an execution environment.

7. The system of claim 1, said queue manager being a function within an operating system.

8. The system of claim 1, said scheduling graph comprising executable elements from a plurality of applications.

9. The system of claim 8, said scheduling graph comprising executable elements defining operating system level functions.

10. The system of claim 1, said queue manager also being configured to modify said second executable element by giving it a memory identifier for an output value from the first executable element.

11. A method implemented at a multiple processor computer system, for scheduling executable elements, said method comprising:

receiving a scheduling graph comprising a plurality of executable elements and relationships between said executable elements;

scheduling a first executable element of the plurality of executable elements to execute on a first processor in said multiple processor system, said first processor being associated with a runnable queue comprising one or more executable elements ready for execution;

from said scheduling graph, identifying a second executable element and a third executable element of the plurality of executable elements that have one or more generational dependent relationships with said first executable element, and placing said second executable element and said third executable element on an idle queue as potential executable elements that may be executed;

based at least on determining that any other dependencies of said second executable element have been fulfilled and that said second executable element is ready to execute when the execution of said first executable element is complete, placing said second executable element in said runnable queue for said first processor, said first processor being connected to a memory cache, said first executable element placing a memory object in said memory cache upon completion and said second executable element retrieving said memory object from said memory cache upon execution, wherein said first executable element and said second executable element are modified to perform a lightweight message passing based at least on determining that said second executable element is the only dependent element in said runnable queue for said first processor; and

based at least on executing said second executable element on said first processor, determining that said third executable element is no longer reachable from said second executable element, and removing said third executable element from said idle queue.

12. The method of claim 11 further comprising:

creating said scheduling graph by identifying said executable elements and said relationships between said executable elements.

13. The method of claim 12 further comprising:

receiving an application to execute, said application comprising said executable elements; and

identifying said relationships between said executable elements.

14. The method of claim 13, said second executable element having a dependent relationship with first executable element based on a message passing between said first executable element and said second executable element.

15. The method of claim 13, said second executable element having a dependent relationship with first executable element based on a common memory object shared by said first executable element and said second executable element.

16. The method of claim 12, said creating said scheduling graph being performed at least in part at runtime.

17. The method of claim 11, further comprising determining if one of the first or second executable elements may be moved to a runnable queue for a second processor.

18. The method of claim 11, further comprising modifying said second executable element by giving it a memory identifier for an output value of the first executable element.

19. A computer program product comprising one or more hardware storage devices having stored thereon computer executable instructions that are executable by one or more processors of a multiprocessor system, and that configure the multiprocessor system to perform at least the following:

receive a scheduling graph comprising a plurality of executable elements and relationships between said executable elements;

schedule a first executable element of the plurality of executable elements to be processed on a first processor of said multiprocessor system, said first processor being associated with a runnable queue comprising one or more executable elements ready for execution;

from said scheduling graph, identify a second executable element and a third executable element of the plurality of executable elements that have one or more generational dependent relationships with said first executable element, and place said second executable element and said third executable element on an idle queue as potential executable elements that may be executed;

based at least on determining that any other dependencies of said second executable element have been fulfilled and that said second executable element is ready to execute when the execution of said first executable element is complete, placing said second executable element in said runnable queue to be executed on said first processor after said first executable element completes processing, said first processor being connected to a memory cache, said first executable element placing a memory object in said memory cache upon completion and said second executable element retrieving said memory object from said memory cache upon execution, wherein said first executable element and said second executable element are modified to perform a lightweight message passing based at least on determining that said second executable element is the only dependent element in said runnable queue for said first processor; and

based at least on executing said second executable element on said first processor, determine that said third executable element is no longer reachable from said second executable element, and remove said third executable element from said idle queue.