Parallelization of the PCA algorithm on the Kalray MPPA-256 platform

Abstract

Las imágenes hiperespectrales permiten extraer información con una gran resolución espectral, que se suele extender desde el espectro ultravioleta hasta el infrarrojo. Aunque esta tecnología fue aplicada inicialmente a la observación de la superficie terrestre, esta característica ha hecho que, en los últimos años, la aplicación de estas imágenes se haya expandido a otros campos, como la medicina y, en concreto, la detección del cáncer. Sin embargo, este nuevo ámbito de aplicación ha generado nuevas necesidades, como la del procesado de las imágenes en tiempo real. Debido, precisamente, a la gran resolución espectral, estas imágenes requieren una elevada capacidad computacional para ser procesadas, lo que imposibilita la consecución de este objetivo con las técnicas tradicionales de procesado. En este sentido, una de las principales líneas de investigación persigue el objetivo del tiempo real mediante la paralelización del procesamiento, dividiendo esta carga computacional en varios núcleos que trabajen simultáneamente. A este respecto, el presente documento describe la implementación de una versión paralelizada del algoritmo PCA (del inglés, Principal Component Analysis) en la plataforma MPPA-256 de Kalray, cuya arquitectura contiene 256 procesadores repartidos en 16 clusters. En concreto, este documento se centra en la implementación de varios métodos para paralelizar las distintas etapas que conforman el algoritmo, particularmente aquellas que consumen un mayor porcentaje del tiempo de ejecución del algoritmo. El presente documento sigue la estructura clásica de un trabajo de investigación, exponiendo, en primer lugar, las motivaciones que han cimentado este Proyecto de Investigación y los objetivos que se esperan alcanzar con él. A continuación, se realiza un amplio análisis del estado del arte de las tecnologías necesarias para su desarrollo, explicando, por un lado, las imágenes hiperespectrales y, por otro, las plataformas multinúcleo más potentes existentes en el mercado. De esta forma, se proporcionarán todos los conceptos técnicos necesarios para el correcto seguimiento de este documento. Tras ello, se describirá la arquitectura de la plataforma elegida, así como la metodología seguida para diseñar los métodos de paralelización para cada una de las fases del algoritmo PCA. Además, también se describirá la adaptación de esta metodología para su implementación en la mencionada arquitectura. Una vez expuesta la metodología utilizada, se analizarán en detalle los resultados obtenidos en las pruebas realizadas; en primer lugar, se explicarán los resultados individuales extraídos del análisis de las etapas del algoritmo y, posteriormente, se discutirán los arrojados por el PCA de manera global. Por último, como resultado de este estudio se extraerán una serie de conclusiones, que engloban aspectos como la bondad de resultados y los tiempos de ejecución; asimismo, se proponen una serie de líneas futuras de trabajo con las que se podría continuar y complementar la investigación desarrollada en este documento.
Abstract:
Hyperspectral imaging collects information from across the electromagnetic spectrum, covering a wide range of wavelengths. Although this technology was initially developed for remote sensing and earth observation, its multiple advantages - such as high spectral resolution - led to its application in other fields, as cancer detection. However, this new field has shown specific requirements; for example, it needs to accomplish strong time specifications, since all the potential applications - like surgical guidance or in vivo tumor detection - imply real-time requisites. Achieving this time requirements is a great challenge, as hyperspectral images generate extremely high volumes of data to process. For that reason, some new research lines are studying new processing techniques, and the most relevant ones are related to system parallelization: in order to reduce the computational load, this solution executes image analysis in several processors simultaneously, so the computational load is divided among the different cores, and real-time specifications can be accomplished. This document describes the implementation of a parallelized version of the PCA (Principal Component Analysis) algorithm on the Kalray MPPA-256 architecture, which contains 256 processors divided in 16 clusters. Concretely, this document focuses on the implementation of several methods to parallelize the atomic operations of this algorithm, particularly the ones that consume most of the execution time of the algorithm. The document follows the classical structure of a research work. Firstly, it introduces the motivations that have inspired this Research Project and the main objectives to achieve. After that, it thoroughly studies the state of the art of the technologies related to the development of the library. The state of the art contains all the concepts needed to understand the contents of this research work, like the definition and applications of hyperspectral imaging and the typical processing chain. Thirdly, it explains the architecture of the Kalray MPPA-256 platform and describes the methodologies followed to design parallelization methods for each one of the PCA steps, as well as the adaptation of these methodologies to the implementation on the mentioned architecture. Afterwards, the collected results will be carefully analyzed: first of all, individual results - from each one of the atomic operations that have been implemented - will be discussed and, after that, complete results will be studied; these results will analyze the effects of multithreading and system parallelization on the mentioned algorithm, calculating the achieved speedups. Finally, as a result of this discussion, some conclusions will be gathered regarding some relevant aspects, such as algorithm behavior and execution times. Likewise, this document will conclude with the proposal of some future research lines that could continue the research work described in this document.