Data Clustering Algorithms on the GPU: Challenges and Benefits

Data clustering techniques are an essential component of most data analysis toolkits. With the availability of simplified APIs for using graphics processors as general purpose computing platforms, speed-ups of one to two orders of magnitude for certain types of algorithms can be achieved. While an initial, correct implementation of any given algorithm in GPU-specific code may closely follow an equivalent CPU code, achieving significant speed-ups often requires a complete rethinking of the underlying design decisions. This in turn necessitates a thorough understanding of the challenges involved in programming such massively parallel architectures. Focusing on Nvidias graphics processors and the CUDA compute platform the talk will include a brief introduction to GPU computing before providing an overview of the design considerations and challenges that have to be addressed when writing highly optimized code. The benefits will be discussed by the specific example of a new open-source data clustering library that is being developed jointly by groups at Stanford University and SFSU. This discussion will center around examples such as hierarchical clustering, which is parallelizable only to a certain extent, as well as parallel K-means, an algorithm that is capable of delivering up to two orders of magnitude speed-up for large data sets when compared to serial CPU code.