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.
