# High Performance Graph Data Imputation on Multiple GPUs
## 6 Performance Evaluation
### Results and Analysis  
We evaluate and compare the performance of the CPU MATLAB implementation and three GPU implementations: baseline, optimized, and multi-GPU implementations. We show running time of all implementations, and calculate the speedups of the GPU-optimized and multi-GPU implementations over the GPU-baseline implementation respectively. By comparing with the GPU-baseline implementation, we show the effectiveness of our optimization schemes in the GPU-optimized and multi-GPU implementations. In addition, we test small-scale, medium-scale, and large-scale synthetic graph-tensors with sizes of \(64\times 64\times k\), \(128\times 128\times k\), and \(512\times 512\times k\), respectively, where \(k\) varied from 100 to 4600. For the application of the GPU algorithm, we test graph-tensors of size \(50\times 50\times 4039\) generated from the real-world ego-Facebook graph [27] at different sampling rate. We use single-precision floating-point in all implementations. Figures 6-8 show the running time and speedups of the CPU and GPU implementations using synthetic data of different size. Compared to the CPU MATLAB implementation running on an Intel Core i7-7820x CPU, the GPU-baseline implementation achieves up to 4.56\(\times\), 8.54\(\times\), and 6.41\(\times\) speedups for graph-tensors of size \(64\times 64\times k\), \(128\times 128\times k\), and \(512\times 512\times k\), respectively. Compared to the GPU-baseline implementation, the GPU-optimized implementation achieves up to 60.50\(\times\), 15.55\(\times\), and 2.46\(\times\) speedups for graph-tensors of size \(64\times 64\times k\), \(128\times 128\times k\), and \(512\times 512\times k\), respectively. With the optimizations in Section 4.2, the GPU-optimized implementation achieves much better performance versus the GPU-baseline implementations. Table 2 shows the running time breakdown for a graph-tensors of size \(64\times 64\times 2100\) using the nvprof tool. In the GPU-optimized implementation, the SVD computation time is significantly reduced compared to the GPU-baseline implementation. The memory copy time is also reduced because the computations are overlapped with the communications using CUDA streams. As shown in Figure 8, both the GPU-baseline and the GPU-optimized implementations are unable to process graph-tensors of \(512\times 512\times 2600\) or larger due to limited resources (i.e., device memory and computing cores) on a single GPU. This motivates us to develop the multi-GPU scheme. The multi-GPU scheme has two major advantages: performance improvement and supporting large-scale graph-tensors. As shown in Figures 6-8, compared to the GPU-baseline implementation on a single GPU, the multi-GPU implementation achieves up to 60.29\(\times\), 25.76\(\times\), and 4.42\(\times\) speedups for graph-tensors of size \(64\times 64\times k\), 128 \(\times\) 128 \(\times\) \(k\), and 512 \(\times\) 512 \(\times\) \(k\), respectively. Compared to the GPU-optimized implementation on a single GPU, the multi-GPU implementation achieves up to 1.81\(\times\) speedups. On small-scale graph-tensors, the multi-GPU implementation running on two GPUs is slightly slower than the GPU-optimized implementation running on a single GPU, as shown in Figure 6. The reason is that there is overhead introduced by data splitting and the synchronization among multiple GPUs. For medium-scale and large-scale graph-tensors, the multi-GPU implementation running on two GPUs significantly outperforms the GPU-optimized implementation running on a single GPU, as shown in Figures 7 and 8. The performance improvement of computing on multiple GPUs outweighs the overhead introduced by the multi-GPU scheme. In addition, Figure 8 shows that the multi-GPU implementation can process large graph-tensors of \(512\times 512\times 2600\) or larger, which are not supported by the GPU-baseline or GPU-optimized implementations running on a single GPU. Figure 9 shows the rMSE of graph-tensor imputation algorithm with synthetic data on CPU and GPUs, respectively.