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.