Thread Cluster Memory Scheduling: Exploiting Differences in Memory Access Behavior

By Yoongu Kim, Michael Papamichael, Onur Mutlu, Mor Harchol-Balter. Micro, 2010

445 citations recorded by the source corpus.

In a modern chip-multiprocessor system, memory is a shared resource among multiple concurrently executing threads. The memory scheduling algorithm should resolve memory contention by arbitrating memory access in such a way that competing threads progress at a relatively fast and even pace, resulting in high system throughput and fairness. Previously proposed memory scheduling algorithms are predominantly optimized for only one of these objectives: no scheduling algorithm provides the best system throughput and best fairness at the same time. This paper presents a new memory scheduling algorithm that addresses system throughput and fairness separately with the goal of achieving the best of both. The main idea is to divide threads into two separate clusters and employ different memory request scheduling policies in each cluster. Our proposal, Thread Cluster Memory scheduling (TCM), dynamically groups threads with similar memory access behavior into either the latency-sensitive (memory-non-intensive) or the bandwidth-sensitive (memory-intensive) cluster. TCM introduces three major ideas for prioritization: 1) we prioritize the latency-sensitive cluster over the bandwidth-sensitive cluster to improve system throughput, 2) we introduce a ``niceness'' metric that captures a thread's propensity to interfere with other threads, 3) we use niceness to periodically shuffle the priority order of the threads in the bandwidth-sensitive cluster to provide fair access to each thread in a way that reduces inter-thread interference. On the one hand, prioritizing memory-non-intensive threads significantly improves system throughput without degrading fairness, because such ``light'' threads only use a small fraction of the total available memory bandwidth. On the other hand, shuffling the priority order of memory-intensive threads improves fairness because it ensures no thread is disproportionately slowed down or starved. We evaluate TCM on a wide variety of multiprogrammed workloads and compare its performance to four previously proposed scheduling algorithms, finding that TCM achieves both the best system throughput and fairness. Averaged over 96 workloads on a 24-core system with 4 memory channels, TCM improves system throughput and reduces maximum slowdown by 4.6%/38.6% compared to ATLAS (previous work providing the best system throughput) and 7.6%/4.6% compared to PAR-BS (previous work providing the best fairness).

Subfields: Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/adeb05eaf20c3d4430b4bd68e90685833f6b05ff

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

Memory scaling: A systems architecture perspective (2013, methodology): “To achieve these goals, we have designed various solutions including QoS-aware memory controllers [57, 58, 53, 32, 33, 54, 5, 69, 41, 23], interconnects [17, 18, 27, 28, 13, 59, 60, 19], and entire memory systems including caches, interconnect, and memory [22, 24, 19].”
Tiered-latency DRAM: A low latency and low cost DRAM architecture (2013, background): “[4, 9, 23, 22, 32, 31]), to mitigate inter-application interference and queueing latencies in multi-core systems.”
A case for exploiting subarray-level parallelism (SALP) in DRAM (2012, methodology): “, [6, 16, 23, 24, 38, 40, 41, 43]) that prioritize certain favorable requests in the memory controller to improve system performance and/or fairness.”
Google Workloads for Consumer Devices: Mitigating Data Movement Bottlenecks (2018, background): “…movement consumes a significant fraction of the total workload energy, (3) it is memory-intensive (i.e., its last-level cache misses per kilo instruction , or MPKI, is greater than 10 [21, 83, 84, 103]), and (4) data movement is the single largest component of the function’s energy consumption.”
MASK: Redesigning the GPU Memory Hierarchy to Support Multi-Application Concurrency (2018, methodology): “Our baseline uses the FR-FCFS memory scheduling policy [110, 152], based on findings from previous works [15, 29, 150] which show that FR-FCFS provides good performance for GPGPU applications compared to other, more sophisticated schedulers [71, 72].”
RowClone: Fast and energy-efficient in-DRAM bulk data copy and initialization (2013, unknown): “Maximum Slowdown [12, 29, 30] Reduction 6% 12% 23%”
Fairness via source throttling: a configurable and high-performance fairness substrate for multi-core memory systems (2010, unknown): “2007], fair memory scheduling [Kim et al. 2010b; Mutlu and Moscibroda 2007, 2008; Nesbit et al. 2006], and fair on-chip interconnects [Das et al.”
Reducing memory interference in multicore systems via application-aware memory channel partitioning (2011, methodology): “Reducing Memory Interference in Multicore Systems via Application-Aware Memory Channel Partitioning Sai Prashanth Muralidhara Lavanya Subramanian Onur Mutlu Pennsylvania State University Carnegie Mellon University Carnegie Mellon University smuralid@cse.psu.edu lsubrama@ece.cmu.edu onur@cmu.edu M”
OWL: cooperative thread array aware scheduling techniques for improving GPGPU performance (2013, background): “Row-buffer locality (RBL) is defined as the average hit-rate of the row buffer across all memory banks [27].”