SHF: Small: K-Way Speculation for Mapping Applications with Dependencies on Modern HPC Systems

现代硬件以大量线程的形式提供并行性。如果应用程序涉及独立的工作组件，则可以将这些组件映射到此类硬件以进行并行执行。然而，当工作组件不是独立的时，通常这样的硬件未被充分利用。用来克服这个问题的一种技术是推测，它涉及猜测某些值或结果，并根据它们将工作分配给线程。如果猜测结果是不正确的，我们需要重新执行工作。 在当前的方法中，考虑（或推测）一个值或结果：即，是否会计算或加载特定值，或者是否存在依赖性。在存在大量线程的情况下，有机会考虑k路推测，例如，推测两个或更多可能的值，或者并行执行一个假设依赖性的线程和另一个假设不存在依赖性的线程。该项目正在开发技术，使k路推测，使用k猜测值，以受益于现代硬件提供的并行多线程。 动机来自于现代硬件具有非常高的并行度的事实，并且与满足于顺序执行相比，在使用这种并行性时具有冗余更好。该项目针对的应用程序类别涵盖科学计算、数据分析、机器学习和优化，因此该项目会影响所有这些领域。该项目还将为推进计算机课程和扩大参与做出贡献。 这个项目建立在两个已证明的结果相关的k路投机。 首先，在某些情况下，人们可能会推测k值，虽然它们都不正确，但使用它们的执行可以用来重建函数。 其次，对于有限状态机（FSM），已经表明k路推测是（1路）推测和枚举的更好替代方案。这两种方法，k路推测和重构以及FSM的k路推测，由于跨不同推测执行的合并的开销，不能扩展到非常大量的核。此外，现有的循环转换方法尊重依赖性，并且不能识别和利用尽管依赖性但可以并行化的循环。探索了以下研究方向。首先，正在开发技术来消除这一瓶颈。第二，现有的框架正在扩展，以考虑嵌套循环，其中一个级别涉及依赖关系。第三，几类算法涉及推测，并且是从k路推测中受益的候选者，可能具有重建，并且这正在被探索。最后，如果对应于循环体的功能没有一个封闭形式的组合，则正在检查对推测值的执行是否仍然能够在一定程度上代表该功能。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern hardware provides parallelism in the form of a large number of threads. If an application involves independent work components, these components can be mapped to such hardware for parallel execution. However, when the work components are not independent, often such hardware is under-utilized. One technique used to overcome this problem is speculation – which involves guessing certain values or outcomes and assigning work to threads based on them. If the guess turns out to be incorrect, we need to re-execute the work. In current approaches one value or outcome is considered (or speculated): i.e., whether a specific value will be computed or loaded, or whether there will be dependence or not. With presence of massive number of threads, there is an opportunity to consider k-way speculation, e.g., speculating two or more likely values, or in parallel executing one thread that assumes dependence and another that assumes there is no dependence. This project is developing techniques enabling k-way speculation, using k guessed values to benefit from parallelism provided by modern hardware with multiple threads. The motivation arrives from the fact that modern hardware has a very high degree of parallelism, and it is better to have redundancy in using this parallelism, as compared to settling for a sequential execution. The class of applications this project targets span across scientific computing, data analytics, machine learning, and optimization, and thus this project impacts all of these areas. This project will also make contributions towards advancing curriculum and broadening participation in computing. This project builds on two demonstrated results relevant to k-way speculation. First, in certain cases, one might speculate k values, and while none of them may be correct, execution using them can be used to reconstruct the function. Second, for Finite State Machines (FSMs), it has been shown that k-way speculation is a better alternative to both (1-way) speculation and enumeration. Both approaches, k-way speculation and reconstruction and k-way speculation for FSMs, are not scalable to a very large number of cores because of the overhead of merging across different speculated executions. In addition, existing loop-transformation methods respect dependencies and cannot identify and exploit loops that can be parallelized despite dependencies. The following research directions are explored. First, techniques are being developed to remove this bottleneck. Second, the existing framework is being extended to consider nested loops, where one of the levels involves dependencies. Third, several classes of algorithms involve speculation and are candidates for benefiting from k-way speculation, possibly with reconstruction, and this is being explored. Finally, it is being examined if the function corresponding to the loop body does not have a closed-form combination, can the execution on speculated values nevertheless represent the function to a certain level of precision.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.