Stall-Time Fair Memory Access Scheduling for Chip Multiprocessors
- 1 January 2007
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 146-160
- https://doi.org/10.1109/micro.2007.21
Abstract
DRAM memory is a major resource shared among cores in a chip multiprocessor (CMP) system. Memory requests from different threads can interfere with each other. Existing memory access scheduling techniques try to optimize the overall data throughput obtained from the DRAM and thus do not take into account inter-thread interference. Therefore, different threads running together on the same chip can experience extremely different memory system performance: one thread can experience a severe slowdown or starvation while another is unfairly prioritized by the memory scheduler. This paper proposes a new memory access scheduler, called the Stall-Time Fair Memory scheduler (STFM), that provides quality of service to different threads sharing the DRAM memory system. The goal of the proposed scheduler is to "equalize " the DRAM-related slowdown experienced by each thread due to interference from other threads, without hurting overall system performance. As such, STFM takes into account inherent memory characteristics of each thread and does not unfairly penalize threads that use the DRAM system without interfering with other threads. We show that STFM significantly reduces the unfairness in the DRAM system while also improving system throughput (i.e., weighted speedup of threads) on a wide variety of workloads and systems. For example, averaged over 32 different workloads running on an 8-core CMP, the ratio between the highest DRAM-related slowdown and the lowest DRAM-related slowdown reduces from 5.26X to 1.4X, while the average system throughput improves by 7.6%. We qualitatively and quantitatively compare STFM to one new and three previously- proposed memory access scheduling algorithms, including network fair queueing. Our results show that STFM provides the best fairness, system throughput, and scalability.Keywords
This publication has 17 references indexed in Scilit:
- DRAMsimACM SIGARCH Computer Architecture News, 2005
- PinPublished by Association for Computing Machinery (ACM) ,2005
- Beyond performance: secure and fair memory management for multiple systems on a chipPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- A performance comparison of contemporary DRAM architecturesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Automatically characterizing large scale program behaviorPublished by Association for Computing Machinery (ACM) ,2002
- A permutation-based page interleaving scheme to reduce row-buffer conflicts and exploit data localityPublished by Association for Computing Machinery (ACM) ,2000
- Symbiotic jobscheduling for a simultaneous multithreaded processorPublished by Association for Computing Machinery (ACM) ,2000
- Scalable hardware priority queue architectures for high-speed packet switchesInternational Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2000
- Dynamic access ordering for streamed computationsInternational Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2000
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973