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

三十多年来，每一代计算机都比上一代计算机速度更快。这种指数级的扩展改变了我们沟通、导航、购买和进行科学的方式。最近，单处理器性能的戏剧性增长已经停止，取而代之的是搭载更多处理器的新一代计算机；例如，即使是我们携带的手机也配备了多处理器。编写有效地利用多个处理元素的软件是困难的，而重写几十年积累的软件既困难又昂贵。这项研究采取了一种不同的方法--该项目开发了存储和重复使用计算的方法，而不是将顺序软件转换为并行软件。想象一下，只有当计算机的时间和精力便宜而充足的时候才进行计算，存储计算，然后在计算可能有限或昂贵的时候使用它。所使用的方法包括对未来可能发生的计算做出明智的预测，主动执行与实际计算并行的可能计算，然后如果实际执行到达已经完成的任何预测计算，则在时间上向前跳跃。这项研究涉及计算机科学、体系结构、编译器、机器学习、系统和理论的许多领域。此外，利用大规模并行计算将在依赖计算的多个科学领域产生立竿见影的回报。本研究中使用的方法将计算执行视为在由传统单线程处理器的寄存器和内存表示的极高维空间中移动系统。它使用机器学习算法来观察执行模式，并对计算的未来可能状态做出预测。基于这些预测，系统从这些可能的计算启动潜在的大量推测性线程以执行，而实际计算按顺序进行。在策略选择的点处，主计算查询推测执行，以确定是否有任何已完成的计算有用；如果有用，则主线程使用推测计算立即开始执行，从推测计算停止的地方开始执行，从而实现对串行执行的加速。这种方法具有极强的可扩展性：可用的内核、内存和通信带宽越多，性能改进的潜力就越大。该方法还可以跨程序扩展--如果今天运行的程序遇到昨天运行的程序遇到的状态，则该程序可以重复使用昨天的计算结果。这个项目有可能在它所涉及的许多计算机科学领域的研究中开辟新的天地。

For over thirty years, each generation of computers has been faster than the one that preceded it. This exponential scaling transformed the way we communicate, navigate, purchase, and conduct science. More recently, this dramatic growth in single processor performance has stopped and has been replaced by new generations of computers with more processors on them; for example, even the cell phones we carry have multiple processors in them. Writing software that effectively leverages multiple processing elements is difficult, and rewriting the decades of accumulated software is both difficult and costly. This research takes a different approach -- rather than converting sequential software into parallel software, this project develops ways to store and reuse computation. Imagine computing only when computer time and energy are cheap and plentiful, storing that computation, and then using it later, when computation might be limited or expensive. 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 arrives at any of the predicted computations that have already been completed. This research touches many areas within Computer Science, 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 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 and 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 extremely 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. This project has the potential to break new ground for research in many areas in Computer Science touched by it.