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

职业：异构系统上采样稀疏计算的编译器和运行时支持

• 批准号: 2338144
• 负责人: Peng Jiang
• 金额: $ 54.89万
• 依托单位: University of Iowa
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-06-01 至 2029-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2338144&HistoricalAwards=false
• 关键词: CAREER; Compiler; Runtime; Support; Sampled

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.

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