Abstract
Dimension reduction has been widely applied in many fields, but it takes a lot of time to process when the data size is large. The rise of GPU computing allows developers using CUDA to solve problems in parallel on GPU. The focus of this thesis is on using CUDA to parallelize the Isomap algorithm, which involves three methods: k-Nearest Neighbor algorithm, Floyd-Warshall algorithm, and Multi-dimensional Scaling. In our approach, we cut the input dataset into small blocks before proposing these solutions so that the block of data can fit in on-chip shared memory, because GPU has limited memory capacity and shared memory is much faster than global memory. Furthermore, we use MAGMA, a GPU-enabled math library, to solve the eigenvalue and eigenvector problem for multidimentional scaling. In the experiments, the input datasets were samples from three dimensional swiss rolls with different number of vertices. Our experiments showed that the processing time of GPU-based program is above 60 times faster than the CPU-based one.