Compressing Graphs Using Quadtrees for Efficient Computation on GPUS - Chatterjee, Amlan (International Journal of Computer Sciences and Engineering, 2020)
Exploiting the computation potential of multi-core Graphics Processing Units (GPUs) requires reducing memory access latency and memory transfer overheads. Although the GPUs provide fast processing capabilities, the memory on such devices is significantly less. Though the memory hierarchy of GPUs provide certain fast levels, these are limited in terms of storage. Also, in order to use the GPUs for computation, the data must be transferred into the memory of the same; hence, in order to reduce the memory latency for large volume of data transfer, efficient techniques are required. Analysis of graph data on GPUs have many practical applications, and has been studied by both academia and industry. The graph data must be stored on the GPU memory to perform computation and analysis on the same. There are different data structures that can be used to store graphs in the GPU memory. Employing compression techniques to reduce the size required by the data is useful; however, the computation must be performed on the compressed data itself since decompressing the data would not be feasible. In addition to saving space on the device, using compressed data structures also reduces the memory transfer overheads both between the CPU & GPU, and between the various levels in the memory hierarchy of the GPU, thereby compensating for some of the additional time to retrieve information from the compressed data. Storing data using efficient compression techniques and operating on the compressed data is therefore useful. Quadtree data structures are generally used for storing and representing images for various applications. However, graphs when represented as adjacency matrix are comparable to images; hence, using recursive partitioning techniques, the data can be effectively compressed. In this paper, we show techniques based on quadtrees to efficiently compress graph data for storing and computation on GPUs. Additional techniques are also introduced which result in hybrid data structures that perform better for specific cases. Empirical results show 80-90% decrease in the space requirements to store graphs with real-world properties.