Skyway:Accelerate Graph Applications with a Dual-Path Architecture and Fine-Grained Data Management

Graph processing is a vital component of many AI and big data applications.However,due to its poor locality and complex data access patterns,graph processing is also a known performance killer of AI and big data applications.In this work,we propose to enhance graph processing applications by leveraging fine-grained memory access patterns with a dual-path architecture on top of existing software-based graph optimizations.We first identify that memory accesses to the offset,edge,and state array have distinct locality and impact on performance.We then introduce the Skyway architecture,which consists of two primary components:1)a dedicated direct data path between the core and memory to transfer state array elements efficiently,and 2)a data-type aware fine-grained memory-side row buffer hardware for both the newly designed direct data path and the regular memory hierarchy data path.The proposed Skyway architecture is able to improve the overall performance by reducing the memory access interference and improving data access efficiency with a minimal overhead.We evaluate Skyway on a set of diverse algorithms using large real-world graphs.On a simulated fourcore system,Skyway improves the performance by 23%on average over the best-performing graph-specialized hardware optimizations.

A Proposal for a Benchmark Generator of Weakly Connected Directed Graphs

The previous studies on detection of communities on complex networks were focused on nondirected graphs, such as Neural Networks, social networks, social interrelations, the contagion of diseases, and bibliographies. However, there are also other problems whose modeling entails obtaining a weakly connected directed graph such as the student access to the university, the public transport networks, or trophic chains. Those cases deserve particularized study with an analysis and the resolution adjusted to them. Additionally, this is a challenge, since the existing algorithms in most of the cases were originally designed for non-directed graphs or symmetrical and regular graphs. Our proposal is a Benchmark Generator of Weakly Connected Directed Graphs whose properties can be defined by the end-users according to their necessities. The source code of the generators described in this article is available in GitHub under the GNU license.

Large-scale graph processing systems: a survey

Graph is a significant data structure that describes the relationship between entries.Many application domains in the real world are heavily dependent on graph data.However,graph applications are vastly different from traditional applications.It is inefficient to use general-purpose platforms for graph applications,thus contributing to the research of specific graph processing platforms.In this survey,we systematically categorize the graph workloads and applications,and provide a detailed review of existing graph processing platforms by dividing them into generalpurpose and specialized systems.We thoroughly analyze the implementation technologies including programming models,partitioning strategies,communication models,execution models,and fault tolerance strategies.Finally,we analyze recent advances and present four open problems for future research.