以CUDA實作並分析Isomap演算法於非線性之降維問題

A CUDA implementation and analysis of Isomap for nonlinear dimensional reduction problems

陳庭甫(Ting-Fu Chen)

指導教授 ： 李哲榮

國立清華大學/電機資訊學院/資訊工程學系/碩士(2013年)

摘要

降維技術廣泛運用於許多科技領域當中，但龐大的資料量，會造成在做降維計算時，得花上許久的時間才能得到結果。但如今GPU快速的進步，發展了多核心的硬體以及程式語言CUDA，使得許多數學計算有了能夠平行處理的方法。因此，本篇論文將分析Isomap演算法，試圖針對其中的k-Nearest Neighbor演算法、Floyd-Warshall演算法以及Multi-dimensional Scaling降維法的部份，利用CUDA來實行平行化的處理。而考慮到GPU上的記憶體有限，在實作kNN演算法、Floyd-Warshall演算法之平行化時，我們會將原始資料分塊，使平行化後的程式在執行時，即使input size過大，無法一次置入硬體上的記憶體，也能夠分批帶入硬體來處理，並維持正確性；同時也能使用擁有較快存取速度的共享記憶體來幫助運算。此外，我們也將利用供於GPU使用的線性代數函式庫-MAGMA裡的函式，來完成於降維過程中，所需的特徵值與特徵向量之運算。完成程式後，我們使用不同頂點數的三維空間swiss roll的dataset作為輸入數據，並分別使用CPU與GPU來進行Isomap降維。而實驗最後呈現出的GPU之於CPU的效能比，最大達到了60倍以上的效能改進。

關鍵字

isomap ； cuda

並列摘要

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.

參考文獻

[2] George B. Rabinowitz. An Introduction to Nonmetric Multidimensional Scaling. American Journal of Political Science, V01. 19, N0. 2. , pp. 343-390, May, 1975.

[3] A Global Geometric Framework for Nonlinear Dimensionality Reduction

[1] Zi Huang, Heng Tao Shen, Jie Shao, Stefan M. Rüger, Xiaofang Zhou. Locality condensation: a new dimensionality reduction method for image retrieval. School of Information Technology and Electrical Engineering, The University of Queensland, Australia Knowledge Media institute, The Open University, United Kingdom, 2008.

Joshua B. Tenenbaum,1* Vin de Silva,2 John C. Langford3, Science 2000.

[4] Ashutosh Saxena, Abhinav Gupta, Amitabha Mukerjee. Non-linear Dimensionality Reduction by Locally Linear Isomaps. Department of Electrical Engineering, Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur 208016, India, 2004.