Embodiments include method, systems and computer program products for performing memory-aware matrix factorization on a graphics processing unit. Aspects include determining one or more types of memory on the graphics processing unit and determining one or more characteristics of each of the one or more types of memory. Aspects also include assigning each of a plurality of memory accesses of a matrix factorization algorithm to one of the one or more types of memory based on the one or more characteristics and executing the matrix factorization algorithm on the graphics processing unit.

BACKGROUND

The present disclosure relates to matrix factorization and more specifically, to methods, systems and computer program products for performing memory-aware matrix factorization.

Recommendation systems are becoming more and more pervasive in Internet applications such as music sharing, e-commerce, and on-demand Internet streaming media. Moreover, recommendation systems can be combined with other applications, like ranking and filtering, to develop new products in online advertisement and user-centric information retrieval. A common technique used in recommendation systems is the factorization of a user-item matrix R, whose entries at (u; v) denote a preference of user u on item v. This user-item matrix R is generally a sparse matrix and matrix factorization is used to generate estimated entries for the entries that have null, or zero values. A matrix-factorization based collaborative filter is generally considered one of the best models for recommendation systems.

The problem of matrix factorization is to decompose matrix R into two dense matrixes X and Θ, such that: R≈X·ΘT. Assuming that ru,vis an non-zero element of matrix R at position (u; v), the matrix factorization can be accomplished by the minimization of the following cost function:

J=∑u,v⁢⁢(ru,v-XuT⁢θv)2+λ(∑u⁢nxu⁢Xu2+∑v⁢nθv⁢θv2)(1)
where xTuand Θvare the uth row of X and the with column of ΘT, respectively.

The optimization of the above cost function (1) can be done through many classical optimization methods, including alternative least square, coordinate descent and stochastic gradient descent have been applied to solve this problem. The nature of matrix factorization is computation expensive and accordingly, for real-life, industry-scale matrix factorization problems, parallel computing is often used. Parallelizing the optimization problem of matrix factorization is difficult because many classical algorithms for matrix factorization are sequential instead of parallel. There have been a lot of efforts in applying parallel computing methods for matrix factorization, especially in the scenario of shared memory, CPU-based systems. However, such methods suffer from locking, discontinuous memory access and memory hotspots.

SUMMARY

In accordance with an embodiment, a method for performing memory-aware matrix factorization is provided. Aspects include determining one or more types of memory on the graphics processing unit and determining one or more characteristics of each of the one or more types of memory. Aspects also include assigning each of a plurality of memory accesses of a matrix factorization algorithm to one of the one or more types of memory based on the one or more characteristics and executing the matrix factorization algorithm on the graphics processing unit.

In accordance with another embodiment, a graphics processing unit for performing memory-aware matrix factorization includes a processor configured to perform a method. Aspects include determining one or more types of memory on the graphics processing unit and determining one or more characteristics of each of the one or more types of memory. Aspects also include assigning each of a plurality of memory accesses of a matrix factorization algorithm to one of the one or more types of memory based on the one or more characteristics and executing the matrix factorization algorithm on the graphics processing unit.

In accordance with a further embodiment, a computer program product for performing memory-aware matrix factorization includes a non-transitory storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method. Aspects include determining one or more types of memory on the graphics processing unit and determining one or more characteristics of each of the one or more types of memory. Aspects also include assigning each of a plurality of memory accesses of a matrix factorization algorithm to one of the one or more types of memory based on the one or more characteristics and executing the matrix factorization algorithm on the graphics processing unit.

DETAILED DESCRIPTION

In accordance with exemplary embodiments of the disclosure, methods, systems and computer program products for performing memory-aware matrix factorization are provided. In exemplary embodiments, a method for executing a matrix factorization algorithm on a graphics processing unit includes determining available types of memory on the graphics processing unit and one or more characteristics for each type of available memory. The method also includes assigning the storage of each variable used by the matrix factorization algorithm to one of the available types of memory based on the characteristics for each type of available memory. In exemplary embodiments, the performance of the graphics processing unit in executing the matrix factorization algorithm is improved by assigning the storage of each variable used by the matrix factorization algorithm to one of the available types of memory based on the characteristics for each type of available memory. In exemplary embodiments, the matrix factorization algorithm is an alternating least square (ALS) algorithm.

In exemplary embodiments, by storing each of the variables used by a matrix factorization algorithm to a type of memory based on the characteristics of the memory, the memory accesses of the matrix factorization algorithm can be optimized. The optimization can include reducing discontiguous memory access and/or caching hotspot, or frequently accessed variables. For example, the optimization of the memory access can include transforming discontiguous memory accesses to contiguous memory accesses, and allocating faster memory to hotspot variables. As a result, the performance of the graphics processing unit, and by extension the computer system having the graphics processing unit, in executing the matrix factorization algorithm is improved.

Thus, as configured inFIG. 1, the system100includes processing capability in the form of processors101, storage capability including system memory114and mass storage104, input means such as keyboard109and mouse110, and output capability including speaker111and display115. In one embodiment, a portion of system memory114and mass storage104collectively store an operating system such as the AIX® operating system from IBM Corporation to coordinate the functions of the various components shown inFIG. 1.

