GPU-based Graph Traversal on Compressed Graphs
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Sha, Mo
Li, Yuchen
Tan, Kian-Lee
Graph processing on GPUs received much attention in the industry and the academia recently, as the hardware accelerator offers attractive potential for performance boost. However, the high-bandwidth device memory on GPUs has limited capacity that constrains the size of the graph to be loaded on chip. In this paper, we introduce GPU-based graph traversal on compressed graphs, so as to enable the processing of graphs having a larger size than the device memory. Designed towards GPU’s SIMT architecture, we propose two novel parallel scheduling strategies Two-Phase Traversal and Task-Stealing to handle thread divergence and workload imbalance issues when decoding the compressed graph. We further optimize our solution against power-law graphs by proposing Warp-centric Decoding and Residual Segmentation to facilitate parallelism on processing skewed out-degree distribution. Extensive experiments show that with 2x-18x compression rate, our proposed GPU-based graph traversal on compressed graphs (GCGT) achieves competitive efficiency compared with the state-of-the-art graph traversal approaches on non-compressed graphs.
 Okay, good afternoon. I am more a PhD candidate in National University of Singapore. I will present our work, GPU-based graph traversal on compressed graphs. I will first introduce some background information, especially on the motivation to traverse compressed graphs on the GPU. Then I will explain the technical details of this work, including the involved compression strategies and the proposed GPU-based graph traversal on compressed graphs. Finally, I will present some experimental evaluation results and summarize in the conclusion. GPU as a parallel accelerator shows a good performance and potential to speed up graph analytics due to its massive number of cores and ultra memory bandwidth. However, the acceleration enabled by the GPU does not come for free. The high bandwidth device memory on the GPU has limited capacity that constrains the size of graph to be loaded on chip. Although there exist some approaches that can solve the situation that the graph cannot be completely loaded into the GPU, for example, the out-call, the multi-GPU or distributed solutions, they will lead to severe performance degradation compared with the graph data can be fully loaded. In this work, we propose an orthogonal approach to further expand the capability of GPU graph processing. The high-level idea is rather intuitive. We compress the graph in advance and execute the GPU workloads on a compressed graph directly and only decode necessary data into caches to limit the memory usage. We leverage on the massive computing power of GPU to hide the decoding cost and retain the performance as that in an uncompressed scenario. And we introduce several kinds of graph compression techniques to compress the graph data and use less device memory to store the graph on chip. To better understand the technology introduced next, let's take an example to showcase some details about compressed graph representation. To represent a graph in a compressed manner, there are three steps to be involved. To start with, we have a traditional and uncompressed graph representation on a GCC list. It means now 16 has 10 neighbors, 12, 18, and so on. For the first step, we can represent neighbors with consecutive indexes as an interval with the starting node and the corresponding length shown in blue. And for the neighbors which cannot form intervals, we need to recall them separately in the residue sequence shown in right. As a consequence, we can denote a north GCC list with intervals and residue sequences. After that, for each sequence, we transform it into the differential sequence that is to denote each element as a difference between itself and its presiding element. The target of gap transformation is to decrease the absolute value of each number in the sequence while maintaining the original information. And finally, we can recall the equivalent sequence information with favor base for the VLC encoding technique. The variable length code is widely used in various data compression scenarios. Compared with the fixed length encoding, VLC can vary the number of bits needed to represent an element. From this example, we can find that the original GCC list, which requires 10 integers, the 320 bits in the representation, can be denoted with only 55 bits on CGR. Similar to most existing approaches related to graph analytics in parallel or on GPUs, this work falls into the category of north-centric parallel graph processing, which intuitively execute a pipeline of expanding, filtering, contraction on ping-pong frontier queues. Let's take an example. For each iteration, there are several nodes in the input queue to be traversed as frontiers. And in the expansion step, we will expand all the neighbors of these frontiers. And then in the filtering step, to filter out those neighbors which are not required. In the case of BFS, nodes which have been visited will be filtered out. And also, for unvisited neighbors, we will update their labels as the results of the traversal and keep them for the next iteration. And finally, in the contraction step, we contract the neighbor array into a compact manner as the output queue for current iteration and the input queue for the next iteration. The graph shown on the right side is the precise of BFS based on the computational pipeline mentioned above. In the paper, we further discuss how to extend this proposal to other graph applications. Let's talk about how to conduct such a computational pipeline on a compressed graph on the GPU. Compared with existing GPU-based graph traversal on uncompressed graphs, the major difference locates on the expansion step which needs to access the GCC list for each frontier. When expanding frontiers, we need to access the compressed graph representation to decode neighbors of a frontier. Obviously, based on the previous mentioned CGR design, when each stride resolves a neighbor from CGR, it may be from an interval or a residue. And we need roughly two instruction branches to handle them. After expansion, we need to handle the neighbor decoded to check whether current neighbor is visited. During this stage, we need to access those labels to check and update those status. We use different color to indicate different instruction branches. GPU execute in a SIMT manner, the single instruction mathematical stress. So at any moment, stress can concurrently execute the same instruction in the same color or be add-on. Let's take an example. Assume that in iteration, we have an input queue with eight frontiers and we assign each frontier a stride. In the expansion step, we need to access CGR to get the neighbors. We assume the corresponding compressed GCC list are here. We use three colors to indicate different instruction branches and use gray color to indicate that the threads are add-on in current instruction cycle due to the SIMT architecture. To simplify the presentation, we assume these three kinds of operations cause a scene. The instruction flow sequence of a traditional implementation is shown here. We cannot that when different threads within the same web are divergent in handling both intervals and residues, they cannot execute concurrently and need two steps to make all threads get the information of at least one neighbor. Through this figure, we can find that the current instruction concurrency is not good and a large amount of computing resources are visited. Hence we propose a set of optimizations to better utilize GPU's power. The first one is two-phase traversal. As we can see from the previous example, one reason for the low concurrency is that when the threads are expanding neighbors of frontier, the threads are divergent in reading intervals and residues. In the meanwhile, when an interval is decoded, all neighbors belonging to such an interval are aware and can be handled in parallel. Hence we divide the expansion into two phases, the interval phase and the residue phase. We first expand neighbors from intervals and in this phase, threads who hold an interval will try to occupy the whole web of threads and dispatch its neighbors to them. After all neighbors represented by intervals are handled, we will start to handle neighbors represented by residues. So far, we can see that the concurrency of the interval phase is good, but the computing resources are still visited a lot in the residue phase. Hence we propose task stealing, meaning that when in the residue phase, we will first decode enough information from CGR and handle the decoded neighbors cooperatively. So far, compared with the original straightforward solution, it is much better. And it is easy to note that the bottleneck of current solution is the imbalance loading when decoding residues. Unfortunately, such issue is quite common in most graph data. Hence we propose the web-centric decoding. The main reason for the bottleneck is that when using VLC to encode CGR, it is not easy to decode multiple residues concurrently because the beginning bit position or the off-site of each VLC encoding is unknown before its predecessor is decoded. Let's take an example. Assume that we have a beta ray that includes five VLC encodings, one, two, three, four, five, respectively. And the encodings of these five numbers are a total of 17 bits. Except for the first encoding, we cannot know where the other encoding start. We even cannot know how many encodings are encoded in a particular bit range. Hence we have to assign a thread to start from each bit position. Each thread then decodes a number according to its beginning bit position. Apparently, only the decodings of those threads starting from a real VLC beginning position are valid. So it is required to identify which decodings are valid among all decoded candidates. Based on the SI-MT execution, we can mark candidates at an exponential rate, meaning that every marked thread can mark a new valid decoding at each round. So far, for imbalanced residues, we can use idle threads to decode long residue chain concurrently. In addition, we know that there exists some nodes whose residue sequences are remarkably longer than those of other nodes in real-world graphs. This leads to low parallelism and degraded performance. To achieve a better load balancing, we divide a long residue sequence into smaller segments for fine-grained workload partitioning. Decomposing the long residue chain into fixed length segments, we can easily handle them by multiple threads. So far, we have introduced the methodology proposed for efficient tremors in compressed graphs on the GPU. Next, let's look at the experimental evaluation results. We collect two web graphs, two social network graphs, and one biology graph throughout this work. In order to verify the effectiveness of each proposed optimizations on the performance, we apply the technique incrementally and illustrate the incremental results in this figure. The two-phase traversal aims to avoid web divisions when threads fall into different logic branches, executing as an interval or a residue decoding. The task stealing is used for, in a situation when the residue number varies significantly. And the web centric shows a relatively stable improvement for a better hardware utilization and poses a larger impact when the average base per edge is fever. The Twitter graph exhibits a severe, severe-skilled distribution, and thus the execution is bottlenecked by several nodes with an extremely large outdegree. So the residue segmentation has a larger impact on the Twitter graph. Next, let's look at the comparison between different baselines. To evaluate our proposal, we compare it with several state-of-the-art CPU-based and GPU-based graph traversal approaches, including the single-threaded solution, the parallel solution on compressed graph, the GPU graph platform, the GPU-based standalone implementation, and our proposal, the GPU-based graph traversal on compressed graphs. We use bar plots to denote each approach's elapsed time of graph traversal and the compression rates are illustrated in the line plots with black dots. According to this result, we can verify that the GPU is a peeling accelerator for graph analytics, and compare with approach based on the traditional non-compressed graph format. We can see that with a considerable compression rates, our proposal only introduces a very low overhead on the performance. In conclusion, in this work, we identify the limitation of GPU-based memory and introduce compressed graph into GPU-based graph computation for optimized device memory usage. For the hardware characteristics of the GPU, we propose a series of optimizations so that the compressed graph can be efficiently traversed on the GPU, and extensive experiments show that with a considerable compression rate, our proposal achieves competitive efficiency compared with state-of-the-art graph traversal approaches on uncompressed graphs. That's all. Thank you for listening.
 Okay, good afternoon. I am more a PhD candidate in National University of Singapore. I will  present our work, GPU-based graph traversal on compressed graphs. I will first introduce  some background information, especially on the motivation to traverse compressed graphs  on the GPU. Then I will explain the technical details of this work, including the involved  compression strategies and the proposed GPU-based graph traversal on compressed graphs. Finally,  I will present some experimental evaluation results and summarize in the conclusion. GPU  as a parallel accelerator shows a good performance and potential to speed up graph analytics due  to its massive number of cores and ultra memory bandwidth. However, the acceleration enabled  by the GPU does not come for free. The high bandwidth device memory on the GPU has limited  capacity that constrains the size of graph to be loaded on chip. Although there exist  some approaches that can solve the situation that the graph cannot be completely loaded  into the GPU, for example, the out-call, the multi-GPU or distributed solutions, they will  lead to severe performance degradation compared with the graph data can be fully loaded. In  this work, we propose an orthogonal approach to further expand the capability of GPU graph  processing. The high-level idea is rather intuitive. We compress the graph in advance  and execute the GPU workloads on a compressed graph directly and only decode necessary data  into caches to limit the memory usage. We leverage on the massive computing power of  GPU to hide the decoding cost and retain the performance as that in an uncompressed scenario.  And we introduce several kinds of graph compression techniques to compress the graph data and  use less device memory to store the graph on chip. To better understand the technology  introduced next, let's take an example to showcase some details about compressed graph  representation. To represent a graph in a compressed manner, there are three steps to  be involved. To start with, we have a traditional and uncompressed graph representation on a  GCC list. It means now 16 has 10 neighbors, 12, 18, and so on. For the first step, we  can represent neighbors with consecutive indexes as an interval with the starting node and the  corresponding length shown in blue. And for the neighbors which cannot form intervals,  we need to recall them separately in the residue sequence shown in right. As a consequence,  we can denote a north GCC list with intervals and residue sequences. After that, for each  sequence, we transform it into the differential sequence that is to denote each element as  a difference between itself and its presiding element. The target of gap transformation  is to decrease the absolute value of each number in the sequence while maintaining the  original information. And finally, we can recall the equivalent sequence information  with favor base for the VLC encoding technique. The variable length code is widely used in  various data compression scenarios. Compared with the fixed length encoding, VLC can vary  the number of bits needed to represent an element. From this example, we can find that  the original GCC list, which requires 10 integers, the 320 bits in the representation, can be  denoted with only 55 bits on CGR. Similar to most existing approaches related to graph  analytics in parallel or on GPUs, this work falls into the category of north-centric parallel  graph processing, which intuitively execute a pipeline of expanding, filtering, contraction  on ping-pong frontier queues. Let's take an example. For each iteration, there are several  nodes in the input queue to be traversed as frontiers. And in the expansion step, we will  expand all the neighbors of these frontiers. And then in the filtering step, to filter out  those neighbors which are not required. In the case of BFS, nodes which have been visited  will be filtered out. And also, for unvisited neighbors, we will update their labels as  the results of the traversal and keep them for the next iteration. And finally, in the  contraction step, we contract the neighbor array into a compact manner as the output queue  for current iteration and the input queue for the next iteration. The graph shown on  the right side is the precise of BFS based on the computational pipeline mentioned above.  In the paper, we further discuss how to extend this proposal to other graph applications.  Let's talk about how to conduct such a computational pipeline on a compressed graph on the GPU.  Compared with existing GPU-based graph traversal on uncompressed graphs, the major difference  locates on the expansion step which needs to access the GCC list for each frontier.  When expanding frontiers, we need to access the compressed graph representation to decode  neighbors of a frontier. Obviously, based on the previous mentioned CGR design, when  each stride resolves a neighbor from CGR, it may be from an interval or a residue. And  we need roughly two instruction branches to handle them. After expansion, we need to handle  the neighbor decoded to check whether current neighbor is visited. During this stage, we  need to access those labels to check and update those status. We use different color to indicate  different instruction branches. GPU execute in a SIMT manner, the single instruction mathematical  stress. So at any moment, stress can concurrently execute the same instruction in the same color  or be add-on. Let's take an example. Assume that in iteration, we have an input queue with  eight frontiers and we assign each frontier a stride. In the expansion step, we need to  access CGR to get the neighbors. We assume the corresponding compressed GCC list are here.  We use three colors to indicate different instruction branches and use gray color to  indicate that the threads are add-on in current instruction cycle due to the SIMT architecture.  To simplify the presentation, we assume these three kinds of operations cause a scene. The  instruction flow sequence of a traditional implementation is shown here. We cannot that  when different threads within the same web are divergent in handling both intervals  and residues, they cannot execute concurrently and need two steps to make all threads get  the information of at least one neighbor. Through this figure, we can find that the current  instruction concurrency is not good and a large amount of computing resources are visited.  Hence we propose a set of optimizations to better utilize GPU's power. The first one  is two-phase traversal. As we can see from the previous example, one reason for the low  concurrency is that when the threads are expanding neighbors of frontier, the threads are divergent  in reading intervals and residues. In the meanwhile, when an interval is decoded, all  neighbors belonging to such an interval are aware and can be handled in parallel. Hence  we divide the expansion into two phases, the interval phase and the residue phase. We first  expand neighbors from intervals and in this phase, threads who hold an interval will try  to occupy the whole web of threads and dispatch its neighbors to them. After all neighbors  represented by intervals are handled, we will start to handle neighbors represented by residues.  So far, we can see that the concurrency of the interval phase is good, but the computing  resources are still visited a lot in the residue phase. Hence we propose task stealing, meaning  that when in the residue phase, we will first decode enough information from CGR and handle  the decoded neighbors cooperatively. So far, compared with the original straightforward  solution, it is much better. And it is easy to note that the bottleneck  of current solution is the imbalance loading when decoding residues. Unfortunately, such  issue is quite common in most graph data. Hence we propose the web-centric decoding.  The main reason for the bottleneck is that when using VLC to encode CGR, it is not easy  to decode multiple residues concurrently because the beginning bit position or the off-site  of each VLC encoding is unknown before its predecessor is decoded. Let's take an example.  Assume that we have a beta ray that includes five VLC encodings, one, two, three, four,  five, respectively. And the encodings of these five numbers are a total of 17 bits. Except  for the first encoding, we cannot know where the other encoding start. We even cannot know  how many encodings are encoded in a particular bit range.  Hence we have to assign a thread to start from each bit position. Each thread then decodes  a number according to its beginning bit position. Apparently, only the decodings of those threads  starting from a real VLC beginning position are valid. So it is required to identify which  decodings are valid among all decoded candidates.  Based on the SI-MT execution, we can mark candidates at an exponential rate, meaning  that every marked thread can mark a new valid decoding at each round. So far, for imbalanced  residues, we can use idle threads to decode long residue chain concurrently.  In addition, we know that there exists some nodes whose residue sequences are remarkably  longer than those of other nodes in real-world graphs. This leads to low parallelism and degraded  performance. To achieve a better load balancing, we divide a long residue sequence into smaller  segments for fine-grained workload partitioning. Decomposing the long residue chain into fixed  length segments, we can easily handle them by multiple threads.  So far, we have introduced the methodology proposed for efficient tremors in compressed  graphs on the GPU. Next, let's look at the experimental evaluation results. We collect  two web graphs, two social network graphs, and one biology graph throughout this work.  In order to verify the effectiveness of each proposed optimizations on the performance,  we apply the technique incrementally and illustrate the incremental results in this figure.  The two-phase traversal aims to avoid web divisions when threads fall into different logic branches,  executing as an interval or a residue decoding. The task stealing is used for, in a situation  when the residue number varies significantly. And the web centric shows a relatively stable  improvement for a better hardware utilization and poses a larger impact when the average  base per edge is fever. The Twitter graph exhibits a severe, severe-skilled distribution,  and thus the execution is bottlenecked by several nodes with an extremely large outdegree.  So the residue segmentation has a larger impact on the Twitter graph.  Next, let's look at the comparison between different baselines. To evaluate our proposal,  we compare it with several state-of-the-art CPU-based and GPU-based graph traversal approaches,  including the single-threaded solution, the parallel solution on compressed graph, the  GPU graph platform, the GPU-based standalone implementation, and our proposal, the GPU-based  graph traversal on compressed graphs. We use bar plots to denote each approach's  elapsed time of graph traversal and the compression rates are illustrated in the line plots with  black dots. According to this result, we can verify that the GPU is a peeling accelerator  for graph analytics, and compare with approach based on the traditional non-compressed graph  format. We can see that with a considerable compression rates, our proposal only introduces  a very low overhead on the performance. In conclusion, in this work, we identify the  limitation of GPU-based memory and introduce compressed graph into GPU-based graph computation  for optimized device memory usage. For the hardware characteristics of the GPU, we propose  a series of optimizations so that the compressed graph can be efficiently traversed on the  GPU, and extensive experiments show that with a considerable compression rate, our proposal  achieves competitive efficiency compared with state-of-the-art graph traversal approaches  on uncompressed graphs. That's all. Thank you for listening.
Sha_Li_Tan_0_143.png Sha_Li_Tan_144_227.png Sha_Li_Tan_228_275.png Sha_Li_Tan_276_323.png Sha_Li_Tan_324_371.png Sha_Li_Tan_372_851.png Sha_Li_Tan_852_6023.png Sha_Li_Tan_6024_10259.png Sha_Li_Tan_10260_12047.png Sha_Li_Tan_12048_12203.png Sha_Li_Tan_12204_13883.png Sha_Li_Tan_13884_15563.png Sha_Li_Tan_15564_15611.png Sha_Li_Tan_15612_15839.png Sha_Li_Tan_15840_17111.png Sha_Li_Tan_17112_17891.png Sha_Li_Tan_17892_21983.png Sha_Li_Tan_21984_22439.png Sha_Li_Tan_22440_22943.png Sha_Li_Tan_22944_22991.png Sha_Li_Tan_22992_23119.png