GPU-based Implementations And Applications Of Clustering Algorithms

With the development of Internet, cloud computing and mobile computing, high-quality and efficient natural language applications greatly facilitate intelligent human-computer interaction. Unfortunately, most high-quality natural language applications employ large statistical models, quality gains at the expense of time cost. Nowadays, Graphics Processor Units(GPUs) have been widely used because of its general purpose parallel computing model and high-parallel hardware. GPU provides an efficient solution to improve algorithm’s performance by exploiting the fine-grained data parallelism in it.This thesis analyzes the possibility of parallelizing two natural language processing algorithm, affinity propagation clustering and brown clustering. In affinity propagation clustering algorithm, hierarchical affinity propagation idea is used to break the bottleneck of GPU’s global memory limitation when dealing with large-scale corpus. The computing architecture is a combination of CPU and GPU, use thread-based mapping and block-based mapping to parallelize computationally intensive parts. We use Compute Unified Device Architecture(CUDA) to re-implement the algorithm and compare its performance on both CPU and GPU. In Chinese handwriting character recognition application, compared with the optimized sequential C implementation, speedup is around 228 times. In brown clustering algorithm, use the idea of class-based bi-gram language model and optimization with fixed window size, proposed a special storage scheme of sparse matrix. The algorithm is optimized with parallel methods of thread-based mapping and block-based mapping and various synchronization methods. In drug name identification application, the speedup is around 66 x without loss of accuracy and it scales up when increasing the amount of training corpus and clustering numbers. In query intent detection application, this implementation overcomes the difficulties of CPU-based brown clustering, which can’t handle large-scale corpus in reasonable time. The optimized algorithm can handle GB level data within a few minutes. Experimental result shows that the combination of brown feature and other features leads to a 2 percentage point increase in the cross validation accuracy. Then an analysis of what influence that brown features based on different amount of corpus and different number of clusters will exert on system performance is performed.