The processor industry is at an inflection point. In the past, performance was the driving force behind the processor industry. But in the coming manycore era, improving programmability and reliability of the system will be at least as important as improving raw performance. To meet this vision, this thesis presents a processor feature that assists programmers in understanding software failures.

Reproducing software failures is a significant challenge. The problem is severe especially for multi-threaded programs because the causes of failure can be non-deterministic in nature. The proposed processor feature continuously logs a program.s execution while sacrificing very little performance ( 1%). If the program crashes, the developer can use the log to debug the failure by deterministically replaying every single instruction executed as part of the failed program.s execution. Two key mechanisms enable this deterministic replay feature. One is BugNet, a checkpointing technique, which logs all of the non-deterministic input to a thread by logging the values of load instructions. The other is Strata, a logging primitive for recording shared-memory dependencies in a snoop-based or a directory-based shared-memory multi-processor. The former is sufficient for uni-processor systems and the later is required for multi-processor systems. As a proof-of-concept, this thesis presents a software implementation of BugNet replayer built using the Pin instrumentation tool.

To understand the space requirements of the BugNet recorder for debugging, this thesis empirically quantifies how much of a program.s execution need to be logged and replayed in order to understand the root cause of a majority of bugs. Finally, to demonstrate the utility of the deterministic replay feature, this thesis presents a software tool built using a deterministic replayer that finds data race bugs in shared-memory multi-threaded programs and automatically prioritizes them. The data race detection tool was built in collaboration with Microsoft. It has been used to find and fix data race bugs in production code, including Windows Vista and Internet Explorer.

Pre-2018 CSE ID: CS2007-0906

The processor industry is at an inflection point. In the past, performance was the driving force behind the processor industry. But in the coming many-core era, improving programmability and reliability of the system will be at least as important as improving raw performance. To meet this vision, this thesis presents a processor feature that assists programmers in understanding software failures. Reproducing software failures is a significant challenge. The problem is severe especially for multi-threaded programs because the causes of failure can be non-deterministic in nature. The proposed processor feature continuously logs a program's execution while sacrificing very little performance (̃1\ %). If the program crashes, the developer can use the log to debug the failure by deterministically replaying every single instruction executed as part of the failed program's execution. Two key mechanisms enable this deterministic replay feature. One is BugNet, a checkpointing technique, which logs all of the non- deterministic input to a thread by logging the values of load instructions. The other is Strata, a logging primitive for recording shared-memory dependencies in a snoop-based or a directory-based shared-memory multi- processor. The former is sufficient for uni-processor systems and the later is required for multi-processor systems. As a proof-of-concept, this thesis presents a software implementation of BugNet replayer built using the Pin instrumentation tool. To understand the space requirements of the BugNet recorder for debugging, this thesis empirically quantifies how much of a program's execution need to be logged and replayed in order to understand the root cause of a majority of bugs. Finally, to demonstrate the utility of the deterministic replay feature, this thesis presents a software tool built using a deterministic replayer that finds data race bugs in shared-memory multi-threaded programs and automatically prioritizes them. The data race detection tool was built in collaboration with Microsoft. It has been used to find and fix data race bugs in production code, including Windows Vista and Internet Explorer

Significant time is spent by companies trying to reproduce and fix bugs. We recently proposed a hardware logging approach called BugNet to aid debugging, by capturing the last few million instructions that occurred right before a bug that results in a crash. A developer can then use this log to deterministically replay the recent portion of execution that lead to the crash. We call this Deterministic Replay Debugging. In this paper, we present a software version of BugNet to be used by developers and quality assurance engineers to efficiently track down bugs. Our software approach does not require any hardware support, and the logs can be used to find bugs that result in a crash as well as those that cause wrong answers, instead of only focusing on bugs that cause crashes as in BugNet. The approach only logs the load values that have changed in order to provide deterministic replay across system calls, interrupts and DMA transfers. In addition, we present implementation details for our deterministic replay debugger. This includes detailed analysis measuring exactly how much execution needs to be logged in order to make sure we have captured the cause of the bug, and quantifying the benefit of using dynamic slicing to aid our deterministic replay debugger.

Pre-2018 CSE ID: CS2005-0839

Significant time is spent by companies trying to reproduce and fix bugs. BugNet is a recent architecture proposal that provides architecture support for debugging. It focuses on continuously recording information about the program execution which can be communicated back to the developer on encountering an abrupt program termination. Using that information the developer can deterministically replay the program execution and can reproduce and fix the bugs. To enable deterministic replay for multi-threaded programs BugNet assumed hardware support to record the ordering between the memory operations executed across all the threads. In this paper, we significantly reduce the hardware support required for logging multi-threaded programs by exploiting an important property in BugNet checkpointing scheme that allows one to independently replay each thread without explicitly logging shared memory dependences. During offline debugging, we independently replay each thread to collect memory traces for their execution. Given these traces, we show how one can infer the memory ordering across the threads. In addition, we present a set of optimizations to improve the complexity and functionality of the BugNet architecture. Those optimizations include supporting self-modifying code and reducing the log size in the presence of frequent interrupts.

Pre-2018 CSE ID: CS2005-0843

