Estructuras métricas para búsquedas por similitud sobre arquitecturas heterogéneas basadas en gpus

• Autores: Roberto Uribe Paredes
• Directores de la Tesis: Enrique Arias (dir. tes.) , Diego Cazorla López (codir. tes.)
• Lectura: En la Universidad de Castilla-La Mancha ( España ) en 2013
• Idioma: español
• Tribunal Calificador de la Tesis: José Luis Sánchez García (presid.) , Jesús Peinado Pinilla (secret.) , Dolores Isabel Rexachs del Rosario (voc.)
• Enlaces
  • Tesis en acceso abierto en: TESEO
• Resumen

  • Resumen La búsqueda por similitud aparece en diferentes campos de la ciencia e ingeniería tales como reconocimiento de patrones, recuperación de la información, etc, convirtiéndose, hoy en día, en un campo de interés muy activo. En general, en las aplicaciones reales que tratan con un gran volumen de datos, el uso del paralelismo se vuelve esencial para obtener resultados en un tiempo razonable. En este contexto, las máquinas actuales poseen dispositivos heterogéneos, combinando algunos de ellos, plataformas multicore y manycore (GPU / MultiGPU). El presente trabajo de Tesis Doctoral desarrolla, analiza y evalúa la implementación de estructuras métricas y sus algoritmos sobre plataformas heterogéneas permitiendo la utilización de todos los recursos disponibles en la plataforma subyacente en la resolución de consultas por rango. Considera adicionalmente diversos aspectos en las diferentes soluciones presentadas, como son las estrategias de planificación para la distribución de consultas, estrategias para la transferencia de datos en función de los distintos niveles de la jerarquía de memoria y análisis del consumo energético de las distintas propuestas. Palabras clave: Búsqueda por similitud, espacios métricos, consultas por rango, plataformas basadas en GPU, plataformas multicore, esquemas de planificación.

    1.- Introducción En la última decada, la búsqueda por similitud en una gran colección de objetos almacenados en una base de datos métrica es un problema que ha adquirido especial interés. Este tipo de búsquedas aparece en diversas aplicaciones de ciencia e ingeniería tales como reconocimiento de voz e imagen, minería de datos, detección de plagio y muchas otras.

    La similitud se modela generalmente a través de un espacio métrico, y la búsqueda de objetos más similares a través de una búsqueda por rango o de vecinos más cercanos. Un espacio métrico (X,d) es un conjunto X con una función de distancia d:X2¿R, tal que ¿ x,y,z ¿ X, se deben cumplir las propiedades de: positividad (d(x,y)>=0 y d(x,y)=0 ssi x=y), simetría (d(x,y)=d(y,x)) y desigualdad triangular (d(x,y)+d(y,z)>=d(x,z)).

    Sobre un espacio métrico (X,d) y un conjunto de datos finito Y ¿ X, se puede realizar una serie de consultas. La consulta básica es la consulta por rango. Sea un objeto x ¿ X, y un rango r ¿ R. La consulta de rango alrededor de x con rango r es el conjunto de puntos y ¿ Y, tal que d(x,y)<= r. Un segundo tipo de consulta, que puede construirse usando la consulta por rango, es los k vecinos más cercanos. Sea un objeto x ¿ X, y un entero k. Los k vecinos más cercanos a x son un subconjunto A de objetos de Y, donde |A|=k y no existe un objeto y ¿ A tal que d(y,x) sea menor a la distancia de algún objeto de A a x.

    El objetivo de los algoritmos de búsqueda es minimizar la cantidad de evaluaciones de distancia realizadas para resolver la consulta. Los métodos para buscar en espacios métricos se basan principalmente en dividir el espacio empleando la distancia a uno o más objetos seleccionados. El no trabajar con las características particulares de cada aplicación tiene la ventaja de ser más general, pues los algoritmos funcionan con cualquier tipo de objeto. Algunas de las estructuras basan la búsqueda en pivotes y otras en clustering. En [1] y en [2] se describen en detalle las diferentes estructuras métricas publicadas en las últimas decadas. Por otro lado, la necesidad de almacenar y procesar grandes volúmenes de datos hace necesario aumentar el rendimiento en términos de tiempo de procesamiento. En general, se utilizan para ello diversas plataformas paralelas. En este sentido, nuevas plataformas basadas en tarjetas gráficas (Graphics Processing Unit, GPU) permiten un alto nivel de paralelismo a un muy bajo coste. En los últimos años, grandes clusters y supercomputadores están incorporando nodos híbridos compuestos de una o más CPUs y GPUs. Muchos de estos sistemas están presentes en las primeras posiciones de las últimas listas TOP500 y GREEN500 (www.top500.org, www.green500.org)). Para garantizar un uso apropiado de estas plataformas computacionales, se han de gestionar diferentes retos. Por un lado, y desde el punto de vista del hardware, es muy importante dimensionar correctamente el sistema debido a su alto coste, y por la misma razón, es esencial obtener el mayor ahorro energético posible.

    Si nos centramos en el caso particular de búsquedas por similitud, se pueden encontrar bastantes contribuciones desde el punto de vista del paralelismo aplicado a este problema tanto para memoria distribuida [3, 4, 5], plataformas de memoria compartida [6], como para GPUs [7, 8, 9]. Al comenzar este trabajo, existían pocas implementaciones que utilizaban GPUs para procesar búsquedas por similitud, todas ellas atacaban el problema desde la búsqueda exhaustiva y para kNN. En la actualidad existen algunos grupos de investigación que desarrollan trabajos sobre estructuras métricas, sin embargo, no se tiene conocimiento de desarrollos en torno a la implementación de versiones heterogéneas, es decir, a la utilización de todos los recursos disponibles en la plataforma subyacente para procesar consultas. Este trabajo de Tesis se centra en la implementación de estructuras métricas sobre plataformas heterogéneas, dando énfasis al análisis, desarrollo y evaluación de estas estructuras sobre dispositivos del tipo GPU/multi-GPU y multicores.

    2.- Descripción General del Trabajo de Tesis La presente Tesis aborda el problema de la búsqueda por similitud desde la visión de la implementación de estructuras métricas sobre plataformas basadas en GPU y en el contexto de implementaciones heterogéneas que aprovechen todos los dispositivos de procesamiento disponibles en la plataforma subyacente presentes en un nodo, sean de tipo multicore o many-core (GPUs, multi-GPUs). En el presente trabajo se analiza un conjunto de estructuras, clásicas en su tipo, y con buen rendimiento en búsquedas secuenciales, para determinar cuáles serían las más idóneas para su implementación en este tipo de arquitectura. El objetivo principal es presentar un conjunto de implementaciones orientadas a la búsqueda eficiente sobre estructuras métricas bajo distintas arquitecturas, de tal manera que todos los dispositivos puedan cooperar, simultáneamente, en la resolución de las consultas ingresadas al sistema. La Tesis se desarrolla principalmente en 4 partes, detalladamente descritas en el documento original de la Tesis, éstas son: 1. La primera parte corresponde a una descripción del marco teórico y conceptos básicos sobre el contexto en el que está basada la Tesis, apuntando principalmente a los tópicos de espacios métricos y paralelización de estructuras métricas (capítulo 2), incluyendo una descripción detallada de las estructuras relevantes a la Tesis y utilizadas en una primera etapa para su análisis (capítulo 3). Se incluye también en esta parte una descripción de la plataforma computacional y los espacios métricos de prueba utilizados en la Tesis (capítulo 4). 2. La segunda parte corresponde a obtener las primeras aproximaciones para una solución sobre una plataforma basada en GPUs. En el capítulo 5 se obtiene una perspectiva inicial de las estructuras a fin de obtener aquellas más idóneas para su implementación sobre GPUs. De este capítulo se obtiene que la estructura más adecuada para implemetar sobre GPUs es una estructura genérica denominada \emph{Generic Metric Structure} (\emph{GMS}) y que la estructura con mejor rendimiento en una plataforma secuencial es la denominada \emph{Spaghettis}, la cual será utilizada para las comparaciones de speed-up. En el mismo capítulo se presentan las primeras implementaciones sobre una plataforma basada en GPU y multi-GPU, se describen los algoritmos y se presentas los primeros resultados. Los resultados preliminares permiten ver el aumento en el rendimiento de la estructura \emph{GMS} por sobre las otras y con speed-ups elevados versus las versiones secuenciales. 3. La tercera parte corresponde al desarrollo de una implementación completa sobre una plataforma heterogénea. Presenta dos alternativas de soluciones, analizando empíricamente el comportamiento de ambas soluciones y el rendimiento sobre los diferentes dispositivos (capítulo 6). La primera versión presentada (versión 1) utiliza una planificación dinámica y reparte las consultas sobre todos los dispositivos disponibles, en este caso los dispositivos GPUs resuelven en forma independiente cada consulta. En la segunda versión (versión 2), los dispositivos más rapidos (GPUs) reciben bloques de consultas y resuelven dicho conjunto de consultas en un sólo kernel. La planificación utilizada en la versión 2 es dinámica pero con modificaciones sobre la distribución de consultas. En este capítulo se presenta un amplio análisis experimental en función de obtener los valores más adecuados para los parámetros a utilizar en los esquemas de planificación. Se presentan resultados que análizan el rendimiento de los sistemas desde diferentes puntos de vista que van desde el número de iteraciones asignadas a cada unidad de procesamiento (planificación), consultas resueltas por unidad, tiempo utilizado en la transferencia de datos entre los distintos dispositivos, escalabilidad del sistema, entre otros. En este capítulo se determina que la versión 2 resulta ser la mejor en términos de reducción de los tiempos de ejecución. 4. La cuarta parte, desarrollada en el capítulo 7, consta de tres secciones donde se analizan las soluciones desde distintas perspectivas. La primera considera los distintos niveles de la jerarquía de memoria y los costos adicionales si se consideran, por ejemplo, los accesos a memoria secundaria. La segunda sección profundiza la situación bajo un nuevo esquema de planificación de distribución de consultas, suponiendo un conocimiento previo respecto de las relaciones entre las velocidades de los diferentes dispositivos de procesamiento. La tercera sección abre una discusión y un análisis en torno al consumo energético de los distintos dispositivos utilizados en la Tesis aquí presentada.

    3.- Conclusiones y trabajo futuro Desde el punto de vista de la arquitectura, las GPUs proveen de una enorme capacidad de cómputo dado su alto grado de paralelismo a nivel de datos. Por otro lado, la utilización de estructuras métricas mejora el rendimiento de la búsqueda tanto en un entorno secuencial como paralelo. Reuniendo estos dos elementos, se obtiene un gran potencial de resolución de búsquedas por similitud. Tras un estudio inicial sobre diferentes estructuras métricas, expuesto en la sección 5.1 (ver documento original Tesis), se consideró que una estructura adecuada para su implementación sobre una plataforma basada en GPU era una versión genérica de una estructura basada en pivotes, la cual se denominó GMS (Generic Metric Structure). En los principales casos de prueba utilizados en la Tesis, espacio de palabras en español (diccionario español) y espacio de histogramas de colores (espacio de vectores), se obtuvieron considerables mejoras respecto de la estructura de mejor comportamiento secuencial (para los rangos menores, Spaghettis). Cada una de las versiones presentadas mejora a las anteriores, es así como en las primeras versiones de las implementaciones sobre una GPU de la estructura GMS versus Spaghettis secuencial, alcanzaron mejoras de 1.9x y 20x para el menor y mayor rango de búsqueda en el caso del espacio de palabras y entre un 1.3x y 5.3x para el menor y mayor rango de recuperación en el caso del espacio de vectores. Con las últimas versiones sobre una GPU, estos valores llegaron a 24.52x y 6.82x en los rangos mayores para el espacio de palabras y de vectores respectivamente. Claramente, al incluir más unidades de procesamiento gráfico las mejoras aumentaron llegando a 67.2x y 16.5x para los mismos casos anteriores (mayores rangos en el espacio de palabras y espacio de vectores). Finalmente, al incluir los núcleos de procesamiento de la CPU el sistema se convierte en heterogéneo. Los speed-ups conseguidos para la mejor alternativa implementada sobre la plataforma heterogénea están entre 10.7x y 96.44x en el caso del diccionario español y entre 7.72x y 25.53x para el caso de los histogramas de colores (para el menor y mayor rango). En los mayores rangos es donde más beneficios se obtienen de los dispositivos gráficos.

    Durante el desarrollo de las versiones heterogéneas fue relevante considerar los esquemas de planificación más adecuados acorde al tipo de dispositivos utilizados y a la diferencia de velocidades en el procesamiento de consultas y así evitar que aquellos dispositivos más lentos perjudicaran el rendimiento del sistema global. Una forma de determinar las ganancias obtenidas por uno u otro sistema es verlas en términos absolutos, por ejemplo, en consultas resueltas en una unidad de tiempo. En este aspecto, se muestran las diferencias entre las distintas versiones implementadas en consultas por segundo (referirse a la sección 6.5 del documento original de la Tesis). En este caso la versión heterogénea (segunda versión) llega a resolver hasta 97 veces más consultas que la mejor versión secuencial en el espacio de palabras y hasta 36 veces más en el espacio de vectores.

    Considerando que dado los requerimientos de plataformas como la GPU, no es posible implementar sobre ellas las mejores versiones secuenciales de estructuras métricas. Entonces, sería factible, si se disponen de los recursos de memoria, que un sistema heterogéneo pueda soportar distintas estructuras, por ejemplo, una para cargar sobre las GPUs y otra para utilizarla con los cores de las CPUs, es decir, ¿lo mejor de los dos mundos¿. Al finalizar la Tesis es importante mencionar que las GPUs no sólo representan una excelente alternativa para su utilización en este tipo de problemas, sino que además, representan una alternativa adecuada, también, desde la perspectiva del consumo energético, el cual es un factor no siempre considerado. En este aspecto el uso de GPUs en un sistema de recuperación de información puede llegar a reducir la energía a valores cercanos al 60% y en los mejores casos hasta un 90% versus otras plataformas, dependiendo del tipo de búsqueda y de la plataforma contra la que se compara. De este modo, se compensa el uso de un dispositivo de elevado consumo, como la GPU, frente a otros como es el caso de la CPUs.

    Referencias [1] Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates, and José Luis Marroquín, ¿Searching in metric spaces¿ . In, ACM Computing Surveys, vol. 33, no. 3, pp. 273¿321, 2001. [2] Magnus Hetland, ¿The basic principles of metric indexing¿ . In Swarm Intelligence for Multi-objective Problems in Data Mining, Carlos Coello, Satchidananda Dehuri, and Susmita Ghosh, Eds., vol. 242 of Studies in Computational Intelligence, pp. 199¿232. Springer Berlin / Heidelberg, 2009. [3] Pavel Zezula, Pasquale Savino, Fausto Rabitti, Giuseppe Amato, and Paolo Ciaccia, ¿Processing m-trees with parallel resources¿. In RIDE ¿98: Proceedings of the Workshop on Research Issues in Database Engineering, Washington, DC, USA, 1998, pp. 147¿, IEEE CS. [4] Adil Alpkocak, Taner Danisman, and Ulker Tuba, ¿A parallel similarity search in high dimensional metric space using m-tree¿. In Advanced Environments, Tools, and Applications for Cluster Computing, vol. 2326 of LNCS, pp. 247¿252. Springer Berlin / Heidelberg, 2002. [5] Veronica Gil-Costa, Mauricio Mar ín and Nora Reyes, ¿Parallel query processing on distributed clustering indexes¿. Journal of Discrete Algorithms, vol. 7, no. 1, pp. 3¿17, 2009. [6] Veronica Gil-Costa, Ricardo Barrientos, Mauricio Marín and Carolina Bonacic, ¿Scheduling metric-space queries processing on multi-core processors¿. In Euromicro Conference on Parallel, Distributed, and Network-Based Processing, vol. 0, pp. 187¿194, 2010. [7] Quansheng Kuang and Lei Zhao, ¿A practical GPU based kNN algorithm,¿ International Symposium on Computer Science and Computational Technology (ISCSCT), pp. 151¿155, 2009. [8] Vincent Garcia, Eric Debreuve, and Michel Barlaud, ¿Fast k nearest neighbor search using GPU¿. In Computer Vision and Pattern Recognition Workshop, vol. 0, pp. 1¿6, 2008. [9] Ricardo J. Barrientos, José I. Gómez, Christian Tenllado, Manuel Prieto, and Mauricio Marín, ¿kNN query processing in metric spaces using GPUs¿. In 17th International European Conference on Parallel and Distributed Computing (Euro-Par 2011), Berlin, Heidelberg, 2011, vol. 6852 of LNCS, pp. 380¿392, Springer-Verlag.