Staged Memory Scheduling: Achieving High Performance and Scalability
in Heterogeneous Systems
Rachata Ausavarungnirun† Kevin Kai-Wei Chang† Lavanya Subramanian†

Onur Mutlu†† Carnegie Mellon University{rachata,kevincha,lsubrama,onur}@cmu.edu‡ Advanced Micro Devices, Inc.

Abstract

cation has a much smaller number of outstanding requests, due
to the sequential execution model and limited instruction window size of CPU cores.
Recent memory scheduling research has focused on memory interference between applications in CPU-only scenarios.
These past proposals are built around a single centralized request buffer at each MC.1 The scheduling algorithm implemented in the MC analyzes the stream of requests in the centralized request buffer to determine application memory characteristics, decides on a priority for each core, and then enforcesthese priorities. Observable memory characteristics may include
the number of requests that result in row-buffer hits [15], thebank-level parallelism of each core [15, 25], memory request
rates [14, 15], overall fairness metrics [24, 25], and other information. Figure 1(a) shows the CPU-only scenario where therequest buffer holds requests only from the CPU cores. In thiscase, the MC sees a number of requests from the CPU cores andhas visibility into their memory behavior. On the other hand,when the request buffer is shared between the CPU cores andthe GPU, as shown in Figure 1(b), the large volume of requests
from the GPU occupies a significant fraction of the MC’s request buffer, thereby limiting the MC’s visibility of the CPU
applications’ differing memory behavior.

gabe.loh@amd.com

When multiple processor (CPU) cores and a GPU integrated
together on the same chip share the off-chip main memory, requests from the GPU can heavily interfere with requests from the CPU cores, leading to low system performanceand starvation of CPU cores. Unfortunately, state-of-the-art
application-aware memory scheduling algorithms are ineffective at solving this problem at low complexity due to the large
amount of GPU traffic. A large and costly request buffer isneeded to provide these algorithms with enough visibility acrossthe global request stream, requiring relatively complex hardware implementations.
This paper proposes a fundamentally new approach that decouples the memory controller’s three primary tasks into threesignificantly simpler structures that together improve system
performance and fairness, especially in integrated CPU-GPU
systems. Our three-stage memory controller first groups requests based on row-buffer locality. This grouping allows thesecond stage to focus only on inter-application request scheduling. These two stages enforce high-level policies regarding performance and fairness, and therefore the last stage consists ofsimple per-bank FIFO queues (no further command reordering
within each bank) and straightforward logic that deals only with
low-level DRAM commands and timing.
We evaluate the design trade-offs involved in our Staged
Memory Scheduler (SMS) and compare it against threestate-of-the-art memory controller designs. Our evaluations
show that SMS improves CPU performance without degrading GPU frame rate beyond a generally acceptable level, while
being significantly less complex to implement than previous
application-aware schedulers. Furthermore, SMS can be configured by the system software to prioritize the CPU or the GPU
at varying levels to address different performance needs.

1

Gabriel H. Loh‡CPU Requests

(a)
(b)

xxxx

xxxx

x

(c)

xxxx

xxxx

xxxxx

x
xxx

GPU Requests
xxxxx

Figure 1. Limited visibility example due to small buffer size. (a) CPU-only
case, (b) MC’s visibility when CPU and GPU are combined, (c) Improved
visibility with a larger request buffer

One approach to increasing the MC’s visibility is to increase
the size of its request buffer. This allows the MC to observe
more requests from the CPU cores to better characterize theirmemory behavior, as shown in Figure 1(c). For instance, witha large request buffer, the MC can identify and service multiple requests from one CPU core to the same row such that they
become row-buffer hits, however, with a small request buffer asshown in Figure 1(b), the MC may not even see these requests
at the same time because the GPU’s requests have occupied the
majority of the request buffer entries.
Unfortunately, very large request buffers impose significant
implementation challenges: analyzing many requests, and assigning and enforcing priorities require large structures withhigh circuit complexity that consume significant die area andpower. Therefore, while building a very large, centralized MC
request buffer could lead to good application-aware memory
scheduling decisions, the resulting area, power, timing and complexity costs are unattractive.
In this work, we propose the Staged Memory Scheduler(SMS), a decentralized architecture for application-aware memory scheduling in the context of integrated multi-core CPU-GPU
systems. The key idea in SMS is to decouple the functional tasksof an application-aware memory controller and partition thesetasks across several simpler hardware structures in a staged fashion. The three primary functions of the MC, which map to theIntroduction

With increasing number of cores in modern chip multiprocessor(CMP) systems, the main memory system has become a criticalshared resource. Memory requests from multiple cores interfere with each other, and this inter-application interference is asignificant impediment to individual application and overall system performance. Previous work on application-aware memory
scheduling [14, 15, 24, 25] has addressed the problem by making the memory controller (MC) aware of application characteristics and appropriately prioritizing memory requests to improvesystem performance and fairness.
Recent systems [4, 10, 27] present an additional challenge byintroducing integrated graphics processing units (GPUs) on thesame die with CPU cores. GPU applications typically demandsignificantly more memory bandwidth than CPU applications
due to a GPU’s ability to execute a large number of parallel
threads. A GPU uses single-instruction multiple-data (SIMD)
pipelines to concurrently execute multiple threads, where agroup of threads executing the same instruction is called a wavefront or a warp. When a wavefront stalls on a memory instruction, a GPU core hides this memory access latency by switching
to another wavefront to avoid stalling the pipeline. Therefore,
there can be thousands of outstanding memory requests fromacross all of the wavefronts. This is fundamentally more memory intensive than CPU memory traffic, where each CPU appli-

1 This buffer can be partly partitioned across banks, but each bank buffer iscentralized for all applications.

1three stages of our proposed MC architecture, are: 1) detectionof basic within-application memory characteristics (e.g., rowbuffer locality), 2) prioritization across applications running on
both CPU cores and GPU, and enforcement of policies to reflect
the application priorities, and 3) low-level command scheduling (e.g., activate, precharge, read/write), enforcement of device
timing constraints (e.g., tRAS , tFAW , etc.), and resolution of resource conflicts (e.g., data bus arbitration).
Our specific SMS implementation makes widespread useof distributed FIFO structures to maintain a simple implementation. SMS can at the same time provide fast service
to low memory-intensity (likely latency-sensitive) applications
and effectively exploit row-buffer locality and bank-level parallelism for high memory-intensity (bandwidth-demanding) applications. While SMS provides a specific implementation of amulti-stage memory controller, our staged approach for MC organization provides a general framework for exploring scalable
memory scheduling algorithms capable of handling the diverse
memory needs of integrated CPU-GPU systems and other heterogeneous systems of the future.
This work makes the following contributions:• We identify and present the challenges posed to existing
memory scheduling algorithms due to the high memorybandwidth demands of GPU applications.
• We propose a new decentralized, multi-stage approach toapplication-aware memory scheduling that effectively handles the interference caused by bandwidth-intensive applications to other applications, while simplifying the hardware implementation by decoupling different functionaltasks of a memory controller across multiple stages.
• We evaluate our proposed approach against three previous
memory scheduling algorithms [14, 15, 31] across a wide
variety of workloads and CPU-GPU systems and showthat it improves CPU performance without degrading GPU
frame rate beyond an acceptable level, while providing adesign that is significantly less complex to implement. Furthermore, SMS can be dynamically configured by the system software to prioritize the CPU or the GPU at varying
levels to address different performance needs.

that controls that memory channel is responsible for scheduling commands such that each bus is used by only one bankat a time. Operations on multiple banks may occur in parallel(e.g., opening a row in one bank while reading data from another bank’s row buffer) so long as the commands are properly
scheduled and any other DRAM timing constraints are obeyed.
An MC can improve memory system throughput by scheduling
requests such that bank-level parallelism, or BLP (i.e., the number of banks simultaneously busy responding to commands), is
increased. A key challenge in the implementation of modern,high-performance MCs is to effectively improve system performance by maximizing both row-buffer hits and BLP while simultaneously providing fairness among multiple CPU cores andthe GPU.

2

2.3

2.2

BackgroundIn this section, we provide a review of DRAM organization anddiscuss how past research dealt with the challenges of providing
performance and fairness for modern memory systems.

2.1

Memory Request Scheduling

Accessing off-chip memory is a major performance bottleneckin microprocessors. The MC is responsible for buffering andservicing memory requests from the different cores and theGPU. Typical implementations make use of a memory request
buffer to hold and keep track of all in-flight requests. Scheduling logic then decides which requests should be serviced andissues the corresponding commands to the DRAM devices.
As all of the cores must share the limited off-chip memory
bandwidth, a large number of outstanding requests greatly increases contention for the memory data and command buses.
Because a bank can only process one command at a time, alarge number of requests also increases bank contention, where
requests must wait for busy banks to finish servicing other requests. A request from one core can also cause a row buffer
containing data for another core to be closed, thereby reducing
the row-buffer hit rate of that other core (and vice-versa). All ofthese effects increase the latency of memory requests by both increasing queuing delays (time spent waiting for the MC to start
servicing a request) and DRAM device access delays (due todecreased row-buffer hit rates and bus contention). As a result,different memory scheduling algorithms have been designed toservice memory requests in an order different from the order inwhich the requests arrived at the MC, to increase row-buffer hit
rates, bank level parallelism, fairness, or to achieve other goals.

Memory Request Scheduling in CPUonly Systems

Memory scheduling algorithms can improve system performance by reordering memory requests to deal with the different constraints of DRAM. The first-ready first-come-first-serve(FR-FCFS) [31, 37] algorithm prioritizes requests that result inrow-buffer hits, and otherwise prioritizes older requests. FRFCFS increases DRAM throughput, but it can cause fairness
problems by unfairly deprioritizing applications with low rowbuffer locality and low memory-intensity, as shown in previous work [21, 24]. Several application-aware memory scheduling algorithms [14, 15, 23, 24, 25] have been proposed to balance both performance and fairness. Parallelism-aware Batch
Scheduling (PAR-BS) [25] batches requests based on their arrival times and prioritizes the oldest batch over others, to provide fairness. In a batch, applications are ranked to preservebank-level parallelism (BLP) within an application’s requests.
ATLAS [14] prioritizes applications that have received the least
memory service. As a result, applications with low memoryintensity, which typically attain low memory service, are prioritized, improving system throughput. However, applications
with high memory-intensity are deprioritized and hence slowed
down significantly, resulting in unfairness [14]. Thread Cluster Memory scheduling (TCM) [15] addresses this unfairness
problem by dynamically clustering applications into low andhigh memory-intensity clusters based on their memory intensities. To improve system throughput, TCM always prioritizes
applications in the low memory-intensity cluster. To prevent unfairness, TCM periodically shuffles priorities of high memory-