Bounds checking can be used to significantly increase software quality control and security. Bounds checking is the process of keeping track of the address boundaries for an object, buffer, or array, and checking loads and stores that access that structure to make sure that they do not stray outside of the bounds. Run-time bounds checking for C has resulted in high overheads. This has prevented its inclusion in most released software due to its overhead, and has limited it to being used for just debugging. In this paper we examine several approaches to reduce this overhead for general purpose C programs. We first examine code generation optimizations to generate efficient code using x86 bounds instruction which incurs about 36% performance overhead which is a significant reduction over baseline bounds checking compiler which incurs about a 73% overhead. Then we evaluate the performance of x86 bound instruction on two different processors and examine what the bound checking overhead should be with an efficient x86 bound implementation. Finally we examine two compiler optimization techniques focused at performing bounds checking only for accesses to strings and at interfaces which are traditional targets for buffer overflow attacks. For these two approaches, the overhead incurred is about 20% on an average.

Pre-2018 CSE ID: CS2004-0805

Future microprocessors will be highly susceptible to transient errors as the sizes of transistors decrease due to CMOS scaling. Prior techniques advocated full scale structural or temporal redundancy to achieve fault tolerance. Though they can provide complete fault coverage, they incur significant area and/or performance overhead. It is desirable to have a mechanism that can provide, incomplete, but still sufficiently high fault coverage with negligible area and/or performance cost. To achieve this goal, in this paper, we examine exploiting speculative structures that already exist in modern processors to provide partial fault coverage. We start by quantifying how much the faulty program deviates from the correct program execution in terms of control flow, address patterns and store values. We find this classification useful to design techniques that can detect a particular form of deviation and thereby ultimately detect the transient fault. In order to detect transient faults, we propose augmenting branch predictors to detect control flow errors, store sets and L2 cache misses to predict faults that might have resulted in incorrect address references, and a value predictor to detect incorrect store values.

Pre-2018 CSE ID: CS2005-0847

The most intuitive memory model for shared-memory multi-threaded programming is sequential consistency (SC), but it disallows the use of many compiler and hardware optimizations and thus affects performance. Data-race-free (DRF) models, such as the C++11 memory model, guarantee SC execution for data-race-free programs. But these models provide no guarantee at all for racy programs, compromising the safety and debuggability of such programs. To address the safety issue, the Java memory model, which is also based on the DRF model, provides a weak semantics for racy executions. However, this semantics is subtle and complex, making it difficult for programmers to reason about their programs and for compiler writers to ensure the correctness of compiler optimizations. We present the drf x memory model, which is simple for programmers to understand and use while still supporting many common optimizations. We introduce a memory model (MM) exception that can be signaled to halt execution. If a program executes without throwing this exception, then drf x guarantees that the execution is SC. If a program throws an MM exception during an execution, then drf x guarantees that the program has a data race. We observe that SC violations can be detected in hardware through a lightweight form of conflict detection. Furthermore, our model safely allows aggressive compiler and hardware optimizations within compiler-designated program regions. We formalize our memory model, prove several properties of this model, describe a compiler and hardware design suitable for drf x , and evaluate the performance overhead due to our compiler and hardware requirements.

Modern architecture research relies heavily on detailed pipeline simulation. A time consuming part of building a simulator is correctly emulating the operating system effects when performing application-level simulation. This requires hand coding the emulation of any system effect (e.g., system call, interrupts, DMA transfers) used by the workload. This can be tedious, especially when having to support running the simulator on completely different operating systems or different versions of the operating system. Once a simulator has correctly emulated the system effects, it can also be costly to maintain this emulation, since the emulation can break with new versions of the operating system the simulator is running on. In addition, system effect emulation can cause some variance in simulation results. In this paper we describe an approach that automatically logs operating system effects to guide architecture simulation of user code. The benefit of this approach is that (a) we do not have to build or support any infrastructure for emulating operating system effects, and (b) the system effect logs provide deterministic simulation in the presence of these system effects.

Pre-2018 CSE ID: CS2005-0840

Transactions have emerged as a promising way to exploit thread-level parallelism in the presence of shared data. Preventing data-races between threads traditionally implies lock-based synchronization. This comes at the risk of deadlock due to programmer error, and overly-conservative locking will limit the performance potential of parallel execution. Transactions circumvent these limitations by detecting and serializing data dependencies between threads at runtime without the need for locks. Hardware supported transactional memory builds on top of the cache coherence mechanism of shared memory multi-processors to detect data dependence conflicts between concurrent transactions. Recent proposals address the need to support the virtualization of transactions when the finite capacity of the cache is exceeded. These techniques have either a fast commit or abort, but not both. Similarly they support either fast conflict detection but are not able to handle swapped processes, or slow but complete. In this paper we examine page-based transactional memory to provide virtual transactions. We combine transaction bookkeeping with page address translation for fast conflict detection with fast access of overflowed transactional data. Our approach provides fast virtual transaction commit and abort, and conflict detection. We provide quantitative measurement of performance, whereas most examinations of virtualized transaction techniques provide only theoretical analysis of performance.

Pre-2018 CSE ID: CS2005-0848