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

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

基本信息

  • 批准号:
    2326141
  • 负责人:
  • 金额:
    $ 58.4万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2023
  • 资助国家:
    美国
  • 起止时间:
    2023-01-01 至 2026-02-28
  • 项目状态:
    未结题

项目摘要

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 Sampling和Random Walk可以大大减少原始图的大小,同时仍然可以捕获下游图分析任务所需的属性。但是,一个全面的系统,可以执行图采样和随机游走在现实世界中的万亿边图在一个可接受的速度是缺席。这项研究开创了将各种图形采样和随机游走算法统一在一个用户友好的框架之后的努力,该框架可以利用世界一流的图形处理单元(GPU)计算设施,包括未来的exascale计算设施,以快速处理万亿边图形。该项目有助于实现美国增加科学和工程参与的国家目标,这对于美国成功应对全球挑战、建立更强大、更多元化的劳动力队伍以及满足全球创新经济的需求至关重要。该项目产生了一个高性能的软件库,作为来自学术界,国家实验室和工业界的科学和工程从业人员的基础工具。通过有趣的投资和奖励教育计划,致力于帮助K-12,本科生,女性和代表性不足的少数民族(URM)人口在科学,技术,工程和数学(STEM)领域,该项目制定了一个全面的路线图,为下一代高性能图形分析专业工作者和研究人员做好准备。这个项目改造和创建核心课程,在研究生和本科水平的PI的家庭部门。为了使整个社会受益,该项目将项目数据,软件和出版物传播到更广泛的研究社区http://personal.stevens.edu/~hliu77/gsrw.html.The本研究的首要目标是使图形采样和随机游走快速,可扩展和用户友好。为此,这个职业建议倡导算法和系统共同设计的研究。首先,本研究介绍了新的更新和建设设计的各种主要的Monte Carlo方法的转移概率是必不可少的快速采样。其次,为了充分释放GPU的潜力,该项目将关键原语公式化为可以利用GPU上的通用和保留张量和光线跟踪核心的问题。第三,基于图采样和随机游走的异步处理特性,本研究利用远程直接内存访问(RDMA)辅助的任务和分区自适应调度机制,以减少可扩展的万亿边图采样和随机游走的数据传输。最后但并非最不重要的是,这项职业研究提供了一个以偏置为中心的框架,它为最终用户提供了表现力,不仅可以编程各种现有的GSRW算法,还可以编程未来的算法,并且通过隐藏上述先进的优化技术来实现简单性。该奖项反映了NSF的法定使命,并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

项目成果

期刊论文数量(1)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Hang Liu其他文献

Dividend tax and capital structure: Evidence from China
股息税和资本结构:来自中国的证据
  • DOI:
    10.1080/21697213.2015.1067854
  • 发表时间:
    2015-07
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Hang Liu;Yixin Zhang;Shenghao Gao
  • 通讯作者:
    Shenghao Gao
A kW-level integrated propulsion system for UAV powered by PEMFC with inclined cathode flow structure design
倾斜阴极流结构设计的质子交换膜燃料电池千瓦级无人机综合推进系统
  • DOI:
    10.1016/j.apenergy.2022.120222
  • 发表时间:
    2022-12
  • 期刊:
  • 影响因子:
    11.2
  • 作者:
    Kehan Zhou;Zhiwei Liu;Xin Zhang;Hang Liu;Nan Meng;Jianmei Huang;Mingjing Qi;Xizhen Song;Xiaojun Yan
  • 通讯作者:
    Xiaojun Yan
Bombyx mori nucleopolyhedrovirus F-like protein Bm14 is a type I integral membrane protein that facilitates ODV attachment to the midgut epithelial cells
家蚕核多角体病毒 F 样蛋白 Bm14 是一种 I 型整合膜蛋白,可促进 ODV 附着于中肠上皮细胞
  • DOI:
    10.1099/jgv.0.001389
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    3.8
  • 作者:
    Weifan Xu;Xiangshuo Kong;Hang Liu;Haiping Wang;Xiaofeng Wu
  • 通讯作者:
    Xiaofeng Wu
Reducing violation behaviors of pedestrians considering group interests of travelers at signalized crosswalk
考虑行人群体利益在信号人行横道处减少行人违规行为
Energy Efficient Two-stage Cooperative Multicast Based on Device to DeviceTransmissions: Effect of User Density
基于设备到设备传输的节能两级协作组播:用户密度的影响

Hang Liu的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Hang Liu', 18)}}的其他基金