Main Memory Organization

DRAM is organized as two-dimensional arrays of bitcells.
Reading or writing data to DRAM requires that a row of bitcells
from the array first be read into a row buffer. This is required
because the act of reading the row destroys the row’s contents.
Reads and writes operate directly on the row buffer. Eventually
the row is “closed” whereby the data in the row buffer is written
back into the DRAM array. Accessing data already loaded in therow buffer, also called a row-buffer hit, incurs a shorter latency
than when the corresponding row must first be “opened” fromthe DRAM array. A modern memory controller (MC) must orchestrate the sequence of commands to open, read, write, andclose rows. Servicing requests in an order that increases rowbuffer hits improves data throughput and reduces the averagelatency to service requests. The MC is also responsible for enforcing a wide variety of timing constraints imposed by modern DRAM standards (e.g., DDR3), such as limiting the rate ofpage-open operations (tFAW ) and ensuring a minimum amountof time between writes and reads (tWTR ).
Each two-dimensional array of DRAM cells constitutes abank. A DRAM chip consists of multiple banks. Multiple
DRAM chips are put together and operated in lockstep to form arank. One or more ranks form a channel. All banks on a channel
share a common set of command and data buses, and the MC
2

80
0

(b)

0.8
0.6
0.4
0.2
0

6

5

80
70
60
50

requires a significant amount of memory bandwidth far exceeding even the most memory-intensive CPU applications, as wehave shown in Figure 2. Previous works [2, 3, 35] have proposed memory request scheduling policies for GPUs and GPGPUs. However, to our knowledge, no previous work has explored application-aware memory scheduling in the context ofintegrated CPU-GPU systems. In particular, as described in
Section 2.4, GPU memory accesses can cause significant interference to other CPU applications since GPU applications havethe combination of high memory intensity, high RBL, and high
BLP. Our goal in this work is to design a new application-aware
scheduler that mitigates inter-application interference to improve system performance and fairness in heterogeneous CPUGPU systems.

3

Challenges with Existing Memory Controllers

3.1

Shortcomings of Previous Mechanisms

As discussed in Section 2,
previously proposed
application-aware memory scheduling algorithms (forCPU-only systems) are designed to improve system performance and fairness by prioritizing some applications overothers, based on applications’ memory access characteristics.
However, when faced with CPU and GPU applications thathave vastly disparate memory access characteristics, thesescheduling algorithms are non-robust, due to specific aspects
in each of their designs, and perform poorly. Figure 3 shows
CPU performance, unfairness, and GPU frame rate of different
previously proposed memory schedulers with varying request
buffer sizes for a 16-core CPU/1-GPU system. These data areaveraged over 35 workloads; details of our methodology are
in Section 5. FR-FCFS [31] provides high GPU frame rate.
However, it provides poor CPU performance and fairness, as it
always prioritizes the row-buffer hits of the GPU. ATLAS [14]provides high CPU performance and fairness compared to otherscheduling mechanisms; however, it significantly degrades theframe rate of the GPU. As CPU applications have lower memory intensities than their GPU counterparts, ATLAS prioritizes
CPU applications over GPU applications, which leads to lower
GPU frame rate. TCM [15] provides good CPU performanceand GPU frame rate; however, it is highly unfair because of theway it clusters applications. TCM places some high-memoryintensity CPU applications in the low memory-intensity cluster,
unfairly prioritizing them over other high-memory-intensity
applications that are placed in the high-memory-intensity
cluster. In the light of these shortcomings of previous memory
scheduling algorithms, we aim to design a fundamentallynew memory scheduler that can robustly provide good system
performance (both CPU performance and GPU performance
together) as well as high fairness to CPU applications.

(c)

5
4
3
2
1
0

Figure 2. Memory access characteristics. (a) Memory intensity, measured by memory requests per thousand instructions, (b) row-buffer locality, measured by the fraction of accesses that hit in the row buffer, and (c)bank-level parallelism, measured by average number of banks kept busy
when there is at least one request outstanding.

In addition to the high-intensity memory traffic of GPU applications, there are other properties that distinguish GPU applications from CPU applications. Kim et al. [15] observed that
CPU applications with streaming access patterns typically exhibit high RBL but low BLP, while applications with less uniform access patterns typically have low RBL but high BLP. In
contrast, GPU applications have both high RBL and high BLP.
The combination of high memory intensity, high RBL and high
BLP means that the GPU will cause significant interference
to other applications across all banks, especially when using amemory scheduling algorithm that preferentially favors requests
that result in row-buffer hits.

2.5

10

90

Figure 3. Performance and unfairness of different memory scheduling algorithms with varying request buffer sizes, averaged over 35 workloads.

f DM
mc tusA
cacmacs
gronch02
Be me05
Game03
Game01Ga

f DM
mc tusA
cacmacs
gronch02
Be me05
Game03
Game01Ga

Bank-Level Parallelism (BLP)160

Row-Buffer Locality (RBL)

240

f DM
mc tusA
cacmacs
gronch02
Be me05
Game03
Game01
Ga

Memory Intensity (MPKI)

320

1

15

M
TC AS
TL
A BS
R S
PA CF
-F
FR

(a)

100

20

M
TC AS
TL
A BS
R S
PA CF
-F
FR

400

25

0

M
TC AS
TL
A BS
R S
PA CF
-F
FR

A typical CPU application has a relatively small number of outstanding memory requests at any time. The size of a processor’s
instruction window bounds the number of misses that can be simultaneously exposed to the memory system. Branch prediction
accuracy limits how large the instruction window size can be
usefully increased. In contrast, GPU applications have very different access characteristics. They generate significantly morememory requests than CPU applications. A GPU application
can consist of many thousands of parallel threads, where memory stalls in one group of threads can be hidden by switchingexecution to one of the many other groups of threads. GPUs
also use fixed-function units (e.g., texture units, z (depth) units,
and color units) that are responsible for a large number of memory requests.
Figure 2 (a) shows the memory request rates for a representative subset of our GPU applications and SPEC2006 (CPU)applications, as measured by memory requests per thousand
instructions when each application runs alone on the system.2
The memory access intensity of the GPU applications is often
multiple times higher than that of the SPEC benchmarks. The
most intensive CPU application we study (mcf) has 42.8% of
the memory intensity of the least memory-intensive GPU application we study (Bench01). Figure 2 (b) shows the row-buffer
hit rates (also called row-buffer locality or RBL). The GPU applications show consistently high levels of RBL, whereas theSPEC benchmarks exhibit more variability. The GPU applications have high levels of spatial locality, often due to access patterns related to large sequential memory accesses (e.g., frame
buffer updates). Figure 2(c) shows the average BLP for each application, demonstrating that the GPU applications access manybanks at the same time.

64
128
256
384
512

GPU Frame Rate

Analysis of GPU Memory Accesses

8
7
6
5
4
3
2
1
0

Unfairness

2.4

CPU Performance

intensity applications. TCM was shown to achieve high system
performance and fairness in multi-core systems.

3.2

The Need for Request Buffer Capacity

The non-robustness of previously proposed CPU-only scheduling algorithms is further magnified when there are a small number of entries in the request buffer, as the memory-intensive
GPU application hogs a large number of request buffer entries.
The results from Figure 2 show that a typical GPU application
has a very high memory intensity. As discussed in Section 1,
the large number of GPU memory requests occupy many of theMC’s request buffer entries, thereby making it difficult for the

Memory Request Scheduling in GPUonly Systems

As opposed to CPU applications, GPU applications are not very
latency sensitive, as there are a large number of independent
threads to tolerate long memory latencies. However, the GPU
2 Section 5 describes our simulation methodology.

34

MC to properly determine the memory access characteristics ofeach of the CPU applications. Figure 3 shows the performance
impact of increasing the MC’s request buffer size for a variety
of memory scheduling algorithms. As can be observed, withincreased visibility within larger request buffers, CPU performance improves (while GPU performance does not degrade beyond a generally acceptable level).

Overview: Our proposed SMS architecture introduces a newmemory controller (MC) design that provides 1) scalability andsimpler implementation by decoupling the primary functions ofan application-aware MC into a simpler multi-stage MC, and2) performance and fairness improvement by reducing the interference from bandwidth-intensive applications. Specifically,
SMS provides these benefits by introducing a three-stage design.
The first stage is the batch formation stage that groups requests
from the same application that access the same row to improverow-buffer locality. The second stage is the batch scheduler thatschedules batches of requests across different applications. The
last stage is the DRAM command scheduler that schedules requests while satisfying all DRAM constraints.
The staged organization of SMS lends directly to a
low-complexity hardware implementation. Figure 4 illustrates
the overall hardware organization of the SMS.

Implementation Challenges in Providing
Request Buffer Capacity

