The relentless execution model for task-uncoordinated parallel computation in distributed memory environments

This thesis demonstrates the feasibility of executing tightly-coupled parallel algorithms in a task-uncoordinated fashion, where that tasks do not use any explicit interprocess communication (e.g., messages, shared memory, semaphores, etc.). The model described in this thesis achieves this through the use of dataflow program representation, and the use of a distributed, eventually-consistent key/value store to memorize intermediate values and their associated state. In addition to describing a model which allows for task-uncoordinated parallel execution, the work in this thesis also details several different means for describing task-uncoordinated parallel algorithms, including a new domain-specific language called StenSAL which allows for simple description of stencil-based scientific applications. This thesis also details experiments, performed on the Stampede supercomputer in Austin, Texas, which demonstrate the ability of task-uncoordinated parallel execution models to scale efficiently in both shared memory and distributed memory environments. The work in this thesis demonstrates, through experiments performed on Stampede, that task-uncoordinated parallel execution models can provide both resiliency and elasticity when executing tightly-coupled parallel algorithms, which cannot be achieved using existing established execution models. This thesis also describes means of mechanically optimizing the fine-grained dataflow tasks inherent to the described model, allowing for the use of wide vector units and more efficient memory and register access.