Speculative Execution Across Layers.

To achieve good performance on modern hardware, software must be designed with a high degree of parallelism. New advancements in processor design and manufacturing have produced chips that offer greater computation capacity, but they do this primarily by providing more processing cores rather than by greatly improving per-core performance. Speculative execution is a technique that can be used improve the parallelism of sequential programs by predicting the dependencies between tasks, allowing a later task to run concurrently with an earlier one. Software systems are composed of many different cooperating layers: CPU, virtual machine, operating system, language runtime, and program code. The effects of speculative execution are traditionally confined to a single layer. Code running at higher layers is unaware that its execution is speculative, and code running at lower layers never observes any speculative behavior or output from higher layers. This thesis explores the benefits of letting speculative executions be visible across the many layers of a software system. Components of the system can be aware of speculative computations and, with controlled access rather than isolation, can be designed to handle speculative state and effects correctly. With cooperation among layers, new opportunities for parallelization appear. This dissertation shows how visible speculations across layers can be applied to application development, network protocols, and dynamic application analysis. I develop a new programming model for applications that separates the mechanism used to implement safety from the policy that describes how to control an individual speculation. The operating system implements the mechanism, leaving each application to describe its own custom policy. I then describe a new agreement protocol for Byzantine fault-tolerant services that is optimized for client applications capable of executing speculatively. Finally, I develop an algorithm for parallelizing data race detection by expressing speculative parallelism and handling it in the algorithm itself.PHDComputer Science & EngineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/93930/1/bwester_1.pd