Figure 3 shows that when the MC has enough visibility acrossthe global memory request stream to properly characterize thebehavior of each core, a sophisticated application-aware algorithm like TCM improves CPU performance and fairness
by making better scheduling decisions compared to FR-FCFS,
which is application-unaware. Unfortunately, implementing a
sophisticated algorithm like TCM over such a large request
buffer introduces significant implementation challenges. For
all algorithms that use a centralized request buffer and prioritize requests that result in row-buffer hits (FR-FCFS, PARBS, ATLAS, TCM), content associative memories (CAMs) areneeded for each request buffer entry, to compare its requested
row against the currently open row in the corresponding DRAM
bank. For all algorithms that prioritize requests based on
rank/age (FR-FCFS, PAR-BS, ATLAS, TCM), a large comparison tree (priority encoder) is needed to select the highest
ranked/oldest request from all request buffer entries. The sizeof this comparison tree grows with request buffer size. Furthermore, in addition to this logic for reordering requests and enforcing ranking/age, TCM also requires additional logic to continually monitor each core’s last-level cache MPKI (note thata CPU core’s instruction count is not typically available at theMC), each core’s RBL, which requires additional shadow row
buffer index tracking [6, 24], and each core’s BLP.
Apart from the logic required to implement the policies of thespecific memory scheduling algorithms, all of these MC designs
need additional logic to enforce DRAM timing constraints. Notethat different timing constraints will apply depending on thestate of each memory request. For example, if a memory request’s target bank currently has a different row loaded in its
row buffer, then the MC must ensure that a precharge (row close)
command is allowed to issue to that bank (e.g., has tRAS elapsed
since the row was opened?), but if the row is already closed, thendifferent timing constraints will apply. For each request buffer
entry, the MC will determine whether or not the request can issue a command to the DRAM based on the current state of therequest and the current state of the DRAM system. The DRAM
timing-constraint checking logic (including data and commandbus availability tracking) needs to keep track of the commands
that come from every request buffer entry. This type of monolithic MC effectively implements a large out-of-order scheduler. Note that typical instruction schedulers in modern outof-order processors have only 32 to 64 entries [9]. Even after
accounting for the clock speed differences between CPU coreand DRAM command frequencies, it is very difficult to implement a fully-associative,3 age-ordered/prioritized, out-of-orderscheduler with hundreds of entries [28]; the resulting complexity, cycle time, and power consumption would be unnecessarily
or prohibitively high.
Our goal in this paper is to devise an easier-to-implement,
scalable, application-aware memory scheduling algorithm thatprovides high system performance and fairness in heterogeneous CPU-GPU systems. To this end, we devise both 1) a
new scheduling algorithm and 2) new principles with which amemory scheduler can be organized and simply implemented.

Batch Boundary

Batch Formation
Batch Scheduler

Memory Request
Counters
Source1
Source2
Source3
Source4

Scheduling
Logic

3.3

The Staged Memory Scheduler{

Source1 Source2 Source3 Source4
Req
Req
Req
Req
Req
Req
Req
Req
Req
Req
Req
Req
Req

Req

Req

Req

source select

DRAM Command
Scheduler{

Bank1 Bank2 Bank3 Bank4
Req

Req

Req

Req

Req

Req

Req

Req

Req

Req

Req

Req

Req

Req

Req

Req

Figure 4. Organization of the SMS.

In Sections 4.1 and 4.2, we describe the algorithm used ineach stage. Section 4.3 describes the rationale behind these algorithms. Section 4.4 describes the hardware implementationof SMS. Section 4.5 qualitatively compares SMS to previously
proposed scheduling algorithms.

4.1

The SMS Algorithm

Stage 1 - Batch Formation: The goal of this stage is to combine individual memory requests from each source into batchesof row-buffer hitting requests. It consists of several simple FIFO
structures, one per source (i.e., a CPU core or the GPU). Eachrequest from a given source is initially inserted into its respective FIFO upon arrival at the MC. A batch is simply one or morememory requests from the same source that access the same
DRAM row. That is, all requests within a batch, except perhaps
for the first one, would be row-buffer hits if scheduled consecutively. A batch is deemed complete or ready when an incoming
request accesses a different row, when the oldest request in thebatch has exceeded a threshold age, or when the FIFO is full.
Only ready batches are considered by the second stage of SMS.
Stage 2 - Batch Scheduler: The batch scheduler deals directlywith batches, and therefore need not worry about scheduling to
optimize for row-buffer locality. Instead, the batch scheduler
can focus on higher-level policies regarding inter-applicationinterference and fairness. The goal of the batch scheduler isto prioritize batches from applications that are latency critical,
while making sure that bandwidth-intensive applications (e.g.,
the GPU) still make reasonable progress.
The batch scheduler operates in two states: pick (a batch tosend downstream) and drain (the picked batch of requests). In
the pick state, the batch scheduler considers every source FIFO
(from stage 1) that contains a ready batch. It picks one readybatch based on either a shortest job first (SJF) or a round-robinpolicy. Using the SJF policy, the batch scheduler chooses theoldest ready batch from the source with the fewest total in-flightmemory requests across all three stages of the SMS. SJF prioritization reduces average request service latency, and it tends to favor latency-sensitive applications, which tend to have fewer total

3 Fully associative in the sense that a request in any one of the request buffer
entries could be eligible to be scheduled in a given cycle.

4requests. Using the round-robin policy, the batch scheduler simply picks the next ready batch in a round-robin manner acrossthe source FIFOs. This ensures that high memory-intensity applications receive adequate service. Overall, the batch scheduler
uses the SJF policy with a probability p and the round-robin policy otherwise. p is a configurable parameter, which is explained
in detail in Section 4.2.
After picking a batch, the batch scheduler enters a drain state
where it forwards the requests from the selected batch to thefinal stage of the SMS. The batch scheduler simply dequeues
one request per cycle until all requests from the batch have been
removed from the selected FIFO. The batch scheduler then reenters the pick state to select the next batch to drain.
Stage 3 - DRAM Command Scheduler (DCS): The DCS
consists of one FIFO queue per DRAM bank (e.g., eightbanks/FIFOs per rank for DDR3). The drain state of the batchscheduler places the memory requests directly into these FIFOs.
Note that because batches are moved into the DCS FIFOs one
batch at a time, row-buffer locality within a batch is preserved
within a DCS FIFO. At this point, any higher-level policy decisions have already been made by the batch scheduler; therefore,
the DCS simply issues low-level DRAM commands, ensuring
DRAM protocol compliance.
In any given cycle, the DCS considers only the requests at thehead of each of the per-bank FIFOs. For each request, the DCS
determines whether that request can issue a command based on
the request’s current row-buffer state (e.g., is the row buffer already open with the requested row?) and the current DRAM
state (e.g., time elapsed since a row was opened in a bank, anddata bus availability). If more than one request is eligible to issue a command in any given cycle, the DCS arbitrates acrosseach DRAM bank in a round-robin fashion.

4.2

memory-intensity, as described in Section 4.1 and 2) all applications’ requests when the system is lightly loaded, such thatrequests are not unnecessarily delayed in the batch formation
FIFOs, while banks are potentially idle. This latter bypass isenabled whenever the total number of in-flight requests (acrossall sources) in the DCS is less than sixteen.
SJF Probability: As described above, the batch scheduler uses
the SJF policy with probability p and the round-robin policy
with probability 1 − p. The value of p determines whether the
CPU or the GPU receives higher priority. When p is high, theSJF policy is applied more often and applications with fewer
outstanding requests are prioritized. Hence, the batches of thelikely less memory-intensive CPU applications are prioritizedover the batches of the GPU application. On the other hand,when p is low, request batches are scheduled in a round-robinfashion more often. Hence, the memory-intensive GPU application’s request batches are likely scheduled more frequently,
and the GPU is prioritized over the CPU. Different systems(and maybe even the same system at different times) could havedifferent performance needs. In some systems, CPU performance could matter more than GPU performance, while in othersystems, GPU performance could matter more. Therefore, we
make p a dynamically configurable parameter that can be tuned
to appropriately prioritize the CPU or the GPU based on the system’s needs. We evaluate sensitivity to p and its configurability
in Section 6.2.1.

4.3

SMS Rationale

In-Order Batch Formation: It is important to note that batchformation occurs in the order of request arrival. This potentially sacrifices some row-buffer locality, as requests to thesame row may be interleaved with requests to other rows. We
considered many variations of batch formation that allowed
out-of-order grouping of requests, to maximize the length ofa run of row-buffer hitting requests, but the overall performance benefit was not significant.5 First, constructing very large
batches of row-buffer hitting requests can introduce significant
unfairness as other requests may need to wait a long time fora bank to complete its processing of a long run of row-buffer
hitting requests [21, 24]. Second, row-buffer locality acrossbatches may still be exploited by the DCS. For example, consider a core that has three batches accessing row X, row Y, andthen row X again. If X and Y map to different DRAM banks,
say banks A and B, then the batch scheduler will send the first
and third batches (row X) to bank A, and the second batch (rowY) to bank B. Within the DCS’s FIFO for bank A, the requests
for the first and third batches could still all be one after the other,
thereby exposing the row-buffer locality across the batches.
In-Order Batch Scheduling from a Per-Source FIFO: Due tocontention and back-pressure in the system, it is possible that a
FIFO in the batch formation stage contains more than one valid
batch. In such a case, it could be desirable for the batch scheduler to pick one of the batches not currently at the head of the
FIFO. For example, the bank corresponding to the head batch
may be busy while the bank for another batch is idle. Scheduling batches out of order could decrease the service latency forthe later batches, but in practice we found that it does not make a
big difference6 and adds significant implementation complexity.
It is important to note that even though batches are dequeued
from the batch formation stage in arrival order per FIFO, request ordering can still slip between FIFOs. For example, thebatch scheduler may choose a recently arrived (and formed)
batch from a high-priority (i.e., latency-sensitive) source eventhough an older, larger batch from a different source is ready.
In-Order DRAM Command Scheduling: For each of theAdditional Algorithm Details

Batch Formation Thresholds: The batch formation stage
holds requests in the per-source FIFOs until a complete batchis ready. This could unnecessarily delay requests, as the batch
will not be marked ready until a request to a different row arrives
at the MC, or the FIFO becomes full. This additional queuing
delay can be particularly detrimental to the performance of low
memory-intensity, latency-sensitive applications.
SMS considers an application’s memory intensity in forming batches. For applications with low memory-intensity (<1miss per thousand cycles (MPKC)), SMS completely bypasses
the batch formation and batch scheduler stages, and forwards
requests directly to the DCS per-bank FIFOs. For these latencysensitive applications, such a bypass policy minimizes the delay to service their requests. Note that this bypass operation
will not interrupt an on-going drain from the batch scheduler,which ensures that any separately scheduled batches maintaintheir row-buffer locality.
For medium memory-intensity (1-10 MPKC) and highmemory-intensity (>10 MPKC) applications, the batch formation stage uses age thresholds of 50 and 200 cycles, respectively.
That is, regardless of how many requests are in the current batch,when the oldest request’s age exceeds the threshold, the entire
batch is marked ready (and consequently, any new requests that
arrive, even if accessing the same row, will be grouped into a
new batch).4
Request Bypass: We observe that there are two instances when
it is beneficial to let requests bypass the batch formation andscheduling stages and proceed directly to the DCS per-bank
FIFOs: 1) the latency-sensitive requests of applications with low
4 Note that while TCM uses the MPKI metric to classify memory intensity,
SMS uses misses per thousand cycles (MPKC) since the per-application instruction counts are not typically available in the MC. While it would not be overly
difficult to expose this information, this is just one more implementation overhead that SMS can avoid. We also evaluated our mechanism using MPKI, andwe found that it provides similar results.

