Methods and apparatus for scheduling threads on multicore processors under fair distribution of cache and other shared resources of the processors

A computerized device comprising:

• a memory;
• a chip multiprocessor;
• a communications interface;
• an interconnection mechanism coupling the memory, the chip multiprocessor and the communications interface;
• and
• wherein the memory is encoded with thread scheduling application that when executed on the chip multiprocessor provides a thread scheduling process causing the computerized device to perform the operations of:
• identifying a thread operable to be scheduled by a scheduling policy for execution on the chip multiprocessor;
• estimating, for the thread, a performance value based on runtime statistics of the thread for a shared resource on the chip multiprocessor;
• applying the performance value to the scheduling policy in order to reallocate processor time of the thread commensurate with the performance value under fair distribution of the shared resource on the chip multiprocessor;
• and
• applying the performance value to the scheduling policy in order to reallocate processor time of at least one co-executing thread to compensate for the reallocation of processor time to the thread;
• wherein the estimating, for the thread, a performance value based on runtime statistics of the thread for a shared resource on the chip multiprocessor comprises at least one of:
• determining a fair level 2 (L2) cache miss rate based on the number of L2 cache misses per processing cycle that the thread would experience under equal L2 cache sharing on the chip multiprocessor;
• and
• determining a fair cycles per instruction (CPI) rate based on the number of processing cycles per instruction achieved by a thread under equal L2 cache sharing on the chip multiprocessor;
• and wherein the estimating, for the thread, a performance value based on runtime statistics of the thread for a shared resource on the chip multiprocessor comprises:
• estimating a fair number of instructions value based on the number of instructions the thread would have executed under the existing scheduling policy using the fair CIP rate;
• and
• determining the actual number of instructions completed by the thread for a predetermined time.

A non-transitory computer readable medium having computer program logic embodied in computer program code encoded thereon as an encoded set of chip multiprocessor based instructions for performing thread scheduling comprising:

• computer program code for identifying a thread operable to be scheduled by a scheduling policy for execution on the chip multiprocessor;
• computer program code for estimating, for the thread, a performance value based on runtime statistics of the thread for a shared resource on the chip multiprocessor;
• computer program code for applying the performance value to be scheduling policy in order to reallocate processor time of the thread commensurate with the performance value under fair distribution of the shared resource on the chip multiprocessor;
• and
• computer program code for applying the performance value to the scheduling policy in order to reallocate processor time of at least one co-executing thread to compensate for the reallocation of processor time to the thread;
• wherein the computer program code for estimating, for the thread, a performance value based on runtime statistics of the thread for a shared resource on the chip multiprocessor comprises at least one of:
• computer program code for determining a fair level 2 (L2) cache miss rate based on the number of L2 cache misses per processing cycle that the thread would experience under equal L2 cache sharing on the chip multiprocessor;
• and
• computer program code for determining a fair cycles per instruction (CPI) rate based on the number of processing cycles per instruction achieved by a thread under equal L2 cache sharing on the chip multiprocessor;
• and wherein the computer program code for estimating, for the thread, a performance value based on runtime statistics of the thread for a shared resource on the chip multiprocessor comprises:
• computer program code for estimating a fair number of instructions value based on the number of instructions the thread would have executed under the existing scheduling policy using the fair CIP rate;
• and
• computer program code for determining the actual number of instructions completed by the thread for a predetermined time.

A computerized device comprising:

• a memory;
• a chip multiprocessor;
• a communications interface;
• an introduction mechanism coupling the memory, the chip multiprocessor and the communications interface;
• and
• wherein the memory is encoded with thread scheduling application that when executed on the chip multiprocessor provides a means for scheduling applications on the chip multiprocessor comprising:
• means for identifying a thread operable to be scheduled by a scheduling policy for execution on the chip multiprocessor;
• means for estimating, for the thread, a performance value based on runtime statistics of the thread for a shared resource on the chip multiprocessor;
• means for applying the performance value to the scheduling policy in order to reallocate processor time of the thread commensurate with the performance value under fair distribution of the shared resource on the chip multiprocessor;
• and
• means for applying the performance value to the scheduling policy in order to reallocate processor time of at least one co-executing thread to compensate for the reallocation of processor time to the thread;
• wherein the estimating, for the thread, a performance value based on runtime statistics of the thread for a shared resource on the chip multiprocessor comprises at least one of:
• determining a fair level 2 (L2) cache miss rate based on the number of L2 cache misses per processing cycle that the thread would experience under equal L2 cache sharing on the chip multiprocessor;
• and
• determining a fair cycles per instruction (CPI) rate based on the number of processing cycles per instruction achieved by a thread under equal L2 cache sharing on the chip multiprocessor;
• and wherein the estimating, for the thread, a performance value based on runtime statistics of the thread for a shared resource on the chip multiprocessor comprises:
• estimating a fair number of instructions value based on the number of instructions the thread would have executed under the existing scheduling policy using the fair CIP rate;
• and
• determining the actual number of instructions completed by the thread for a predetermined time.