Many-core process scheduling to maximize cache usage
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
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.
-
Specification