5 We evaluated our mechanism with out-of-order batch formation. Out-oforder provides <5% performance difference over in-order batch formation.
6 We found there is less than 1% performance difference because per-source
FIFOs already keep batches in age order.

5

Storage
Description
Storage Overhead of Stage 1: Batch formation stage
CPU FIFO queues
A CPU core’s FIFO queue
GPU FIFO queues
A GPU’s FIFO queue
MPKC counters
Counts per-core MPKC
Last request’s row index
Stores the row index of the last request to the FIFO
Storage Overhead of Stage 2: Batch Scheduler
CPU memory request counters
Counts the number of outstanding memory requests of a CPU core
GPU memory request counter
Counts the number of outstanding memory requests of the GPU
Storage Overhead of Stage 3: DRAM Command Scheduler
Per-Bank FIFO queues
Contains a FIFO queue per bankSize
Ncore × Queue Sizecore = 160 entries
NGPU × Queue SizeGPU = 20 entries
Ncore × log2 MPKCmax = 160 bits
(Ncore + NGPU ) × log2 Row Index Size = 204 bits
Ncore × log2Countmax CPU = 80 bits
NGPU × log2Countmax GPU = 10 bits
Nbanks × Queue Sizebank = 120 entries

Table 1. Hardware storage required for SMS.

per-bank FIFOs in the DCS, the requests are already groupedby row-buffer locality (because the batch scheduler drains anentire batch at a time), and arranged in an order that reflects
per-source priorities. Further reordering at the DCS could undo
the prioritization decisions made by the batch scheduler. The
in-order nature of each of the DCS per-bank FIFOs does notprevent out-of-order scheduling at the global level. A CPU’s
requests may be scheduled to the DCS in arrival order, but therequests may get scattered across different banks, and the issueorder among banks may be out-of-order relative to each other.

4.4

sixteen CPU cores and a GPU, the aggregate capacity of allof these FIFOs is 300 requests, although at any point in time,
the SMS logic can only consider or act on a small subset ofthe entries (i.e., the seventeen batches at the heads of the batchformation FIFOs and the requests at the heads of the per-bank
DCS FIFOs). In addition to these primary structures, there are asmall number of bookkeeping counters. One counter per sourceis needed to track the number of in-flight requests. Counters
are also needed to track per-source MPKC rates for memoryintensity classification, which are periodically reset to adapt tophase changes.7 Table 1 summarizes the hardware overhead required for each stage of SMS.

Hardware Implementation

Batch Formation: The batch formation stage consists of one
FIFO per source. Each FIFO maintains an extra register thatrecords the row index of the last request inserted into the FIFO,
so that any incoming request’s row index can be compared todetermine if the request can be added to the existing batch. Notethat this requires only a single comparator (used only once at
insertion) per FIFO. Contrast this to a conventional monolithic
request buffer where comparisons on every request buffer entry
are made every cycle, potentially against all currently open
rows across all banks.
Batch Scheduler: The batch scheduling stage consists primarily of combinatorial logic to implement the batch selection
rules. When using the SJF policy, the batch scheduler needs
to pick the batch corresponding to the source with the fewest
in-flight requests, which can be easily performed with a treeof MIN operators (a priority encoder). Note that this tree
is relatively shallow since it grows as a function of only the
number of FIFOs. Contrast this to the monolithic scheduler
where the various ranking trees grow as a function of the total
number of request buffer entries.
DRAM Command Scheduler: The DCS stage consists of the
per-bank FIFOs. The logic to track and enforce the various
DRAM timing and power constraints is identical to the case of
the monolithic scheduler, but the scale is drastically different.
The DCS’ DRAM command-processing logic considers only
the requests at the head of each of the per-bank FIFOs (eight
per rank for DDR3), whereas the monolithic scheduler requires
logic to consider every request buffer entry.
Request Bypass: Bypass for a low memory-intensity application is enabled by setting its threshold age for batching to zero.
This allows incoming requests of the application to fall throughthe first stage into the batch scheduler. The batch scheduler, bydesign, prioritizes low memory-intensity applications using the
SJF policy. Therefore, no additional logic/wiring is required to
bypass low memory-intensity applications’ requests. Bypassing
requests of all applications when the system is lightly loaded
can be accomplished by simply setting both SJF probability andthreshold age to zero. This will allow requests from every application to proceed directly into the DCS FIFOs in a round-robinfashion at a rate of one request per cycle. However, request bypass in both of these cases incurs a minimum two-cycle delay as
a request needs to spend at least one cycle in the batcher and at
least one cycle in the DCS.
Overall Configuration and Hardware Cost: The final configuration of SMS that we use in this paper consists of the following hardware structures whose sizes are empirically determined. The batch formation stage uses 10-entry FIFOs for eachof the CPU cores, and a 20-entry FIFO for the GPU. The DCS
uses a 15-entry FIFO for each of the eight DDR3 banks. For

4.5

Qualitative Comparison with Previous
Scheduling Algorithms

We described recently proposed application-aware memory
schedulers (PAR-BS [25], ATLAS [14], and TCM [15]) in Section 2. We now qualitatively compare SMS with these schedulers.
PAR-BS batches memory requests based on their ages andcores, and prioritizes all requests from one batch over others.
As a result, the bandwidth-intensive GPU’s requests in the oldest batch are prioritized over all CPU requests that are not in
the oldest batch. This leads to significant CPU performance andfairness loss compared to SMS, which keeps the slowdown of
CPU applications in check by employing the SJF batch scheduling policy described in Section 4.
ATLAS ranks applications based on their attained memory
service and prioritizes higher-ranked (low-attained-service) applications over lower-ranked ones. As a result, it effectively
deprioritizes the GPU, which has high memory bandwidth demand, for most of the time. ATLAS prioritizes the GPU overa CPU application only when the attained service of that application becomes higher than that of the GPU. While thisattained-service based behavior of ATLAS was shown to leadto high unfairness in CPU-only systems (due to its almostconsistent deprioritization of heavily memory-intensive applications) [14], we found that ATLAS provides the best fairness(and the best performance) among previous algorithms becauseof the shortcomings of TCM we describe next. However, as
it consistently deprioritizes the GPU and has a strict rank order
between applications, ATLAS reduces the row-buffer locality of
the GPU and leads to unfairness among CPU applications. SMS
overcomes these two problems by 1) servicing GPU requests inbatches, and 2) prioritizing requests at the batch level insteadof enforcing a rank order among applications (which improves
fairness).
TCM was shown to provide the best performance andfairness in CPU-only systems [15]. Grouping applications
into latency-sensitive or bandwidth-sensitive clusters based on
their memory intensities and employing a throughput oriented
scheduling policy for the former cluster and a fairness oriented policy for the latter leads to both high system performance and fairness in CPU-only systems. However, in an integrated CPU-GPU system, the GPU generates a significantly
larger number of memory requests compared to the CPU cores,
which makes it difficult for TCM to appropriately group applications into two clusters using a single threshold value. As
7 In a 16-core CPU/1-GPU design, SMS requires sixteen 10-bit counters, sixteen 5-bit counters, and one 10-bit counter. In our experiment, we reset every
10,000 cycles.

6

Parameter
CPU Clock Speed
CPU reorder buffer
CPU L1 cache
CPU L2 cache

Setting
3.2GHz128 entries
32KB Private, 4-way
8MB Shared, 16-way

Parameter
GPU Clock Speed
GPU Max Throughput
GPU Texture/Z/Color units

Setting
800Mhz1600 ops/cycle
80/128/32

Parameter
Channels/Ranks/BanksDRAM BustRAS/tRC/tRRD
CPU Cache Rep. Policy

Setting
4/1/8
64 bits/channel
35/47.5/6.25 ns
LRU

Parameter
DRAM Row buffer sizetRCD/tCAS/tRPtWTR/tRTP/tWR
MC request buffer size

Setting
2KB
12.5/12.5/12.5 ns
7.5/7.5/15 ns
300

Table 2. Simulation parameters.

shows the memory intensity of GPU applications, measured interms of misses per kilo instructions (MPKI)9 and also the percentage of memory requests that come from fixed function units.
GPU memory accesses are collected after having first been filtered through the GPU’s internal cache hierarchy; therefore, we
do not further model internal GPU caches in our hybrid CPUGPU simulation framework.

a result, TCM ends up grouping the GPU together with othermemory-intensive CPU applications in the bandwidth-sensitive
cluster. The fairness-oriented policy employed in this cluster
causes the GPU to be prioritized over the memory-intensive
CPU applications, thereby leading to high slowdowns for thedeprioritized CPU applications and thus low fairness. In addition, we found that TCM makes non-robust clustering decisions,which classify some applications with high memory-intensity
into the latency-sensitive cluster, again due to the fact that theintensity of the GPU skews the bandwidth measurements TCM
uses to form the clusters. These misclassified memory-intensive
applications that are admitted to the latency-sensitive cluster
cause significant slowdowns to memory-non-intensive applications, leading to high unfairness and low system performancecompared to ATLAS and SMS.
In contrast to all these previous schedulers, SMS prioritizes
shorter batches of row-buffer-hit requests over longer batches(as determined by the SJF probability, p). As a result, SMS
1) preserves row-buffer locality, and most of the time, prioritizes the CPU applications which have shorter batches than the
GPU (for sufficiently high values of p), leading to high system
performance, and 2) does not result in a strict ranking of CPU
applications among each other, leading to high fairness. As wewill quantitatively demonstrate in Section 6, SMS provides thebest CPU performance and fairness compared to these previous
schedulers, while maintaining GPU frame rate above an acceptable level, at a lower hardware cost and with simpler scheduling
logic.

