Cache performance prediction, partitioning and scheduling based on cache pressure of threads

A method for scheduling a plurality of threads on a processor having a plurality of cores, the cores sharing a last level cache (LLC), the method comprising:

• identifying a first scenario having a first combination of threads running on the processor;
• identifying a second scenario having a second combination of threads running on the processor;
• predicting cache occupancies of each of the threads for each of the first and second scenarios, the predicted cache occupancies being a representation of an amount of the LLC that each of the threads would occupy when running with other threads on the processor according to the scenario;
• identifying which of the first and second scenarios results in least objectionable impacts on all threads, the least objectionable impacts taking into account the impact resulting from the predicted cache occupancies;
• and
• scheduling the threads according to the one of the scenarios that results in the least objectionable impacts,
• wherein the predicting of the cache occupancies comprises steps for divvying a hypothetical cache among the threads for each of the first and second combinations of threads using a cache divvying algorithm, the cache divvying algorithm including:
• initializing an amount of unassigned cache;
• initializing a hypothetical cache occupancy for each of the threads to zero;
• and
• assigning a block of the unassigned cache to one of the threads that would exert a maximum cache pressure of all the threads at a currently assigned hypothetical cache occupancy, the hypothetical cache occupancy of the one thread being increased by an amount of the size of the block of the unassigned cache;
• and
• repeating the assigning of the block of the unassigned cache for additional blocks of the unassigned cache until all the unassigned cache is depleted or all the threads have a cache pressure of zero.

A machine readable storage medium for scheduling a plurality of threads on a processor having a plurality of cores, the cores sharing a last level cache (LLC), the machine readable storage medium being non-transitory storage of computer instructions that cause a computer to implement a method, the method comprising:

• identifying a first scenario having a first combination of threads running on the processor;
• identifying a second scenario having a second combination of threads running on the processor;
• predicting cache occupancies of each of the threads for each of the first and second scenarios, the predicted cache occupancies being a representation of an amount of the LLC that each of the threads would occupy when running with other threads on the processor according to the scenario;
• identifying which of the first and second scenarios results in least objectionable impacts on all threads, the least objectionable impacts taking into account the impact resulting from the predicted cache occupancies;
• and
• scheduling the threads according to the one of the scenarios that results in the least objectionable impacts,
• wherein the predicting of the cache occupancies comprises for each of the first and second combination of threads, executing a cache divvying algorithm, the cache divvying algorithm including calculating cache pressure exerted by each of the threads in the combinations of threads, and assigning a block of unassigned cache to one of the threads that would exert a maximum cache pressure of all the threads at a currently assigned hypothetical cache occupancy, the hypothetical cache occupancy of the one thread being increased by an amount of the size of the block of the unassigned cache, the algorithm repeating the assigning until all the unassigned cache is depleted or all cache pressures of all threads of the combination of threads are zero, each of the threads having a predicted occupancy defined by the assigned hypothetical cache occupancy.