
\section{Introduction}

Modern computer systems are inherently nondeterministic due to a variety of events that occur during an execution, including I/O, interrupts, and DMA fills.  The lack of repeatability that arises from this nondeterminism can make it difficult to develop and maintain correct software.  Furthermore, it is likely that the impact of nondeterminism will only increase in the coming years as commodity systems are now shared memory multiprocessors, which, in addition to the sources of nondeterminism in uniprocessors, are also impacted by the outcome of memory races among threads.  

In an effort to help ease the pain of developing software in a nondeterministic environment, researchers have proposed adding \textit{deterministic replay} capabilities to computer systems.  A system with a deterministic replay capability can record sufficient information during an execution to enable a replayer to (later) create an equivalent execution despite the inherent sources of nondeterminism that exist.  With the ability to replay an execution verbatim, many classes of new applications may be possible:

\begin{description}
\item[Debugging] Deterministic replay could be used to provide the illusion of a \emph{time-travel debugger} that has the ability to selectively execute both forward and backward in time.  
\item[Security] Deterministic replay could also be used to enhance the security of software by providing the means for an in-depth analysis of an attack, hopefully leading to rapid patch deployment and a reduction in the economic impact of new threats.  
\item[Fault Tolerance] With the ability to replay an execution, it may also be possible to develop hot-standby systems for critical service providers using commodity hardware.  A virtual machine (VM) could, for example, be fed, in real time, the replay log of a primary server running on a physically separate machine.  The standby VM could use the replay log to mimic the primary's execution, so that in the event that the primary fails, the backup can take over operation with almost zero downtime.  
\end{description}

As existing commercial products have already shown, deterministic replay can be achieved with a software-only solution when executing in a uniprocessor environment \cite{xu:retrace-vmware:mobs:2007}.  This is due, in part, to the fact that sources of nondeterminism in a uniprocessor, such as interrupts or I/O, are relatively rare events that take a long time to complete.  However, when executing in a shared memory multiprocessor environment, memory races, which can potentially occur on every memory access, are another source of nondeterminism.  All-software solutions exist \cite{dunlap:revirt-mp-replay:vee:2008, leblanc:instant-replay:ieeetoc:1987}, but results show that they do not perform well on workloads that interact frequently.  Thus, it is likely that a general solution will require hardware support.  To this end, Bacon and Goldstein \cite{bacon:hardware-replay:padd:1991} originally proposed recording all snooping coherence transactions, which, while fast, produced a serial and voluminous log.

Xu, et al. \cite{xu:flight-data-recorder:isca:2003} modernized hardware support for multiprocessor deterministic replay in general and \emph{memory race recording} in particular.  A memory race recorder is responsible for logging enough information to reconstruct the order of all fine-grained memory interleavings that occur during an execution.  To reduce the amount of information that needs to be logged (so that longer periods can be recorded for a fixed hardware cost), the system proposed by Xu, et al. implemented in hardware an enhancement to Netzer's
transitive reduction optimization~\cite{netzer}. The idea is to skip the logging of
those races that can be implied through transitivity, i.e., those races implied through the combination of previously logged races and sequential program semantics.  Figure \ref{fig:transitive}a illustrates a transitive reduction.  Inter-thread races between instructions accessing locations \texttt{A} and \texttt{B}, respectively, are not logged since they are implied by the recorded race for location \texttt{F}.  

\begin{figure}[t]
\begin{center}
\includegraphics{figs/transitive.pdf}
\caption{An example of efficient race recording using (a) an explicit transitive reduction and (b) independent regions.  In (a), solid lines between threads are races written to the log, while dashed lines are those races implied through transitivity.  }
\label{fig:transitive}
\end{center}
\end{figure}

While both the original \cite{xu:flight-data-recorder:isca:2003} and follow-on \cite{xu:rtr:asplos:2006} work by Xu, et al. were successful in achieving efficient log compression (\verb ~1 byte/1000 instructions executed), they required a large amount of hardware state, on the order of an additional L1 cache per core, in order to do so.   Subsequent work by Narayanasamy, et al. \cite{satish:strata:asplos:2006} on the Strata race recorder reduced this hardware requirement but, as results in \cite{hower:rerun:isca:2008} show, may not scale well as the number of hardware contexts in a system increases.  This is largely because Strata writes global information to its log entries that contains a component from each hardware thread context in the system.  

A key observation, discovered independently by the authors of this paper at the Universities of Illinois and Wisconsin, is that by focusing on regions of \textit{independence}, rather than on individual dependencies, an efficient and scalable memory race recorder can be made \emph{without} sacrificing logging efficiency.  Figure \ref{fig:transitive}b illustrates this notion by breaking the execution of Figure \ref{fig:transitive}a into an ordered series of independent execution regions.  Because intra-thread dependencies are implicit and do not need to be recorded, the execution in Figure \ref{fig:transitive}b can be completely described by the three inter-thread dependencies, which is the same amount of information required after a transitivity reduction shown in Figure \ref{fig:transitive}a.  

The authors of this paper have developed two different systems, called \emph{DeLorean}~\cite{delorean_isca08} and \emph{Rerun}~\cite{hower:rerun:isca:2008}, that both exploit the same independence observation described above.  These systems, presented in the same session of ISCA, exemplify different tradeoffs in terms of logging efficiency and implementation complexity.  Rerun can be implemented with small modifications to existing memory system architectures but writes a larger log than DeLorean. DeLorean can achieve a greater log size reduction but requires novel hardware to do so.  
