XPS: FULL: CCA: Collaborative Research: Automatically Scalable Computation

Harvard University, Cambridge MA

Investigators

Abstract

The era of performance scaling by increasing the performance of individual processors is over, having been replaced by the era of massive parallelism via multiple cores. Amdahl's law tells us that our ability to parallelize computation is limited by the inherently sequential portion of a computation. This unfortunate combination of facts paints a bleak picture for the future of scalable software. This work explores a radical new approach to parallelism with the potential to bypass Amdahl's Law. The approach used involves making informed predictions about computation likely to happen in the future, proactively executing likely computations in parallel with the actual computation, and then "jumping forward in time" if the actual execution stumbles upon any of the predicted computations that have already been completed. This research touches many areas within Computer Science, i.e., architecture, compilers, machine learning, systems, and theory. Additionally, exploiting massively parallel computation will produce immediate returns in multiple scientific fields that rely on computation. The research here provides an approach to speedup on such real-world problems. The approach used in this research views computational execution as moving a system through the enormously high dimensional space represented by its registers and memory of a conventional single-threaded processor. It uses machine learning algorithms to observe execution patterns to make predictions about likely future states of the computation. Based on these predictions, the system launches potentially large numbers of speculative threads to execute from these likely computations, while the actual computation proceeds serially. At strategically chosen points, the main computation queries the speculative executions to determine if any of the completed computation is useful; if it is, the main thread uses the speculative computation to immediately begin execution where the speculative computation left off, achieving a speed-up over the serial execution. This approach has the potential to be infinitely scalable: the more cores, memory, and communication bandwidth available, the greater the potential for performance improvement. The approach also scales across programs -- if the program running today happens upon a state encountered by a program running yesterday, the program can reuse yesterday's computation.