# High Performance Graph Data Imputation on Multiple GPUs
## 5 Large-Scale and Multi-GPU Graph-Tensor Imputation  
Real-world graphs such as Facebook and Twitter networks have more than one billion vertices, which poses challenges for the graph-tensor imputation on a single GPU because of limited computing cores and device memory. The SVD computation consumes lots of device memory, including the buffer size calculated by cusolverDnDSyved_bufferSize(.) and variables \(\mathcal{U},\mathcal{S},\mathcal{V}^{T}\) that store the calculated results. In addition, the required computing cores increase rapidly with the growing size of graphs. Therefore, it is beneficial to scale the GPU convolutional imputation algorithm onto multiple GPUs in order to support the computing of large-scale graph-tensors that beyond the device memory capacity of a single GPU. We design a multi-GPU scheme for the convolutional imputation algorithm, as shown in Figure 5. Since the data reorganizing step in GFT and iGFT computation requires the entire graph-tensor as input, and the computing time of GFT and iGFT only accounts for a small part of the total time, the multi-GPU scheme is focused on the computation of singular value soft-threshold on multiple GPUs, which includes the compute-intensive SVD operation.  
The multi-GPU scheme uses CUDA and OpenMP as a hybrid. Assuming that there are \(n\) GPUs on a computing node, the scheme use \(n\) OpenMP threads to control \(n\) GPUs for computation and communication, respectively. In the scheme, after allocating memory for input \(\mathcal{P}_{\Omega}(\mathcal{G})\) and \(\Omega\) on all GPUs, the scheme performs the following major steps in each algorithm iteration:  
* GPU\({}_{0}\) utilizes a partitioning strategy to split the frontal slice of \(\mathcal{G}_{t}^{\text{est}}\) into \(n\) partitions, then sends a partition to each of the other \(n-1\) GPUs by using a peer to peer, asynchronous memory transferring routine in the CUDA library [24]. Each GPU computes its own part of \(\mathcal{G}^{\text{impute}}\) independently and sends the result back to GPU\({}_{0}\);
* GPU\({}_{0}\) performs synchronization to ensure results are received from all GPUs, then performs GFT computation to obtain \(\vec{\mathcal{G}}^{\text{impute}}\);
* GPU\({}_{0}\) utilizes a partitioning strategy to split \(\vec{\mathcal{G}}^{\text{impute}}\) into n partitions, then sends a partition to each of the other \(n-1\) GPUs by using a peer to peer, asynchronous memory transferring routine. All GPUs perform singular value soft-threshold computation with their own data independently. After the completion of computation, each of the other \(n-1\) GPUs sends the result back to GPU\({}_{0}\).  
\(\bullet\) GPU\({}_{0}\) performs synchronization to ensure all GPUs finish their tasks and then performs the iGFT computation.  
In this scheme, using OpenMP threads achieves overlap of communications and eliminates the use of cudaSetDevice(.) routine in the CUDA library to switch GPU during computation. Besides, we utilize peer to peer, asynchronous communications between GPUs, which transfers data between a pair of GPUs directly without accessing CPU memory. To make full use of device memory, variables are immediately released when they are no longer needed in each step.  
The data partition strategy is based on GPU hardware performance that can be obtained from the GPU specification on the NVIDIA website [25; 26]. The size of the data partition received by a GPU is proportional to its hardware performance. For instance, we use \(P_{i}\) to denote the performance of GPU\({}_{i}\), then GPU\({}_{i}\) receives \(R_{i}\) frontal slices for processing, where \(R_{i}\) is the number of frontal slices distributed to GPU\({}_{i}\) and \(\dfrac{R_{i}}{P_{i}}=\dfrac{R_{j}}{P_{j}}\), \(i,j\in[n]\).