Referring now toFIG. 2, a graphics processing unit200is illustrated. The graphics processing unit200includes one or more processors202that each include a plurality of registers204. The graphics processing unit200also includes a shared memory206, which may also be embodied in a cache memory. In exemplary embodiments, the access latency for the shared memory206is greater than the access latency for the registers204, but is less than other memory types available to the processors202. The graphics processing unit200also includes a texture memory208, which is a read-only memory which may be embodied in a cache memory. In exemplary embodiments, the access latency for the texture memory208is greater than the access latency for the registers204and the shared memory206, but is less than other memory types. The graphics processing unit200also includes a global memory210, which may be embodied in a DRAM or other suitable type of memory. In exemplary embodiments, the access latency for the global memory208is greater than the access latency for the registers204, the shared memory206and the texture memory208. In exemplary embodiments, the texture memory208can be used to store cached entries from a global memory210. In exemplary embodiments, the global memory210is relatively slow, the texture memory208is read only, and the register204and shared memory206are not visible across kernels (i.e., GPU device functions).

In general, the implementation of matrix factorization algorithm on a graphics processing unit200is more complex than implementing the matrix factorization algorithm on a general processor or CPU. One reason is due to the lower clock frequency (e.g., 850 Hz) of a graphics processing unit200than CPU (e.g., 2 GHz). Another reason is that the graphics processing unit200typically includes less memory (e.g. 4-12 GB) than a CPU (e.g., 32-256 GB). In addition, the control of registers, shared and texture memory is not as easily performed in a graphics processing unit200as it is in a CPU. This is because the compilers on GPUs are less powerful in automatically managing a complex memory hierarchy, and as a consequence GPU programmers have to make more explicit control of the memory hierarchy.

One approach to optimize the non-convex cost function in (1) is to iteratively optimize X while fixing Θ, and then optimize Θ while fixing X. Consider:

∂J∂xu=0∂J∂θv=0
Which leads to the following equation:

θv·∑ruv≠0⁢(Xu⁢XuT+λ⁢⁢I)=XT·R⁡(:,v)(3)
which is known as the alternating least squares (ALS) method. As used herein, λ is a user-provided real number for regularization purpose; I is an identity matrix of dimension f (f is the number of columns of X).

The computational cost of executing the ALS method can be analyzed by the following solution as a representation to update xuand Θv:

As can be seen in Eq. (4), X and Θ are updated alternatively and iteratively, while the update of each xuand Θvare independent of each other, respectively. Eq. (4)'s memory access comes in several aspects including: accessing a row R(u; :) or a column R(: ; v) from the user-item matrix R; accessing collection of columns Θvsubject to ru;v≠0 for every u; and accessing collection of rows xTusubject to ru;v≠0 for every v; aggregating many Θv·ΘvTfor every u; and aggregating many xu·xTufor every v.

In each iteration of Eq. (4) to solve for X and Θ, a certain row or column of R needs to be accessed only once. In contrast, in each iteration, to solve for a single xu, a Σv1 ru;v≠0number of columns spread discontiguously across the many columns in ΘTneed to be accessed. For example, in a sample data set, assume on average one user rates 200+ items; this leads to a discontiguous access of 200+Θvcolumns among the total 17,770 columns in ΘT. Similarly, to solve for a single Θv, a Σu1 ru;v≠0number of rows of X need to be accessed.

In addition, according to Eq. (4), solving for one xurequires computing and aggregating Θv·ΘvT. Therefore, each element in column vector Θvis accessed frequently, and the aggregation updated frequently. Suppose the dimensionality of Θvis f, then to compute Θv·ΘvT, each element of Θvwill be read f times and to add Θv·ΘvTto Σru;v≠0(Θv·ΘvT+λI) will require f2writes. Table 1 compares the cost from these three types of memory accesses.

In exemplary embodiments, a method for performing memory aware matrix factorization reduces the cost of memory access. In exemplary embodiments, the number of memory access may not be reduced from traditional matrix factorization. However, the method for performing memory aware matrix factorization transforms discontiguous memory accesses to contiguous memory accesses and allocates faster memory to hotspot variables to reduce the cost of the memory access.

In exemplary embodiments, a given column vector Θvis needed to update many xus as long as ru;v≠0. Therefore one Θvwill be read Σu1 ru;v≠0many times and is worth storing in a cache memory. Also, updating a given column vector xurequires many Θvs as long as ru;v≠0. Accordingly, in exemplary embodiments, discontiguous memory accesses can be reduced by caching all needed Θvs in the memory space of xuupdate, so that later computation on Θvs does not need to access the discontiguous memory again. In exemplary embodiments, memory accesses can further be optimized by caching hotspot variables. In one embodiment, the aggregation variable Σru;v≠0(Θv·ΘvT+λI) is stored in register because it needs to be updated frequently, i.e., each time a Θv·ΘvTis added in.

