Modern chip-level multiprocessors (CMPs) contain multiple processor cores sharing a common last-level cache, memory interconnects, and other hardware resources. Workloads running on separate cores compete for these resources, often resulting in highlyvariable performance. To improve fairness and performance, it is helpful to co-schedule workloads having minimal cache and other forms of resource contention. In this work, we develop several cache modeling techniques to help make informed resource management decisions. Using only commonly-available performance counters on existing processors, we introduce an efficient online technique for estimating the cache occupancies of software threads. We derive an analytical model that considers the impact of set-associativity, line replacement policy, and memory locality effects. We demonstrate the effectiveness of occupancy estimation with a series of CMP simulations using SPEC benchmarks. Our occupancy estimation technique is currently being used to develop online utility functions, such as miss-ratio curves (MRCs), which capture performance impacts as a function of resource usage. We are leveraging both online cache occupancy estimation and MRC construction in our ongoing studies of cache-aware scheduling.  Categories and Subject Descriptors For the purposes of our model, we consider a shared last-level cache that may be direct-mapped or n-way set associative. Our objective is to determine the amount of cache space occupied by some thread, τ , at time t, given contention for cache lines by multiple competing threads. Since hardware caches reveal very little information to software, we use hardware performance counters to infer cache state. Using two commonly-available hardware performance events, namely the Copyright is held by the author/owner(s). PACT'10, September 11-15, 2010, Vienna, Austria. ACM 978-1-4503-0178-7/10/09. local and global last-level cache misses, we estimate the number of cache lines, E, occupied by τ at time t. Global cache misses are accumulated across all cores, rather than just the local core. We start by assuming the shared cache is accessed uniformly at random and later relax this requirement in Section 1.1. We also assume each cache line is allocated to a single thread at any time. Data sharing is not considered in this paper, although it is part of our ongoing work. Cache occupancy is effectively dictated by the number of misses experienced by a thread, because cache lines are allocated in response to such misses. Essentially, the current execution phase of a thread τ i influences its cache investment, since any of its lines that it no longer accesses may be evicted by conflicting references to the same cache index by other threads. Evicted lines no longer relevant to the current execution phase of τ i will not incur subsequent misses that would cause them to return to the cache. In what follows, let m l represent the number of misses experienced by the local thread, τ l , under observation over some sampling interval. This term also represents the number of cache lines allocated due to misses. We denote m o to represent the aggregate number of misses by every thread other than τ l , on all cores of a CMP that cause cache lines to be allocated in response to such misses. Finally, τ o represents all other threads, as though they were acting as a single aggregate thread. The linear model described above consists of an inexpensive computation that requires only the ability to measure per-core and per-CMP cache misses, which is provided by most modern processor architectures.
In REF , the authors use performance counters to capture performance impacts as a function of resource usage.
Online cache modeling for commodity multicore processors
PACT '10
Computer Science