%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This is the template for submission to MICRO 2016
% The cls file is a modified from  'sig-alternate.cls'
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass{sig-alternate}

\newcommand{\ignore}[1]{}
\usepackage{fancyhdr}
\usepackage[normalem]{ulem}
\usepackage[hyphens]{url}
\usepackage{hyperref}
\usepackage{tabularx}

\usepackage{datetime}

\usepackage[usenames,dvipsnames,svgnames,table]{xcolor}

% Compress itemize and enumerate environments.
\RequirePackage{enumerate}
\RequirePackage{enumitem}
\setlist[itemize]{noitemsep, leftmargin=*, topsep=5pt,partopsep=5pt}
\setlist[enumerate]{noitemsep, leftmargin=*, topsep=5pt,partopsep=5pt}


\usepackage{pifont}
\newcommand{\lena}[1]{\textcolor{Green}{L: #1}}
\newcommand{\stall}{\textit{stall}}
\newcommand{\yescheck}{\textcolor{Green}{\ding{51}}}
\newcommand{\nox}{\textcolor{Red}{\ding{55}}}

%%%%%%%%%%%---SETME-----%%%%%%%%%%%%%
\newcommand{\microsubmissionnumber}{52}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\fancypagestyle{firstpage}{
  \fancyhf{}
\setlength{\headheight}{50pt}
\renewcommand{\headrulewidth}{0pt}
%  \fancyhead[C]{\normalsize{MICRO 2016 Submission
%      \textbf{\#\microsubmissionnumber} -- Confidential Draft -- Do NOT Distribute!!}} 
%\fancyhead[C]{\lena{Compiled on \today\ at \currenttime}}
  \fancyhead[C]{Under Submission -- Confidential Draft -- Please Do NOT Distribute!}
  \pagenumbering{arabic}
}  

\usepackage{graphicx}
\usepackage{epstopdf}


%%%%%%%%%%%---SETME-----%%%%%%%%%%%%%
\vspace{-20pt}
\title{Crossing Guard: Mediating Host-Accelerator Coherence Interactions} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vspace{-20pt}
\numberofauthors{3}
\author{
    Lena E. Olson \qquad Mark D. Hill \qquad David A. Wood\\
\vspace{-20pt}
    \email{\{lena, markhill, david\}@cs.wisc.edu}
}



\begin{document}
\maketitle
\thispagestyle{firstpage}
\pagestyle{plain}



%%%%%% -- PAPER CONTENT STARTS-- %%%%%%%%

\begin{abstract}


Specialized hardware accelerators have performance and energy-efficiency advantages over general-purpose processors.
To fully realize these benefits and aid programmability, accelerators may share a physical and virtual address space and full cache coherence with the host system.
However, allowing accelerators, particularly those designed by third parties, to directly communicate with host coherence protocols poses several problems.
Host coherence protocols are complex, vary between companies, and may be proprietary, increasing burden on accelerator designers.
Bugs in the accelerator implementation may cause crashes and other serious consequences to the host system.

We propose \textit{Crossing Guard}, a coherence interface between the host coherence system and accelerators.
The Crossing Guard interface provides the accelerator designer with a standardized set of coherence messages that are simple enough to aid in bug-free coherence design while also providing performance comparable to the host protocol.
The Crossing Guard hardware is implemented in the trusted host design, and translates the accelerator messages into the host coherence protocol while providing safety guarantees for the host system, even in the presence of arbitrarily bad accelerator behavior.
We show that our proof-of-concept design allows varying coherence and cache organizations on both the accelerator and host.


\end{abstract}

\section{Introduction}
Specialized hardware accelerators have recently been proposed for a wide range of applications~\cite{maloney:myriad:hot-chips:2014,park:raychip:hot-chips:2014,esmaeilzadeh:npu:micro:2012,kocberber:walkers:micro:2013,phillips:sparc-m7:hot-chips:2014,lunteren:xml-accelerator:2004,atasu:regex:fpl:2013,rajagopalan:xilinx-keynote:micro:2013}.
Some complex accelerators can benefit from the ability to access a shared, unified address space with the host system.
In particular, future accelerators may wish to share data with the host at a fine granularity, where the particular data to be accessed is not known a priori.
For CPU workloads with these characteristics, hardware coherence aids in both performance and programmability by avoiding the need for the programmer to explicitly manage where data is located in memory and the cache hierarchy.
There is an increasing recognition that accelerators can benefit from hardware coherence as well~\cite{power:hsc:micro:2013,kumar:fusion:isca:2015,agarwal:selective:hpca:2016}.

There are several major differences between coherence protocols designed for CPUs and those designed for accelerators.
First, some accelerators may have data access characteristics that benefit from specific accelerator cache organizations.
Unlike CPUs, which are general-purpose and must handle many access patterns well, accelerators may tend to access data in very specific ways.
For example, the FUSION accelerator coherence protocol~\cite{kumar:fusion:isca:2015} is designed to migrate data between a set of cooperating accelerators working on the same application.

The coherence and cache organization design space is large: caches may be inclusive, exclusive, or non-inclusive; write-back or write-through; write allocate or write no-allocate.
They may also include hardware prefetchers of various types.
A simple coherence protocol may include only Invalid (I) and Valid (V) states; most coherence protocols also include states such as M (Modified), S (Shared), E (Exclusive), O (Owned) and/or F (Forward)~\cite{sorin:memory-consistency:book:2011}.
Accelerator designers may have extensive knowledge of likely data access patterns, and may choose to allocate the resources they have for caches depending on these characteristics.
For example, an accelerator that performs some streaming accesses may benefit from prefetching more than an accelerator that tends to perform highly data-dependent, unpredictable accesses.
\textbf{Giving accelerator designers extensive flexibility will lead to better accelerator performance.}

Second, any particular accelerator may be integrated with a range of host systems.
These host systems will be designed by different companies and will have different coherence protocols.
For example, Intel uses an inclusive cache hierarchy with a MESI protocol, ARM uses a MESI-like protocol and inclusive or exclusive caches, and AMD uses an exclusive MOESI protocol.
In addition, the specific messages that these host systems use may be proprietary and unknown to the accelerator designer.
Even if the protocol is known, it is a substantial burden for the accelerator designer to need to design and implement different caches for each host system.
\textbf{Giving accelerator designers a single standard coherence interface will ease accelerator development.}

Third, accelerator designers may not have the same expertise in developing complex coherence protocols as host designers.
Coherence protocols are notoriously difficult to design and implement correctly~\cite{deorio:coherence-verification:iccd:2008}.
One reason for this is that for high-performance, protocols allow race conditions between messages between components of the coherence system.
Direct communication between caches at the same level of the hierarchy, such as between L1s, also improves performance at the cost of complexity.
Much of the difficulty of implementing coherence protocols comes from dealing with these cases.
\textbf{Giving accelerator designers a simple coherence interface will make it easier to implement and verify correct coherent accelerator caches.}

Finally, accelerators may not share the same presumption of correctness and trustworthiness as CPUs.
If the accelerator cache incorrectly discards a request from the host rather than responding to it, the host system may wait indefinitely.
Over time, this bug could consume host resources until the host system in rendered unusable -- including for processes that \textit{never use the accelerator}.
Similarly, unexpected messages from the accelerator could crash the host system.
It is even possible that an accelerator could contain malicious hardware that could be triggered to perform incorrect coherence actions as a denial of service attack.
\textbf{Giving host designers a standardized coherence interface will allow them to limit the incorrect actions an accelerator can perform, reducing the attack surface and improving reliability and security.}

Current approaches to accelerator memory access fulfill some of these goals.
For example, IBM's Coherent Accelerator Processor Interface (CAPI)~\cite{ibm:capi:manual:2014} provides a standardized interface and safety for the host; however, it does not allow accelerator designers the freedom to include optimized coherent caches.
At the opposite end of the spectrum, GPUs may make high-performance accesses to the coherent memory system with highly optimized caches, but do not use a standardized public interface to do so; this approach is sensible for accelerators designed by the same company as the host system, but not for third-party accelerators.

We propose \textit{Crossing Guard}: host hardware that forms an interface between the host system and the accelerator and which mediates coherence interactions between the host and the accelerator.
Crossing Guard is similar to the software concept of an Application Program Interface (API), which provides a public interface which is simple and stable.
Meanwhile, the back-end implementation can be treated as a black box and can change without notifying users of the API.
The narrow set of interactions that are allowed by the API (or Crossing Guard) limits the potential error cases.

Crossing Guard provides benefits to both the host and accelerator designers.
For the host designer, Crossing Guard provides a set of safety guarantees even in the presence of a buggy or malicious accelerator.
Crossing Guard ensures that:

\begin{itemize}
\item Coherence messages are in a format understandable to the host.
\item Host coherence requests to the accelerator will always be answered with a response within a maximum worst-case time.
\item An accelerator cannot send a response without the host first sending a request.
\item Virtual memory permissions are enforced, as in Border Control~\cite{olson:border-control:micro:2015}.
\end{itemize}

These guarantees allow the host designer to integrate potentially buggy accelerators as full participants in host coherence, without sacrificing reliability, liveness, or data correctness.
Crossing Guard also benefits the accelerator designer by providing them with a standardized interface for making coherence requests, while still allowing them to design their own optimized accelerator cache(s).

We define a standardized set of coherence requests and responses for accelerators, and implement two accelerator coherence protocols that use the interface.
The first is a single-level high-performance MESI cache, which requires only 4 stable states and single transient state.
The second is a two-level accelerator protocol, with an L2 shared between multiple accelerator cores running the same application.

We implement Crossing Guard in a heterogeneous system where CPUs and GPGPUs coherently access shared memory.
To demonstrate that it allows freedom for the host designer, we show that the CPUs can use an exclusive, AMD Hammer-like protocol or an inclusive MESI protocol.
Our results show that our approach has comparable performance to running the CPU protocols on the accelerator side of a heterogeneous system.
In addition, Crossing Guard provides safety even when the accelerator is behaving badly: in our tests, sending a stream of random coherence messages to the host system never leads to a crash or deadlock.

%\section{Coherence Background}
%Hardware cache coherence aids in programmability and performance by transferring data between caches on demand, in response to processor memory requests.
%We assume that the coherence protocol maintains a single-writer invariant, where a block is only ever in a writable state in a single cache at the time; this invariant ensures that a load to the same address as a previous store receives the most up-to-date data.
%We briefly review coherence and define our terminology.

%For each cache, a block can be in one of several \textbf{stable states}. Not all are implemented in every protocol, but typical states include:
%\begin{itemize}
%\item \textbf{I: Invalid} The block is not present in the cache.
%\item \textbf{M: Modified Exclusive} The block is present in exactly one cache and is dirty relative to memory.
%\item \textbf{E: Clean Exclusive} The block is present in exactly one cache and is clean relative to memory.
%\item \textbf{S: Shared} The block is present in one or more caches in S, and is not dirty.
%\item \textbf{O: Owned} The block is present in zero or more other caches in S. The block might be dirty, and this cache may be requested to provide the data to other caches or update them if the data changes.
%\item \textbf{F: Forward} The block is present in zero or more other caches in S, and is clean. This cache may be requested to provide data to another cache, at which point it would transition to S and the recipient would take state F.
%\end{itemize}

%When the cache has sent a request but not yet seen a response to that request, it will be in a \textbf{transient state}.
%Typical requests towards memory include \textit{GetS}/\textit{GetM} to obtain a copy of a block and \textit{PutS}/\textit{PutE}/\textit{PutM} to relinquish a block.
%Typical responses to \textit{Get}s include \textit{Data} in various states, and \textit{Acks} to indicate that other caches do not hold a copy of the block in a conflicting state.
%Responses to \textit{Put}s are \textit{WritebackAcks} or \textit{WritebackNacks} depending on success.
%Typical requests towards the processor include \textit{Invalidate}, which requires the cache to send a \textit{Writeback} or \textit{InvAck} towards memory, or a \textit{Forward} request which requires the cache to send \textit{Data} or an \textit{Ack} to the requestor.

\begin{table*}[t]
  \begin{centering}
  \small
    \begin{tabular}{ |c|c|c|c|c|c|c|c|c| }
    \hline
    ~ & \multicolumn{3}{c|}{\textbf{Accelerator Events}} & \textbf{XG Requests} & \multicolumn{4}{c|}{\textbf{XG Responses}} \\
    States & Load & Store & Replacement & Invalidate & DataM & DataE & DataS & WB Ack \\
    \hline
    \hline
    M & hit & hit & issue PutM / B & send WB / I & - & - & - & - \\
    \hline
    E & hit & hit / M & issue PutE / B & send clean WB / I & - & - & - & - \\
    \hline
    S & hit & issue GetM / B & issue PutS / B & send InvAck / I & - & - & - & - \\
    \hline
    I & issue GetS / B & issue GetM / B & -  & send InvAck & - & - & - & - \\
    \hline
    B & \stall & \stall & \stall & send InvAck & / M & / E & / S & / I \\
    \hline
    \end{tabular}
    \caption{Sample accelerator L1 cache implementing Crossing Guard's interface.  Entries are of the form \texttt{action} / \texttt{next\_state}, and - indicates an impossible transition.}
    \label{table:accelL1}
    \end{centering}
\end{table*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%SECTION START%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Crossing Guard}
Crossing Guard consists of hardware that implements a simple, standardized interface for coherence and translates requests between the host and the accelerator.
It also ensures that an accelerator cannot affect other processes running on the CPU, no matter how pathologically bad the accelerator's behavior is; in particular, it protects against crashing or deadlocks.
We target systems where the accelerator maintains a TLB to allow it to use physical addresses and has fully coherent caches.

Crossing Guard provides translation between protocols: the accelerator caches can make requests to Crossing Guard with a standardized set of coherence messages, and the host can use the normal host protocol.
To the host coherence protocol, the Crossing Guard will appear as simply another coherent cache.
Any complex interactions with the other caches in the system, such as counting acknowledgment messages or handling races, will be taken care of by the Crossing Guard.

There is one instance of Crossing Guard per accelerator in the system.
It is implemented by the host designer, who has full knowledge of the coherence protocol running on the host.
Once implemented, the Crossing Guard hardware works with any accelerator making use of the interface; it only needs to be updated when the host protocol changes.

\subsection{Accelerator Coherence Interface}
We define a set of requests and responses that form the coherence interface.
The messages chosen determine optimizations the accelerator coherence protocol can make.
For example, if the only way for the accelerator to request a block is with a generic \textit{Get} message, the accelerator will only be able to implement a VI protocol.

The accelerator can make a total of 5 requests to the host and receive one of 4 responses; the host can make 1 request to accelerator and receive one of 3 responses.
Every request always results in exactly 1 response.

The accelerator requests a block from the host with \textit{GetS} (shared and read-only) or \textit{GetM} (exclusive and read-write).
In return, it can receive \textit{DataS} (shared+clean), \textit{DataE} (exclusive+clean), or \textit{DataM} (exclusive+modified).
The accelerator may receive \textit{DataE} or \textit{DataM} on either a \textit{GetS} or \textit{GetM} request; in the former case, the accelerator cache has the block in E state and can, on a store, silently upgrade to the M state.

When the cache replaces a block, it must send an appropriate request: \textit{PutM}, \textit{PutE}, or \textit{PutS}.
The \textit{PutM} and \textit{PutE} messages carry data, to avoid the complexity of a multi-phase commit.
In response to any \textit{Put} request, the cache will receive a \textit{WritebackAck}.
M and E are both owned states; when the host sends an \textit{Invalidate} request, the accelerator must respond with \textit{Writeback} or \textit{Writeback Clean}, respectively.
Otherwise, the accelerator must respond with an \textit{InvAck} (Invalidation Acknowledgment).

As long as the accelerator cache follows these rules, the interface guarantees that the system will follow normal coherence invariants, such as that only a single cache in the host or accelerator may ever hold a block in an exclusive state.
These messages are sufficient to implement a fully coherent cache with similar performance characteristics to more complex traditional protocols such as AMD Hammer or Intel MESI(F), and which can communicate with a variety of host cache designs.
Not all of these messages are necessary for integration with all host protocols; for example, when connecting to a host protocol that allows silent eviction of blocks in S state, the PutS message is unnecessary.
However, the goal of the interface is to work with a wide variety of traditional coherence protocols.

Table \ref{table:accelL1} shows an example transition matrix in the style of Sorin et al.~\cite{sorin:memory-consistency:book:2011} for an accelerator L1 cache implementing this interface.
In this case, a single private L1 cache is connected to each Crossing Guard.
We implemented a MESI cache.
The single-level cache has only a single transient state, B (Busy).
In comparison, the private L1 in our baseline implementation of an inclusive MESI host protocol has 6 transient states, some of which include extra information such as a dirty bit or counters for pending acks, and can receive 4 host requests and 7 host responses.
These extra states and messages are required to deal with races and counting pending acks.
We require that the network between the Crossing Guard and the accelerator be ordered, which avoids all races between the accelerator except between an accelerator \textit{Put} and a host \textit{Invalidate} request.
All other races and complexity are hidden by the Crossing Guard.

In addition to the single-level accelerator cache, we also implemented a hierarchical two-level accelerator cache design: private per-core L1s connected to a shared L2, which communicates with the Crossing Guard.
Blocks can be shared between accelerator L1s even if the block is in M state at the accelerator L2; the L2 coordinates sharing.
The accelerator cache hierarchy and protocol are completely independent of the host design, and connect to the host using the same Crossing Guard hardware as the single-level protocol.

If an accelerator benefits more from simplicity than from being able to implement a full MESI protocol, the accelerator cache can reduce complexity by treating several messages identically.
For example, an accelerator cache can implement a VI design by sending only \textit{GetM} requests.
An MSI design is possible by treating \textit{DataE} as \textit{DataM} (in which case the accelerator will never need to send clean \textit{Writeback}s).

\subsection{Crossing Guard Invariants}
Crossing Guard provides the following invariants to the host:
\begin{enumerate}
\item The accelerator cannot make any request for a block for which it has no page access permissions.
\item The accelerator cannot make an exclusive (write) request or respond with exclusive data for a block for which it does not have page write permission.
\item The accelerator cannot send any response except in reply to a host request.
\item The accelerator must respond to a host request with the correct response message type.
\item The accelerator must respond to all requests from the host within a reasonable time.
\item The accelerator cannot make a second request for the same block until the first one receives a response.
\item The accelerator cannot send any unexpected requests.
\end{enumerate}

If the accelerator attempts to violate one of these invariants, the Crossing Guard will block the message (or send an appropriate message on a timeout), and will report an error to the OS.
The OS can then use an appropriate policy to handle the error; for example, it can terminate the process running on the accelerator, disable the accelerator to prevent it from making further accesses, and/or not schedule further processes on the accelerator and alert the user.
In practice, we believe that the simpler coherence interface associated with Crossing Guard will limit the number of accelerator protocol errors.

We now discuss in general terms how Crossing Guard enforces each invariant above:

\textbf{Invariants 1 \& 2}: Crossing Guard checks page permissions, as described in prior work such as Border Control~\cite{olson:border-control:micro:2015}, and blocks incorrect accesses.

\textbf{Invariant 3}: Crossing Guard keeps state indicating whether there is a pending request from the host for the block.  If not, it blocks the response.

\textbf{Invariant 4}: Crossing Guard tracks the type of pending host coherence request, as well as the state of the block at the accelerator.  If the response type is incorrect based on this information, it corrects the response type.  For example, if the accelerator has a block but responds to an \textit{Invalidate} with an \textit{InvAck}, Crossing Guard will send a \textit{Writeback} message instead.

\textbf{Invariant 5}: Crossing Guard keeps a timer on every pending request from the accelerator.  If the accelerator does not respond to the request within a timeout, Crossing Guard will respond on its behalf with an appropriate message.

\textbf{Invariant 6}: Crossing Guard tracks all pending accelerator coherence requests. If there is already a pending request from an accelerator, it will block all subsequent accelerator requests.

\textbf{Invariant 7}: Crossing Guard tracks the state relative to the host of all blocks in the accelerator caches. If the request type does not make sense given the state (e.g., writing back a block it does not have), Crossing Guard will block the request.

To enforce these invariants, Crossing Guard must assume that an incorrect accelerator might send any message at any time.
This means that every state at the Crossing Guard must have transitions for every accelerator response and request.
Many of these transitions will never occur with a correct accelerator; however, they must be implemented such that the above invariants are always maintained.

\subsubsection{Invariants Not Provided by Crossing Guard}
One consequence of coherence bugs is that normal coherence invariants such as single-writer might be broken, leading to application data becoming corrupted and thus errors in the application, such as incorrect output or application crashes.
Although this is undesirable, the damage caused by incorrect data in memory accessed by the accelerator is limited.
With memory address protection as in prior work, the accelerator can only access addresses with the permissions of the process it is running.
Thus, corrupt data can only affect processes running on the accelerator, and the rest of the system is protected.

It is in general not possible to provide complete protection against incorrect data from the accelerator.
Bugs in the accelerator's cache implementation, register files, or core can also produce incorrect data, and the host system generally does not have enough information to detect this type of error.
It is the responsibility of the accelerator designer to ensure that the accelerator produces correct data; a simple and standardized coherence interface makes it easier to implement a correct accelerator cache, but does not remove the necessity of testing.
Crossing Guard focuses instead on keeping accelerator bugs from affecting the rest of the system.

\subsection{Types of Crossing Guard}

There are several possible implementations of the Crossing Guard hardware.
They provide the same interface to the accelerator, but have different benefits depending on specifics of the host protocol and the importance of minimizing the storage needed by Crossing Guard.
We discuss two types of Crossing Guard.
First, the \textit{Full State Crossing Guard} places few restrictions on the characteristics of the host protocol, allowing it to be used with no modifications to the host protocol.
However, it needs to store information about every block currently owned by the accelerator.
Second, the \textit{Transactional Crossing Guard} alternative only tracks open coherence transactions: cases where the host or the accelerator has made a request but not yet received all responses.
It has much lower storage requirements, but requires that the host coherence protocol have certain properties.
We found that existing coherence protocols (such as an AMD Hammer-like protocol and an inclusive MESI protocol) required only minor changes to work with Transactional Crossing Guard.

\subsubsection{Full State Crossing Guard}
Full State Crossing Guard adds hardware that tracks the state of every block present at the accelerator, as well as keeping a copy of the data for read-only blocks.
In effect, this design adds a trusted inclusive directory between the host protocol and the accelerator.

Because this directory contains a trusted copy of all data and metadata for each block, it allows Crossing Guard to work with a wide variety of host coherence protocols.
Whenever Crossing Guard receives a copy of a block in some state, it can forward on that information to the accelerator, no matter the details of how the block was obtained (e.g., via a data message + acks or by gathering tokens in a Token protocol).
When the Crossing Guard loses access to a block, due to an invalidation or forward request or timeout, it can notify the accelerator to invalidate its copy.
Thus, Full State Crossing Guard works with a variety of unchanged host coherence protocols.

Full State Crossing Guard must store all data and metadata that could lead to a host coherence error if it were improperly modified.
At a minimum, it must store tags for all blocks currently stored in the accelerator.
For a 256kB accelerator cache with 64-byte blocks, this storage is around 16kB.
In addition, there would need to be storage for blocks in MSHRs or buffers.

The Crossing Guard may also need to store data for some blocks, if that data should not be modified by the accelerator.
For example, if the accelerator is allowed to own a block to which it does not have Read-Write permission, the Crossing Guard must store a copy of the data to avoid violating \textbf{Invariant 2}.

Due to the storage overhead for Full State Crossing Guard, it may be most appropriate for accelerators with small caches or where the host protocol maintains metadata with all blocks.

\subsubsection{Transactional Crossing Guard}
Transactional Crossing Guard only tracks open coherence transactions, which reduces the storage required.
In addition, it may allow time-sharing of the Crossing Guard hardware between accelerators, because its storage will not need to be sized for a specific accelerator.

Most of Crossing Guard's invariants can be enforced without Crossing Guard knowing the state of the block at the accelerator.
\textbf{Invariants 1 \& 2} require only knowledge of each coherence request/response type and address, because they maintain page access permissions.
\textbf{Invariant 3} requires knowing whether there is an open request from the host, \textbf{Invariant 4} requires knowing whether there is an open host request and how long the transaction has been pending, and \textbf{Invariant 6} requires knowing whether the accelerator has a pending request for the address.
None of these require knowledge of stable states.

However, \textbf{Invariants 4 \& 7} do require more knowledge than is available to Transactional Crossing Guard.
We therefore replace these invariants with weaker forms:

\begin{enumerate}
\item [4$'$] The accelerator \textit{may} respond with an \textit{incorrect} response type to a host request, if some host requests have multiple corresponding responses depending on the block's stable state.
\item [7$'$] The accelerator \textit{can} send unexpected requests.
\end{enumerate}

The host protocol must be able to deal safely with these cases.
We give examples of how these cases can occur and solutions that maintain safety.

\textbf{Invariant 4$'$} can occur because Transactional Crossing Guard has no information about what stable state the accelerator cache is in.
As an example, consider a protocol that does not exactly track owners/sharers and thus broadcasts a \textit{Forward} message to all caches, whether or not they have the block.
The correct response thus depends on the state of the block at the accelerator: a \textit{Data} message if the accelerator is the owner, otherwise an \textit{InvAck}.
Because Crossing Guard does not store information about blocks in stable states, it has no means of determining which of these messages is correct, and must send either to the requestor.
This can result in problems in the accelerator host protocol, where a cache might receive zero or multiple copies of data instead of the exactly one copy it expects.

Safety may be maintained in this case by ensuring that there is only a single type of response per request in the host protocol.
One way to do this is by exactly tracking owner and sharer information, and sending a different type of request in each case: splitting the requests into two types.
An alternative approach is to modify the host protocol to handle the different responses interchangeably; rather than counting acks, the requestor can count the number of responses received.
If a cache receives zero or multiple copies of data for the same block, it can detect that an error has occurred and the process can be terminated.

\textbf{Invariant 7$'$} is also due to the lack of Crossing Guard knowledge of accelerator stable state.
An example unexpected accelerator request would be a \textit{Put} message for a block the accelerator does not own, or a \textit{PutM} message for a block in S.
Since Crossing Guard does not know whether the accelerator has the block in an appropriate state, it must forward the request to the host.

To maintain safety, the host protocol therefore needs to be able to handle unexpected \textit{Put} requests without failing.
In some cases, the directory maintains owner information, which allows the host to determine if a \textit{Put} is erroneous and report an error.
Similarly, a protocol that uses \textit{PutS} is likely to do exact sharer tracking, allowing it to determine if a \textit{PutS} message is correct.

In some protocols, non-owner \textit{PutM} requests can occur due to a non-erroneous race condition.
However, if the host protocol generates \textit{Nack}s or takes other action on the \textit{Put} (besides simply sinking it), it is necessary to ensure that these actions do not cause harm.
For example, if an improper accelerator \textit{Put} can result in a spurious \textit{Nack} being sent to a CPU cache, it is necessary that the CPU cache can detect this case and safely handle the message.

The other requirement of Transactional Crossing Guard is that \textbf{any data or metadata associated with an accelerator stable state must be able to be corrupted by the accelerator without causing a crash or deadlock}.
In general, any data or metadata given to the accelerator in a stable state must be considered unsafe and potentially modified; this means that, for example, a Token protocol where each block is associated with virtual tokens, would require extensive changes to work with Transactional Crossing Guard.

Similarly, since Transactional Crossing Guard does not keep copies of read-only blocks, it must ensure that the accelerator never owns a block with read-only permissions.
Some host protocols will respond to a \textit{GetS} request with \textit{DataE} or \textit{DataM} if no other cache is has the block as a performance optimization.
This allows silent upgrades to M state later.
However, if the accelerator has Read-Only permission for the block, the accelerator should never have an owned copy of the data, because the accelerator cannot be trusted to provide a correct and unmodified copy of the data.
Furthermore, the performance optimization is not helpful because the block will not be written by the accelerator.
To address this issue, we require that the host protocol provide a way to make \textit{GetS} requests that are never upgraded.

In practice, we found that the baseline protocols we used require minor changes to work correctly with these weakened invariants (see Section \ref{sec:hostchanges}.
Since both the Crossing Guard and the host coherence protocol are designed by the host designer, it may be reasonable to optimize Crossing Guard storage by making host protocol changes, especially if the changes do not require extensive redesign.
The trade-offs between Full State Crossing Guard and Transactional Crossing Guard may weigh differently for different host systems.
Since both use the same interface with the accelerator, the decision can be made independently of any accelerator design decisions and can be different for different host systems.

\subsection{Comparison with Traditional Protocols}
There are several differences between our interface and existing host protocols like AMD Hammer and Intel-like inclusive MESI.
First, the Crossing Guard prevents direct communication between an accelerator cache and other sibling caches in the system.
In contrast, many protocols allow a cache to forward data to other caches at the same level.
Crossing Guard's interface allows the accelerator cache to communicate only with a single controller (Crossing Guard), which in turn communicates with the other caches in the system.

This design choice has benefits and disadvantages.
The main benefit is avoidance of the complexity associated with sending data or acknowledgements between sibling caches.
In Hammer, a request for a block will result in a response from every other cache; in the MESI protocol, the requestor is told by the L2 how many responses it should receive.
In both cases, the requestor must count acks, determine the type (e.g., \textit{DataS}, \textit{DataE}, or \textit{DataM}) of data received, and determine whether to send an unblock message to the parent, which adds complexity and thus implementation, debugging, and verification difficulty.
We shift this complexity to the Crossing Guard, which only needs to be designed once per host protocol.
In return, the accelerator protocol needs to handle fewer response types, and is guaranteed to receive exactly one response message per request sent.

Second, the Crossing Guard is able to filter out race conditions, which also contributes to a simpler accelerator protocol.
In some traditional protocols, if a cache requests a block in S, it may receive an invalidation before the data, in which case it must go into a transient state such as ISI~\cite{sorin:memory-consistency:book:2011}, because the cache does not know whether the data or the invalidation was sent first.
Dealing with race conditions correctly is difficult and adds complexity.
Crossing Guard hides these races from the accelerator cache by providing simple messages over an ordered network between the Crossing Guard and the accelerator cache, while placing no other constraints on the networks in the system.
The accelerator designer then does not need to consider these race conditions; if the block is not in a stable state, the accelerator cache should always return an InvAck on an Invalidate request and take no further action.

Third, the protocol does not constrain cache design in terms of inclusivity/non-inclusivity/exclusivity or number of levels.
In the two-level accelerator protocol, the accelerators can use an entirely different cache organization than the host.
Our accelerator L2 is inclusive and shared between a number of L1s, all running the same application, which allows data to be transferred between the L1s without going through the Crossing Guard and the host directory.
It can be integrated with the host protocol, regardless of host inclusivity and the number of levels in the host protocol.

\subsection{Limitations on Host Protocols}
Crossing Guard is designed to work with protocols such as those currently used commercially.
In general, Full State Crossing Guard works with a wide range of protocols, because the Crossing Guard can implement features of the protocols such as token collection or timeouts, and communicate them to the accelerator though the coherence interface (for example, by sending an invalidate request to the accelerator sufficiently long before a timeout expires).

However, some types of protocols that have been proposed by the research community may not work with Transactional Crossing Guard.
For example, Token protocols~\cite{martin:token-coherence:isca:2003} have been proposed which associate virtual tokens with each block in memory.
%These tokens are passed between caches, and the number of tokens a cache owns determines the operations it can perform: a cache with all tokens for a block can write, and a cache with at least one token can read.
A Token protocol does not work well with Transactional Crossing Guard, because the number of tokens per block is associated with blocks in both transient and stable states, and will result in errors if modified incorrectly by the accelerator.
For protocols where stable states contain important information, Full State Crossing Guard is necessary.
%Because Transactional Crossing Guard only stores information about open coherence transactions, this would result in the accelerator caches tracking the number of tokens per block.
%If the accelerator caches are incorrect, they could ``lose'' or ``gain'' tokens, resulting in the total number of tokens in the system changing and breaking the safety properties of Token coherence.

\subsection{Rate Limiting}
Crossing Guard limits the types of messages the accelerator can send to the host, providing safety against system unresponsiveness due to missing or inappropriate messages.
However, a misbehaving accelerator could also send legitimate messages such as requests at a very high rate, consuming bandwidth, directory entries, or other resources shared with the host.
This could cause significant performance degradation for processes being run on the host system by either intentionally or unintentionally causing a Denial of Service attack.

To avoid this situation, Crossing Guard can limit the rate at which an accelerator can send requests (responses should always be sent immediately).
This rate limiting could be controlled by registers set by OS policies.
Using a configurable limit would also allow correct accelerators to be throttled when they are impacting performance of other components of the system, while allowing them much resources when other processes have lower priority.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%SECTION START%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Crossing Guard Implementation}
To better understand how our proposed interface works with various host protocols, we design Crossing Guard hardware to connect our example one- and two-level accelerator protocols with two baseline host protocols: an AMD Hammer-like exclusive protocol and an inclusive MESI protocol.
We focus on Transactional Crossing Guard, because it can operate with high-performance accelerators with large caches.
%Actually because it's like 1000x more interesting
For our baseline protocols, we use the versions implemented in gem5 as the protocol description.
We integrate Crossing Guard with pre-existing protocol implementations to avoid making design choices in the host protocols that might inadvertently make it easier for us to integrate Crossing Guard.

Crossing Guard appears to the host protocol as an ordinary cache: for Hammer-like as a private L2, and for MESI inclusive as a private L1.
Because the accelerator caches are behind the Crossing Guard, the host protocol is completely agnostic to their design.
Figure \ref{fig:hammer} shows an example system with a Hammer-like protocol for the CPUs and a two-level protocol on the accelerator side, while Figure \ref{fig:inc} shows an inclusive MESI protocol on the CPU and a single-level protocol on the accelerator side; in total there are four possible combinations.

\begin{figure}[t]
\includegraphics[width=\linewidth]{hammer}
\caption{A heterogeneous system where the CPU side is using a Hammer-like protocol with exclusive private L1 and L2s (left, green),  while the accelerator is using an inclusive protocol with a shared L2 (right, blue).}
\label{fig:hammer}
\end{figure}

\begin{figure}[t]
\includegraphics[width=\linewidth]{inc}
\caption{A heterogeneous system where the CPU side is using an inclusive MESI protocol with private L1s (left, yellow) and the accelerator is using a single-level protocol (right, green), connected to a shared L2 cache by multiple instances of Crossing Guard.}
\label{fig:inc}
\end{figure}


\subsection{Permission Information}
Crossing Guard assumes that page access permissions are respected, as in prior works~\cite{olson:border-control:micro:2015}.
For each accelerator or host request where there is not already a pending transaction, Crossing Guard first obtains the page permissions (Read-Write, Read, or None), as in Border Control.
It then stores the page permission information with the transaction.

These permissions are used both to provide protection and also to optimize performance.
For example, if a block has read-only permission, the accelerator should not be able to send any messages for that block containing data.
Transactional Crossing Guard can also be sure that the accelerator does not have the block in M state, so it can acknowledge forwarded shared requests without consulting the accelerator, improving performance.

Similarly, if an accelerator has no permissions for a block, any coherence requests for it should be blocked and reported to the operating system.
In addition, Transactional Crossing Guard can respond to all snoops for that block without consulting the accelerator.
This has two benefits: first, it avoids needless messages and associated latency.
Second, if the accelerator is malicious, coherence traffic could be a side-channel; preventing the accelerator from observing coherence traffic for blocks it cannot access closes the channel.

%\subsection{Snoop Locality}
%Crossing Guard obtains block page permissions in a similar fashion to prior work~\cite{olson:border-control:micro:2015}, where permissions for recently accessed blocks are stored in a small permission cache.
%This works well when accesses have locality, as they do for requests generated by accelerator demand accesses.
%However, in protocols that do not track exact sharer information, there may be many snoops forwarded to the accelerator for blocks that are not accessible by the accelerator.
%Once Crossing Guard knows the permission, it can immediately ack the request; however, looking up these permissions may thrash the permission cache and contribute to long latencies for future permission lookups.

%To avoid polluting the permission cache, we add a non-counting Bloom filter to Crossing Guard, to which we add each page the accelerator accesses.
%On a permission lookup, if the Bloom filter returns a miss, the page must have no permissions at the accelerator and thus by definition cannot reside in the accelerator caches; the Crossing Guard can simply ack any forwarded or invalidate requests.
%If the Bloom filter returns a hit, then the page \textit{may} be accessible to the accelerator, so Crossing Guard checks the permission cache / protection table, as normal, to determine if the page permissions are None, Read-only, or Read-Write.

%Because pages can only be inserted in the Bloom filter and never removed, the Bloom filter will gradually report more and more false positives.
%Crossing Guard maintains correctness by always checking the permission cache / protection table for the canonical page permissions, but the false positives will once again thrash the permission cache.
%However, on updates to page tables for the process running on the accelerator, the accelerator TLBS, caches, and all permission information is flushed.
%In that case, the Bloom filter will be cleared, leading the false positive rate to drop.


\subsection{Integration with Host Protocols}
\label{sec:hostchanges}
We integrated Transactional Crossing Guard and the accelerator caches with two existing coherence protocols in gem5-gpu~\cite{power:gem5-gpu:cal:2014}, with the general-purpose GPU as a proxy for a high-performing accelerator that can benefit from coherence.
We discuss our experiences with each and the necessary host protocol modifications.
%We used the MOESI\_hammer protocol as an example of an exclusive protocol; it is similar to the AMD Hammer protocol.
%The MESI\_Two\_Level protocol is an example of an inclusive protocol meant to be similar to Intel's.

Although a different Transactional Crossing Guard implementation is needed for each host protocol, there were significant similarities.
The Crossing Guard stores information about in-flight coherence transactions, which can be of several types.

First, the accelerator may have an open \textit{Get} request.
In this case, Crossing Guard makes the request and then waits for data and/or acks from the host system.
When Crossing Guard determines the request has been satisfies (i.e., it has received a copy of the data and the requisite number of acks), it passes the data along to the accelerator with the appropriate message (\textit{DataS}, \textit{DataE}, \textit{DataM}).
If necessary, it also sends the appropriate unblock message to the host directory.

Second, the accelerator may have an open \textit{Put} request.
In this case, the Crossing Guard makes the request and acks the accelerator, then waits for a writeback acknowledgment from the host.
In a two-part writeback as in the Hammer-like protocol, the Crossing Guard then sends the data.
Otherwise, it waits until it receives the ack and then removes the transaction entry.

Third, the host may have an open invalidate or forward request.
In this case, Crossing Guard sends an \textit{Invalidate} to the accelerator, then waits for its response so it can translate it and send it to the host (i.e., directory, sibling cache, or both), sending the appropriate message type and number of acks, etc.
Crossing Guard also maintains a timer for these transactions, so that if the accelerator takes too long to reply, the Crossing Guard can recover by sending either a zero data block or an ack to the requestor, and then alert the OS that an error has occurred.

Finally, there may be a race between an accelerator and host request, resulting in a transaction that is waiting for both the host and the accelerator.
For example, the accelerator may make a \textit{Put} request at the same time as the host makes an \textit{Invalidate} request for the same block.
In this case, Crossing Guard must ensure that both the host and accelerator have received responses before closing its transaction entry.

Transactional Crossing Guard also performs some performance optimizations with its information on accelerator transient states.
For example, if the Crossing Guard has a transaction open for a block because the accelerator has sent a \textit{GetM} or \textit{GetS} request, Crossing Guard can immediately respond to a forwarded message because a correctly functioning accelerator would not have requested a block it already has.
If the accelerator is not functioning correctly, invariants for data correctness do not apply.

\subsubsection{Integration with Hammer-Like Protocol}
The \texttt{MOESI\_hammer} protocol, as implemented in gem5, combines the private L1I, L1D, and L2 into a single cache controller.
There is a directory in a separate controller.
We integrate the Crossing Guard to act like a private L1/L2 cache.
The left side of Figure \ref{fig:hammer} shows the configuration.

When making a request for a block, the Crossing Guard handles counting acknowledgements.
Once the Crossing Guard has seen the correct number of responses, it passes the block along to the accelerator with an appropriate message (e.g., \textit{DataS}, \textit{DataE}, \textit{DataM}).
Because our protocol has no means of representing a non-exclusive owned state, Crossing Guard must ensure that the host never considers the accelerator to be in one.
For example, if there are multiple \textit{GetS} requests from different cores in the Hammer-like protocol, the directory will forward a \textit{merged GetS} request to the owner.
The expected response is for the owner to downgrade to an owned shared state and also provide the data to the requestors.
We deal with this case by having the Crossing Guard request an invalidation from the accelerator cache, then forward the data in the resulting writeback to the requestors.
Crossing Guard also sends the data to the directory with a \textit{Put} message, relinquishing ownership.

At the directory, we add a \textit{GetS\_only} request, because \textit{GetS} responses serviced by a cache in a modified M state send exclusive data.
The accelerator cannot own modified data without violating \textbf{Invariant 2}, so we require this non-upgradable \textit{GetS} request.
Similarly, we add a \textit{Fwd\_GetS\_only} message to the host L1/L2.

For \textbf{Invariant 4$'$}: incorrect response types from the accelerator (e.g., invalidate instead of a writeback), we change the host cache to count responses rather than acks.
If the host cache receives the wrong number of copies of data, it reports an error but still transitions to a stable state.

Finally, \textbf{Invariant 7$'$} is satisfied because the Hammer-like protocol already handles unexpected \textit{Put} requests by using \textit{Nack}s.
However, spurious accelerator \textit{Put}s can cause a \textit{Nack} to be sent to a (correct) host L1/L2 cache due to incorrect accelerator behavior.
We generate an error and sink expected \textit{Nack}s at the host cache.
Hammer does not use \textit{PutS} messages, so the Crossing Guard simply sends an acknowledgment and takes no further action upon receiving them.

None of these changes required additional states; in total, we added one new event to the directory and one to the L1/L2.
In total, for the Hammer-like protocol, the Transactional Crossing Guard requires 16 states and 23 events.
The Crossing Guard interface converts the 5 request types from the host to the accelerator to a single \textit{Invalidate} request, and the 8 response types from the host to 4.
%It converts the 5 request types from the baseline (\textit{Fwd\_GetM}, \textit{Fwd\_GetS}, \textit{Fwd\_GetS\_only}, \textit{Fwd\_GetS\_merged}, \textit{Invalidate}) into a single accelerator request (\textit{Invalidate}), and the 8 response types (Data (dirty), Data (clean), DataM (dirty), DataM (clean), DataS, Fwd\_Ack, Writeback\_Ack, Writeback\_Nack) to 4.

\subsubsection{Integration with MESI Two-Level}
The \texttt{MESI\_Two\_Level} protocol has a shared L2 that is inclusive of private L1s (where the L1I and L1D share a controller).
We integrate the Crossing Guard as a child of the L2 and sibling of the private L1s, as seen in the left side of Figure~\ref{fig:inc}.

For \textbf{Invariant 2}, MESI Two-Level already fulfills the requirement that the host provide a means of making non-upgradable \textit{GetS} requests.
The implementation in gem5 has a request type, \textit{Get\_Instr}, meant for instruction caches, but which provides the semantics we require.

Similar to the Hammer-like protocol, the MESI protocol requires \textit{Ack}s and \textit{Data} to be treated as equivalent responses (\textbf{Invariant 4$'$}).
This is mostly straight-forward, except in the case where the Crossing Guard receives an invalidation due to a \textit{GetM} request from a host L1 and the accelerator is not the owner.
If the accelerator is buggy and responds with a \textit{Writeback} rather than an \textit{InvAck}, then the Crossing Guard will forward the data to the L2 rather than acking the requesting L1.
Therefore, it is necessary for the L2 to respond to this unexpected event by acking the requestor on behalf of the accelerator.

MESI Two-Level handles unexpected \textit{Put} messages by simply acking them, because they can occur as races in the baseline protocol (\textbf{Invariant 7$'$}).
Thus, no changes were required.
MESI Two-Level does not use \textit{PutS} requests, so these are acked by the Crossing Guard and then discarded.
Again, none of these changes required additional states in the host controllers, and for MESI none of them added any events.

\begin{table}[t]
\begin{centering}
\small
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{CPU}} \\ \hline
\multicolumn{2}{|c|}{CPU Cores} & 1 \\ \hline
\multicolumn{2}{|c|}{CPU Frequency} & 3 GHz \\ \hline
\multicolumn{3}{|c|}{\textbf{Host Caches}} \\ \hline
~ & \textbf{Hammer-like} & \textbf{MESI Inclusive} \\ \hline
L1I \& L1D & 32kB each & 32kB each \\ \hline
L2 (inclusive) & 128kB private & 640kB shared w/ GPGPU \\ \hline \hline
\multicolumn{3}{|c|}{\textbf{GPGPU}} \\ \hline
\multicolumn{2}{|c|}{Cores} & 4 \\ \hline
\multicolumn{2}{|c|}{L1 TLB} & 64 entries \\ \hline
\multicolumn{2}{|c|}{GPU Frequency} & 700 MHz \\ \hline
\multicolumn{3}{|c|}{\textbf{GPGPU Caches (Baseline)}} \\ \hline
~ & \textbf{Hammer-like} & \textbf{MESI Inclusive} \\ \hline
L1I \& L1D & 16kB each & 16kB each \\ \hline
L2 & 128kB each & -  \\ \hline
\multicolumn{3}{|c|}{\textbf{GPGPU Caches (Crossing Guard)}} \\ \hline
~ & \textbf{Single-Level} & \textbf{2 Level} \\ \hline
L1 & 32kB & 32kB \\ \hline
L2 & - & 128 kB \\ \hline \hline

%\multicolumn{3}{|c|}{\textbf{Memory System}} \\ \hline
%\multicolumn{2}{|c|}{Peak Memory Bandwidth} & 180 GB/s \\ \hline
%\multicolumn{2}{|c|}{Memory Capacity} & 3 GB \\ \hline
%\hline
\multicolumn{3}{|c|}{\textbf{Border Control}} \\ \hline
\multicolumn{2}{|c|}{Permission Cache Size} & 8KB \\ \hline
\multicolumn{2}{|c|}{Permission Cache Access Latency} & 2 cycles \\ \hline
\multicolumn{2}{|c|}{Protection Table Access Latency} & 200 cycles \\ \hline
\end{tabular}
\caption{Simulation configuration details.}
\label{table:gem5}
\end{centering}
\end{table}

\begin{figure}[t]
\includegraphics[width=\linewidth]{inc-graph}
\caption{Performance with MESI protocol and a single-level accelerator cache (Figure \ref{fig:inc}) normalized to MESI on both host and accelerator.}
\label{fig:performance-inc}
\end{figure}

\begin{figure}[t!]
\includegraphics[width=\linewidth]{hammer-graph}
\caption{Performance with Hammer-like protocol and a two-level accelerator cache (Figure \ref{fig:hammer}) normalized to Hammer-like on both host and accelerator.}
\label{fig:performance-hammer}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%SECTION START%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Results}

To evaluate the performance and error tolerance properties of Crossing Guard, we implement a Transactional Crossing Guard which uses our coherence interface in gem5-gpu~\cite{power:gem5-gpu:cal:2014}, an open-source simulator that combines gem5~\cite{gem5:can:2011} and GPGPU-Sim~\cite{aamodt:gpgpu-sim:ispass:2009}.
We chose a general-purpose GPU as the accelerator because GPUs are high-performance accelerators that can benefit from sharing a coherent address space with the host system.
Table~\ref{table:gem5} gives details of our simulator configuration.
We evaluate our approach using shared-memory versions of workloads from the Rodinia benchmark suite~\cite{che:rodinia-benchmark:iiswc:2009}, which demonstrate a variety of memory access patterns.
For obtaining page permissions, we used the configurations from Border Control~\cite{olson:border-control:micro:2015}.

We ran tests with 6 coherence configurations.
For the baseline, we ran a single coherence protocol (MESI Two-Level or Hammer-like) on both the CPU and GPGPU side of the system, with no need for Crossing Guard hardware.
We then added the Crossing Guard and ran each accelerator protocol (single and 2-level) with both host protocols to demonstrate that accelerators can use varying protocols regardless of host cache organization.


\subsection{Performance}

Comparing performance across different cache organizations is not straight forward.
For example, adding a level to the cache hierarchy leads to longer demand miss latencies.
Inclusive organizations are able to store fewer blocks than exclusive ones, but can obviate having a separate directory.
Therefore, when presenting performance numbers, we focus on two comparisons.
In the first case, we compare MESI Two-Level on both host and accelerator to MESI Two-Level on the host plus the single-level accelerator protocol.
In the second case, we compare the Hammer-like protocol on both host and accelerator versus Hammer-like on the host plus the 2-level accelerator protocol.


\begin{table*}[t]
\setlength\extrarowheight{2pt}
  \begin{centering}
  \small
    \begin{tabular}{ |c|c|c|c|c|c|c|c| }
    \hline
    \multicolumn{2}{|c|}{\textbf{Protocol}} & \multicolumn{3}{c|}{\textbf{States}} & \multicolumn{3}{c|}{\textbf{Transitions}} \\
    \textbf{Host} & \textbf{Accel} & \textbf{Visited} & \textbf{Possible} & \textbf{\%} & \textbf{Visited} & \textbf{Possible} & \textbf{\%} \\
    \hline
    \textbf{Hammer-like} & \textbf{1-level} & 14+24+12+5 & 16+24+12+5 & \textbf{96\%} & 60+148+65+22 & 72+148+69+22 & \textbf{95\%} \\
    \hline
    \textbf{Hammer-like} & \textbf{2-level} & 14+24+12+20+7 & 16+24+12+20+7 & \textbf{97\%} & 60+148+66+93+18 & 72+148+69+93+18 & \textbf{97\%} \\
    \hline
    \textbf{MESI} & \textbf{1-level} & 17+11+11+5 & 17+11+11+5 & \textbf{100\%} & 121+60+43+22 & 121+60+43+22 & \textbf{100\%} \\
    \hline
    \textbf{MESI} & \textbf{2-level} & 17+11+11+20+7 & 17+11+11+20+7 & \textbf{100\%} & 121+60+43+93+18 & 121+60+43+93+18 & \textbf{100\%} \\
    \hline
    
    \end{tabular}
    \caption{Coverage with random tester. Hammer-like totals are for Directory+Host L1/L2 Cache+Crossing Guard+Accelerator L1 (+ Accelerator L2).  MESI totals are for Host L2+Host L1+Crossing Guard+Accelerator L1 (+ Accelerator L2).}
    \label{table:coverage-good}
    \end{centering}
\end{table*}
\begin{table*}[tbh]
\setlength\extrarowheight{2pt}
  \begin{centering}
  \small
    \begin{tabular}{ |c|c|c|c|c|c|c|c| }
    \hline
    \textbf{Host Protocol} & \multicolumn{3}{c|}{\textbf{States}} & \multicolumn{3}{c|}{\textbf{Transitions}} \\
    ~ & \textbf{Visited} & \textbf{Possible} & \textbf{\%} & \textbf{Visited} & \textbf{Possible} & \textbf{\%} \\
    \hline
    \textbf{Hammer-like} & 14+24+12 & 16+24+12 & \textbf{96\%} & 61+172+154 & 72+172+155 & \textbf{97\%} \\
    \hline
    \textbf{MESI} & 17+11+10 & 17+11+10 & \textbf{100\%} & 127+60+93 & 127+60+93 & \textbf{100\%} \\
    \hline
    
    \end{tabular}
    \caption{Coverage with fuzz tester. Hammer-like totals are for Directory+Host L1/L2 Cache+Crossing Guard.  MESI totals are for Host L2+Host L1+Crossing Guard.}
    \label{table:coverage-evil}
    \end{centering}
\end{table*}


Figure \ref{fig:performance-inc} shows performance for the MESI case.
For most workloads, the overhead is within a few percent of the baseline.
The exceptions are \texttt{bfs}, with an overhead of 11.6\%, and \texttt{lud}, where the Crossing Guard configuration is 5.5\% faster.
The geometric mean is an overhead of 1.6\%.

Figure \ref{fig:performance-hammer} shows performance for the Hammer-like case.
The maximum overhead is 4.3\%, and the geometric mean is 1.8\%.
These results show that the coherence interface does not significantly degrade performance.

\subsection{Protocol Stress Test}
We next evaluated the correctness of our implementation of the accelerator protocols and the interface with the host protocols.
We stress-tested the protocols by running a random testing framework which makes rapid loads and stores to random addresses and checks correctness of the data~\cite{wood:random-tester:design-and-test:1990}.
To increase contention, only a small number of addresses are used, and the cache sizes are correspondingly decreased so that replacements are frequent; message latencies are chosen randomly to model the case where messages are delayed in the network.
The longer the stress tester is run with different random seeds, we expect that eventually all possible transitions will be found.
We assume for this test that all blocks have full read-write permission on the accelerator.

We chose this approach over formal verification because of the practical limitations of existing verification methods.
These approaches typically can verify a system that has only one address in the system, and they may rely on symmetry between cores that our heterogeneous system lacks, increasing the memory needed to run.
In addition, these methods require making simplifications for tractability and do not model all aspects of the protocol.
An industrial implementation of Crossing Guard would likely include formal verification to complement stress testing.

We ran the random tester for at least 5 billion loads per configuration.
Across configurations, the tests ran for a sum of 1,308 compute days.
To understand the coverage of the tester, we counted the state/event pairs that the random tester visited at each cache controller and compared it with the number that we believe are possible, based on transitions defined by the baseline protocols.
In the case of a missing transition or coherence bug that caused incorrect data, the tester would produce an error; we did not observe any errors or missing transitions.
We manually inspected transitions that were never visited and determined that some of them were not actually reachable (e.g., \textit{Replacement} event for a block not in the cache); we therefore removed them from the total.
We show the totals in Table \ref{table:coverage-good}.
These coverage totals do not include states or events that are only reachable due to bugs in the accelerator protocol.

The higher the percentage of states visited, the more likely it is that the tester would have uncovered bugs.
Although the percentage of visited states and transitions at each controller does not directly indicate the percentage of visited \textit{global} state-event pairs, it provides a lower bound on coverage.

For the MESI protocol, we observed 100\% of states and 100\% of transitions at each state.
The coverage for the Hammer-like protocol was lower, with only 96\%/97\% of states and 95\%/97\% of transitions reached.
This was largely due to several transitions in the host directory that never occurred, and which were the only way to enter two states; none of the transitions out of those states could then occur either.
These cases accounted for the 2 missing states and 12 of the missing transitions.
The remaining transitions were in the Crossing Guard, out of transient states only reachable due to races between host invalidations and accelerator replacements, and which only occurred infrequently.

\begin{table*}[t]
  \begin{centering}
  \small
    \begin{tabular}{ |c|c|c|c|c|c| }
    \hline
    \textbf{Approach} & \textbf{Unchanged Host} & \textbf{CAPI} & \textbf{Robust} & \textbf{Full State XG} & \textbf{Transactional XG} \\
    \hline
    \textbf{Avoid Host Changes} & \yescheck & \yescheck & \nox & \yescheck & Minimal \\
    \hline
    \textbf{Standardized for Accel.} & \nox & \yescheck & \nox & \yescheck & \yescheck \\
    \hline
    \textbf{Safe} & \nox & \yescheck & \yescheck & \yescheck & \yescheck \\
    \hline
    \textbf{High Performance} & \yescheck & \nox & \nox & \yescheck & \yescheck \\
    \hline
    \textbf{Low Storage Overheads} & \yescheck & \yescheck & \nox & \nox & \yescheck \\
    \hline
    \textbf{Allows Accelerator Customization} & \yescheck & \nox & \yescheck & \yescheck & \yescheck \\
    \hline
    \end{tabular}
    \caption{Sample accelerator L1 cache implementing Crossing Guard's interface.}
    \label{table:approaches}
    \end{centering}
\end{table*}
\subsection{Accelerator Protocol Fuzz Testing}

To test whether the host is protected from the accelerator when the accelerator caches are incorrect, we employed fuzz testing~\cite{miller:fuzz:cacm:1990}, where we generated random input to the Crossing Guard from the accelerator side.
The fuzz tester takes the place of the accelerator cache(s).
It repeatedly randomly selects one message type and an address, and makes a request to the host (via Crossing Guard), without considering the cache state of the address.
This generates a stream of requests unlike what would be seen in a correctly functioning cache: for example, multiple \textit{GetM} messages without receiving or relinquishing data, \textit{PutM} messages when not the owner, and unsolicited \textit{Writebacks} or \textit{InvAcks}.
It also can lead to missing responses, leading to deadlock.
The host side continues to run the previous random stress tester, but the check for data correctness is removed.

Table \ref{table:coverage-evil} shows the coverage with the fuzz tester.
We found no missing transitions or deadlocks.
The MESI protocol showed 100\% coverage of states and transitions.
The Hammer-like protocol once again did not reach the same 2 directory states and 12 directory transitions.
In addition, it is missing 1 transition at the Crossing Guard that can occur due to a race between the host and accelerator.
These results indicate that Transactional Crossing Guard can, in concert with a slightly modified host protocol, hide accelerator misbehavior from the rest of the system.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%SECTION START%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{-2pt}
\section{Related Work}

Crossing Guard targets accelerators that are high-performance, potentially buggy, and may be designed by third parties.
For accelerators that do not fall into these categories, other existing approaches may be viable.
We discuss several alternatives to Crossing Guard which trade off host modification, safety, and performance, and summarize them in Table~\ref{table:approaches}.

One possible design is to make no changes to the host coherence protocol.
This requires the host protocol to be known to the accelerator designer, and for the host designer to trust or verify that the accelerator is correctly implemented.
The benefit of this approach is that there is no need to add hardware or modify existing cache coherence protocols, and performance will be good.
It may be suitable for accelerators designed by the same company as the host system.
There is considerable work on testing and verifying~\cite{clarke:verification:chdl:1993,abts:cray-x1-verification:ipdps:2003,park:flash-verification:spaa:1996,dill:murphi:cav:1996,manerkar:ccicheck:micro:2015} cache coherence of systems without accelerators, some of which may be applied to heterogeneous systems.

Several companies have introduced interfaces for coherent memory accesses for third-party accelerators.
IBM's Coherent Accelerator Processor Interface (CAPI)~\cite{ibm:capi:manual:2014} allows accelerators to make coherent load and store requests to host memory, but precludes accelerator designers from implementing high-performance customized cache hierarchies.
This model is well-suited for FPGAs, but may not be for complex, high-performance accelerators that can benefit from specific customized and optimized accelerator cache organizations.

The ARM Accelerator Coherency Port (ACP))~\cite{goodacre:arm-big-data:vhpc:2013} allows an accelerator to make coherent accesses to the host: an ACP access will return the most up-to-date copy of the block, even if it resides in a CPU cache.
However, it does not provide full coherence: a request from the host will not return data modified by the accelerator until the accelerator has flushed its caches.
This may be a reasonable approach for some classes of accelerators; in particular, those using a bulk-synchronous model where a kernel is launched to the accelerator, which performs computations on the data and then flushes all blocks at the end of the kernel execution.
However, it is not well-suited when the accelerator, workload, or programming model cannot determine when the accelerator is done with a particular block, or where the CPU and GPU wish to access blocks simultaneously.

Similarly, if data access patterns are coarse-grained or known a priori, coherence may be unnecessary and the accelerator can instead use scratchpads or other software-managed storage.
Even if coherence is desirable from a programmability or performance standpoint, knowledge of specific coherence patterns may allow the accelerator designer to emulate hardware coherence at the cost of lower performance~\cite{agarwal:selective:hpca:2016}.
% XXX cite Matt's work  here?


Another possibility is to redesign host coherence protocols so that they can tolerate bad coherence messages from accelerators.
This approach has the benefit of providing protection both against bugs in the host caches and the accelerators.
However, it has the major drawback of requiring a complete redesign of host coherence protocols, which is expensive.
In addition, prior work degrades performance or is limited to certain error conditions (e.g., missing messages but not incorrect messages)~\cite{sorin:safetynet:isca:2002,fernandez-pascual:fault-tolerant-token-coherence:hpca:2007}.
% XXX
This is because these robust coherence protocols generally address a different fault model: they guarantee correctness of \textit{data} as well as correctness of \textit{coherence messages}.
This might be appropriate for accelerators in critical systems where the accelerator is implemented by the host designer.


Prior work has dealt with incorrect accelerator behavior.
Border Control~\cite{olson:border-control:micro:2015} enforces virtual memory permissions for accelerators, even if they make memory accesses by physical addresses.
However, it does not prevent against incorrect types of coherence messages.

There have been several proposals for hardware that converts between coherence protocols; Stanford FLASH~\cite{kuskin:flash:isca:1994} mentions the possibility, but does not explore its implementation.
Hagersten et al.~\cite{hagersten:coherence-transformer:patent:1999} propose a coherence transformer.
To our knowledge, no previous work discusses translating between coherence protocols with protection against incorrect coherence behavior.

\vspace{-2pt}
\section{Conclusion}
Some future hardware accelerators will benefit from hardware cache coherence.
However, accelerator designers face complex and proprietary host protocols, while host designers may be reluctant to allow potentially buggy accelerator caches to participate in host coherence.
Crossing Guard addresses both challenges by providing a safe and standardized coherence interface, while maintaining high performance.

%%%%%%% -- PAPER CONTENT ENDS -- %%%%%%%%

\clearpage
%%%%%%%%% -- BIB STYLE AND FILE -- %%%%%%%%
\bibliographystyle{ieeetr}
\bibliography{references,misc,security,accel,os,simulation,bash-grapevine,token-coherence,crossref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
