Precise-Restartable Execution of Parallel Programs

Abstract

Precise interruptibility enabled a broad range of system capabilities and microarchitectural techniques in instruction-level parallel processors. Arguably, it was key to the success of computers. Multiprocessors lack a similarly-capable feature. As parallelism evolves from instructions to threads or tasks, we envision a similar feature in future multiprocessors.

We define precise restartability of parallel programs, analogous to precise interruptibility. We present a model to achieve instruction-level precise restart of parallel programs executing on multiple processors. The model permits trade-offs between overheads, complexity, and performance based on the expected operating conditions. We present a prototype of the model. Its application to fault-recovery is evaluated on a stock multiprocessor system. Analytical and experimental results showed that the prototype significantly outperformed the traditional approaches, by a factor as high as the number of processors in the system.