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

最近，由于人们对理解关系的需求日益增加，图处理受到了广泛的关注。例如，在网络安全中，需要使用图分析来识别网络上的探测器。在社交媒体中，图表分析被用来找出人与人之间的关系和影响。在基础设施监控(例如智能建筑)中，在故障变得严重并导致级联故障之前，图形分析在根据系统依赖关系发现故障方面至关重要。另一方面，由于最近的技术进步(例如，具有3D集成的NDP)以更低的成本提高了存储器系统的可扩展性，内存中的图形处理变得越来越有吸引力。因此，本研究项目及时考虑图形处理(具有广泛应用)和内存系统的新兴趋势，研究一种涉及编程模型、运行时系统和体系结构的垂直集成方法，以整体加速内存中的图形处理。它包含三个研究创新和跨栈集成：(1)通过新颖的编程模型减少数据移动。它将研究一种新的图形处理编程模型--两阶段顶点程序，它是为PIM设计的，它支持一种新颖的“源-割”数据划分。(2)批量规则立方体间通信和立方体内局部性增强。它将研究如何重新组织计算，使立方体之间的通信以受控的方式发生。这允许批处理通信以及计算和通信的重叠。为此，将研究如何将同一立方体中的核心划分为两组(进程和应用单元)，以提高立方体内内存访问的局部性。(3)共同设计的位置感知调度器和预取器。该项目将开发一种新颖的体系结构界面，以便软件和体系结构可以交互。一方面，它为调度者提供了查询调度候选者的局部性信息以做出更好决策的能力。另一方面，调度器可以将调度决策传达给体系结构，以便即使是一个简单的预取器也可以准确地获取与即将调度的活动顶点相关的数据。拟议的研究还将通过吸引少数群体服务机构的高中生和本科生参与研究，吸引妇女和代表性不足的群体接受研究生教育，利用图形处理体系结构和运行时系统扩展计算机工程课程，传播用于教育和培训的研究基础设施，以及与业界合作，为社会做出贡献。

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.