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

图形分析是解决我们这个时代重大挑战的关键技术之一，例如了解流行病的传播，设计超大规模集成电路和发现软件漏洞等。然而，随着图的大小不断增长，学习、挖掘和计算这种巨大的图变得无效、不切实际，甚至可能是可怕的。幸运的是，图采样和随机漫步可以显著减少原始图的大小，同时仍然捕获下游图分析任务所需的属性。但是，一个能够以可接受的速度在现实世界的万亿边图上执行图采样和随机漫步的综合系统是不存在的。这项研究开创了将各种图形采样和随机漫步算法联合在一个用户友好的框架后面的努力，该框架可以利用世界级的图形处理单元（GPU）计算设施，包括未来的百亿亿次，来快速处理万亿边缘图。该项目有助于实现美国提高科学和工程参与度的国家目标，这对美国成功应对全球挑战、建立一支更强大、更多样化的劳动力队伍以及满足全球创新经济的需求至关重要。这个项目产生了一个高性能的软件库，作为来自学术界、国家实验室和工业的科学和工程实践者的基础工具。该项目致力于通过有趣的投资和有益的教育计划，帮助科学、技术、工程和数学（STEM）领域的K-12、本科生、女性和代表性不足的少数族裔（URM）人口，为培养下一代高性能图形分析专业工作者和研究人员制定了全面的路线图。该项目为PI的家庭部门改造和创建了研究生和本科生的核心课程。为了使整个社会受益，该项目将项目数据，软件和出版物传播到更广泛的研究社区http://personal.stevens.edu/~hliu77/gsrw.html.The，该研究的总体目标是使图形采样和随机漫步快速，可扩展和用户友好。为此，本职业建议提倡算法与系统协同设计研究。首先，本研究介绍了各种主要蒙特卡罗方法的转移概率的更新和构造设计，这些方法对快速采样至关重要。其次，为了充分释放gpu的潜力，本项目将关键原语制定为可以利用gpu上通用的、预留的张量核和光线追踪核的问题。第三，基于图采样和随机漫步的异步处理特性，利用远程直接内存访问（RDMA）辅助任务和分区自适应调度机制，减少可扩展万亿边图采样和随机漫步的数据传输。最后但并非最不重要的是，这项职业研究提供了一个以偏差为中心的框架，它为最终用户提供了编程的表现力，不仅可以编写各种现有的GSRW算法，还可以编写未来的算法，并且通过隐藏上述高级优化技术实现了简单性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.