CUDA Matrix Factorization Library with Alternating Least Square (ALS)
Cuda C C++ Makefile Python Jupyter Notebook Shell
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
data changed parameter input of main; added data preparation scripts for n… Jun 24, 2016
hugewiki hugewiki use CG32 by default Oct 27, 2016
images Initial commit Apr 23, 2016
tensorflow change TF code to use CG Sep 11, 2016
LICENSE Initial commit Apr 23, 2016
Makefile optimize smem load: remove dlcm and ldg, keep __restricted__ Nov 1, 2016
README.md add icpp paper Aug 14, 2018
als.cu replace isnan(a) with a!=a Mar 21, 2017
als.h fix a bug in als.h;change feature initialization and lambda;update RE… Sep 5, 2016
cg.cu nvcc add c++ support; add debug function to save model. Aug 31, 2016
cg.h added fp16 option for tt and xx; reduce latency by 20% per iteration;… Aug 14, 2016
device_utilities.cu added fp16 option for tt and xx; reduce latency by 20% per iteration;… Aug 14, 2016
device_utilities.h added fp16 option for tt and xx; reduce latency by 20% per iteration;… Aug 14, 2016
getRuntime.sh calculate run time from debug output Sep 29, 2016
hermitiantime.sh two scripts to calculate hermitian kernel and solver kernel time Oct 27, 2016
host_utilities.cpp move printf to debug mode. May 7, 2016
host_utilities.h added test script; separated host util functions Apr 26, 2016
main.cpp change theta init for better convergence in Kepler and Pascal Sep 22, 2016
print-test-result.sh get_hermitian: remove redundant computation Sep 28, 2016
solvertime.sh two scripts to calculate hermitian kernel and solver kernel time Oct 27, 2016
test_als.sh get_hermitian: remove redundant computation Sep 28, 2016

README.md

CuMF: CUDA-Accelerated ALS on multiple GPUs.

What is matrix factorization?

Matrix factorization (MF) factors a sparse rating matrix R (m by n, with N_z non-zero elements) into a m-by-f and a f-by-n matrices, as shown below.

Matrix factorization (MF) is at the core of many popular algorithms, e.g., collaborative filtering, word embedding, and topic model. GPU (graphics processing units) with massive cores and high intra-chip memory bandwidth sheds light on accelerating MF much further when appropriately exploiting its architectural characteristics.

What is cuMF?

CuMF is a CUDA-based matrix factorization library that optimizes alternate least square (ALS) method to solve very large-scale MF. CuMF uses a set of techniques to maximize the performance on single and multiple GPUs. These techniques include smart access of sparse data leveraging GPU memory hierarchy, using data parallelism in conjunction with model parallelism, minimizing the communication overhead among GPUs, and a novel topology-aware parallel reduction scheme.

With only a single machine with four Nvidia GPU cards, cuMF can be 6-10 times as fast, and 33-100 times as cost-efficient, compared with the state-of-art distributed CPU solutions. Moreover, cuMF can solve the largest matrix factorization problem ever reported yet in current literature.

CuMF achieves excellent scalability and performance by innovatively applying the following techniques on GPUs:

(1) On one GPU, MF deals with sparse matrices, which makes it difficult to utilize GPU's compute power. We optimize memory access in ALS by various techniques including reducing discontiguous memory access, retaining hotspot variables in faster memory, and aggressively using registers. By this means cuMF gets closer to the roofline performance of a single GPU.

(2) On multiple GPUs, we add data parallelism to ALS's inherent model parallelism. Data parallelism needs a faster reduction operation among GPUs, leading to (3).

(3) We also develop an innovative topology-aware, parallel reduction method to fully leverage the bandwidth between GPUs. By this means cuMF ensures that multiple GPUs are efficiently utilized simultaneously.

Use cuMF to accelerate Spark ALS

CuMF can be used standalone, or to accelerate the ALS implementation in Spark MLlib.

We modified Spark's ml/recommendation/als.scala (code) to detect GPU and offload the ALS forming and solving to GPUs, while retain shuffling on Spark RDD.

This approach has several advantages. First, existing apps relying on mllib/ALS need no change. Second, we leverage the best of Spark (to scale-out to multiple nodes) and GPU (to scale-up in one node). Check this GitHub project for more details. It is also a part of IBM packages for Apache Spark version 2.

Build

Type:

make clean build

To see debug message, such as the run-time of each step, type:

make clean debug

Input Data

CuMF need training and testing rating matrices in binary format, and in CSR, CSC and COO formats. In ./data/netflix and ./data/ml10M we have already prepared (i)python scripts to download Netflix and Movielens 10M data, and preprocess them, respectively.

For Netflix data, type:

cd ./data/netflix/
python ./prepare_netflix_data.py

Note: this can take 30+ minutes. You can download this file from your brower, extract and put the extracted files in ./data/netflix directly.

For Movielens:

cd ./data/ml10M/
ipython prepare_ml10M_data.py

Note: you will encounter a NaN test RMSE. Please refer to the "Known Issues" Section.

Run

Type ./main you will see the following instructions:

Usage: give M, N, F, NNZ, NNZ_TEST, lambda, X_BATCH, THETA_BATCH and DATA_DIR.

E.g., for netflix data set, use:

./main 17770 480189 100 99072112 1408395 0.048 1 3 ./data/netflix/

E.g., for movielens 10M data set, use:

./main 71567 65133 100 9000048 1000006 0.05 1 1 ./data/ml10M/

E.g., for yahooMusic dataset, use:

./main 1000990 624961 100 252800275 4003960 1.4 6 3 ./data/yahoo/

Prepare the data as instructed in the previous section, before you run.

Note: rank value F has to be a multiple of 10, e.g., 10, 50, 100, 200.

Large-Scale Problems

For Netflix data, you need to adjust the number of batches to solve X (movie features) and Theta (user features). When F is 100, we set X_BATCH and THETA_BATCH to 1 and 3, respectively. Check test_als.sh for the reference settings for different F values.

Note: we checked these settings on Kepler, Maxwell and Pascal GPU cards where there is more than 12 GB RAM. If you have cards with small memory capacity, you need to increase X_BATCH and THETA_BATCH to run more (smaller) batches.

Directory hugewiki contains the code to solve the much larger hugewiki data set. Read Section 4 of our [paper] (http://arxiv.org/abs/1603.03820) for more details.

Performance Optimization

Conjugate Gradient Solver

CuMF offers two solvers:

(1) Direct LU solver provided by cuBLAS (http://docs.nvidia.com/cuda/cublas/#cublas-lt-t-gt-getrfbatched). It requires O(n^3) computation and also the implementation on GPU is slow.

(2) Conjugate gradient method (https://en.wikipedia.org/wiki/Conjugate_gradient_method). We implement our own CG kernel.

You can use the CG instead of the LU solver, by uncomment #define USE_CG in als.cu.

Half Precision (FP16)

The CG solver can use FP16 to store the left-hand square matrix. Since the CG solver is memory-bound, this can further improve performance.

Known Issues

We are trying to improve the usability, stability and performance. Here are some known issues we are working on:

(1) NaN test error. This is because in some datasets such as movielens 10M, there are users or items with no ratings in training set but some ratings in test set. To overcome this, we have defined a flag in als.cu (#define SURPASS_NAN). If SURPASS_NAN is defined, we check NaN in calculating RMSE and ignore the NaN values. Normally #define SURPASS_NAN should be commented out, as the additional check slows down the computation.

(2) Multi GPU support. We have tested on very large data sets such as SparkALS and HugeWiki, on multiple GPUs on one server. We will make our multi GPU support code available soon.

Teams

References

More details can be found at: