\HeadingLevelC{LLC Address Input Transformation}
\label{sec:dram_regions}

Figure~\ref{fig:dram_regions_stripes} depicts a physical address in a toy
computer with 32-bit virtual addresses and 21-bit physical addresses,
4,096-byte pages, a set-associative LLC with 512 sets and 64-byte lines, and
256 KB of DRAM.

\begin{figure}[htb]
  \centering
  \includegraphics[width=80mm]{figures/dram_regions_stripes.pdf}
  \caption{
    Interesting bit fields in a physical address.
  }
  \label{fig:dram_regions_stripes}
%\EndFigure
\end{figure}

The location where a byte of data is cached in the LLC depends on the low-order
bits in the byte's physical address. The \textit{set index} determines which of
the LLC lines can cache the line containing the byte, and the \textit{line
offset} locates the byte in its cache line. A virtual address's low-order bits
make up its \textit{page offset}, while the other bits are its \textit{virtual
page number} (VPN). Address translation leaves the page offset unchanged, and
translates the VPN into a \textit{physical page number} (PPN), based on the
mapping specified by the page tables.

Sanctum defines the \textbf{DRAM region index} in a physical address as the
intersection between the PPN bits and the cache index bits. This is the maximal
set of bits that impact cache placement \textit{and} are determined by
privileged software via page tables. Sanctum defines a \textbf{DRAM
region} to be the subset of DRAM with addresses having the same DRAM region
index. In Figure~\ref{fig:dram_regions_stripes}, for example, address bits
$[14\ldots12]$ are the DRAM region index, dividing the physical address
space into 8 DRAM regions.

\begin{figure}[htb]
  \centering
  \includegraphics[width=80mm]{figures/dram_region_map.pdf}
  \caption{
    Address shift for contiguous DRAM regions.
  }
  \label{fig:dram_region_maps}
%\EndFigure
\end{figure}

In a typical system without Sanctum's hardware extensions, DRAM regions are
made up of multiple continuous \textbf{DRAM stripes}, where each stripe is
exactly one page long. The top of Figure~\ref{fig:dram_region_maps} drives this
point home, by showing the partitioning of our toy computer's 256 KB of
DRAM into DRAM regions. The fragmentation of DRAM regions makes it difficult
for the OS to allocate contiguous DRAM buffers, which are essential to the
efficient DMA transfers used by high performance devices. In our example, if
the OS only owns 4 DRAM regions, the largest contiguous DRAM buffer it can
allocate is 16 KB.

Observe that, up to a certain point, circularly shifting (rotating) the PPN
of a physical address to the right by one bit, before it enters the LLC,
doubles the size of each DRAM stripe and halves the number of stripes in a DRAM
region, as illustrated in Figure~\ref{fig:dram_region_maps}.

Sanctum takes advantage of this effect by adding a \textbf{cache address
shifter} that circularly shifts the PPN to the right by a certain amount of
bits, as shown in Figures \ref{fig:cache_address_shift} and
\ref{fig:uncore_changes}. In our example, configuring the cache address shifter
to rotate the PPN by 3 yields contiguous DRAM regions, so an OS that owns 4
DRAM regions could hypothetically allocate a contiguous DRAM buffer covering
half of the machine's DRAM.

The cache address shifter's configuration depends on the amount of DRAM present
in the system. If our example computer could have 128 KB - 1 MB of DRAM, its
cache address shifter must support shift amounts from 2 to 5.  Such a shifter
can be implemented via a 3-position variable shifter circuit (series of 8-input
MUXes), and a fixed shift by 2 (no logic), as illustrated by Figure~\ref{fig:limited_shifter}.
Alternatively, in systems with
known DRAM configuration (embedded, SoC, etc.), the shift amount can be fixed,
and implemented with no logic.

\begin{figure}[htb]
  \centering
  \includegraphics[width=80mm]{figures/cache_address_shift.pdf}
  \caption{
    Cache address shifter, 3 bit PPN rotation.
  }
  \label{fig:cache_address_shift}
%\EndFigure
\end{figure}

\begin{figure}[htb]
  \center{\includegraphics[width=50mm]{figures/limited_shifter.pdf}}
  \caption{
    A variable shifter that can shift by 2-5 bits can be composed of a fixed
    shifter by 2 bits and a variable shifter that can shift by 0-3 bits.
  }
  \label{fig:limited_shifter}
\end{figure}

\begin{figure}[htb]
  \centering
  \includegraphics[width=80mm]{figures/uncore_changes.pdf}
  \caption{
    Sanctum's cache address shifter and DMA transfer filter logic in the
    context of a Rocket uncore.
  }
  \label{fig:uncore_changes}
%\EndFigure
\end{figure}
