Parallel implementation of nonlinear dimensionality reduction methods using cuda in gpu

Abstract

Manifold learning, is one of the methods for nonlinear dimensionality reduction, which affords a way to understand and visualize the structure of nonlinear hyperspectral datasets. These methods use graphs to represent the manifold topology, and use metrics like geodesic distance, allowing embedding higher dimension objects into lower dimensional space. However the complexities of some manifold learning algorithms is ??(????), therefore they are very slow (high computational algorithms). In this project, we present a CUDA-based parallel implementation of the three most popular manifold learning algorithms: Isomap, Locally linear embedding, and Laplacian eigenmaps, using the CUDA multi-thread model. Each of these algorithms has three main parts: find ?? nearest neighbors, build the matrix of distances or weights, and compute the low dimension of the hyperspectral image. The first part was implemented in CUDA by (Garcia, Debreuve, & Barlaud, 2008), the second part was implemented by us in pure C++ and CUDA to measure the speedup between these implementations, and the third was carried out using the libraries of CULA and MKL LAPACK. The manifold learning algorithms were implemented on a 64-bit workstation equipped with a quad-core Intel® Xeon with 12 GB RAM and two NVIDIA Tesla C1060 GPU cards. The CUDA implementation achieved 26?? speedup compared to a pure C++ implementation. It also showed good scalability when varying the size of the dataset and the number of K nearest neighbors.Manifold learning, es uno de los métodos de reducción de dimensionalidad no lineal, el cual proporciona una manera para entender y visualizar la estructura no lineal de los conjuntos de datos hyperspectrales. Estos métodos usan grafos para representar la topología del manifold y métricas como la distancia geodésica, permitiendo representar un objeto de una dimensión mayor dentro de una dimensión menor. Sin embargo la complejidad algunos de los algoritmos de manifold learning es ??(????), por lo tanto estos son muy lentos (alto procesamiento computacional). En este proyecto presentamos la implementación en paralelo basado en CUDA de los tres más famosos algoritmos de manifold learning como son: Isomap, locally linear embedding y Laplacian eigenmaps, usando el modelo CUDA de multi- hilo. Cada uno de estos algoritmos tiene tres partes principales: encontrar los ?? vecinos más cercanos, construir la matriz de distancias o pesos, y calcular la dimensión baja de la imagen hiperespectral. La primera parte fue implementada en CUDA por (Garcia, Debreuve, & Barlaud, 2008), la segunda parte se llevó a cabo por nosotros en C++ puro y CUDA para medir la aceleración entre estas implementaciones, y el tercero se llevó a cabo utilizando las bibliotecas de CULA y LAPACK MKL. Los algoritmos de manifold learning fueron implementados en un estación de trabajo de 64–bits equipado con un quad-core Intel® Xeon con 12 GB RAM y dos tarjetas GPU de Tesla C1060 de NVIDIA. La implementación en CUDA logro ser 26?? veces más rápido que la implementación en C++ puro. También muestra una buena escalabilidad al variar el tamaño del conjunto de datos y el número de los ?? vecinos más cercanos.