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

通过提高单个处理器的性能来扩展性能的时代已经结束，取而代之的是通过多核实现大规模并行的时代。阿姆达尔定律告诉我们，我们将计算并行化的能力受到计算固有的顺序部分的限制。这一不幸的事实组合为可伸缩软件的未来描绘了一幅黯淡的图景。这项工作探索了一种全新的并行性方法，有可能绕过Amdahl定律。使用的方法包括对未来可能发生的计算做出知情预测，主动执行可能的计算与实际计算并行，然后如果实际执行碰巧发现任何已经完成的预测计算，则在时间上向前跳跃。这项研究涉及到计算机科学的许多领域，即体系结构、编译器、机器学习、系统和理论。此外，利用大规模并行计算将在依赖计算的多个科学领域产生立竿见影的回报。这项研究提供了一种加速这类实际问题的方法。这项研究中使用的方法将计算执行视为将系统移动到由其寄存器和传统单线程处理器的内存所表示的极高维空间中。它使用机器学习算法来观察执行模式，以预测计算机未来可能的状态。基于这些预测，系统从这些可能的计算中启动潜在的大量推测性线程来执行，而实际的计算是按顺序进行的。在策略选择的点上，主计算查询推测执行，以确定完成的计算中是否有任何计算有用；如果有用，主线程使用推测计算立即开始执行，从推测计算停止的地方开始执行，从而实现比顺序执行更快的速度。这种方法具有无限可伸缩性的潜力：可用的内核、内存和通信带宽越多，性能改进的潜力就越大。这种方法还可以跨程序扩展--如果今天运行的程序遇到昨天运行的程序遇到的状态，程序可以重复使用昨天的计算。

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.