5

Name
Bench01
Bench02
Bench03
Game01
Game02
Game03
Game04
Game05

Description
3D Mark 1
3D Mark 2
3D Mark 3
Shooting Game 1
Shooting Game 2
Shooting Game 3
Adventure Game
Role-playing Game

MPKI
204.0
267.0
419.7
304.7
173.5
345.8
206.6
321.2

% of Requests from FFUs
62.3%
54.2%
99.6%
80.2%
51.0%
60.3%
61.0%
78.5%

Table 3. GPU benchmarks.

We classify CPU benchmarks into three categories (Low,
Medium, and High) based on their memory intensities, measured as last-level cache misses per thousand instructions(MPKI). Table 4 shows the MPKI for each CPU benchmark.
Benchmarks with less than or equal to 1 MPKI are classified as low memory intensity, between 1 and 15 MPKI as
medium memory intensity, and greater than 15 as high memory intensity. Based on these three categories, we randomly
choose a number of benchmarks from each category to form
workloads with seven different intensity mixes: L (All Low),
ML (Medium/Low), M (All Medium), HL (High/Low), HML(High/Medium/Low), HM (High/Medium) and H (All High).
The co-running GPU benchmark is randomly selected for eachworkload.

Experimental Methodology

Namepovraytonto
calculix
perlbenchdealII
namd
wrf
gcc
sjeng

We use an in-house cycle-level simulator to perform our evaluations. For our performance evaluations, we model a systemwith sixteen x86-like CPU cores and a GPU. Each CPU coreis a three-wide out-of-order processor with a cache hierarchy
including per-core L1 caches and a shared L2 cache. The GPU
does not share the CPU caches. The specification of the GPU wemodel is similar to the AMD RadeonTM 5870 specification [1].8
The GPU has 20 cores, and each core consists of 16 SIMD functional units. A SIMD functional unit can process a VLIW instruction that can span up to 5 scalar operations, every cycle.
As a result, the GPU has the capability to provide a maximum
throughput of 1600 scalar operations per cycle. Table 2 shows
the detailed system parameters for the evaluated CPU and GPU.
The parameters for the main memory system (DDR3
SDRAM-1600 [20]) are shown in Table 2. Unless stated otherwise, we use four memory controllers (one channel per memory controller) for all experiments. In order to prevent the GPU
requests from occupying the vast majority of the request buffer
entries, we reserve half of the request buffer entries for CPU
requests for non-SMS MCs. To model the memory bandwidth
used by the GPU accurately, we perform coalescing of GPU
memory requests before they are sent to the MC as is done incurrent GPUs [17].
Workloads: We evaluate our system with a set of 105 multiprogrammed workloads, each simulated for 500 million cycles.
Each workload consists of sixteen SPEC CPU2006 benchmarks
and one GPU application selected from a mix of video games
and graphics performance benchmarks described in Table 3. For
each CPU benchmark, we use Pin [18] with PinPoints [29] to select the representative phase. Our GPU traces are collected fromGPU benchmarks and recent games through a proprietary GPU
simulator. Note that our GPU memory traces include memory requests coming from fixed function units (FFUs). Table 3

MPKI
0.01
0.01
0.04
0.08
0.11
0.11
0.12
0.22
0.37

Name
gobmk
gromacs
h264refhmmer
bzip2
cactusADM
astar
sphinx3
leslie3d

MPKI
0.51
1.12
1.22
2.82
4.10
4.74
5.19
13.21
14.79

Name
milc
xalancbmk
omnetpp
GemsFDTD
libquantum
soplex
lbm
mcf

MPKI
16.18
18.32
19.20
24.70
26.24
27.96
28.30
74.35

Table 4. L2 Cache Misses Per Kilo-Instruction (MPKI) of 26 SPEC 2006
benchmarks.

Performance Metrics: We measure the performance of themulti-core CPU using the weighted speedup metric [8, 33], asshown in Equation 1. We measure the performance of the GPU
by calculating the frame rate (frames per second), a commonlyused graphics performance metric [16, 32]. We compute the
GPU speedup as the ratio of its frame rate when it is sharing thesystem with the CPU over the GPU’s frame rate when it is run
alone on the same baseline system, as shown in Equation 2.
NumCoressharedGPUFrameRate
IPCishared
GPUSpeedup =
alone
alone
GPUFrameRate
IPCi
i=1
(2)
(1)
Measuring overall system performance in an integrated CPUGPU system is not straightforward. Using the conventional
weighted speedup metric for this purpose weights the GPU asequivalent to a single CPU core. However, having the same
weight for the GPU as a single CPU core does not allow for flexibility in quantifying the system performance of different systems that have different performance requirements. In some systems (e.g., those used by video gaming enthusiasts), GPU performance could be much more important than CPU performanceto the end-user. In contrast, in some other systems (e.g., those

CPUW S =∑9 MPKI of a GPU application is calculated as the total number of memory
accesses divided by the number of scalar GPU operations, where a scalar GPU
operation is the closest unit of work to a CPU instruction.

8 AMD, the AMD Arrow logo, and combinations thereof are trademarks ofAdvanced Micro Devices, Inc.

7

10
8

FR-FCFS
CFR-FCFS
ATLAS
TCM

6

CTCM
SMS0.9SMS0-18.1%-35.5% -26.7%
22.1%
69.9% 35.7%

4
2
0

120
105
90
75
60
45
30
15
0

GPU Frame Rate

CPU Weighted Speedup

12

L
ML
M
HL HML HM
H Avg
L
ML
M
HL HML HM
H
Avg
Figure 5. Performance of CPU and GPU for 7 workload categories (105 workloads). % values are gains of SMS0.9 over FR-FCFS, ATLAS, and TCM.

with interactive applications running together with graphics orin mobile systems), CPU performance could be much more important than GPU performance. Therefore, we need a metricthat is flexible to evaluate the performance of different heterogeneous systems, given different end-user needs. To this end, we
propose an integrated CPU-GPU Weighted Speedup (CGWS)
metric (Eqn. 3) where the GPU’s speedup is weighted by a parameter GPUweight .
CGW S = CPUW S + GPUweight ∗ GPUSpeedup(3)
The GPUweight parameter determines the weight of the GPU
relative to a CPU core. When the GPUweight is set to 1, the GPU
is treated as equivalent to a single CPU core, and CPU performance (weighted speedup) becomes an important factor in determining system performance. On the other hand, when the
GPUweight is set to a large value (e.g., 1000), CPU performance
becomes negligible, and GPU performance becomes the dominant factor. Section 6.2.1 shows the performance of our system
for a wide range of values of the GPUweight parameter.
In addition to system performance, we measure Unfairness(Eqn. 4) using maximum slowdown [5, 14, 15, 34] over all of the
CPU cores and the GPU. We report the harmonic mean insteadof arithmetic mean for Unfairness in our evaluations because
slowdown is the inverse metric of speedup.
(
)
alone
alone
IPCCoreGPUFrameRatei
Un f airness = max max(4),i IPCshared GPU shared
FrameRateCoreiintensity categories described in Section 5, with workload memory intensities increasing from left to right.
Figure 5 shows the performance of the CPU (weighted
speedup), and the individual performance of the GPU (framerate) separately. Three major conclusions are in order. First,
SMS0.9 improves CPU performance by 22.1%/ 35.7% over thetwo best previous scheduling policies, ATLAS and TCM, on average. This is because ATLAS, TCM, and other previously proposed scheduling policies11 are not designed to robustly handle the high degree of disparity in memory access intensities
present between CPU and GPU applications in an integrated
CPU-GPU system, as we explained in Section 4.5. Previous
scheduling policies allocate a large fraction of the system memory bandwidth to the GPU, thereby penalizing the CPU applications. Second, CFR-FCFS provides better CPU performance than FR-FCFS as it prioritizes CPU requests, preventing the GPU’s row-buffer hits from hogging memory bandwidth.
CTCM performs similarly as TCM because the baseline TCM
is already application-aware as it prioritizes low-intensity applications over others. However, SMS0.9 still provides better
CPU performance than both CFR-FCFS and CTCM, on average
across all workloads. Third, SMS0.9 achieves this CPU performance improvement over previous schedulers and their variants
by appropriately restricting the fraction of system bandwidth allocated to the GPU, resulting in 18.1%/ 26.7% reduction in GPU
frame rate as compared to ATLAS and TCM, on average. Although SMS0.9 reduces the frame rate of the GPU, it still maintains a frame rate greater than 30 frames per second (for all
workload categories except the HM category), which is likely
acceptable for a large number of applications and users. In systems and use cases that require a higher GPU frame rate, we
can adjust the value of p, the SJF probability, to ensure that an
adequate frame rate is achieved. In particular, Figure 5 showsthat SMS0 (p = 0) provides a significantly higher GPU frame
rate, at the cost of lower CPU performance. In Section 6.2.1, we
present further analysis on the tradeoff between CPU and GPU
performance by configuring the SJF probability appropriately.

Parameters of Evaluated Algorithms: For SMS, we set thebatching FIFO queue size for each CPU core to 10 entries, andfor the GPU to 20 entries. The DCS FIFO queue size for eachbank is 15 entries. In addition to the age thresholds given in Section 4.2, the thresholds for a low-intensity CPU application (<1 MPKC) and the GPU are 0 and 800 cycles, respectively. We
use a QuantumLength of 1M cycles and HistoryWeight of 0.875
for ATLAS. We use a ClusterThresh of 0.1 and ShuffleCycles of
800 for TCM.
Area and Power Modeling: We use Verilog models synthesized with a commercial 180nm design library. The standardcell synthesis models area, leakage power and timing of FRFCFS and SMS scheduling logic and buffers.10 In Section 6.4,
we report the area and leakage power of SMS normalized to
FR-FCFS.

