Recently, there has been active research on utilizing GPUs for the efficient processing of large-scale dynamicgraphs. However, challenges arise due to the repeated transmission and processing of identical data during...
详细信息
Recently, there has been active research on utilizing GPUs for the efficient processing of large-scale dynamicgraphs. However, challenges arise due to the repeated transmission and processing of identical data during dynamicgraph operations. This paper proposes an efficient processing scheme for large-scale dynamicgraphs in GPU environments with limited memory, leveraging dynamic scheduling and operation reduction. The proposed scheme partitions the dynamicgraph and schedules each partition based on active and tentative active vertices, optimizing GPU utilization. Additionally, snapshots are employed to capture graph changes, enabling the detection of redundant edge and vertex modifications. This reduces unnecessary computations, thereby minimizing GPU workloads and data transmission costs. The scheme significantly enhances performance by eliminating redundant operations on the same edges or vertices. Performance evaluations demonstrate an average improvement of 280% over existing static graphprocessing techniques and 108% over existing dynamic graph processing schemes.
In many applications of the analysis of dynamicgraph, many Timing iterative graphprocessing (TGP) jobs usually need to be generated for the processing of the corresponding snapshots of the dynamicgraph to obtain th...
详细信息
In many applications of the analysis of dynamicgraph, many Timing iterative graphprocessing (TGP) jobs usually need to be generated for the processing of the corresponding snapshots of the dynamicgraph to obtain the results at different points of time. For high throughput of such applications, it is expected to run the TGP jobs on the GPU concurrently. Although many GPU-based systems have been recently developed, for out-of-GPU-memory dynamic graph processing, this concurrent way suffers from significant data access overhead due to a large volume of data transfer between CPU and GPU and the interference between these concurrently running jobs, which eventually incurs low GPU utilization ratio. In this work, we observed that the TGP jobs have strong temporal and spatial similarity when they access different snapshots for their own processing as most parts of the snapshots are the same and only a few parts are changing with time. It creates ideal opportunities for efficient concurrent execution of the TGP jobs by dramatically reducing CPU-GPU graph data transfer cost. Based on this observation, we develop the first GPU-based dynamic graph processing system Egraph, which can be integrated into the existing out-of-GPU-memory static graphprocessing systems to enable them to efficiently support concurrent execution of TGP jobs on dynamicgraphs with the help of GPU accelerators. Different from the existing approaches, we propose in Egraph an effective Loading-processing-Switching (LPS) execution model. It is able to effectively reduce the overhead of CPU-GPU data transfer and ensures a higher GPU utilization ratio for efficient execution of the TGP jobs by fully utilizing the data access similarity between the TGP jobs. Experimental results show that the existing GPU-accelerated systems achieve performance improvements of 2.3-3.5 times after being integrated with Egraph.
graph Convolutional Networks (GCNs) have emerged as pivotal tools in addressing intricate optimization and scheduling challenges within logistics, encompassing canonical problems such as the Vehicle Routing Problem (V...
详细信息
graph Convolutional Networks (GCNs) have emerged as pivotal tools in addressing intricate optimization and scheduling challenges within logistics, encompassing canonical problems such as the Vehicle Routing Problem (VRP), Traveling Salesman Problem (TSP), and dynamic job scheduling. This survey presents a comprehensive exploration of GCN applications, emphasizing their capacity to model spatial-temporal dependencies and their seamless integration with advanced paradigms, including reinforcement learning and hybrid optimization techniques. By leveraging these capabilities, GCNs have demonstrated enhanced scalability and interpretability, rendering them indispensable for large-scale, real-time logistics systems. The review extends to real-world implementations, illustrating GCN-driven innovations in resource allocation, traffic management, and supply chain optimization. In addition, the study critically examines persistent challenges-ranging from processingdynamicgraphs to ensuring ethical deployment through fairness and sustainability. The paper concludes with forward-looking recommendations, advocating for the evolution of GCN architectures to adeptly manage real-time decision-making and uncertainty in increasingly complex logistical landscapes.
graphs processing has become an important part of various areas of computing, including machine learning, medical applications, social network analysis, computational sciences, and others. A growing amount of the asso...
详细信息
graphs processing has become an important part of various areas of computing, including machine learning, medical applications, social network analysis, computational sciences, and others. A growing amount of the associated graphprocessing workloads are dynamic, with millions of edges added or removed per second. graph streaming frameworks are specifically crafted to enable the processing of such highly dynamic workloads. Recent years have seen the development of many such frameworks. However, they differ in their general architectures (with key details such as the support for the concurrent execution of graph updates and queries, or the incorporated graph data organization), the types of updates and workloads allowed, and many others. To facilitate the understanding of this growing field, we provide the first analysis and taxonomy of dynamic and streaming graphprocessing. We focus on identifying the fundamental system designs and on understanding their support for concurrency, and for different graph updates as well as analytics workloads. We also crystallize the meaning of different concepts associated with streaming graphprocessing, such as dynamic, temporal, online, and time-evolving graphs, edge-centric processing, models for the maintenance of updates, and graph databases. Moreover, we provide a bridge with the very rich landscape of graph streaming theory by giving a broad overview of recent theoretical related advances, and by discussing which graph streaming models and settings could be helpful in developing more powerful streaming frameworks and designs. We also outline graph streaming workloads and research challenges.
Recent advances in dynamic graph processing have enabled the analysis of highly dynamicgraphs with change at rates as high as millions of edge changes per second. Solutions in this domain, however, have been demonstr...
详细信息
暂无评论