Speculative Execution Across Layers

The ability to write parallel programs is increasingly important to keep up with modern
hardware trends. 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.