6.2

Combined CPU-GPU PerformanceFirst, we compare the individual CPU and GPU performanceof SMS with three state-of-the-art memory scheduler configurations: FR-FCFS, ATLAS and TCM, and their variants, CFRFCFS and CTCM, which are similar to FR-FCFS and TCM respectively, but always prioritize the CPU cores’ requests overthe GPU’s requests. We present SMS with two values of p,
the SJF probability: SMS0.9 denotes the configuration wherep = 0.9 (i.e., with 90% probability the application with fewest
total requests is selected to be scheduled), and SMS0 denotes
the configuration where p = 0 (i.e., the batch scheduler always
is round-robin). Results are presented across 105 workloads of 7

6.2.1 Effect of Configurable SJF Probability
In this section, we present and analyze the combined CPU-GPU
performance of the 16-core CPU/1 GPU system and the effectof changing the parameter p (SJF probability).
Figure 6 (a) shows the performance of SMS at different values of p, the SJF probability, when the GPUweight is varied from0.001 to 1000. This weight represents the relative importanceof GPU performance vs. CPU performance in the combined
CPU-GPU Weighted Speedup (CGWS) metric. Two key conclusions are in order. First, SMS0.9 has higher CGWS than FRFCFS, ATLAS and TCM, for low values of GPUweight (< 7.5).
However, as GPUweight increases, SMS0.9 has lower CGWS thanprevious scheduling policies like FR-FCFS, ATLAS and TCM.
This is because previous scheduling policies prioritize the GPU
at varying levels, while penalizing CPU cores, hence providing higher GPU performance, as illustrated in Figure 5 and described qualitatively in Section 4.5. Therefore, they provide

10 Each buffer is modeled using a flip-flop. Neither logic nor buffers are optimized for area and power.

11 We do not show PAR-BS in these figures so as not to clutter the graphs, but
it consistently has lower performance and fairness than that of ATLAS/TCM.

6
6.1

Experimental Evaluation
Individual CPU and GPU Performance

8

0.7
0.6
0.5

0.9

0.4

0.3
0.2
0
0.001

0.1

10

0.7
0.6

ATLAS

20

TCM
SMSMax

0.5
0.4

15
10

0
0.001

5

(b)

0.1

1000

FR-FCFS
ATLAS
TCM
SMSMax

0.3
0.2

(a)

0.1

0.8

25

FR-FCFS

Unfairness

Normalized CGWS

0.8

1

FR-FCFS
ATLAS
TCM
SMS0.9SMS0.05
SMS0.02
SMS0

Normalized CGWS

1

0.9

0.1

GPUweight

10

GPUweight

1000

0
0.001

(c)
0.1

10

1000

GPUweight

Unfairness(Lower is Better)

CGWS (GPUweight = 1)

Figure 6. Combined performance of the CPU-GPU system (a) for different SMS configurations with different SJF probability, (b) for the SMS configurationthat provides the maximum CGWS, and (c) unfairness for the configuration that provides the maximum CGWS.
14
105
FR-FCFS
CTCM
SMS0.9CFR-FCFS
12
90
SMS0
ATLAS
10
75
TCM
8
60
17.2%
46.4% 25.7%
244.6%
645
205.7%
47.6%
4
30
2
15
0
0
L
ML
M
HL HML HM
H Avg
L
ML
M
HL HML HM
H
Avg
Figure 7. System performance and fairness for 7 workload categories (105 workloads). % values are gains of SMS0.9 over FR-FCFS, ATLAS, and TCM.

6.2.2 Performance & Fairness Analysis (GPUweight = 1)
We study the system performance and fairness of SMS when the
GPUweight has a low value of 1. This represents a system or a
dynamic use case where CPU performance matters significantly
to the user, e.g., a typical system running a GPU application
alongside multiple CPU applications.
Figure 7 shows the system performance (measured as
CGWS) and fairness of the previously proposed algorithms,
SMS0.9 , and SMS0 for all workload categories, when the
GPUweight is 1. SMS0.9 provides 46.4%/17.2%/25.7% system performance improvement and 244.6%/47.6%/205.7%
fairness improvement over FR-FCFS/ATLAS/TCM. SMS0
provides 6.8%/33.4%/24.3% system performance degradation and 15.2%/89.7%/36.7% fairness degradation over
FR-FCFS/ATLAS/TCM, respectively. As discussed in Section 4, SMS0.9 improves system performance and fairness fora low GPUweight of 1, as it prioritizes the short batches of the
CPU cores over the long batches of the GPU, while SMS0
degrades system performance, as it selects between CPU andGPU batches in merely a round-robin fashion. Therefore, we
conclude that for a GPUweight of 1, SMS with an appropriately
selected p value of 0.9 provides better system performance andfairness than all previously proposed scheduling policies.
Based on the results for each workload category, we
make the following major observations. First, SMS0.9 consistently outperforms previously proposed algorithms both interms of system performance and fairness across most of
the workload categories. Second, in the “H” category with
only high memory-intensity applications, SMS0.9 underperforms ATLAS and TCM by 16.7% and 12.5%, but it still provides 7.1% higher system performance than FR-FCFS. ATLAS’
attained service based scheduling tends to prioritize all CPU applications equally, as all CPU applications in a “H” category
workload have similar memory intensities. This leads to highperformance and fairness for ATLAS (SMS achieves similar
fairness). TCM, on the other hand, improves performance by
unfairly prioritizing certain applications over others, which is reflected by its higher unfairness in the “H” category, as comparedto other workload categories. Specifically, TCM misclassifies
some high memory-intensity applications into the low memoryintensity cluster, which starves the requests of applications in
the high memory-intensity cluster. On the other hand, SMS preserves fairness in all workload categories by using its probabilistic SJF batch scheduling policy described in Section 4. As
a result, SMS provides 205.7% better fairness relative to TCM.

higher CGWS than SMS, when the contribution of the GPU
to the CGWS metric is weighted significantly higher. Second, although SMS0.9 provides a lower value of CGWS compared to previous algorithms when GPUweight is higher than 7.5,
SMS0 leads to higher CGWS than all previous algorithms. A
small p value enables SMS to prioritize GPU requests much
more often than CPU requests (due to round-robin scheduling ofbatches and long batches for the GPU), thereby largely improving GPU performance over other algorithms except FR-FCFS(which achieves a similar effect by prioritizing the row hit requests, which are much more common in the GPU than in theCPU).
Note that p is an adjustable knob provided by our SMS
design, which can be statically or dynamically configured to
trade off between CPU and GPU performance, depending on
the needs of the system. If a designer or system software caremore about GPU performance, they can set p to be very low(causing the SMS algorithm to implicitly favor the GPU over
the CPU, as we have seen in Figure 6(a)). On the other hand,
if they care more about CPU performance, they can set p to bevery high (causing the SMS algorithm to favor the CPU cores
over the GPU). Therefore, one can determine and select at design time the best SJF probability, p for a given GPUweight . Thismeans that for each GPUweight , we can find an SJF probability
that maximizes CGWS.12
Figures 6 (b) and (c) show the performance and fairness of
SMSMax , which is defined as SMS with a p value that maximizes CGWS for each given GPUweight . Two key observations
are in order. First, as we increase the GPUweight , a p value thatmaximizes CGWS favors the GPU over CPU cores, increasing
the slowdown of CPU applications, and thus leading to higher
unfairness. However, for smaller values of GPUweight (i.e., when
CPU performance is important), SMS provides the highest fairness across all schedulers. Second, SMSMax provides the best
CPU-GPU Weighted Speedup (CGWS) compared to FR-FCFS,ATLAS and TCM across all values of GPUweight considered.
Therefore, we conclude that SMS can be configured to consistently provide better system performance than state-of-the-art
memory schedulers regardless of how important the CPU or the
GPU is to system performance.
12 In fact, new instructions can be added to the ISA to change p dynamicallyto achieve the best performance in cases where GPUweight (importance of theGPU) varies dynamically.

9

FR-FCFS/ATLAS/TCM (averaged over 75 workloads13 ) withthe same number of request buffers, as the number of CPU
cores is varied. We make the following observations. First,
SMS always provides better CPU performance and fairness
than FR-FCFS/ATLAS/TCM. Second, the fairness gains
increase as the number of CPU cores increases to 16, as thissignificantly reduces the memory bandwidth per core given thesame memory system configuration. With lower bandwidth
per core, the interference between applications becomes more
severe. SMS mitigates the interference by effectively throttlingback the GPU. Third, similar to the observation made in
Section 6.1, SMS reduces GPU frame rate compared to othermemory schedulers. However, SMS still maintains a frame rate
above 30 frames per second for all systems. In general, SMS
provides consistent improvement in CPU performance andfairness relative to other memory schedulers while maintaining
likely acceptable GPU performance (30 frames per second)across systems with different numbers of CPU cores. SMS’
benefits are likely to become more significant as CPU core
counts in future technology nodes increase, as this would leadto higher interference between the CPU cores and the GPU,
which previous scheduling algorithms like ATLAS and TCM
do not handle robustly.

L

TCM
CTCM
SMS0.9MLM

HL HML HM

SMS0
32.7%
1.6%
16.4%

H

17.7%

4
2
0

22.1%

25.2%
21.2%
2

4

8

16

120
100
80
60
40
20
0

Number of Cores-3.8%-5.4%-7.3%-35.8%

20

Unfairness(Lower is Better)

ATLAS
TCM
SMS

GPU Frame Rate
(Higher is Better)

6

47.4%

15
22.8%

10

2

4

8

5
0

16

Number of Cores

32.3%
25.6%

2 4 8 16
Number of Cores

Figure 9. Performance and fairness vs. number of CPU cores. % values
are gains of SMS0.9 over the best previous algorithms (ATLAS for weighted
speedup and fairness, and FR-FCFS for GPU frame rate).

