System and method for high performance
View Patent ↗Provided is a high-performance implementation of the k-means clustering algorithm on a graphics processing unit (GPU), which leverages a set of GPU kernels with complimentary strengths for datasets of various dimensions and for different numbers of clusters. The concepts of non-dominated GPU kernels and efficient strategies to select high-throughput kernels that match the arguments of the clustering problem with the underlying GPU hardware for maximum speedup are provided.
1. A method of performing a k-means clustering algorithm using a graphics processing unit (GPU) to perform operations on an electronically stored dataset, the method comprising:
identifying a set of k-means GPU kernels, the k-means GPU kernels including (i) k-means GPU assignment kernels and (ii) k-means GPU update kernels;
identifying a set of test dimensions;
identifying a set of test numbers of clusters;
creating a test problem for each combination of the test dimensions and the test numbers of clusters, wherein an assignment k-means GPU kernel or update k-means GPU kernel is labeled as a k-means GPU assignment α-kernel or an k-means GPU update α-kernel if and only if it achieves the best performance among all the k-means GPU assignment kernels or k-means GPU update kernels for at least one combination of the test dimensions and the test numbers of clusters;
writing test results to an electronic table or a file that records (i) the set of k-means GPU assignment and update α-kernels discovered and (ii) the best k-means GPU assignment and update α-kernels for each combination of the test dimensions and the test numbers of clusters, such that already-tested kernel and parameter combinations do not have to be tested again on the same GPU hardware;
applying, once a set of k-means GPU assignment α-kernels and a set of update α-kernels are determined, an intelligent kernel selection algorithm to the set of the α-kernels to (i) select one of the k-means GPU assignment α-kernels as the assignment kernel for a given number of dimensions and a given number of clusters, and (ii) select one of the k-means GPU update α-kernels as the update kernel for a given number of dimensions and a given number of clusters; applying (i) the selected assignment α-kernel to perform an assignment phase of the k-means algorithm, and (ii) the selected update α-kernel to perform an update phase of the k-means algorithm; and repeating the applying of the selected assignment α-kernel and the selected update α-kernel until cluster centroids assigned to the clusters reach an accepted state;
wherein at least one of the k-means GPU kernels is configured to bind input data stored in a global memory of the GPU to a texture memory of the GPU, when a number of floats encoding the input data is less than a hardware limit for a ID texture memory of the GPU.
2. The method of claim 1 wherein at least one of the k-means assignment GPU kernels accesses the cluster centroids stored in a global memory of the GPU without first loading the cluster centroids into a shared memory of the GPU, and the at least one k-means assignment GPU kernel is further configured to prefer a L1 cache of the GPU over the shared memory of the GPU.
3. The method of claim 1 wherein at least one of the k-means assignment GPU kernels loads the cluster centroids or at least some of the centroids into a shared memory of the GPU, and the at least one k-means assignment GPU kernel is configured to prefer the shared memory of the GPU over L1 cache of the GPU.
4. The method of claim 3 wherein implementing the at least one k-means assignment GPU kernel, further includes performing a loop unrolling technique that eliminates if-statements in order to unroll a centroid-enumeration loop.
5. The method of claim 1 wherein at least one k-means update GPU kernel updates the cluster centroids stored in a global memory of the GPU without first loading the cluster centroids into a shared memory of the GPU, and the at least one k-means update GPU kernel is configured to prefer a L1 cache of the GPU over the shared memory of the GPU.
6. The method of claim 1 wherein at least one k-means update GPU kernel updates cluster centroids stored in a shared memory of the GPU, and writes out updated cluster centroids to a global memory of the GPU, and wherein the at least one k-means update GPU kernel is configured to prefer the shared memory of the GPU over a L1 cache of the GPU.
7. The method of claim 1 wherein at least one k-means assignment GPU kernel includes input data which is bound to texture memory.
8. The method of claim 3 wherein the at least one k-means assignment GPU kernel, includes having input data which is bound to texture memory.
9. The method of claim 4 wherein the at least one k-means assignment GPU kernel includes having input data which is bound to texture memory.
10. The method of claim 5 wherein the at least one k-means update GPU kernel has input data bound to texture memory.
11. The method of claim 6 wherein the at least one k-means update GPU kernel has input data bound to texture memory.
12. A graphics processing unit (GPU) based k-means clustering system comprising:
an electronic based memory configured to store a set of k-means GPU kernels, wherein the set of k-means GPU kernels include (i) k-means GPU assignment kernels and (ii) k-means GPU update kernels;
an electronic dataset storage area for storing datasets;
a set of test dimensions;
a set of test numbers of clusters;
a graphics processing unit (GPU) configured to include a test processing area for creating a test problem for each combination of the set of test dimensions and the set of test numbers of clusters, wherein an assignment k-means GPU kernel or update k-means GPU kernel is labeled as a k-means GPU assignment α-kernel or k-means GPU update α-kernel if and only if it achieves the best performance among all the k-means GPU assignment kernels or k-means GPU update kernels for at least one combination of the test dimensions and the test numbers of clusters, and the GPU further configured to apply an intelligent kernel selection algorithm to the set of the identified α-kernels to: (i) select one of the k-means GPU assignment α-kernels as the assignment kernel for a given number of dimensions and a given number of clusters, and (ii) select one of the k-means GPU update α-kernels as the update kernel for a given number of dimensions and a given number of clusters, wherein (i) the selected assignment α-kernel is applied to perform an assignment phase of the k-means algorithm, and (ii) the selected update α-kernel is applied to perform an update phase of the k-means algorithm, and wherein the applying of the assignment α-kernel and the update α-kernel is repeated until cluster centroids assigned to the clusters reach an accepted state; and
a central processing unit (CPU) configured to communicate with the GPU, wherein the CPU stores an electronic table or file that records (i) the set of k-means GPU assignment and update α-kernels discovered and (ii) the best k-means GPU assignment and update α-kernels for each combination of the test dimensions and the test numbers of clusters, such that already-tested kernel and parameter combinations do not have to be tested again on the same GPU hardware;
wherein at least one of the k-means GPU kernels is configured to bind input data stored in a global memory of the GPU to a texture memory of the GPU, when a number of floats encoding the input data is less than a hardware limit for a ID texture memory of the GPU.
13. The system of claim 12 wherein the GPU includes a plurality of GPUs.
14. The method of claim 1 wherein the test problem is a reduced version of an original problem.