EAGER: Practical Graph Sparsification on GPUs

EAGER：GPU 上的实用图稀疏化

• 批准号: 1550302
• 负责人: Srinivasan Parthasarathy
• 金额: $ 11.12万
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1550302&HistoricalAwards=false
• 关键词: EAGER; Practical; Graph; Sparsification; GPUs

A large number of real-world problems can be concisely abstracted and modeled as a graph or a network. A fundamental challenge with processing and analyzing such graphs is the issue of scale, millions or billions of nodes and billions and trillions of edges. While advances in technology have led to the development of faster and better architectures, simply porting existing codes to such architectures will not suffice -- performance gains are typically not commensurate with advances in technology in part due to the inherent data movement costs associated with such algorithms. This project seeks to investigate two complementary strategies (graph sparsification and architecture-aware algorithm designs) to address this challenge head on. The key outcomes of this research will be algorithmic and systemic innovations that can radically impact next generation graph analytic systems. This effort is expected to provide a model for the research, education and training of both undergraduate and graduate students including those from under-represented groups.With respect to innovation, practical graph sparsification strategies as a generic strategy to scaling down the data movement requirements of modern graph and network analysis algorithms will be investigated. Specifically, innovative hashing-based approaches to accommodate edge directionality, weighted graphs, and heterogeneous content will be developed. Additionally, radically new ways to implement and re-architect such analysis algorithms on current and next generation Graphics Processor Unit (GPU)-based systems while expicitly accounting for data movement costs within the architecture will be designed. Specifically, a novel sketching strategy will be employed for this purpose. In terms of impact, the sparsification-based approach can be significant in terms of the wide use and application of such strategies for scaling up tasks such as link prediction, community discovery, and collective classification and deploying them on modern GPUs. Exemplar outcomes are expected to include a high performance GPU-based network analysis tools for data scientists, and the interdisciplinary training of students in data mining, network science and high performance computing leveraging research in pedagogy, in conjunction with Ohio State University's new undergraduate major in data analytics. For further information see the project web site at: http://www.cse.ohio-state.edu/~srini/GraphSpar/

大量现实世界的问题可以被简洁地抽象和建模为图或网络。处理和分析此类图的一个基本挑战是规模问题、数百万或数十亿的节点以及数十亿和数万亿的边。虽然技术的进步导致了更快、更好的架构的开发，但仅仅将现有代码移植到此类架构是不够的——性能增益通常与技术的进步不相称，部分原因是与此类算法相关的固有数据移动成本。该项目旨在研究两种互补的策略（图稀疏化和架构感知算法设计）来应对这一挑战。这项研究的主要成果将是算法和系统创新，这些创新可以从根本上影响下一代图分析系统。这项工作预计将为本科生和研究生（包括来自代表性不足群体的学生）的研究、教育和培训提供一个模型。在创新方面，将研究实用的图稀疏化策略作为减少现代图和网络分析算法的数据移动要求的通用策略。具体来说，将开发基于哈希的创新方法来适应边缘方向性、加权图和异构内容。此外，还将设计在当前和下一代基于图形处理器单元（GPU）的系统上实施和重新架构此类分析算法的全新方法，同时明确考虑架构内的数据移动成本。具体来说，为此目的将采用一种新颖的草图策略。就影响而言，基于稀疏化的方法可以在此类策略的广泛使用和应用方面发挥重要作用，以扩大链路预测、社区发现和集体分类等任务并将其部署在现代 GPU 上。预计示范成果将包括为数据科学家提供基于 GPU 的高性能网络分析工具，以及利用教育学研究，结合俄亥俄州立大学新设的数据分析本科专业，对学生进行数据挖掘、网络科学和高性能计算方面的跨学科培训。有关更多信息，请参阅该项目网站：http://www.cse.ohio-state.edu/~srini/GraphSpar/