Figure 10 shows the CPU performance (weighted speedup),
GPU performance (frame rate), and fairness of SMS comparedagainst FR-FCFS, ATLAS, and TCM as the number of memory channels is varied. Three key observations are in order.
First, SMS provides consistent improvement in CPU performance and fairness across a wide range of system configurations with different numbers of channels. Second, as thenumber of memory channels increases to eight, the available
memory bandwidth increases, and hence SMS is able to provide GPU frame rates that are within 13.4%/7.6%/10.5% of
FR-FCFS/ATLAS/TCM, while improving CPU system performance by 54.7%/22.2%/38.5%, respectively. Third, the GPU
frame rate of SMS drops below 30 frames per second in a
two-channel system. However, these results are without an appropriate reconfiguration of p. As described in Section 6.2.1,
SMS can provide more adequate GPU frame rates by adjusting the SJF probability, p, while trading off CPU performance.
We conclude that SMS provides high CPU performance andhigh fairness compared to previously proposed scheduling algorithms without degrading the GPU frame rate below a usuallyacceptable level, across a wide range of system configurations
with different core and memory channel counts.

Avg

Figure 8. System performance for 7 workload categories (105 workloads).
% values are gains of SMS0 over FR-FCFS, ATLAS, and TCM.

CPU Weighted Speedup(Higher is Better)

Observing the results for each workload category, we see that
SMS0 performs better as the CPU workload intensity increases.
In the high-intensity workloads that have high interference between the CPU and GPU, SMS0 allows the GPU to form batcheswith high row-buffer locality without being interfered by requests from high-intensity CPU applications. On the other hand,
FR-FCFS performs better at lower CPU workload intensities.
When the CPU applications in a workload have low memory intensities, they seldom interfere with the GPU application. Thus,
merely prioritizing row-buffer hits favors the GPU application,
which has high row-buffer locality, thereby providing high GPU
performance (which is good in this scenario as GPUweight is1000). However, the wait time for batch formation in SMS0
can sometimes throttle back the GPU application unnecessarily, leading to a slight performance degradation for the GPU.
On the other hand, when the CPU applications in a workload
have high memory intensities, these applications sometimes interfere with the GPU application in the row buffers when a naive
application-unaware scheduling policy like FR-FCFS is used. In
contrast, SMS explicitly prioritizes the GPU application by using a very low value of the parameter p, which improves GPU’s
row buffer locality, leading to a larger improvement in GPU performance and, thus, CGWS than FR-FCFS.

10
8
6
4
2
0

FR-FCFS
ATLAS
TCM
SMS
38.5%
22.2%
54.7%

2 4 8
Number of Channels

100
80
60
40
20
0

-13.4%-35.8%-58.7%

2
4 8
Number of Channels

60
50
40
30
20
10
0

Unfairness(Lower is Better)

FR-FCFS
CFR-FCFS
ATLAS

8 FR-FCFSGPU Frame Rate
(Higher is Better)

1400
1200
1000
800
600
400
200
0

CPU Weighted Speedup(Higher is Better)

CGWS (GPUweight = 1000)

6.2.3 Performance & Fairness Analysis (GPUweight =1000)
We also study the system performance and fairness of SMS
when the GPUweight is 1000. This represents a system ora use case where CPU performance matters less to the user
than GPU performance does, e.g., a system intended forgaming or watching high definition video. Figure 8 shows
the system performance (measured as CGWS) of the previously proposed algorithms, SMS0 , and SMS0.9 for all workload categories when the GPUweight is 1000. SMS0 provides 1.6%/32.7%/16.4% system performance improvement,
while SMS0.9 provides 44.3%/13.3%/27.7% system performance degradation, over FR-FCFS/ATLAS/TCM. Fairness ofthese algorithms was already shown in Figure 7 (note that theunfairness measure does not depend on GPUweight ). However,when GPUweight is high, fairness is not an important concern
because the goal is to optimize for GPU performance. Two
key observations are in order from Figure 8. First, when the
GPUweight is very high, FR-FCFS, which predominantly prioritizes the GPU owing to the GPU’s very high row-buffer locality
and very high memory intensity, provides the best system performance among previous techniques. Second, SMS0 provides
similar system performance as FR-FCFS, on average, across all
workload categories, as it predominantly prioritizes the GPU
requests when a low value of p is used. Therefore, we conclude that for a GPUweight of 1000, SMS with an appropriately
selected p value of 0 provides better system performance thanpreviously proposed scheduling policies.

229.8%
47.8%
87.2%

2

4

8

Number of Channels

Scalability with CPU Cores and Memory
ChannelsFigure 10. Performance and fairness vs. number of channels. % values
are gains of SMS0.9 over the best previous algorithms (ATLAS for weighted
speedup and fairness, and FR-FCFS for GPU frame rate).

Figure 9 compares the CPU performance (weighted
speedup), GPU performance (frame rate), and fairness of
SMS (we use SMS0.9 for our sensitivity studies) against

13 We use 75 randomly selected workloads per core count. We could not use
the same workloads/categorizations as earlier because those were for 16-coresystems, whereas we are now varying the number of CPU cores.

6.3

10

Power and Areasame system parameters as described in Section 5, except thatthe system does not have a GPU. We present results for only
workload categories with at least some high memory-intensity
applications, as the performance and fairness of SMS in theother workload categories are quite similar to that of ATLAS
and TCM. First, we observe that SMS degrades performance by
only 8.8% and 4% respectively compared to ATLAS and TCM,
while it improves fairness by 1.2% and 25.7% respectively, on
average across all workloads, compared to ATLAS and TCM.
Compared to ATLAS, SMS improves fairness in “HL”, “HML”
and “HM” categories but reduces the performance in those categories slightly. However, ATLAS provides the best fairness inthe “H” workload category, as ATLAS’ attained service basedprioritization mechanism achieves the same effect as shuffling
request priorities between applications, when they have similar memory intensities. Compared to TCM, SMS’ performancedegradation mainly comes from the “H” workload category; as
discussed in our main evaluations in Section 6, TCM places
some high memory-intensity applications into the low memoryintensity cluster, which results in the strict prioritization of suchapplications over those (slightly more intensive applications)placed in the high memory-intensity cluster. Therefore, TCM
gains performance at the cost of unfairness to the memoryintensive applications that fall into the latter cluster. On the other
hand, SMS reduces unfairness with its probabilistic SJF policy,
while still maintaining good system performance. We conclude
that SMS can be employed in CPU-only systems as an effective, low-complexity, and scalable memory scheduling policy toprovide high fairness and reasonably high performance.

We present the power and area of FR-FCFS and SMS in Table 5 for a system with 300 request buffers. Two major conclusions are in order. First, SMS consumes 66.7% less leakage power than FR-FCFS, the simplest of all evaluated previous memory schedulers. Second, SMS requires 46.3% lessarea than FR-FCFS. The majority of the power and area savings of SMS over FR-FCFS comes from the decentralized request buffer queues and simpler scheduling logic in SMS, as
compared to centralized request buffer queues, CAMs, andcomplex scheduling logic in FR-FCFS. Because ATLAS andTCM require more complex ranking and scheduling logic than
FR-FCFS does, SMS provides likely more significant power andarea reductions over ATLAS and TCM.
Data Type
Leakage (Normalized)
Area (Normalized)

FR-FCFS
1
1

SMS
0.667
0.463

Table 5. Power and area comparison.

6.5

Analysis of SMS Algorithm Parameters

0%
50%
100%
200%
300%

CP

U
F
U- nfai ram
Pe rne eRrf.
ss ate

1.6
1.4
1.2
1
0.8
0.6
0.4

8
6

40

FR-FCFS
ATLAS
TCM
SMS

30
20

4
10

2
0
HL HML HM

7

H

Avg

HL HML HM

H

Avg

Related Work

Memory Scheduling: We have already compared SMS tostate-of-the-art memory schedulers designed for CPU-only systems (FR-FCFS [31, 37], ATLAS [14], PAR-BS [25], andTCM [15]). SMS outperforms these schedulers in terms of both
system performance and fairness as explained in Sections 4.5
and 6. Other memory schedulers (e.g., [11, 19, 21, 22, 24, 26,
30, 35, 36]) that are either aware or unaware of applications havebeen proposed for CPU-only systems. However, none of theseworks has been shown to provide better performance and fairness than TCM, which SMS outperforms across a wide range of
workloads. Furthermore, previous works [2, 3, 35] have also
explored memory scheduling for GPUs/GPGPUs. However,these works are not targeted toward integrated CPU-GPU systems and are application-unaware. On the other hand, SMS isa new application-aware memory scheduler that mitigates interference between CPU and GPU applications in heterogeneous
CPU-GPU systems.
Parallel Application Memory Scheduling: Ebrahimi et al. [7]propose a memory scheduler to explicitly manage inter-thread
memory interference in parallel applications. However, the proposed memory scheduler is not designed to mitigate interference between heterogeneous applications in CPU-GPU systems.
Their proposed principles can be combined with our work toprioritize limiter threads in CPU-GPU systems. We aim to investigate the interaction between parallel CPU applications andGPU applications as part of future work.
QoS for CPU-GPU heterogeneous systems: A concurrent
work by Jeong et al. proposes a QoS-aware memory controllerthat has the explicit goal of providing QoS for the GPU by adjusting the priority of the CPU and the GPU based on whether

5
10
15
20

F
U
U- nfai ram
Pe rne eRrf.
ss ateCP

Figure 11. Sensitivity of SMS to different design parameters.

6.6

10

Figure 12. Results on a 16-core CPU system for 4 workload categories.

DCS FIFO Size
Normalized Value

Normalized Value

Threshold Age
1.6
1.4
1.2
1
0.8
0.6
0.4

System Performance(Higher is Better)

