Introduction for joint CACM paper.

Bucky Illini

Department of Determinism (DoD) 1210 W. Dayton St. Champaign, Ilinois

bucky.illini@dod.wiscuiuc.edu

ABSTRACT

Something abstract.

1. INTRODUCTION

Modern computer systems are inherently nondeterministic. This nondeterminism arrises from a variety of sources, including I/O, interrupts, and DMA fills, and can make it difficult to develop software due to the presence of heisenbugs. It is likely that the impact of nondeterminism will only increase in the coming years due to the fact that 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 between threads.

In an effort to help ease the pain of developing software in a nondeterministic environment, researchers have recently proposed adding deterministic replay capability to computer systems. A system exhibiting 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. Enabling deterministic replay in a uniprocessor environment can be done with a software layer (e.g. hypervisor), due largely to the fact that sources of nondeterminism in a uniprocessor are relatively rare events. Memory races, however, can potentially occur on every memory access, making it unlikely that software can record a multiprocessor execution with an acceptable overhead.

Recently, hardware support for multiprocessor deterministic replay has been proposed. These systems all share a common component, namely a memory race recorder, that is responsible for recording enough information to ensure all memory accesses interleave in the same order during replay as they did during execution. These recorders attempt to exploit a transitivity reduction of the instruction dependence graph in order to minimize the amount of information logged. A dependence can be reduced by transitivity if it is implied by the combination of a previously recorded interthread dependence and intra-thread program order. Figure 1a exemplifies a transitive reduction. Inter-thread dependencies for instructions accessing locations A and B, respectively, are implied by the dependencies recorded for location

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Copyright 2008 ACM 0001-0782/08/0X00 ...$5.00.

Figure 1: default

                                                        F.

While prior memory race recording proposals have been able to achieve an efficient reduction in log size, they have have so far required a large amount of hardware state in order to do so (e.g., 24KB/core).

A key observation, discovered independently by the authors of this paper, is that by focusing on regions of independence, rather than on individual dependencies, an efficient and scalable memory race recorder can be made. ...

DeLorean and Rerun present different tradeoffs in terms of logging efficiency and implementation complexity. DeLorean can achieve a greater log size reduction but requires novel hardware in order to do so. Rerun can be implemented with small additions to existing memory system architectures but writes a larger log than DeLorean.

2. RERUN

The Rerun system’s main advantage over DeLeorean is it ability to work with existing memory system architectures with only small modifications. The Rerun race recorder does not interfere with a running program in any way; it is an impartial observer of a running execution.

2.1 Episodic Memory Race Recording

This section develops insights behind Rerun. It motivates Rerun with an example, gives key definitions, and explains how Rerun establishes and orders episodes.

2.1.1 Motivating Example and Key Ideas

Consider the execution in Figure ?? that highlights two threads i and j executing on a multiprocessor system. Dynamic instructions 1-4 of thread i happen to execute without interacting with instructions running concurrently on thread j (or thread k). We call these instructions, collectively labeled E_{1}, and episode in thread i’s execution. Similarly, instructions 1-3 of thread j execute without interaction and constitute an episode E_{2} for thread j. As soon as a thread’s episode ends, a new episode begins. Thus, every instruction execution is contained in an episode, and episodes cover the entire execution (right side of Figure ??.)

Rerun must solve two subproblems in order to ensure that enough episodic information is recorded to enable deterministic replay of all memory races. First, it must determine when an episode ends, and, by extension, when the next one begins. To appear atomic, an episode E must end when another thread issues a memory reference that conflicts with references made in episode E. Two memory accesses conflict if the reference the same memory block, are from different threads, and at least one is a write. For example, episode E_{1} in Figure ?? ends because threads j accesses the variable F that was previously written (i.e. F is in the write set of E_{1}).

