SHF: Small: Accelerating Graph Processing with Vertically Integrated Programming Model, Runtime and Architecture

SHF：小型：利用垂直集成编程模型、运行时和架构加速图形处理

• 批准号: 1717754
• 负责人: Xuehai Qian
• 金额: $ 45万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-15 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1717754&HistoricalAwards=false
• 关键词: SHF; Small; Accelerating; Graph; Processing

Recently, graph processing received intensive interests due to the increasing need to understand relationships. For example, in cyber security, the graph analytics are needed to identify probes on the network. In social media, the graph analytics are employed to figure out the relationships and influences between people. In infrastructure monitoring (e.g. smart building), the graph analytics are crucial in spotting failures based on system dependencies before they become critical and cause cascading failures. On the other hand, in-memory graph processing is becoming more appealing due to recent technology advances (e.g. NDP with 3D integration) that improved the scalability of memory system with lower cost. Therefore, this research program timely considers graph processing(which has broad applications) with the emerging trends in the memory system.This project will investigate a vertically integrated approach involving programming model, runtime system and architecture to holistically accelerate in-memory graph processing. It contains three research innovations and cross-stack integration: (1) Reducing data movements with novel programming model. It will study a new graph processing programming model,?Two-phase Vertex Program?, designed for PIM that supports a novel "source-cut" data partition. (2) Batched regular inter-cube communication and intra-cube locality enhancement. It will examine how to re-organize the computation to make the inter-cube communications happen in a controlled manner. This allows batched communication and the overlapping of computation and communication. To this end, it will study how to partition the cores in the same cube into two groups (Process and Apply unit) to improve intra-cube memory access locality. (3) Co-designed locality-aware scheduler and prefetcher. This project will develop a novel architectural interface so that the software and architecture could interact. On one side, it provides scheduler the capability to query the locality information of scheduling candidates to make better decisions. On the other side, the scheduler could convey the scheduling decisions to architecture so that even a simple prefetcher can precisely fetch the data related to the active vertices that will be scheduled soon. The proposed research will also contribute to society through engaging high-school and undergraduate students from minority-serving institutions into research, attracting women and under-represented groups into graduate education, expanding the computer engineering curriculum with graph processing architectures and runtime systems, disseminating research infrastructure for education and training, and collaborating with the industry.

最近，由于对了解关系的需求越来越大，图形处理获得了密集的兴趣。例如，在网络安全性中，需要图形分析来识别网络上的探针。在社交媒体中，使用图形分析来弄清者之间的关系和影响。在基础架构监视（例如智能建筑物）中，图表分析对于基于系统依赖性的失败至关重要，然后才能引起层次的失败并导致级联故障。另一方面，由于最近的技术进步（例如与3D集成的NDP），内存图形处理变得越来越有吸引力，从而提高了成本较低的内存系统的可扩展性。因此，该研究计划及时考虑了记忆系统中新兴趋势的图形处理（具有广泛的应用程序）。本项目将调查涉及编程模型，运行时系统和体系结构的垂直集成方法，以整体加速内存内图处理。它包含三个研究创新和跨堆栈集成：（1）通过新颖的编程模型减少数据运动。它将研究一个新的图形处理编程模型，“两相顶点程序”，专为PIM设计，该模型支持一种新型的“源切割”数据分区。 （2）批处理常规群间通信和立体内部的位置增强。它将检查如何重新组织计算以使立体间的通信以受控方式进行。这允许批处理通信以及计算和通信的重叠。为此，它将研究如何将同一立方体中的核心分为两组（过程和应用单元），以改善立即内的内存访问区域。 （3）共同设计的局部感知调度程序和预摘要。该项目将开发一个新颖的体系结构界面，以便软件和体系结构可以交互。一方面，它为调度程序提供了查询调度候选人以做出更好决策的当地信息的功能。另一方面，调度程序可以将调度决策传达给架构，以便即使是简单的预摘要也可以精确获取与很快计划的活动顶点相关的数据。拟议的研究还将通过使少数派服务机构的高中和本科生参与研究，吸引妇女和代表性不足的群体进入研究生教育，通过图表处理结构和跑步时间系统扩展计算机工程课程，以教育和与该行业协作进行研究基础结构。