Hierarchical clustering with CUDA/GPU

摘要

Graphics processing units (GPUs) are powerful computational devices tailored towards the needs of the 3-D gaming industry for high-performance, real-time graphics engines. Nvidia Corporation provides a programming language called CUDA for general-purpose GPU programming. Hierarchical clustering is a common method used to determine clusters of similar data points in multidimensional spaces; if there are n data points, it can be computed in O(n~2) to O(n~2 log n) sequential time, depending on the distance metrics employed. The present work explores parallel computation of hierarchical clustering with CUDA/GPU, and obtains an overall speed-up of up to 48 times over sequential computation with an Intel Pentium CPU.