Second, Rerun must order episodes across threads such that episode causal dependencies are respected. An active episode E is causally dependent on an episode F from another thread if E either (a) reads a variable written in F or (b) writes a variable read or written in F. Rerun records episode dependencies using Lamport scalar clocks [?]. This technique guarantees that the timestamp of any episode E executing on thread i has a scalar value that is greater than the timestamp of any episode on which E is dependent and less than the timestamp of any episode dependent on E. In our example, since the episode E_{1} ends with a timestamp of 43, the subsequent episode executing on thread j (E_{2}, which uses block F after thread i. must be assigned a timestamp of (at least) 44.

A replayer (not shown) uses information about episode duration and ordering to reconstruct an execution with the same behavior. If episodes are replayed in timestamp order, then the replayed execution will be logically equivalent to the recorded execution.

2.1.2 Key Definitions

Let an episode E be a contiguous sequence of dynamic instructions executed by one thread without conflicting with other threads via memory. Let thread_{E} denote the thread executing E, references_{E} denote the number of dynamic memory references in E, and timestamp_{E} denote the Lamport scalar clock associated with E. Finally, let R_{E} denote the memory blocks read in E (its read set) and W_{E} denote the memory blocks written in E (its write set).

2.1.3 Establishing Epsiodes

A new episode begins whenever a thread begins execution. When a thread starts a new episode E, ti resets references_{E} to zero and empties the read and write sets, R_{E} and W_{E}. As the thread executes dynamic memory references, it increments references_{E} and adds memory block addresses to R_{E} and W_{E} as appropriate. Whenever a thread terminates an episode, it writes references_{E} into a per-thread log, immediately begins a new episode, and repeats. Thus, a thead’s execution will be logged as a series of episodes without affecting the execution.

[W_{E} ∩ (R_{E} ∪ W_{F}) = ∅] ∧ [R_{E} ∩ W_{F} = ∅]  (1)

Importantly, while a thread must end an episode for conflicts, Rerun may end an episode early for any or no reason, since any subset of an atomic region in an execution is itself atomic (and, unlike transactional memory, programmers do not specify what should be atomic). In Section ??, we will ease implementation cost by ending some episodes early.

2.1.4 Ordering Epsiodes

Episodes must be correctly ordered to enable a faithful deterministic replay. Rerun’s ordering mechanism meets three conditions sufficient for a Lamport Scalar Clock [?] implementation:

1. When an episode E begins, its timestamp_{E} begins with a value one greater than the timestamp of the previous episode executed by thread_{E} (or 0 if episode E is thread_{E}’s first episode).

2. When an episode E adds a block to its read set R_{E} that was most-recently in the write set W_{D} of completed episode D, it sets its timestamp_{E} to maximum[timestamp_{E}, timestamp_{D+1}].

3. When an episode E adds a block to its write set W_{E} that was most-recently in the write set W_{D_{0}} of completed episode D_{0} or in the read set of any episode D_{1}...D_{N}, it sets its timestamp_{E} to maximum[timestamp_{E}, timestamp_{D_{0}} + 1, timestamp_{D_{1}} + 1, ..., timestamp_{D_{N}} + 1].

Finally, when each episode E ends, Rerun logs its timestamp_{E}, along with references_{E}, in a per-thread log. The Lamport clock algorithm ensures that the execution order of all conflicting episodes corresponds to monotonically increasing timestamps. Two episodes can only be assigned the same timestamp if they do not conflict and, thus, can be replayed in any alternative order with affecting replay fidelity.

2.2 Rerun Implementation

Here we develop a Rerun implementation for a system based on a cache-coherent multicore chip.

2.2.1 Base System

Out base system is a multicore chip together with DRAM and I/O. Figure ?? displays the multicore chip, while Table ?? gives key parameters. These include private L1 writeback caches, a shared L2 cache, an MESI directory protocol, and a sequentially consistent memory model. We discuss varying these assumptions in Section 2.2.4.

2.2.2 Rerun Hardware

As Figure ?? depicts, Rerun adds modest hardware state to the base system. To each core, Rerun adds:

• Read and Write Bloom filters, W F and RF, to track the current episode’s write and read sets (e.g., 32 and 128 bytes, respectively),

• A Timestamp Register, T S, to hold the Lamport Clock of the current episode executing on the core (e.g., four bytes), and

• A Memory Reference Counter, REF S, to record the current episode’s references (e.g., two bytes).

To each L2 cache bank, Rerun also adds a “memory” timestamp register, MT S (e.g., four bytes). This register holds the maximum of all timestamps for victimized blocks that map to its bank. A victimized block is one replaced from an L1 cache, and its timestamp is the timestamp of the core at the time of vicitimization.

Finally, coherence response messages - data, acknowledgements, and writebacks - carry logical timestamps. Bookkeeping state, such as a per-core pointer to the end of its log, is not shown.

2.2.3 Rerun Operation

Rerun allows programmers to view logs as per thread, rather than per core, by gracefully handling virtualization events. At a context switch, the OS ends the core’s current episode and writes its REF S and T S state to the log. When the thread is rescheduled, it begins a new episode with reset W F, RF, and REF S, and a timestamp equal to the max of the last logged T S for that thread and the T S of the core on which the thread is rescheduled. Similarly, Rerun can handle paging by ensuring that TLB shootdowns end episodes.

Rerun also ends episodes when implementation resources are about to be exhausted. Ending episodes just before 64K memory references, for example, allows REF S to be logged in two bytes.

2.2.4 Extensibility

Though we have described an implementation of Rerun in terms of a specific base system, Rerun can be applied to other systems, including systems with:

• a TSO Memory Consistency Model

• Out-of-Order cores

• Multithreaded Cores

• Alternate Cache Designs

• Snooping Coherence

• Hardware Transactional Memory

Details of the changes needed to accommodate these alternate architectures can be found in the original paper [?].

2.3 Evaluation

2.3.1 Methods

We evaluate the Rerun recording system using the Wisconsin GEMS [?] full system simulation infrastructure. The simulator configuration matches the baseline shown in Table ?? with the addition of Rerun hardware support. Experiments were run using the Wisconsin Commercial Workload Suite ??.

2.3.2 Rerun Performance

Figure 2.3.2 shows the performance of Rerun on all four commercial workloads. Rerun achieves a log size of about 4 bytes logged per 1000 instructions. Importantly, we notice little variation among the log size of each workload, leading us to believe that Rerun can perform well under a variety of memory access patterns.

We show the relative performance of Rerun in comparison to the prior state of the art in memory race recording in Figure ??. Rerun achieves a log size comparable to the most efficient prior recorder (RTR [?]), but does so with a fraction of the hardware cost (~0.2KB per core vs. 24KB per core). Like RTR, and unlike Strata, Rerun scales well as the number of cores in the system increases, due, in part, to the fact that Rerun and RTR both write thread-local log entries rather than a global entry with a component from each thread.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 ; \begin{matrix}−1 \\ −2 \\ −3 \\ −4 \\ −5 \\ −6 \\ −7 \\ −8 \\ −9 \\ −10 \\ −11 \\ −12 \\ −13 \\ −14 \\ −15 \\ −16 \\ −17 \\ −18 \\ −19 \\ −20 \\ −21 \\ −22 \\ −23 \\ −24 \\ −25 \\ −26 \\ −27 \\ −28 \\ −29 \\ −30 \end{matrix} apache jbb oltp zeus avg