\section{\sp/ steps to service a memory access}
\label{sec:steps}

In order to check if a desired cache-line is in the L3 cache, we need
to do the following steps.  We are assuming that the L3 cache is
implemented using a direct-mapped scheme.  We assume that the ACD has
already captured the transaction.

\begin{enumerate}
\item ACD raises the line to the NIU.  This should happen almost
instantanously.
\item \sp/ reads NIU (15 cycles) and jumps to the handler (3 cycles).
\item \sp/ reads ACD (30 cycles) to get address (including operation).
\item \sp/ extracts offset into direct mapped cache by performing one
shift and one {\sc and} operation (2 cycles.)
\item \sp/ adds base of cache to offset (1 cycle) and reads the stored
tag and presence bits (3, 15 or 30 cycles depending on hit in L1 or L2.)
\sp/ computes tag (simply a mask) and computes the address of the
cache-line itself during the latency to read the stored tag.
\item \sp/ compares tag to stored tag (1 cycle)
\item if tags compare, \sp/ reads cache-line (3, 15 or 30 cycles
depending on hit in L1 or L2.)  This may be pipelined by speculatively
reading when the tag is read.  Reading the other words in the cache
take another 7 cycles.
\item write cache-line to the ACD.  Assume write-through (32 cycles +
15 cycle latency for 8 words).
\item write bus tag to ACD.  Assume uncached write (15 cycle latency.)
\end{enumerate}

Assuming that everything hits in the L2 cache and there is no
pipelining of reading the L3 cache, the total time is 15 + 3 + 30 + 2
+ 1 + 15 + 1 + 15 + 7 + 32 + 15 + 15 = 157 cycles.  This time is
approximately 5 times longer than a normal local access.

Let us assume that the desired cache-line is not available in the L3
cache.  If the home is the current site, then the \sp/ needs to do the
following actions after the tag for the L3 is compared.

\begin{enumerate}
\item check to see if home is this site, mask, compare and branch (2
cycles).  
\item compute directory address by adding offset to another base (1
cycle) and read directory (3, 15 or 30 cycles depending on L1 or L2
cache hits.)
\item discover that cache-line is at home, read data (30 cycles + 7
cycles for other reads.)
\item write cache-line to the ACD.  Assume write-through (32 cycles +
15 cycle latency for 8 words).
\item write bus tag to ACD.  Assume uncached write (15 cycle latency.)
\end{enumerate}

Thus, a miss in the L3 that results in reading the cache-line from
local memory takes 15 + 3 + 30 + 2 + 1 + 15 + 1 + 2 + 1 + 30 + 30 + 7
+ 32 + 15 + 15 = 199 cycles.

If the cache-line is a local cache-line, but it is dirty in a remote
location, the \sp/ needs to perform an invalidation.  The steps to do
so are listed below.  The steps follow checking the directory.

\begin{enumerate}
\item \sp/$_{home}$ finds that cache-line is not clean at home and sends and
invalidation message (35 cycles)
\item message propogates through NIU (12 cycles)
\item request goes through Arctic network (18 cycles per stage, assume
5 stages 90 cycles)
\item \sp/$_{remote}$ receives message (20 cycles)
\item \sp/$_{remote}$ writes flush to cC (20 cycles)
\item \sp/$_{remote}$ cC flushes (30 cycles)
\item \sp/$_{remote}$ reads that flush has completed (30 cycles to do
first read, 30 cycles to read cache-line first word, 7 cycles to
finish reading)
\item \sp/$_{remote}$ sends back cache-line (60 cycles) to home
\item request goes through Arctic network (18 cycles per stage, assume
5 stages 90 cycles)
\item message enters NIU (54 cycles + 12 cycles)
\item \sp/$_{home}$ receives cache-line (60 cycles)
\item write cache-line to the ACD.  Assume write-through (32 cycles +
15 cycle latency for 8 words).
\item write bus tag to ACD.  Assume uncached write (15 cycle latency.)
\end{enumerate}

The total time to read a cache-line whose home is local but is dirty
on another site is 15 + 3 + 30 + 2 + 1 + 15 + 1 + 2 + 1 + 30 + 35 + 12
+ 90 + 20 + 20 + 30 + 30 + 7 + 60 + 90 + 54 + 12 + 60 + 32 + 15 + 15 =
692 cycles.

If the home is on another site, the \sp/ then has to send a message to
the home location.  Assume that no invalidations need to be performed,
that the requested cache-line is available from the home location.
Assume that sending a request takes 35 cycles, sending a full
cache-line and address takes 60 cycles, receiving a simple request
takes 20 cycles and receiving a full cache-line and address takes 55
cycles.

These steps take place after the tag comparision completes.