Figure 11 shows CPU performance, fairness and GPU frame
rate (all normalized to SMS0.9 ), when we vary threshold age(left) for applications in all intensity categories from 0% (nobatching) to 300% of the default values specified in Section 5
and DCS FIFO queue size (right) from 5 to 20 entries. Threeobservations are in order. First, as threshold age increases, theGPU frame rate increases. However, CPU performance degrades, when threshold age is increased beyond a point. Thisis because as threshold age increases, SMS takes longer to forma batch. While longer batches help improve the GPU’s rowbuffer hit rate and hence its frame rate, they increase the wait
time of latency-sensitive CPU applications, degrading CPU performance. Second, as threshold age decreases, batches become
smaller, degrading row-buffer locality. This reduces both GPU
performance and CPU performance; however, GPU performance degrades more than CPU performance because SMS0.9
prioritizes CPU requests over GPU requests, leading to additional interference from the CPU cores to the GPU. Third, CPU
performance and fairness increase while GPU performance decreases as we lower DCS FIFO queue size. When DCS FIFO
queue size becomes smaller, the DCS FIFOs can hold a smaller
number of batches. Hence, once a few batches are scheduled to a
DCS FIFO, other batches would need to wait until the batches inthe DCS FIFO are drained. This particularly impacts the GPU,
as SMS0.9 prioritizes CPU requests over GPU requests. This
reduction in GPU performance leads to lower interference fromthe GPU, and hence increases CPU performance. We also foundthat increasing the DCS FIFO size beyond 20 entries provides
only very small performance benefit.

Unfairness(Lower is Better)

6.4

Analysis of CPU-only Systems

In Sections 6.1-6.3, we showed that SMS effectively mitigatesinter-application interference in a CPU-GPU integrated system. In this section, we evaluate the performance of SMS ina CPU-only scenario.14 Figure 12 shows the system performance and fairness of SMS on a 16-core system with exactly the
14 In view of simulation bandwidth and time constraints, we reduce the simulation time to 300M cycles for these studies. We did not tune the configuration
parameters of ATLAS, TCM and SMS for CPU-only cases.

11

from NSF (CAREER Award CCF-0953246 and CCF-1147397),
GSRC, and Intel ARO Memory Hierarchy Program. Rachata
Ausavarungnirun is supported by the Royal Thai Government
Scholarship, and was an intern at AMD while he did part of thiswork.

the GPU meets its target frame rate [12]. Our goal, in contrast, isto provide high system performance and fairness, which makes
our approach complementary. Principles from [12] can be applied to SMS to dynamically adjust the priority of the GPU (pvalue), which can provide QoS to the GPU and further improvesystem performance.
Sub-row Interleaving: In order to preserve row-buffer locality and prevent applications from monopolizing the row bufferwhen an open-page policy is used, Kaseridis et al. [13] propose
a scheme that interleaves data at a sub-row granularity acrosschannels and banks. Our batch formation process provides similar qualitative benefits to the sub-row interleaving approach oflimiting row-buffer hit streaks. However, their proposal stillneeds a large centralized scheduler that requires complex logic
to support the memory access demands of the vastly different
CPU and GPU applications.
Memory Channel Partitioning: Instead of mitigating memory interference between applications by intelligently prioritizing requests at the memory controller, Muralidhara et al. [23]propose memory channel partitioning (MCP) to map the dataof badly interfering applications to different channels. Our approach is complementary to MCP, as it has been shown that
MCP can be integrated with different memory schedulers to further improve system throughput and fairness [23].
Source Throttling: Ebrahimi et al. [6] mitigate interapplication interference in a shared-memory system by throttling the request injection rates of interference-causing applications at the source. This approach is complementary to
SMS which reduces inter-application interference via memory
scheduling. Note that, the staged nature of SMS allows throttling of sources at the source FIFOs.

8

References[1] Advanced Micro Devices.
AMD Radeon HD 5870 Graphics.
http://www.amd.com/us/products/desktop/graphics/ati-radeon-hd5000/hd-5870.
[2] N. B Lakshminarayana et al. DRAM scheduling policy for GPGPU architectures based on a potential function. IEEE CAL, 2011.
[3] N. B. Lakshminarayana and H. Kim. Effect of instruction fetch and memory scheduling on GPU performance. GPGPU Workshop, 2010.
[4] B. Burgess et al. Bobcat: AMD’s low-power x86 processor. IEEE Micro,
2011.
[5] R. Das et al. Application-aware prioritization mechanisms for on-chip
networks. In MICRO-42, 2009.
[6] E. Ebrahimi et al. Fairness via source throttling: a configurable andhigh-performance fairness substrate for multi-core memory systems. In
ASPLOS-15, 2010.
[7] E. Ebrahimi et al. Parallel application memory scheduling. In MICRO-44,
2011.
[8] S. Eyerman and L. Eeckhout. System-level performance metrics for multiprogram workloads. In MICRO-41, 2008.
[9] A. Fog.
The Microarchitecture of Intel, AMD and VIA CPUs.
http://www.agner.org/optimize/#manuals.
[10] Intel. Sandy Bridge Intel processor graphics performance developer’s
guide. http://software.intel.com/file/34436.
[11] E. Ipek et al. Self-optimizing memory controllers: A reinforcement learning approach. In ISCA, 2008.
[12] M. K. Jeong et al. A QoS-aware memory controller for dynamically balancing GPU and CPU bandwidth use in an MPSoC. In DAC-49, 2012.
[13] D. Kaseridis et al. Minimalist open-page: A DRAM page-mode scheduling policy for the many-core era. In MICRO-44, 2011.
[14] Y. Kim et al. ATLAS: a scalable and high-performance scheduling algorithm for multiple memory controllers. In HPCA-16, 2010.
[15] Y. Kim et al. Thread cluster memory scheduling: Exploiting differencesin memory access behavior. In MICRO-43, 2010.
[16] V. W. Lee et al. Debunking the 100x GPU vs. CPU myth: an evaluation ofthroughput computing on CPU and GPU. In ISCA-37, 2010.
[17] E. Lindholm et al. NVidia Tesla: A unified graphics and computing architecture. IEEE Micro, 2008.
[18] C. Luk et al. Pin: Building customized program analysis tools with dynamic instrumentation. In PLDI, 2005.
[19] S. A. McKee et al. Dynamic access ordering for streamed computations.
IEEE Transactions on Computers, 2000.
[20] Micron Technology Inc. 1Gb: x4, x8, x16 DDR3 SDRAM Features. http://download.micron.com/pdf/datasheets/dram/ddr3/
1Gb_DDR3_SDRAM.pdf.
[21] T. Moscibroda and O. Mutlu. Memory performance attacks: Denial ofmemory service in multi-core systems. In USENIX Security, 2007.
[22] T. Moscibroda and O. Mutlu. Multi-level DRAM controller to manage
access to DRAM. U.S. Patent Number 8001338, Aug 2011.
[23] S. Muralidhara et al. Reducing memory interference in multi-core systems
via application-aware memory channel partitioning. In MICRO-44, 2011.
[24] O. Mutlu and T. Moscibroda. Stall-time fair memory access schedulingfor chip multiprocessors. In MICRO-40, 2007.
[25] O. Mutlu and T. Moscibroda. Parallelism-aware batch scheduling: Enhancing both performance and fairness of shared DRAM systems. In
ISCA-35, 2008.
[26] K. J. Nesbit et al. Fair queuing memory systems. In MICRO, 2006.
[27] NVIDIA. Tegra 2 Tech. Ref. Manual. http://www.nvidia.com/object/tegra2.html.
[28] S. Palacharla et al. Complexity-effective superscalar processors. In ISCA24, 1997.
[29] H. Patil et al. Pinpointing representative portions of large Intel Itanium
programs with dynamic instrumentation. In MICRO-37, 2004.
[30] N. Rafique et al. Effective management of DRAM bandwidth in multicore
processors. In PACT, 2007.
[31] S. Rixner et al. Memory access scheduling. In ISCA-27, 2000.
[32] C. J. Rossbach et al. PTask: operating system abstractions to manage
GPUs as compute devices. In SOSP-23, 2011.
[33] A. Snavely and D. M. Tullsen. Symbiotic jobscheduling for a simultaneous
multithreaded processor. In ASPLOS-9, 2000.
[34] H. Vandierendonck and A. Seznec. Fairness metrics for multi-threaded
processors. IEEE CAL, 2011.
[35] G. L. Yuan et al. Complexity effective memory access scheduling for
many-core accelerator architectures. In MICRO-42, 2009.
[36] Z. Zhu and Z. Zhang. A performance comparison of DRAM memory
system optimizations for SMT processors. In HPCA-11, 2005.
[37] W. K. Zuravleff and T. Robinson. Controller for a synchronous DRAM
that maximizes throughput by allowing memory requests and commands
to be issued out of order. U.S. Patent Number 5,630,096, May 1997.

Conclusion

While many advances in memory scheduling policies have been
made to deal with multi-core processors, the integration ofGPUs on the same chip as CPUs has created new system design challenges. We demonstrate how the inclusion of GPU
memory traffic can cause severe difficulties for existing memory
controller designs in terms of performance, fairness and design
complexity. To solve this problem, we propose a fundamentally
new approach to memory scheduler design, the Staged Memory
Scheduler (SMS). The key idea of SMS is to decouple the primary functions of an application-aware memory controller into
three stages: (1) per-source FIFO queues that group requests tothe same row into batches for each source/application, to improve row-buffer locality, (2) the batch scheduler that prioritizes
between the batches of different sources, to maximize performance and fairness and (3) the DRAM command scheduler that
simply issues requests to DRAM in the order it receives them(as the previous stages have already made application-awareand row-buffer locality aware batch scheduling decisions). This
staged design provides two benefits. First, it is simpler andmore scalable than previous application-aware memory schedulers with large monolithic request buffers. Second, it provides
a new memory scheduling algorithm by composing these three
separate stages. Our evaluations show that SMS delivers better
performance and fairness compared to state-of-the-art memory
schedulers, while providing a design that is significantly simpler to implement. We conclude that the new staged approach tomemory scheduling can provide a scalable substrate for memory
controller design for future heterogeneous systems.

Acknowledgments
We thank Stephen Somogyi and Fritz Kruger at AMD for theirassistance with the modeling of the GPU applications. We also
thank Antonio Gonzalez, anonymous reviewers and membersof the SAFARI group at CMU for their feedback. We acknowledge the generous support of AMD, Intel, Oracle, andSamsung. This research was also partially supported by grants
12