EAGER: Practical Graph Sparsification on GPUs

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

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/