A Data-Driven Approach to Dataflow-Aware Online Scheduling for Graph Neural Network Inference

• URL: http://arxiv.org/abs/2411.16342v1
• Date: Mon, 25 Nov 2024 12:38:59 GMT
• Title: A Data-Driven Approach to Dataflow-Aware Online Scheduling for Graph Neural Network Inference
• Authors: Pol Puigdemont, Enrico Russo, Axel Wassington, Abhijit Das, Sergi Abadal, Maurizio Palesi,
• Abstract summary: We propose a data-driven framework for dataflow-aware latency prediction in GNN inference. Our regressors can predict the optimal dataflow for a given graph with up to 91.28% accuracy and a Mean Absolute Percentage Error (MAPE) of 3.78%. We introduce an online scheduling algorithm that uses these regressors to enhance scheduling decisions.
• Score: 3.734578883171713
• License:
• Abstract: Graph Neural Networks (GNNs) have shown significant promise in various domains, such as recommendation systems, bioinformatics, and network analysis. However, the irregularity of graph data poses unique challenges for efficient computation, leading to the development of specialized GNN accelerator architectures that surpass traditional CPU and GPU performance. Despite this, the structural diversity of input graphs results in varying performance across different GNN accelerators, depending on their dataflows. This variability in performance due to differing dataflows and graph properties remains largely unexplored, limiting the adaptability of GNN accelerators. To address this, we propose a data-driven framework for dataflow-aware latency prediction in GNN inference. Our approach involves training regressors to predict the latency of executing specific graphs on particular dataflows, using simulations on synthetic graphs. Experimental results indicate that our regressors can predict the optimal dataflow for a given graph with up to 91.28% accuracy and a Mean Absolute Percentage Error (MAPE) of 3.78%. Additionally, we introduce an online scheduling algorithm that uses these regressors to enhance scheduling decisions. Our experiments demonstrate that this algorithm achieves up to $3.17\times$ speedup in mean completion time and $6.26\times$ speedup in mean execution time compared to the best feasible baseline across all datasets.

Related papers

• DA-MoE: Addressing Depth-Sensitivity in Graph-Level Analysis through Mixture of Experts [70.21017141742763]
  Graph neural networks (GNNs) are gaining popularity for processing graph-structured data. Existing methods generally use a fixed number of GNN layers to generate representations for all graphs. We propose the depth adaptive mixture of expert (DA-MoE) method, which incorporates two main improvements to GNN.
  arXiv  Detail & Related papers  (2024-11-05T11:46:27Z)
• DCP: Learning Accelerator Dataflow for Neural Network via Propagation [52.06154296196845]
  This work proposes an efficient data-centric approach, named Dataflow Code Propagation (DCP), to automatically find the optimal dataflow for DNN layers in seconds without human effort. DCP learns a neural predictor to efficiently update the dataflow codes towards the desired gradient directions to minimize various optimization objectives. For example, without using additional training data, DCP surpasses the GAMMA method that performs a full search using thousands of samples.
  arXiv  Detail & Related papers  (2024-10-09T05:16:44Z)
• Graph Pruning Based Spatial and Temporal Graph Convolutional Network with Transfer Learning for Traffic Prediction [0.0]
  This study proposes a novel Spatial-temporal Convolutional Network (TL-GPSTGN) based on graph pruning and transfer learning framework. The results demonstrate the exceptional predictive accuracy of TL-GPSTGN on a single dataset, as well as its robust migration performance across different datasets.
  arXiv  Detail & Related papers  (2024-09-25T00:59:23Z)
• SiHGNN: Leveraging Properties of Semantic Graphs for Efficient HGNN Acceleration [9.85638913900595]
  Heterogeneous Graph Neural Networks (HGNNs) have expanded graph representation learning to heterogeneous graph fields. Recent studies have demonstrated their superior performance across various applications, including medical analysis and recommendation systems. We propose a lightweight hardware accelerator for HGNNs, called SiHGNN. This accelerator incorporates a tree-based Semantic Graph Builder for efficient semantic graph generation and features a novel Graph Restructurer for optimizing semantic graph layouts.
  arXiv  Detail & Related papers  (2024-08-27T14:20:21Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
  arXiv  Detail & Related papers  (2023-10-23T01:25:44Z)
• Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation [80.227864832092]
  Graph neural networks (GNNs) have exhibited exceptional efficacy in a diverse array of applications. The sheer size of large-scale graphs presents a significant challenge to real-time inference with GNNs. We propose an online propagation framework and two novel node-adaptive propagation methods.
  arXiv  Detail & Related papers  (2023-10-17T05:03:00Z)
• Efficient Graph Neural Network Inference at Large Scale [54.89457550773165]
  Graph neural networks (GNNs) have demonstrated excellent performance in a wide range of applications. Existing scalable GNNs leverage linear propagation to preprocess the features and accelerate the training and inference procedure. We propose a novel adaptive propagation order approach that generates the personalized propagation order for each node based on its topological information.
  arXiv  Detail & Related papers  (2022-11-01T14:38:18Z)
• Bottleneck Analysis of Dynamic Graph Neural Network Inference on CPU and GPU [3.4214598355901638]
  Dynamic graph neural network (DGNN) is becoming increasingly popular because of its widespread use in capturing dynamic features in the real world. deploying DGNNs on hardware presents additional challenges due to the model complexity, diversity, and the nature of the time dependency. We select eight prevailing DGNNs with different characteristics and profile them on both CPU and GPU.
  arXiv  Detail & Related papers  (2022-10-08T03:41:50Z)
• SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization [23.609017952951454]
  We propose SCARA, a scalable Graph Neural Network (GNN) with feature-oriented optimization for graph computation. SCARA efficiently computes graph embedding from node features, and further selects and reuses feature results to reduce overhead. It is efficient to process precomputation on the largest available billion-scale GNN dataset Papers100M (111M nodes, 1.6B edges) in 100 seconds.
  arXiv  Detail & Related papers  (2022-07-19T10:32:11Z)
• ASFGNN: Automated Separated-Federated Graph Neural Network [17.817867271722093]
  We propose an automated Separated-Federated Graph Neural Network (ASFGNN) learning paradigm. We conduct experiments on benchmark datasets and the results demonstrate that ASFGNN significantly outperforms the naive federated GNN.
  arXiv  Detail & Related papers  (2020-11-06T09:21:34Z)
• Robust Optimization as Data Augmentation for Large-scale Graphs [117.2376815614148]
  We propose FLAG (Free Large-scale Adversarial Augmentation on Graphs), which iteratively augments node features with gradient-based adversarial perturbations during training. FLAG is a general-purpose approach for graph data, which universally works in node classification, link prediction, and graph classification tasks.
  arXiv  Detail & Related papers  (2020-10-19T21:51:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.