Graph neural networks (GNNs) have gained significant attention across diverse areas due to their superior performance in learning graph representations. While GNNs exhibit superior performance compared to other methods, they are primarily designed for homogeneous graphs, where all nodes and edges are of the same type. Training a GNN model for large-scale graphs incurs high computation and storage costs, especially when considering the heterogeneous structural information of each node. To address the demand for efficient GNN training, various sampling methods have been proposed. In this paper, we propose a sampling method based on bandit sampling, an online learning algorithm with provable convergence under weak assumptions on the learning objective. To the best of our knowledge, this is the first bandit-based sampling method applied to heterogeneous GNNs with a theoretical guarantee. The main idea is to prioritize node types with more informative connections with respect to the learning objective. Compared with existing techniques for GNN training on heterogeneous graphs, extensive experiments using the Open Academic Graph (OAG) dataset demonstrate that our proposed method outperforms the state-of-the-art in terms of the runtime across various tasks with a speed-up of 1.5-2x, while achieving similar accuracy.

Sparse Matricized Tensor Times Khatri-Rao Product (spMTTKRP) is the most computationally intensive kernel in sparse tensor decomposition. In this paper, we propose a hardware-algorithm co-design on FPGA to minimize the execution time of spMTTKRP along all modes of an input tensor. We introduce FLYCOO, a novel tensor format that eliminates the communication of intermediate values to the FPGA external memory during the computation of spMTTKRP along all the modes. Our remapping of the tensor using FLYCOO also balances the workload among multiple Processing Engines (PEs). We propose a parallel algorithm that can concurrently process multiple partitions of the input tensor independent of each other. The proposed algorithm also orders the tensor dynamically during runtime to increase the data locality of the external memory accesses. We develop a custom FPGA accelerator design with (1) PEs consisting of a collection of pipelines that can concurrently process multiple elements of the input tensor and (2) memory controllers to exploit the spatial and temporal locality of the external memory accesses of the computation. Our work achieves a geometric mean of 8.8X and 3.8X speedup in execution time compared with the state-of-the-art CPU and GPU implementations on widely-used real-world sparse tensor datasets.

Task mapping is critical for the effective utilization of high performance computing systems. Recently, heterogeneous platforms consisting of CPUs, GPUs, FPGAs, and hardware accelerators have become popular. While there have been extensive studies to optimize task mapping, existing approaches have primarily focused on homogeneous platforms and rely on heuristics like greedy algorithms and do not effectively explore the search space. In this paper, we focus on a class of task mapping problems that captures heterogeneity in the application as well as in the target platform. We consider task mapping under a generalized computational setting where heterogeneous applications consisting of interdependent tasks with platform-dependent execution and communication parameters are to be mapped onto heterogeneous resource-limited execution platforms including CPUs, GPUs, FPGAs, and accelerators. This abstracts modern scientific workflows where computations proceed in an iterative fashion. We propose Pick-Best-Pair with Running Best (PRB) - a Monte Carlo Tree Search (MCTS) based approach to identify a task-hardware mapping for an input application. We formulate the task mapping problem as an integer linear programming problem and solve it using our PRB approach that conducts a series of LP relaxations with randomized rounding by leveraging exploration of long-term cumulative reward in terms of the total completion time, instead of a local optimal solution. We evaluate our approach by varying the number of stages, number of tasks per stage, and types of tasks, as well as resources with mixed types. Experimental results show that our proposed algorithm is effective in finding efficient mapping compared with classic approaches, such as the greedy heuristic and the randomized LP rounding. PRB achieves up to 20% improvement over greedy algorithm and 15% over LP relaxation with randomized rounding.