Search

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.

The processor industry is at an inflection point. In the past,performance was the driving force behind the processor industry. But in thecoming manycore era, improving programmability and reliability of the systemwill be at least as important as improving raw performance. To meet thisvision, this thesis presents a processor feature that assists programmers inunderstanding software failures. Reproducing software failures is asignificant challenge. The problem is severe especially for multi-threadedprograms because the causes of failure can be non-deterministic in nature. Theproposed processor feature continuously logs a program.s execution whilesacrificing very little performance ( 1%). If the program crashes, thedeveloper can use the log to debug the failure by deterministically replayingevery single instruction executed as part of the failed program.s execution.Two key mechanisms enable this deterministic replay feature. One is BugNet, acheckpointing technique, which logs all of the non-deterministic input to athread by logging the values of load instructions. The other is Strata, alogging primitive for recording shared-memory dependencies in a snoop-based ora directory-based shared-memory multi-processor. The former is sufficient foruni-processor systems and the later is required for multi-processor systems.As a proof-of-concept, this thesis presents a software implementation of BugNetreplayer built using the Pin instrumentation tool. To understand the spacerequirements of the BugNet recorder for debugging, this thesis empiricallyquantifies how much of a program.s execution need to be logged and replayed inorder to understand the root cause of a majority of bugs. Finally, todemonstrate the utility of the deterministic replay feature, this thesispresents a software tool built using a deterministic replayer that finds datarace bugs in shared-memory multi-threaded programs and automaticallyprioritizes them. The data race detection tool was built in collaboration withMicrosoft. 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

Transactions have emerged as a promising way to exploit thread-levelparallelism in the presence of shared data. Preventing data-races betweenthreads traditionally implies lock-based synchronization. This comes at therisk of deadlock due to programmer error, and overly-conservative locking willlimit the performance potential of parallel execution. Transactions circumventthese limitations by detecting and serializing data dependencies betweenthreads at runtime without the need for locks. Hardware supported transactionalmemory builds on top of the cache coherence mechanism of shared memorymulti-processors to detect data dependence conflicts between concurrenttransactions. Recent proposals address the need to support the virtualizationof transactions when the finite capacity of the cache is exceeded. Thesetechniques have either a fast commit or abort, but not both. Similarly theysupport either fast conflict detection but are not able to handle swappedprocesses, or slow but complete. In this paper we examine page-basedtransactional memory to provide virtual transactions. We combine transactionbookkeeping with page address translation for fast conflict detection with fastaccess of overflowed transactional data. Our approach provides fast virtualtransaction commit and abort, and conflict detection. We provide quantitativemeasurement of performance, whereas most examinations of virtualizedtransaction techniques provide only theoretical analysis of performance.Pre-2018 CSE ID: CS2005-0848

Future microprocessors will be highly susceptible to transienterrors as the sizes of transistors decrease due to CMOS scaling. Priortechniques advocated full scale structural or temporal redundancy to achievefault tolerance. Though they can provide complete fault coverage, they incursignificant area and/or performance overhead. It is desirable to have amechanism that can provide, incomplete, but still sufficiently high faultcoverage with negligible area and/or performance cost. To achieve this goal, inthis paper, we examine exploiting speculative structures that already exist inmodern processors to provide partial fault coverage. We start by quantifyinghow much the faulty program deviates from the correct program execution interms of control flow, address patterns and store values. We find thisclassification useful to design techniques that can detect a particular form ofdeviation and thereby ultimately detect the transient fault. In order to detecttransient faults, we propose augmenting branch predictors to detect controlflow errors, store sets and L2 cache misses to predict faults that might haveresulted in incorrect address references, and a value predictor to detectincorrect store values.Pre-2018 CSE ID: CS2005-0847

Significant time is spent by companies trying to reproduce and fixbugs. BugNet is a recent architecture proposal that provides architecturesupport for debugging. It focuses on continuously recording information aboutthe program execution which can be communicated back to the developer onencountering an abrupt program termination. Using that information thedeveloper can deterministically replay the program execution and can reproduceand fix the bugs.To enable deterministic replay for multi-threaded programs BugNet assumedhardware support to record the ordering between the memory operations executedacross all the threads. In this paper, we significantly reduce the hardwaresupport required for logging multi-threaded programs by exploiting an importantproperty in BugNet checkpointing scheme that allows one to independently replayeach thread without explicitly logging shared memory dependences. Duringoffline debugging, we independently replay each thread to collect memory tracesfor their execution. Given these traces, we show how one can infer the memoryordering across the threads.In addition, we present a set of optimizations to improve the complexity andfunctionality of the BugNet architecture. Those optimizations includesupporting self-modifying code and reducing the log size in the presence offrequent interrupts.Pre-2018 CSE ID: CS2005-0843

Modern architecture research relies heavily on detailed pipelinesimulation. A time consuming part of building a simulator is correctlyemulating the operating system effects when performing application-levelsimulation. This requires hand coding the emulation of any system effect(e.g., system call, interrupts, DMA transfers) used by the workload. This canbe tedious, especially when having to support running the simulator oncompletely different operating systems or different versions of the operatingsystem. Once a simulator has correctly emulated the system effects, it canalso be costly to maintain this emulation, since the emulation can break withnew versions of the operating system the simulator is running on. In addition,system effect emulation can cause some variance in simulation results. In thispaper we describe an approach that automatically logs operating system effectsto guide architecture simulation of user code. The benefit of this approach isthat (a) we do not have to build or support any infrastructure for emulatingoperating system effects, and (b) the system effect logs provide deterministicsimulation in the presence of these system effects.Pre-2018 CSE ID: CS2005-0840

Significant time is spent by companies trying to reproduce and fixbugs. We recently proposed a hardware logging approach called BugNet to aiddebugging, by capturing the last few million instructions that occurred rightbefore a bug that results in a crash. A developer can then use this log todeterministically replay the recent portion of execution that lead to thecrash. We call this Deterministic Replay Debugging.In this paper, we present a software version of BugNet to be used by developersand quality assurance engineers to efficiently track down bugs. Our softwareapproach does not require any hardware support, and the logs can be used tofind 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 approachonly logs the load values that have changed in order to provide deterministicreplay across system calls, interrupts and DMA transfers. In addition, wepresent implementation details for our deterministic replay debugger. Thisincludes detailed analysis measuring exactly how much execution needs to belogged in order to make sure we have captured the cause of the bug, andquantifying the benefit of using dynamic slicing to aid our deterministicreplay debugger.Pre-2018 CSE ID: CS2005-0839

Bounds checking can be used to significantly increase softwarequality control and security. Bounds checking is the process of keeping trackof the address boundaries for an object, buffer, or array, and checking loadsand stores that access that structure to make sure that they do not strayoutside of the bounds. Run-time bounds checking for C has resulted in highoverheads. This has prevented its inclusion in most released software due toits overhead, and has limited it to being used for just debugging. In thispaper we examine several approaches to reduce this overhead for general purposeC programs. We first examine code generation optimizations to generateefficient code using x86 bounds instruction which incurs about 36% performanceoverhead which is a significant reduction over baseline bounds checkingcompiler which incurs about a 73% overhead. Then we evaluate the performance ofx86 bound instruction on two different processors and examine what the boundchecking overhead should be with an efficient x86 bound implementation.Finally we examine two compiler optimization techniques focused at performingbounds checking only for accesses to strings and at interfaces which aretraditional targets for buffer overflow attacks. For these two approaches, theoverhead incurred is about 20% on an average.Pre-2018 CSE ID: CS2004-0805