\begin{enumerate}
\item \sp/ sends request (35 cycles)
\item message propogates through NIU (12 cycles)
\item request goes through Arctic network (18 cycles per stage, assume
7 stages, 126 cycles)
\item \sp/ receives message (20 cycles)
\item \sp/ computes offset for directory state by performing a shift
and an {\sc and} operation.  (2 cycles)
\item \sp/ adds base to offset (1 cycle) and reads directory word (3,
15 or 30 cycles.)
\item \sp/ checks to see that it cache-line is home (2 cycles)
\item \sp/ reads cache-line (3, 15 or 30 cycles + 7 cycles.)
\item \sp/ sends cache-line + address back (60 cycles)
\item message travels through Arctic (18 cycles per stage, assume 7
stages, 126 cycles.)
\item message enters NIU (54 cycles + 12 cycles)
\item \sp/ reads message from NIU (60 cycles)
\item write cache-line to the ACD.  Assume write-through (32 cycles +
15 cycle latency for 8 words).
\item write bus tag to ACD.  Assume uncached write (15 cycle latency.)
\end{enumerate}

Again, some pipeline may be possible here.  The total time is 15 + 3 +
30 + 2 + 1 + 15 + 1 from the first sequence subtotalling to 67 cycles.
Then we add 35 + 12 + 126 + 20 + 2 + 1 + 30 + 2 + 30 + 60 + 126 + 54 +
12 + 60 + 32 + 15 + 15 = 699 cycles.  This is approximately a factor
of 5 more than a hit in the L3 cache.

If a local invalidation needs to be performed before the value can be
returned, the following steps occur after the check to see if the
cache-line is home.

\begin{enumerate}
\item \sp/$_{home}$ writes flush to cC (20 cycles)
\item \sp/$_{home}$ cC flushes (30 cycles)
\item \sp/$_{home}$ reads that flush has completed (30 cycles to do
first read, 30 cycles to read cache-line first word, 7 cycles to
finish reading)
\item \sp/$_{home}$ sends cache-line + address back to requester (60 cycles)
\item message travels through Arctic (18 cycles per stage, assume 7
stages, 126 cycles.)
\item message enters NIU (54 cycles + 12 cycles)
\item \sp/ reads message from NIU (60 cycles)
\item write cache-line to the ACD.  Assume write-through (32 cycles +
15 cycle latency for 8 words).
\item write bus tag to ACD.  Assume uncached write (15 cycle latency.)
\end{enumerate}

Thus, the total time to perform a memory access to a cache-line from a
remote site and the line is dirty at that site is 67 +  35 + 12 + 126
+ 20 + 2 + 1 + 30 + 2 + 20 + 30 + 30 + 30 + 7 + 60 + 126 + 54 + 12 +
60 + 32 + 15 + 15 = 786.

If a non-local invalidation needs to be performed before the value can
be returned, the following steps need to be performed.  These steps
occur after the tag comparision takes place.

\begin{enumerate}
\item \sp/ sends request (35 cycles)
\item message propogates through NIU (12 cycles)
\item request goes through Arctic network (18 cycles per stage, assume
7 stages, 126 cycles)
\item \sp/$_{home}$ receives message (20 cycles)
\item \sp/$_{home}$ computes offset for directory state by performing a shift
and an {\sc and} operation.  (2 cycles)
\item \sp/$_{home}$ adds base to offset (1 cycle) and reads directory word (3,
15 or 30 cycles.)
\item \sp/$_{home}$ checks to see that it cache-line is home (2 cycles)
\item \sp/$_{home}$ finds that cache-line is not clean at home and sends and
invalidation message (35 cycles)
\item message propogates through NIU (12 cycles)
\item request goes through Arctic network (18 cycles per stage, assume
5 stages 90 cycles)
\item \sp/$_{remote}$ receives message (20 cycles)
\item \sp/$_{remote}$ writes flush to cC (20 cycles)
\item \sp/$_{remote}$ cC flushes (30 cycles)
\item \sp/$_{remote}$ reads that flush has completed (30 cycles to do
first read, 30 cycles to read cache-line first word, 7 cycles to
finish reading)
\item \sp/$_{remote}$ sends back cache-line (60 cycles) to home
\item request goes through Arctic network (18 cycles per stage, assume
5 stages 90 cycles)
\item message enters NIU (54 cycles + 12 cycles)
\item \sp/$_{home}$ receives cache-line (60 cycles)
\item \sp/$_{home}$ sends cache-line + address back to requester (60 cycles)
\item message travels through Arctic (18 cycles per stage, assume 7
stages, 126 cycles.)
\item message enters NIU (54 cycles + 12 cycles)
\item \sp/ reads message from NIU (60 cycles)
\item write cache-line to the ACD.  Assume write-through (32 cycles +
15 cycle latency for 8 words).
\item write bus tag to ACD.  Assume uncached write (15 cycle latency.)
\end{enumerate}

Thus the total for reads is 67 cycles + 35 + 12 + 126 + 20 + 2 + 1 +
30 + 2 + 35 + 12 + 90 + 20 + 20 + 30 + 30 + 30 + 7 + 60 + 90 + 54 + 12
+ 60 + 60 + 126 + 54 + 12 + 60 + 32 + 15 + 15 = 1219 cycles.

It is possible that some of these numbers could be optimized down or
could go up.  It is important to note that \start/ will be configured
in a Fat tree topology, which allows locality to be exploited.  Thus,
network numbers could be smaller.

