INFINEL: An efficient GPU-based processing method for unpredictable large output graph queries
With the introduction of GPUs, which are specialized for iterative parallel computations, the execution of computation-intensive graph queries using a GPU has seen significant performance improvements. However, due to the memory constraints of GPUs, there has been limited research on handling large-scale output graph queries with unpredictable output sizes on a GPU. Traditionally, two-phase methods have been used, where the query is re-executed after splitting it into sub-tasks while only considering the size of the output in a static manner. However, two-phase methods become highly inefficient when used with graph data with extreme skew, failing to maximize the GPU performance. This paper proposes INFINEL, which handles unpredictable large output graph queries in a one-phase method through chunk allocation per thread and kernel stop/restart methods. We also propose applicable optimization techniques due to the corresponding unique characteristics of operating with low time/space overhead and not heavily relying on the GPU output buffer size. Through extensive experiments, we demonstrate that our one-phase method of INFINEL improves the performance by up to 31.5 times over the conventional two-phase methods for triangle listing ULO query.
Mon 4 MarDisplayed time zone: London change
16:10 - 17:10 | |||
16:10 20mTalk | INFINEL: An efficient GPU-based processing method for unpredictable large output graph queries Main Conference Sungwoo Park Korea Advanced Institute of Science and Technology, Seyeon Oh GraphAI, Min-Soo Kim Korea Advanced Institute of Science and Technology Link to publication DOI | ||
16:30 20mTalk | GraphCube: Interconnection Hierarchy-aware Graph Processing Main Conference Xinbiao Gan National University of Defense Technology, Guang Wu National University of Defense Technology, Shenghao Qiu , Feng Xiong National University of Defense Technology, Jiaqi Si National University of Defense Technology, Jianbin Fang National University of Defense Technology, Dezun Dong National University of Defense Technology, Chunye Gong National University of Defense Technology & National Supercomputer Center in Tianjin, Tiejun Li National University of Defense Technology, Zheng Wang Link to publication DOI | ||
16:50 20mTalk | Exploiting Fine-Grained Redundancy in Set-Centric Graph Pattern Mining Main Conference linzhiheng Institute of Computing Technology, Chinese Academy of Sciences, University of Chinese Academy of Sciences, Ke Meng Alibaba, Chaoyang Shui Institute of Computing Technology, Chinese Academy of Sciences, University of Chinese Academy of Sciences, Kewei Zhang Institute of Computing Technology, Chinese Academy of Sciences, University of Chinese Academy of Sciences, Junmin Xiao Institute of Computing Technology, Chinese Academy of Sciences, University of Chinese Academy of Sciences, Guangming Tan Chinese Academy of Sciences(CAS) Link to publication DOI |