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

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

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.