Derek Gordon Murray
In computer science, data-dependent control flow is the fundamental concept that enables a machine to change its behaviour on the basis of intermediate results. This ability increases the computational power of a machine, because it enables the machine to execute iterative or recursive algorithms. In such algorithms, the amount of work is unbounded a priori, and must be determined by evaluating a fixpoint condition on successive intermediate results. For example, in the von Neumann architecture—upon which almost all modern computers are based—these algorithms can be programmed using a conditional branch instruction.
A distributed execution engine is a system that runs on a network of computers, and provides the illusion of a single, reliable machine that provides a large aggregate amount of computational and I/O performance. Although each individual computer in these systems is a von Neumann machine capable of data-dependent control flow, the effective computational power of a distributed execution engine is determined by the expressiveness of the execution model that describes distributed computations.
In this dissertation, I present a new execution model for distributed execution engines that supports data-dependent control flow. The model is based on dynamic task graphs, in which each vertex is a sequential computation that may decide, on the basis of its input, to spawn additional computation and hence rewrite the graph. I have developed a prototype system that executes dynamic task graphs, and discuss details of its design and implementation, including the fault tolerance mechanisms that maintain reliability throughout dynamic task graph execution. Dynamic task graphs support a variety of programming models, and I introduce a model based on multiple distributed threads of execution that synchronise deterministically using futures and continuations. To demonstrate the practicality of dynamic task graphs, I have evaluated its performance on several microbenchmarks and realistic applications, and it achieves performance that is similar to or better than an existing, less-powerful execution engine.