DRAM Modeling
August 20, 2018
Can queuing models be used to model main memory (memory
controller and DRAM)? Why does DRAM latency increase with utilized
bandwidth? What is the correct way to model main memory? To answer
these questions in this post, we will use an example from everyday
life.
Consider a cashier at a store. Our aim, as store manager, is to
process as many customers as possible i.e. keep the cashier as busy
as possible. Assume that the cashier has a service rate (customers per
unit time), $\mu$, and that customers arrive with an average arrival rate,
$\lambda$. Assume that the customer arrivals are random i.e. we have
a Poisson process. In reality, customer arrivals might be bursty i.e.
Pareto distributed. Also assume that the maximum number of customers in
the queue, $L$, is finite i.e. the queue cannot grow indefinitely. This
assumption reflects the fact that on-chip buffers have finite capacity.
Given a service rate, $\mu$, and maximum queue length, $L$, we
want to understand the relationship between arrival rate, $\lambda$,
cashier utilization (bandwidth) and average customer wait time
(latency). Now consider three cases.
Case 1
In this case, assume that the cashier processes the customers in FIFO
(First In First Out) order. Also assume that the service time is the
same for all customers.
The plot on the right shows the cashier utilization (bandwidth) as a
function of $\frac{\lambda}{\mu}$. As the arrival rate increases,
the cashier utilization increases. As soon as the fraction
$\frac{\lambda}{\mu}$ exceeds 1 i.e. the arrival rate exceeds
the service rate i.e. there is atleast 1 customer in the queue
at all times, the cashier is always busy and his utilization is 100%.
As is obvious, when the arrival rate exceeds the service rate, the queue
(on chip buffer) will get full.
The plot on the right shows the average customer latency as a function of
cashier utilization (bandwidth). The average latency seen by the customer
is fairly small until the utilization approaches 100%. We observed
in the plot above, that utilization approaches 100% when the arrival
rate exceeds the service rate and the queue will get full. At that time,
the latency seen by every customer will be $L \times s$.
The plot on the right shows the average customer latency as a function
of $\frac{\lambda}{\mu}$. As above, the average latency is fairly small
until the fraction approaches 1. As the fraction exceeds 1, the queue
gets full and the average latency approaches $L \times s$. We estimate
latency from the time the customer enters the queue and so it will never
exceed $L \times s$.
Case 2
In this case, assume there are three kinds of customers viz. customers
paying with cash, card and cheque. As before, assume that the cashier
processes the customers in FIFO order and that the service time is the
same for all customers. However, there is an overhead in switching the
payment processing system from cash to card, card to cheque and so on.
The plot on the right shows the cashier utilization (bandwidth) as a
function of $\frac{\lambda}{\mu}$. As the arrival rate increases, the
cashier utilization increases. In the best case if there are, say, only
cash paying customers, there will be no switching overhead and the cashier
utilization will reach 100%. In the worst case, there can be switching
overhead between every customer and the cashier utilization will fall
to $\frac{s}{s + o}$. On average, the utilization will be between these
two values. If $o=0$ or $t=1$, the cashier utilization will reach 100%.
The service time as seen by a customer is either $s$ or $s + o$ and on
average somewhere in between. Therefore, the effective service rate is
less than $\mu$. As a result, the cashier utilization saturates when
$\frac{\lambda}{\mu_{eff}} \rightarrow 1$ i.e.
before $\frac{\lambda}{\mu} \rightarrow 1$.
The plot on the right shows the average customer latency as a function of
cashier utilization (bandwidth). The average latency seen by the customer
is fairly small until we reach the saturation bandwidth at which point
the queue gets full and the latency seen by every customer
$\in [L \times s, L \times (s+o)]$.
The plot on the right shows the average customer latency as a function of
$\frac{\lambda}{\mu}$. The average latency is small until the fraction
$\frac{\lambda}{\mu_{eff}}$ approaches 1. As the fraction exceeds 1,
the queue gets full and the average latency $\in [L \times s, L \times
(s+o)]$.
Case 3
In case 2, the cashier processed the customers in a FIFO order and
there was no way to reduce switching overhead. However, if the store
manager has the ability to choose any customer from the queue, he
can reduce the switching overhead and increase the cashier's utilization. The
manager can, say, first select all cash paying customers, switch the
payment system once, select all card paying customers, switch the
payment system once, select all cheque paying customers and so on.
As in case 2, assume there are three kinds of customers viz. customers
paying with cash, card and cheque, the service time is the same for all
customers and there is an overhead in switching the payment processing
system from cash to card, card to cheque and so on. However, the manager
can choose any customer from the queue to reduce switching overhead and
maximize the cashier's utilization.
The plot on the right shows the cashier bandwidth (utilization) as a
function of $\frac{\lambda}{\mu}$. As the arrival rate increases, the
cashier utilization increases. As the fraction exceeds 1 i.e.
the arrival rate exceeds the service rate, the queue gets longer and
the manager has more opportunity to intelligently choose customers to
minimize switching overhead, and increase the cashier's utilization. In
such systems, long queues are, therefore, a requirement for achieving
high utilization.
The plot on the right shows the average customer latency as a function
of cashier utilization (bandwidth). The average latency as seen by the
customer is fairly small until the utilization approaches 100%. We saw
in the plot above that utilization approaches 100% only when the queue
has a lot of customers and the switching overhead is minimum. At that
time, the average latency approaches $L\times s$. In such a system,
some customers will see very short latencies and some will see very
high latencies. This is because the manager can choose customers from
anywhere in the queue.
The plot on the right shows the average customer latency as a function of
$\frac{\lambda}{\mu}$. As above, the latency is fairly small until the
fraction approaches 1. As the fraction exceeds 1, the queue gets full,
switching overhead reduces and the average latency approaches $L\times s$.
Putting it all together
The plot below shows the average customer latency as a function of
cashier utilization (bandwidth) for the three cases,
case 1 in ,
case 2 in , and
case 3 in .
In case 1, there is no switching overhead and hence it can achieve 100%
utilization. In case 2, there is switching overhead and hence it cannot
achieve 100% utilization. In case 3, as in case 2, there is switching
overhead. However, its impact can be minimized, by selecting customers
intelligently, and hence its utilization is better than case 2.
At a given utilization, the average latency is smallest in case 1
and largest in case 2.
Needless to say, the three cases are very distinct and they should be
modeled accordingly. It would be incorrect to approximate case 3 with
a model of case 1.
Let us now translate the cashier analogy to a DRAM subsystem.
- Cashier = DRAM bank
- Store (queue) manager = Memory controller
- Service Time = Read/write time (under row hit)
- Switching overhead = Row miss (precharge and activate delay)
- Queue = Memory controller queue
- Customer types = Number of rows
A DRAM subsystem is like case 3, albeit an order of magnitude more
complicated. There are many banks, many queues, many sources of overheads
(e.g. refresh, bus read/write turns, activate windows, row cycle time
etc.) and many constraints (e.g. request priorities, maximum age etc.).
To summarize, a DRAM subsystem cannot be modeled or approximated with
simple queuing models. Bruce Jacob's book [1] on the subject is
aptly named ''The Memory System: You Can't Avoid It, You Can't Ignore It,
You Can't Fake It''.
References
- The Memory System: You Can't Avoid It, You Can't Ignore It, You Can't Fake It