EAGER: Practical Graph Sparsification on GPUs

大量的现实问题可以被简明地抽象和建模为图或网络。处理和分析这些图的一个基本挑战是规模问题，数百万或数十亿个节点以及数十亿和数万亿条边。虽然技术的进步导致了更快和更好的体系结构的发展，但简单地将现有代码移植到这种体系结构是不够的-性能增益通常与技术的进步不相称，部分原因是与这种算法相关的固有数据移动成本。该项目旨在研究两种互补的策略（图稀疏化和架构感知算法设计）来应对这一挑战。这项研究的关键成果将是算法和系统创新，这些创新将从根本上影响下一代图分析系统。这一努力预计将提供一个模型的研究，教育和培训的本科生和研究生，包括那些来自代表性不足的group.With方面的创新，实用的图形稀疏化战略作为一种通用的战略，以缩小现代图形和网络分析算法的数据移动要求将进行调查。具体来说，将开发基于哈希的创新方法，以适应边缘方向性，加权图和异构内容。此外，还将设计全新的方法，在当前和下一代基于图形处理器单元（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/