Abstract
Exorbitant computation cost hinders the practical application of recommendation algorithm, especially in time-critical application scenario. Although experiments show that recommendation algorithm based on an integrated diffusion on user-item-tag tripartite graphs can significantly improve accuracy, diversification and novelty of recommendation, it is also very time-consuming. Therefore, a parallel solution is frequently needed to improve the execution speed of the algorithm. This paper explicitly presents the parallel implementation and optimizations of diffusion-based recommendation on weighted tripartite graphs algorithm using Compute Unified Device Architecture and related optimization solutions including accelerated memory access with shared memory, stream scheduling and GPU clusters optimization. Compared to the algorithm running on a single CPU core, the unoptimized GPU kernel can achieve 153.9 speedup on average with the input dataset consists of 30000 records on GTX 980. With shared memory applied, the time cost on device memory access saves about 50% on dataset of 90000 records and with 2-way streams scheduling, the kernel's performance improves about 7% ~ 13%. Based on the optimized GPU kernel, we evaluate the performance of the recommendation algorithm with customized socket communication mechanism on GPU clusters. And compared to a single GPU node, we achieve 7.55 speedup on clusters of 9 GPUs when recommending for 8000 users. Besides this, the speedup of GPU clusters is also 26.1 times of the speedup of our CPU clusters of 9 nodes and 1586.28 times of serial algorithm on one CPU core. It proves that GPU technology can dramatically improve the algorithm's performance.
Introduction
In the era of information overload, recommendation engines are essential for navigating digital content. While standard systems often rely on simple user-item matrices, these approaches frequently suffer from data sparsity. Integrating user-generated tags into a tripartite graph (User-Item-Tag) significantly enhances recommendation quality by capturing more nuanced relationships. However, the diffusion process required to calculate scores across these complex graphs is computationally intensive, often proving too slow for real-time applications on traditional CPU architectures.
Methods and Parallel Implementation
The core of the research involves parallelizing a diffusion-based algorithm that distributes resources from a starting item to neighboring users and tags, then back to other items. To overcome the performance bottleneck, the researchers implemented several CUDA-based optimizations:
- Kernel Design and Thread Mapping: Independent diffusion loops were mapped to thousands of GPU threads to exploit the intrinsic parallelism of the SIMT (Single Instruction, Multiple Threads) architecture.
- Shared Memory Optimization: To mitigate slow global memory access, on-chip shared memory was utilized to store intermediate arithmetic results, reducing device memory access latency by approximately 50%.
- Stream Scheduling: Two-way asynchronous streams were implemented to hide data transfer latency between the CPU and GPU, allowing the GPU to compute one batch while simultaneously loading the next.
- Customized Cluster Communication: To scale beyond a single node, a lightweight, socket-based communication protocol was developed to synchronize data across a 9-node GPU cluster, avoiding the overhead of heavier standard frameworks like MPI.
Experimental Results
Evaluations were conducted using the MovieLens dataset, scaling from 7,500 to 100,000 records. The performance gains were substantial:
- Single Node Performance: An unoptimized GPU kernel on a GTX 980 achieved a 153.9x speedup over a single CPU core. Shared memory and stream scheduling further boosted performance by 50% and 7-13%, respectively.
- Cluster Scalability: The 9-node GPU cluster provided a 7.55x speedup over a single GPU node, demonstrating efficient scaling with the custom communication protocol.
- Total System Acceleration: The optimized 9-node GPU cluster achieved a massive 1586.28x speedup compared to the serial CPU implementation. When compared to a 9-node CPU cluster, the GPU cluster remained 26.1x faster.
Conclusion
This research demonstrates that GPU clusters can effectively bridge the performance gap for complex graph-based recommendation algorithms. By optimizing memory access and implementing efficient cluster communication, high-quality tripartite graph recommendations become practical for large-scale datasets. Future work will focus on scaling to "mega-datasets" with millions of interactions and exploring alternative hardware accelerators like FPGAs for improved energy efficiency.
Summary updated