CRII: SHF: Expediting Subgraph Matching on GPUs
CRII:SHF:加快 GPU 上的子图匹配
  • 批准号:
    2331536
  • 财政年份:
    2023
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Standard Grant
CAREER: Processing Intrinsically Conductive Polymers for Fibers via Side-by-Side Spinning
职业:通过并列纺丝加工本质导电聚合物纤维
  • 批准号:
    2145468
  • 财政年份:
    2022
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Standard Grant
CAREER: An Algorithm and System Co-Designed Framework for Graph Sampling and Random Walk on GPUs
职业生涯:用于 GPU 上的图形采样和随机游走的算法和系统协同设计框架
  • 批准号:
    2046102
  • 财政年份:
    2021
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Continuing Grant
CRII: SHF: Expediting Subgraph Matching on GPUs
CRII:SHF:加快 GPU 上的子图匹配
  • 批准号:
    2000722
  • 财政年份:
    2019
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Standard Grant
CRII: SHF: Expediting Subgraph Matching on GPUs
CRII:SHF:加快 GPU 上的子图匹配
  • 批准号:
    1850274
  • 财政年份:
    2019
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Standard Grant
CNS Core: Small: Collaborative Research: A Stochastic Resource Allocation and Task Assignment Framework for Mobile Edge Computing
CNS 核心:小型:协作研究:移动边缘计算的随机资源分配和任务分配框架
  • 批准号:
    1910348
  • 财政年份:
    2019
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Continuing Grant
Phase II IUCRC The Catholic University of America: Broadband Wireless Access and Applications Center (BWAC)
第二阶段 IUCRC 美国天主教大学:宽带无线接入和应用中心 (BWAC)
  • 批准号:
    1822087
  • 财政年份:
    2018
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Continuing Grant
Conference: Travel Support for GlobalSIP 2016, To Be Held This Year in Crystal City, VA, December 7-9, 2016
会议:GlobalSIP 2016 的差旅支持将于今年于 2016 年 12 月 7 日至 9 日在弗吉尼亚州水晶城举行
  • 批准号:
    1646998
  • 财政年份:
    2016
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Standard Grant
I/UCRC for Broadband Wireless Access and Applications Center Site at the Catholic University of America
美国天主教大学 I/UCRC 宽带无线接入和应用中心站点
  • 批准号:
    1624485
  • 财政年份:
    2016
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Continuing Grant
Collaborative Research: Multi-Input Multi-Output (MIMO) Aware Cooperative Dynamic Spectrum Access
协作研究:多输入多输出(MIMO)感知协作动态频谱接入
  • 批准号:
    1443773
  • 财政年份:
    2015
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Standard Grant

相似海外基金

Time-Evolving Graph Learning with Algorithm-System Co-Design
算法系统协同设计的时间演化图学习
  • 批准号:
    23KJ1786
  • 财政年份:
    2023
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
Optimization of bone remodeling algorithm and development of innovative orthodontic treatment support system using AI technology
利用AI技术优化骨重塑算法并开发创新正畸治疗支持系统
  • 批准号:
    23K16188
  • 财政年份:
    2023
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
High Accuracy Vision System with Enhanced AI algorithm for IVF ICSI Process
具有增强型 AI 算法的高精度视觉系统,适用于 IVF ICSI 流程
  • 批准号:
    10079725
  • 财政年份:
    2023
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Collaborative R&D
Development of Hybrid Flood Forecasting System based on Rainfall Information from Machine Learning Algorithm
基于机器学习算法的降雨信息的混合洪水预报系统开发
  • 批准号:
    22K04332
  • 财政年份:
    2022
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Implementation of a Multipath Signal Processing Algorithm for a Microwave Transmission System
微波传输系统多径信号处理算法的实现
  • 批准号:
    575659-2022
  • 财政年份:
    2022
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Alexander Graham Bell Canada Graduate Scholarships - Master's
3D tracking system for micro magnetization vector realized by inverse problem algorithm
反问题算法实现的微磁化矢量3D跟踪系统
  • 批准号:
    22K04246
  • 财政年份:
    2022
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
ERI: Variational Quantum Algorithm for Power System Simulation
ERI:电力系统仿真的变分量子算法
  • 批准号:
    2138702
  • 财政年份:
    2022
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Standard Grant
CAREER: An Algorithm and System Co-Designed Framework for Graph Sampling and Random Walk on GPUs
职业生涯:用于 GPU 上的图形采样和随机游走的算法和系统协同设计框架
  • 批准号:
    2046102
  • 财政年份:
    2021
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Continuing Grant
Collaborative Research: Power System Flexibility: Metric, Assessment, and Algorithm
合作研究:电力系统灵活性:度量、评估和算法
  • 批准号:
    2046243
  • 财政年份:
    2021
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Standard Grant
Collaborative Research: Power System Flexibility: Metric, Assessment, and Algorithm
合作研究:电力系统灵活性:度量、评估和算法
  • 批准号:
    2045978
  • 财政年份:
    2021
  • 资助金额:
    $ 58.4万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了