Aceleración de algoritmos de clasificación basados en disimilitudes, utilizando arquitecturas computacionales con múltiples núcleos.

Abstract

En esta tesis se proponen estrategias y estructuras computacionales, basadas en arquitecturas multi-core y many-core, orientadas a desarrollar implementaciones paralelas de una selección representativa de algoritmos de reconocimiento de patrones basados en disimilitudes. Los algoritmos escogidos, tanto para clasificación supervisada como para agrupamiento, corresponden a algoritmos cuyas versiones secuenciales son costosas computacionalmente y para los que no se encontraron, en la revisión del estado del arte, implementaciones sobre arquitecturas paralelas como las arriba mencionadas. Los algoritmos que se paralelizaron tienen costos computacionales diversos en sus versiones secuenciales. Algunos de ellos son tan costosos que su uso práctico, sin paralelización, resulta inviable cuando se tienen requerimientos como la obtención de respuestas en pseudo-tiempo real, el enriquecimiento de conjuntos de datos pequeños mediante sobre-muestreo combinatorio, la ejecución repetida para estimar medidas de desempeño estadísticamente confiables durante simulaciones exhaustivas o las actualizaciones frecuentes de los resultados en escenarios de grandes flujos de datos. Las versiones paralelas de los algoritmos de clasificación y agrupamiento se presentan como seudocódigos y fueron implementadas principalmente en ANSI C y CUDA para sus ejecuciones sobre arquitecturas multi-core y many-core, respectivamente. Se realizaron experimentos con conjuntos de datos representativos y se reportaron los tiempos de respuesta tanto de las versiones secuenciales como de las versiones paralelas respectivas, así como las aceleraciones logradas con la paralelización. En todos los casos, se garantizó que las etiquetas de clase asignadas por las dos versiones --secuencial y paralela—coincidiera incluso bajo condiciones distintas de precisión de punto flotante, por ejemplo, precisión de CPU vs. precisión de GPU. Los análisis de los algoritmos seleccionados, la novedad de sus implementaciones paralelas, las aceleraciones logradas en las ejecuciones y la representatividad de las aplicaciones ilustradas componen los principales aportes de esta tesis. Entre estas últimas, se pueden destacar las paralelizaciones de algoritmos de clasificación costosos como los de enriquecimiento combinatorio de representación mediante líneas de características y el agrupamiento de datos masivos de georreferenciación. La mayor parte del material original presentado en todos los capítulos ha sido discutido y publicado previamente, bien sea como ponencias en eventos académicos o como artículos en revistas científicas indexadas. Las publicaciones correspondientes se indican al inicio de cada capítulo.

This thesis proposes computational strategies and structures, based on multi-core and manycore architectures, aimed at developing parallel implementations of a representative selection of dissimilarity-based pattern recognition algorithms. The algorithms chosen for both supervised classi cation and clustering correspond to algorithms whose sequential versions are computationally expensive and for which, in the review of the state of the art, implementations on parallel architectures such as those mentioned above were not found. The algorithms that were parallelized have di erent computational costs in their sequential versions. Some of them are so expensive that their practical use, without parallelization, is not feasible when there are requirements such as obtaining responses in pseudo-real time, enrichment of small data sets by combinatorial oversampling, repeated execution to estimate statistically reliable performance measures during exhaustive simulations, or frequent updates of the results in scenarios of big data streams. The parallel versions of the classi cation and clustering algorithms are presented as pseudocodes and were implemented mainly in ANSI C and CUDA for their executions on multi-core and many-core architectures, respectively. Experiments were carried out with representative datasets and the response times of both the sequential and the respective parallel versions were reported, as well as the accelerations achieved with parallelization. In all cases, the class labels assigned by the two versions |sequential and parallel| were guaranteed to match even under di erent oating point precision conditions, for example CPU precision vs. GPU precision. The novelty of the parallel implementations of the selected algorithms, the accelerations achieved in the executions and the representativeness of the illustrated applications compose the main contributions of this thesis. Among the latter, we can highlight the parallelizations of expensive classi cation algorithms such as those of combinatorial enrichment of representation through features lines and the clustering of massive geospatial data. Most of the original material presented in all chapters has been previously discussed and published, either as presentations at academic events or as papers in indexed scienti c journals. The corresponding publications are indicated at the beginning of every chapter.