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

点击翻译按钮获取中文摘要

The era of performance scaling by increasing the performance ofindividual processors is over, having been replaced by the era ofmassive parallelism via multiple cores. Amdahl's law tells us thatour ability to parallelize computation is limited by the inherentlysequential portion of a computation. This unfortunate combinationof facts paints a bleak picture for the future of scalable software.This work explores a radical new approach to parallelism with thepotential to bypass Amdahl's Law. The approach used involves makinginformed predictions about computation likely to happen in thefuture, proactively executing likely computations in parallel withthe actual computation, and then "jumping forward in time" if theactual execution stumbles upon any of the predicted computationsthat have already been completed. This research touches many areaswithin Computer Science, i.e., architecture, compilers, machine learning,systems, and theory. Additionally, exploiting massively parallelcomputation will produce immediate returns in multiple scientificfields that rely on computation. The research here provides anapproach to speedup on such real-world problems.The approach used in this research views computational executionas moving a system through the enormously high dimensional spacerepresented by its registers and memory of a conventional single-threadedprocessor. It uses machine learning algorithms to observe executionpatterns to make predictions about likely future states of thecomputation. Based on these predictions, the system launchespotentially large numbers of speculative threads to execute fromthese likely computations, while the actual computation proceedsserially. At strategically chosen points, the main computationqueries the speculative executions to determine if any of thecompleted computation is useful; if it is, the main thread uses thespeculative computation to immediately begin execution where thespeculative computation left off, achieving a speed-up over theserial execution. This approach has the potential to be infinitelyscalable: the more cores, memory, and communication bandwidthavailable, the greater the potential for performance improvement.The approach also scales across programs -- if the program runningtoday happens upon a state encountered by a program running yesterday,the program can reuse yesterday's computation.