# High Performance Graph Data Imputation on Multiple GPUs
## 6 Performance Evaluation
### Results and Analysis
We set the missing rate to 20% and configure the algorithm to execute for 20 iterations with \(\epsilon=10^{-8}\). Both the GPU implementation and the CPU implementation achieve low recovery errors in the order of \(10^{-5}\) (i.e., good accuracy). In addition, the rMSEs of the GPU implementation are very close to those of the CPU MATLAB implementation under different sizes of graph-tensors, which validates the correctness of the GPU implementations. For the graph-tensor of size \(50\times 50\times 4039\) generated from the real-world ego-Facebook graph [27], we vary the missing rates from 5% to 50% and evaluate the performance of algorithms. Figure 10 shows the running time and speedups of the CPU MATLAB, GPU-baseline, and GPU-optimized implementations. We can observe that as the growth of the missing rates, the recovery time also increases both on CPU and GPU. The average running time of the CPU implementation, the GPU-baseline implementation, and the GPU-optimized implementation is 1051.73 s, 522.04 s and 6.75 s, respectively. Compared to the GPU-baseline implementation, the GPU-optimized implementation achieves up to 77.88\(\times\) speedups. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**GPU Algorithm** & **Total Time** **(s)** & **SVD Time** **(s)** & **GFT Time** **(s)** & **Memory** **Copy Time** **(s)** & **Right-Singular Vectors Time (s)** \\ \hline
**GPU-baseline** & 149.54 & 146.37 & 0.27 & 1.96 & - \\
**GPU-optimized** & 2.47 & 1.43 & 0.27 & 0.11 & 0.02 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Running time breakdown for a graph-tensor of \(64\times 64\times 2100\) using nvprof. Figure 8: Running time of the GPU-base baseline, optimized, and multi-GPU implementations and the CPU MATLAB implementation with large-scale synthetic graph-tensors of \(512\times 512\times k\). Speedups of the GPU-optimized and multi-GPU implementations correspondingly. Graph-tensors of \(512\times 512\times 2600\) and larger exceed the capability of a single GPU. For the graph-tensor of size \(50\times 50\times 4039\) generated from the real-world ego-Facebook graph [27], Table 3 shows the average recovery errors of the CPU implementation and the GPU implementation under varying observing rates \(N_{obs}\) from \(0.5N\) to \(0.9N\), where \(N=4039\) (i.e., the number of vertices). The rMSEs decreases with the increasing of observing rates both on CPU and GPU since fewer slices are missed in the graph-tensors. Besides, the GPU implementation achieves the same rMSEs with the CPU implementation on all observing rates. Figure 10: Running time and speedups of the graph-tensor imputation with the ego-Facebook graph [27] under varying missing rates on GPU and CPU, respectively. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(N_{obs}=\) & \(\mathbf{0.5}N\) & \(\mathbf{0.6}N\) & \(\mathbf{0.7}N\) & \(\mathbf{0.8}N\) & \(\mathbf{0.9}N\) \\ \hline CPU & 0.038 & 0.032 & 0.018 & 0.008 & 0.001 \\ GPU & 0.038 & 0.032 & 0.018 & 0.008 & 0.001 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Average relative mean square errors (rMSEs) under varying observing rates. Figure 9: The relative square errors of the algorithm with synthetic graph-tensors of different sizes on GPU and CPU, respectively.