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

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.