Many-core process scheduling to maximize cache usage

摘要

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.

主权项

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; andbased 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.