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)批处理规则立方体间通信和立方体内部局部性增强。它将研究如何重新组织计算，以使多维数据集之间的通信以受控的方式进行。这允许批处理通信以及计算和通信的重叠。为此，本文将研究如何将同一多维数据集中的核划分为两组（Process和Apply单元），以提高多维数据集中内存访问局部性。(3)协同设计位置感知调度器和预取器。这个项目将开发一个新颖的体系结构接口，以便软件和体系结构可以交互。一方面，它为调度器提供了查询调度候选者的位置信息以做出更好决策的能力。另一方面，调度器可以将调度决策传递给体系结构，这样即使是简单的预取器也可以精确地获取与即将调度的活动顶点相关的数据。拟议的研究还将通过吸引来自少数民族服务机构的高中生和本科生参与研究，吸引女性和代表性不足的群体参加研究生教育，扩大计算机工程课程与图形处理架构和运行时系统，传播教育和培训的研究基础设施，以及与业界合作，为社会做出贡献。