CAREER: An Algorithm and System Co-Designed Framework for Graph Sampling and Random Walk on GPUs

职业生涯：用于 GPU 上的图形采样和随机游走的算法和系统协同设计框架

• 批准号: 2326141
• 负责人: Hang Liu
• 金额: $ 58.4万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-01-01 至 2026-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2326141&HistoricalAwards=false
• 关键词: CAREER; Algorithm; System; Co; Designed

Graph analytics is one of the key technologies to address the grand challenges of our time, such as understanding the spread of pandemics, designing extremely large-scale integrated circuits and uncovering software vulnerabilities among many others. However, as the size of the graph continues to grow, learning, mining and computing such gigantic graphs become ineffective, impractical, and potentially dire. Fortunately, Graph Sampling and Random Walk can dramatically reduce the size of the original graphs, while still capturing the desired properties for downstream graph analytics tasks. But a comprehensive system that can perform graph sampling and random walk on real-world trillion-edge graphs at an acceptable speed is absent. This research pioneers the effort of uniting various graph sampling and random walk algorithms behind a user-friendly framework that can take advantage of world-class Graphics Processing Unit (GPU) computing facilities, including the future exascale ones, to rapidly handle trillion-edge graphs. This project contributes to the U.S. national goal of increasing participation in science and engineering, which is crucial to America’s success in addressing global challenges, building a stronger and more diversified workforce, and meeting the needs of the global innovation economy. This project produces a high-performance software library that serves as a foundational tool for fellow science and engineering practitioners from academia, national laboratories and industry. With a commitment to helping K-12, undergraduate, female, and Underrepresented Minority (URM) populations in the Science, Technology, Engineering, and Mathematics (STEM) field through the interesting investment and rewarding education plan, this project lays out a comprehensive road map to prepare the next-generation high-performance graph analytics professional workers and researchers. This project revamps and creates core courses in both graduate and undergraduate levels for the PI's home department. To benefit the society at large, this project disseminates the project data, software, and publications to the broader research community at http://personal.stevens.edu/~hliu77/gsrw.html.The overarching goal of this research is to make graph sampling and random walk fast, scalable and user-friendly. Towards that end, this career proposal advocates algorithm and system co-designed researches. First, this research introduces novel update and construction designs for transition probability of various major Monte Carlo methods that are essential for fast sampling. Second, to fully unleash the potential of GPUs, this project formulates the key primitive into problems that can take advantage of general, and reserved tensor and ray tracing cores on GPUs. Third, based upon the asynchronous processing nature of graph sampling and random walk, this research exploits Remote Direct Memory Access (RDMA)-assisted task and partition adaptive scheduling mechanism to reduce the data transfers for scalable trillion-edge graph sampling and random walk. Last but not the least, this career research delivers a bias-centric framework, which offers end users expressiveness to program not only a variety of exiting GSRW algorithms but also future ones, and simplicity by hiding the aforementioned advanced optimization techniques.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.

Graph Analytics是应对我们这个时代巨大挑战的关键技术之一，例如了解大流行技术的传播，设计极大的集成电路和发现软件漏洞等。但是，随着图的大小不断增长，学习，采矿和计算，此类巨大的图形变得无效，不切实际且潜在的可怕。幸运的是，图形采样和随机步行可以大大减少原始图的大小，同时仍捕获下游图分析任务所需的属性。但是，可以以可接受的速度在现实世界中执行图形采样和随机步行的综合系统。这项研究开创了将各种图形采样和随机步行算法团结在一个用户友好型框架背后的努力，该框架可以利用世界一流的图形处理单元（GPU）计算设施，包括未来的Exascale，以快速处理数万亿架图。该项目有助于美国全国的目标，即增加对科学和工程的参与，这对于美国在应对全球挑战，建立更强大，更多元化的劳动力以及满足全球创新经济需求方面的成功至关重要。该项目生产了一个高性能的软件库，该库是学术界，国家实验室和行业的科学和工程从业人员的基础工具。通过致力于帮助K-12，本科，女性和代表性不足的少数族裔（URM）人口在科学，技术，工程和数学（STEM）中通过有趣的投资和奖励教育计划，因此该项目列出了全面的路线图，以准备下一代高性能图形分析专业人士和研究者，以准备下一代高性能图形。该项目在PI的内政部为研究生和本科级别的研究生和本科级别改造并创建了核心课程。为了使整个社会受益，该项目将项目数据，软件和出版物传播给了更广泛的研究社区，网址为http://personal.stevens.edu/~hliu77/gsrw.html。此研究的总体目标是使图形采样和随机步入快速，可扩展，可扩展和用户友好。为此，这项职业建议倡导算法和系统共同设计的研究。首先，这项研究介绍了新颖的更新和构造设计，用于对快速采样至关重要的各种主要蒙特卡洛方法的过渡概率。其次，为了完全释放GPU的潜力，该项目将关键原始性提出为可以利用GPU上的一般张量和射线追踪核心的问题。第三，基于图形采样和随机步行的异步处理性质，这项研究利用了远程直接内存访问（RDMA）辅助任务和分区自适应调度机制，以减少可扩展的数万亿个边缘图形采样和随机步行的数据传输。最后但并非最不重要的一点是，这项职业研究提供了一个以偏见为中心的框架，该框架为最终用户提供了表达能力，不仅可以对各种退出GSRW算法进行编程，而且还提供了未来的框架，并且通过隐藏了先前提到的高级优化技术来简单。该奖项反映了NSF的法定任务，并通过评估基金会的智力效果来表现出珍贵的支持。