The challenge of implementing such changes to the memory accesses is that, in any computer architecture with a memory hierarchy, faster memory such as cache is a limited resource. Therefore, both the memory access patterns of the matrix factorization algorithm and the memory hierarchy, capacity and characteristics of a given computer hardware need to be considered. For example, all needed Θvs, and Σru;v≠0(Θv·ΘvT+λI) for a single xumay be too big to store in the cache memory of a graphics processing unit and therefore the computation and caching may need to be performed in stages. In exemplary embodiments, the memory aware method performing matrix factorization includes selecting Θvaccording to the constraint ru;v≠0, which is different from the traditional dense matrix multiplication, and since there are many Θv·ΘvTof executed in parallel, careful allocation of the multiple processors to utilize the limited cache is needed for efficient computing.FIG. 3Bis an alternating least square (ALS) algorithm for performing memory-aware matrix factorization in accordance with an exemplary embodiment.

When running Algorithm 1, shown inFIG. 3A, it was observed that about 80% of the total execution time lies in computing Au, while generating Buand solving the equations take about 20% of the total execution time. Accordingly, in order to efficiently compute Au, the memory accesses need to be optimized, as discussed in further detail below.

As shown in line 2, Algorithm 1 includes reading from ΘT·ΘTwhose dimension is f×n, is stored in global memory. Accordingly, when collecting submatrix ΘuTfrom ΘT, texture memory is used as cache because the collecting process enjoys spatial locality and because ΘTis read-only, as is shown in line 2 of Algorithm 2. In addition, different ΘuTcan potentially re-use the same Θvs cached in texture memory. In exemplary embodiments, this caching step also reduces discontiguous memory access.

As shown in line 2, caching the read-only ΘTin texture memory reduces the need for concurrency control since the data ΘTwill not be changed by any thread that accesses it. With this hint, the graphics processing unit can speed up the memory access.

As shown in line 2, Algorithm 1 includes storing ΘuT. In exemplary embodiments, one thread block consisting off threads is used to solve each xu, and the per-block shared memory is used to store ΘuT, so as to speed up the subsequent read in line 5. However, for each block, the whole ΘuTis not copied into its shared memory space because ΘuTis of size f×nxu(recall that nxuis the number of items user u has rated) and is too large compared to the shared memory. If a single thread block consumes a large portion of the limited shared memory, other blocks that cannot obtain the shared memory are prohibited from launching, resulting in low parallelism in the graphics processing unit. To achieve a higher parallelism and utilization, for each xu, instead of allocating an f×nxublock, a bin size bin is selected and a block ΘuT[bin] of size f×bin is allocated. In exemplary embodiments, a bin between 10 and 20 can be used, while nxucan be hundreds or thousands. A subset of ΘuTis iteratively moved into ΘuT[bin] to be processed in the following step.

As shown in line 5, Algorithm 1 includes writing Auby reading a Θvfrom ΘuT[bin], calculating the f×f elements of ΘvΘvT, and adding them to global memory Au. Since Auis a memory hotspot, it is stored in the register memory to partially aggregate

∑θv⁢⁢_∈ΘuT⁡[bin]⁢θv⁢θvT
and only need to update global memory Auafter iterating over all columns in ΘuT[bin]. In exemplary embodiments, storing Auin the register memory reduces global memory access by a factor of nxu.

FIG. 3Billustrates an alternating least square (ALS) algorithm for performing memory-aware matrix factorization in accordance with an exemplary embodiments. As illustrated, each of the memory accesses of the algorithm have been assigned to one of the various types of memory available on the graphics processing unit based on the characteristics of the memory type and upon the type of memory access.

Referring now toFIG. 4, a flow diagram of a method400for performing memory-aware matrix factorization on a graphics processing unit in accordance with an exemplary embodiment is shown. As shown at block402, the method400includes determining one or more types of memory on the graphics processing unit. In exemplary embodiments, the one or more types of memory may include registers, cache and global memory, such as DRAM. Next, as shown at block404, the method400includes determining one or more characteristics of each of the one or more types of memory. In exemplary embodiments, the characteristics may include, but are not limited to, size, access latency, read/write permissions, and the like. In exemplary embodiments, the cache may be divided into shared memory and texture memory, wherein the texture memory is a cache memory that is read-only. In exemplary embodiments, the texture memory is used to store cached entries from a global memory. In exemplary embodiments, the shared memory may not be visible across kernels (i.e., GPU device functions). Next, as shown at block406, the method400includes assigning each of a plurality of memory accesses of a matrix factorization algorithm to one of the one or more types of memory based on the one or more characteristics. In exemplary embodiments, the assignment of memory accesses to the memory types is configured to reduce discontiguous memory access and/or to cache hotspot, or frequently accessed, variables. In exemplary embodiments, the each of the memory accesses have one or more attributes that include, but are not limited to, a frequency that a stored variable is accessed and a contiguousness that accessed data is stored in the memory. The assignment of the memory accesses to the memory types is configured to align the attributes of the memory accesses with the characteristics of the memory types. The method400also includes executing the matrix factorization algorithm on the graphics processing unit, as shown at block408.