Oracle America, Inc.

Sun Microsystems, Inc.

Alexandra Fedorova

Christopher Small

Daniel Nussbaum

A thread scheduling technique for assigning multiple threads on a single integrated circuit is dependent on the CPIs of the threads. The technique attempts to balance, to the extent possible, the loads among the processing cores by assigning threads of relatively long-latency (low CPIs) with threads of relatively short-latency (high CPIs) to the same processing core.

Thread scheduling in chip multithreading processors

A computer system includes an integrated circuit that has a plurality of processing cores fabricated therein and configured to perform operations in parallel. Each processing core is configured to process multiple threads, where a thread is assigned to one of the plurality of processing cores dependent on a cache hit rate of the thread.

In a computer system with a multi-core processor having a shared cache memory level, an operating system scheduler adjusts the CPU latency of a thread running on one of the cores to be equal to the fair CPU latency which that thread would experience when the cache memory was equally shared by adjusting the CPU time quantum of the thread. In particular, during a reconnaissance time period, the operating system scheduler gathers information regarding the threads via conventional hardware counters and uses an analytical model to estimate a fair cache miss rate that the thread would experience if the cache memory was equally shared. During a subsequent calibration period, the operating system scheduler computes the fair CPU latency using runtime statistics and the previously computed fair cache miss rate value to determine the fair CPI value.

Method and apparatus for achieving fair cache sharing on multi-threaded chip multiprocessors

A thread scheduler identifies a thread operable to be scheduled by a scheduling policy for execution on the chip multiprocessor. The thread scheduler estimates, for the thread, a performance value that is based on runtime statistics of the thread for a shared resource on the chip multiprocessor. Additionally, the thread scheduler applies 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. The thread scheduler also applies 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.

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

A chip multithreading processor schedules and assigns threads to its processing cores dependent on estimated miss rates in a shared cache memory of the threads. A cache miss rate of a thread is estimated by measuring cache miss rates of one or more groups of executing threads, where at least one of the groups includes the thread of interest. Using a determined estimated cache miss rate of the thread, the thread is scheduled with other threads to achieve a relatively low cache miss rate in the shared cache memory.

Cache-aware scheduling for a chip multithreading processor

A caching estimator process identifies a thread for determining the fair cache miss rate of the thread. The caching estimator process executes the thread concurrently on the chip multiprocessor with a plurality of peer threads to measure the actual cache miss rates of the respective threads while executing concurrently. Additionally, the caching estimator process computes the fair cache miss rate of the thread based on the relationship between the actual miss rate of the thread and the actual miss rates of the plurality of peer threads. As a result, the caching estimator applies the fair cache miss rate of the thread to a scheduling policy of the chip multiprocessor.

Methods and apparatus for estimating fair cache miss rates on a chip multiprocessor

An estimate of the throughput of a multi-threaded processor based on measured miss rates of a cache memory associated with the processor is adjusted to account for cache miss processing delays due to memory bus access contention. In particular, the throughput calculated from the cache memory miss rates is initially calculated assuming that a memory bus between the cache memory and main memory has infinite bandwidth, this throughput estimate is used to estimate a request cycle time between memory access attempts for a typical thread. The request cycle time, in turn, is used to determine a memory bus access delay that is then used to adjust the initial processor throughput estimate. The adjusted estimate can be used for thread scheduling in a multiprocessor system.

Method and apparatus for estimating the effect of processor cache memory bus delays on multithreaded processor throughput

An estimate is calculated of the throughput of a multi-threaded processor having N threads based on measured miss rates of a cache memory associated with the processor by calculating, based on the cache miss rates a probability that the processor is in a state with one thread running, a probability that the processor is in a state with two threads are running and continuing to a probability that the processor is in a state with N threads running, multiplying each probability by a measured throughput of the processor when it is in the corresponding state and summing the resulting products. This estimate may also be corrected for bus delays in transferring information between the cache memory and main memory. The estimate can be used for thread scheduling in a multiprocessor system.

Growing community of inventors

Lincoln, MA, United States of America

Alexandra Fedorova