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）2）为本科生提供研究机会，包括来自代表性不足的团体的学生，目的是对系统相关研究引起兴趣的目标。首先，通过在现代计算机系统中合并异质计算设备和互连，将数据划分和同步数据是不平凡的。为了应对这一挑战，研究人员将开发一个运行时系统，该系统提供了分区数据的虚拟化视图。此外，开发了一个编译器工具，以使用用于随机数据访问的统计性能模型来优化跨设备的数据放置。其次，基于抽样的算法中不断变化的计算模式使现有的昂贵数据预处理技术不切实际地加速了每个设备上的稀疏计算。为了克服这一点，研究者将探索基于抽样的方法，以减少数据预处理的开销。第三，基于抽样的算法通常在准确性和效率之间取消权衡。但是，尚不清楚如何系统地探索这些权衡。研究人员将基于投机性执行开发运行时系统，以适应性地调整抽样策略并在准确性和效率之间实现最佳平衡。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响审查标准通过评估来进行评估的。