CAREER: Compiler and Runtime Support for Sampled Sparse Computations on Heterogeneous Systems

基于采样的算法在数据密集型应用中越来越受欢迎，因为它们有助于降低计算成本。然而，由于随机内存访问和计算模式，它们在硬件上的效率受到限制。本研究旨在通过开发一套编译器和运行时工具来解决这个问题。与之前特定于某些应用程序的方法不同，该项目的新颖之处包括：1)一个高级编程接口，允许用户为不同类型的采样稀疏计算指定数据管理和预处理，以及2)利用硬件和随机算法特性来提高性能的技术。该项目的影响在于它能够简化基于采样的算法的实现，提高许多科学计算和大数据应用的性能，并增强我们大规模解决现实问题的能力。该项目还将为教育和改善多样性做出一些贡献，包括：1)加强该机构的操作系统和高性能计算课程的课程项目和实验平台，以及2)为本科生提供研究机会，包括来自代表性不足群体的学生，目的是培养对系统相关研究的兴趣。这项工作将解决三个主要挑战。首先，随着现代计算机系统中异构计算设备和互连的结合，在多个设备之间划分和同步数据是很重要的。为了应对这一挑战，研究者将开发一个运行时系统，提供分区数据的虚拟化视图。此外，还开发了一个编译器工具，使用随机数据访问的统计性能模型来优化跨设备的数据放置。其次，基于采样的算法中不断变化的计算模式使得现有昂贵的数据预处理技术无法在每个设备上加速稀疏计算。为了克服这一点，研究者将探索基于采样的方法来减少数据预处理的开销。第三，基于采样的算法通常暴露了精度和效率之间的权衡。然而，目前尚不清楚如何系统地探索这些权衡。研究者将开发一个基于推测执行的运行时系统，以自适应地调整采样策略，实现准确性和效率之间的最佳平衡。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Sampling-based algorithms are gaining popularity in data-intensive applications because they help reduce computation costs. However, their efficiency on hardware is limited due to random memory access and computation patterns. This research aims to address this issue by developing a suite of compiler and runtime tools. Unlike previous approaches that were specific to certain applications, the project's novelties include: 1) a high-level programming interface that allows users to specify data management and preprocessing for different types of sampled sparse computation, and 2) techniques that exploit both hardware and randomized algorithm features to improve performance. The impact of the project lies in its ability to simplify the implementation of sampling-based algorithms, improve the performance of many scientific computing and big data applications, and enhance our capacity to solve real-world problems at a large scale. This project will also make several contributions towards education and improving diversity, including: 1) enhancing course projects and experimental platforms for the operating systems and high-performance computing courses at the institution, and 2) providing research opportunities to undergraduate students, including students from the underrepresented groups, with the goal of creating interest in system-related research.There are three main challenges that this work will address. First, with the incorporation of heterogeneous computing devices and interconnects in modern computer systems, it is nontrivial to divide and synchronize data across multiple devices. To address this challenge, the investigator will develop a runtime system that provides a virtualized view of the partitioned data. Additionally, a compiler tool is developed to optimize data placement across devices using a statistical performance model for random data accesses. Second, the constantly changing computation patterns in sampling-based algorithms make existing expensive data preprocessing techniques impractical for accelerating sparse computation on each device. To overcome this, the investigator will explore sampling-based methods to reduce the overhead of data preprocessing. Third, sampling-based algorithms generally expose tradeoffs between accuracy and efficiency. However, it is not clear how to systematically explore these tradeoffs. The investigator will develop a runtime system based on speculative execution to adaptively adjust the sampling strategies and achieve the optimal balance between accuracy and efficiency.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.