Graph algorithms support a broad spectrum of big data applications. A typical approach to scale graph algorithms is to run in a distributed and parallel setting with multiple processing devices. The approach requires balanced and effective utilization of computation, memory, and communication resources across devices. To address the problem, a large number of studies have been conducted, such as graph partitioning and asynchronous computation. However, there are still many outstanding issues yet to be solved. For example, the workloads can be skewed differently across devices, and between iterations, even with the state-of-the-art graph partitioners. As the graph partitions are typically static, they fall short in capturing the dynamic characteristics with different algorithms, inputs, and progress, leading to poor utilization of resources. Recently, GPUs have been increasingly used to accelerate various graph algorithms. Their highly efficient interconnection technologies, such as NVLink, open new opportunities for us to achieve better resource utilization. In this paper, we analyze the dynamic load-imbalance (DLB) problem and the long tail (LT) problem in multi-GPUs and solve them by adaptive remote work stealing on-the-fly. We first introduce a frontier stealing algorithm to solve the DLB problem, then an ownership stealing algorithm to solve the LT problem. Based on these two algorithms, we developed Gum — a multi-GPU graph processing system with high device utilization. We evaluated Gum on four typical graph algorithms (BFS, WCC, PR, SSSP). The results show that Gum can run up to an order of magnitude faster than Gunrock and Groute, with fewer stragglers and less synchronization overhead.

This paper proposes a notion of parametric simulation to link entities across a relational database$\mathcal{D}$and a graph$G$. Taking functions and thresholds for measuring vertex close-ness, path associations and important properties as parameters, parametric simulation identifies tuples$t$in$\mathcal{D}$and vertices$v$in$G$that refer to the same real-world entity, based on topological and semantic matching. We develop machine learning methods to learn the parameter functions and thresholds. We show that parametric simulation is in quadratic-time, by providing such an algorithm. Putting these together, we develop HER, a parallel system to check whether$(t,v)$makes a match, find all vertex matches of$t$in$G$, and compute all matches across$\mathcal{D}$and$G$, all in quadratic-time. Using real-life and synthetic data, we empirically verify that HER is accurate with$\mathbf{F}$-measure of 0.94 on average, and is able to scale with database$\mathcal{D}$and graph$G$.

The ever-growing amount of dynamic graph data demands efficient techniques of incremental graph processing. However, incremental graph algorithms are challenging to develop. Existing approaches usually require users to manually design nontrivial incremental operators, or choose different memoization strategies for certain specific types of computation, limiting the usability and generality. In light of these challenges, we propose Ingress, an automated system for incremental graph processing. Ingress is able to incrementalize batch vertex-centric algorithms into their incremental counterparts as a whole, without the need of redesigned logic or data structures from users. Underlying Ingress is an automated incrementalization framework equipped with four different memoization policies, to support all kinds of vertex-centric computations with optimized memory utilization. We identify sufficient conditions for the applicability of these policies. Ingress chooses the best-fit policy for a given algorithm automatically by verifying these conditions. In addition to the ease-of-use and generalization, Ingress outperforms state-of-the-art incremental graph systems by 15.93X on average (up to 147.14X) in efficiency.

In database and large-scale data analytics, recursive aggregate processing plays an important role, which is generally implemented under a framework of incremental computing and executed synchronously and/or asynchronously. We identify three barriers in existing recursive aggregate data processing. First, the processing scope is largely limited to monotonic programs. Second, checking on conditions for monotonicity and correctness for async processing is sophisticated and manually done. Third, execution engines may be suboptimal due to separation of sync and async execution. In this paper, we lay an analytical foundation for conditions to check if a recursive aggregate program that is monotonic or even non-monotonic can be executed incrementally and asynchronously with its correct result. We design and implement a condition verification tool that can automatically check if a given program satisfies the conditions. We further propose a unified sync-async engine to execute these programs for high performance. To integrate all these effective methods together, we have developed a distributed Datalog system, called PowerLog. Our evaluation shows that PowerLog can outperform three representative Datalog systems on both monotonic and non-monotonic recursive programs.