Scalability analysis for server systems
AssigneeMicrosoft Corporation
InventorsTrishul A. Chilimbi, Chen Ding
Life of this patent
Estimating the term…
Abstract
Described is predicting cache locality in a multicore/multithreaded processing environment including when threads share cache data in a non-uniform interleaving manner. Thread execution traces are analyzed to compute a set of per-thread parameters that can then be used to predict cache miss rates for other cache sizes. In one aspect, a model is based upon a probability that the cache reuse distance will increase because of accesses by other threads, and another probability that the reuse distance will decrease because of intercept accesses by other threads to shared data blocks. Estimates of the number of shared data blocks, possibly shared data blocks and private data blocks are used in the computations.
Claims20
In a computing environment having a plurality of threads, a method comprising, obtaining a plurality of execution traces, each execution trace corresponding to a thread and that thread's accesses to data elements in a cache, and using the execution traces to determine a model for predicting cache locality, including computing a probability of a change to a reuse distance for a thread based upon non-uniform interleaved execution with another thread.
In a computing environment, a system comprising, a multicore processor having a cache accessed by a plurality of threads, a thread tracing mechanism that obtains execution traces corresponding to each thread's access to data blocks in the cache, and an analysis mechanism that builds a model by analyzing the execution traces, including to approximate asymmetrical sharing of a sub-group of the plurality of threads and to estimate effects of concurrent execution on at least some reuse distances of at least one of the threads by using the execution traces to compute a probability that other threads will modify a reuse distance between cache data accesses by one thread.
One or more computer-readable storage media having computer-executable instructions, which when executed perform steps, comprising, computing a footprint for peer threads of a selected thread;
- computing a reuse distance without intercept effects;
- and modifying the reuse distance based on intercept effects, including modeling a number of coherence misses using an intercept probability and a write probability.
Dependencies are inferred from the claim text.