La resolución de problemas de álgebra lineal numérica (ALN) es la etapa de más costosa en diversas áreas de la ciencia y la ingeniería, como inteligencia artificial, optimización, simulación, procesamiento de señales y control. Desde sus orígenes, el ALN es una de las áreas que requiere mayor poder de cómputo, lo cual motiva el uso de estrategias de computación eficiente tanto desde el punto de vista de las implementaciones como de los dispositivos que se utilizan. El álgebra dispersa, es decir cuando se trabaja con matrices que cuentan con un gran número de coeficientes con valor cero, introduce varias problemáticas extras respecto al álgebra densa, como la irregularidad y el indireccionamiento en el acceso a los datos.
Motivadas por la resolución de problemas cada vez más demandantes, las plataformas de cómputo científico y posteriormente las de cómputo doméstico han tendido al procesamiento paralelo para mitigar limitantes físicas que surgen al aumentar el desempeño de los procesadores secuenciales y disminuir el área de los mismos. En este sentido, las CPUs y GPUs actuales ofrecen la posibilidad de ejecutar tareas en paralelo sobre varios núcleos. Como respuesta a la evolución del poder de cómputo de las plataformas secuenciales, se han desarrollado o actualizado las estrategias de uso de otros aceleradores de hardware entre los que se destacan los Field–Programmable Gate Arrays (FPGAs). Estas plataformas no solo proporcionan la aceleración requerida, sino que también se destacan en eficiencia energética. Además, debido a la reconfigurabilidad y la adopción de herramientas de síntesis de alto nivel (HLS), los FPGA se están convirtiendo en una alternativa prometedora a las GPUs al momento de procesar cómputo altamente demandante. Es importante notar también que existen contextos en los que el consumo de energía presenta restricciones severas. Tal es el caso, entre otros, de dispositivos como celulares, sensores autónomos, etc., los cuales tienen un papel fundamental en áreas como IoT y Smart Cities. Los usuarios de estos dispositivos demandan cada día mayores niveles de cómputo (tratamiento de imágenes, algoritmos de optimización, etc.) y un menor consumo de energía. En este sentido, avanzar en la relación entre capacidad de cómputo y consumo permite aumentar la autonomía de los dispositivos.
En este proyecto se plantea estudiar y diseñar un conjunto de kernels de álgebra dispersa capaces de aprovechar eficientemente las características de las FPGAs modernas. En particular, se espera avanzar en las operaciones de álgebra dispersa más difundidas para la resolución de problemas de computación científica (entre otros: multiplicación de matriz dispersa por vector, resolución de sistemas lineales dispersos triangulares y multiplicación de matrices dispersas) con especial atención al uso de las memorias de las FPGAs para alcanzar accesos eficientes. Las implementaciones se evaluarán en múltiples plataformas FPGA tanto en términos de tiempo de ejecución como de consumo energético.
El cómputo de problemas cada vez más complejos en dispositivos autónomos es uno de los principales desafíos de la actualidad. En especial, la necesidad de contar con técnicas altamente eficientes, tanto desde el punto de vista del tiempo de resolución, como de los valores de consumo energético que implican.
En este contexto se ha desarrollado de manera importante el uso de plataformas de hardware heterogéneas, es decir, que cuentan con varios dispositivos de cómputo que ofrecen características disímiles. Es de vital importancia, entonces, poder entender en profundidad las bondades y restricciones de cada dispositivo de cálculo y avanzar en el desarrollo de técnicas que sean capaces aprovechar al máximo las distintas plataformas.
En este proyecto se espera profundizar sobre las características de las plataformas de hardware basadas en FPGAs, procesadores ARM y microcontroladores RISC-V. Particularmente, recopilar y/o implementar versiones eficientes de operaciones básicas de álgebra densa (por ejemplo, un sub-conjunto de las operaciones de la biblioteca BLAS), evaluar y comparar el desempeño alcanzado, y caracterizar el uso de las distintas plataformas de hardware.
La masificación de los procesadores multi-core, menos de dos décadas atrás, y la posterior adopción de las tarjetas gráficas (GPUs) como procesadores de propósito general implicaron una revolución en el campo del hardware para grandes volúmenes de cómputo. Más recientemente, esta revolución alcanzó a los Field–Programmable Gate Arrays (FPGAs). El creciente interés por plataformas de hardware energéticamente eficientes transforma a las FPGAs en una opción altamente atractiva en comparación con otros dispositivos multi-core. Esto ha motivado, entre otras cosas, la incursión en el terreno de las FPGAs de grandes fabricantes de hardware como Intel, que recientemente se fusionó con el fabricante de FPGAs Altera.
La estrategia clásica para explotar las FPGAs implica el uso de low–level Hardware Description Languages (HDL) como VHDL o Verilog. Esto implica una diferencia radical con los modelos de programación de otros tipos de dispositivos y exige, para su aprovechamiento, un conocimiento altamente especializado del hardware subyacente. Esto es uno de los puntos por los cuales las FPGAs no han sido masivamente adoptadas por la comunidad. Para abatir dicha desventaja, las empresas fabricantes de FPGAs están haciendo importantes esfuerzos por adoptar High Level Synthesis languages como C/C++, System C u OpenCL. Una de las evidencias más relevantes en la introducción por parte de Intel y Xilinx de SDKs basados en OpenCL para sus FPGAs, facilitando la adopción del uso de estos aceleradores de hardware por la comunidad de software.
OpenCL es un estándar de programación paralela, open-source y royalty-free, que permite la descripción del paralelismo mediante un modelo abstracto que es independiente del hardware utilizado. Este tipo de herramientas reduce, considerablemente, el tiempo de desarrollo y además habilita la portabilidad entre plataformas. Sin embargo, queda mucho por investigar en cuanto a los desempeños alcanzables con este tipo de herramientas al utilizar FPGAs.
En este proyecto se espera estudiar en profundidad las herramientas de alto nivel para desarrollar kernels para FPGAs, en especial OpenCL. Entender, identificar y caracterizar las brechas en desempeños entre el uso de HDLs y HLSs, tanto desde el punto de vista de tiempo de cómputo como de consumo energético. Las comparaciones se centrarán en kernels paradigmáticos del álgebra lineal, como son la multiplicación de matrices densas (gemm) y la multiplicación de una matriz dispersa por un vector denso (spmv).
El cómputo de problemas cada vez más complejos en dispositivos autónomos es uno de los principales desafíos de la actualidad. En especial, la necesidad de contar con técnicas altamente eficientes, tanto desde el punto de vista del tiempo de resolución, como de los valores de consumo energético que implican.
En este contexto se ha desarrollado de manera importante el uso de plataformas de hardware heterogéneas, es decir, que cuentan con varios dispositivos de cómputo que ofrecen características disímiles. Es de vital importancia, entonces, poder entender en profundidad las bondades y restricciones de cada dispositivo de cálculo y avanzar en el desarrollo de técnicas que sean capaces aprovechar al máximo las distintas plataformas.
En este proyecto se espera profundizar sobre las características de las plataformas de hardware basadas en procesadores ARM y microcontroladores RISC-V. Particularmente, recopilar y/o implementar versiones eficientes de operaciones básicas de álgebra densa (por ejemplo, un sub-conjunto de las operaciones de la biblioteca BLAS), evaluar y comparar el desempeño alcanzado, y caracterizar el uso de las distintas plataformas de hardware.
En los últimos años el campo de arquitecturas de hardware para computación de alto desempeño (HPC, por su sigla en inglés) ha cambiado de forma drástica. Las GPUs han evolucionado para convertirse en parte fundamental de los sistemas de HPC modernos, siendo capaces de ejecutar miles de hilos concurrentemente, y acelerando de forma notable la resolución de problemas en áreas como bases de datos, computación gráfica, computación científica, inteligencia artificial, etc.
En el caso particular del álgebra lineal numérica, son muchas las bibliotecas que proveen implementaciones eficientes para operaciones básicas como el producto matriz-vector, matriz-matriz y la resolución de sistemas de ecuaciones lineales. Sin embargo, en ciertas aplicaciones es común la solución de secuencias de productos matriz-vector o sistemas de ecuaciones que son idénticos a menos de un desplazamiento en la diagonal de la matriz. Si bien estas operaciones “desplazadas” son resolubles mediante las bibliotecas tradicionales, las mismas no sacan partido de la estructura particular de estas secuencias. Adicionalmente, cuando se trabaja con el tipo de datos complejo se duplica la utilización de la memoria y las transferencias de datos, por lo que contar con métodos que representen estas estructuras de forma eficiente y permitan reutilizar datos almacenados en memorias rápidas (como registros o cachés) puede acarrear importantes ventajas.
El objetivo del proyecto es proponer implementaciones eficientes en GPU para el producto matriz-vector “desplazado” y la solución de sistemas “desplazados” de ecuaciones lineales sobre el tipo de datos complejo.
En los últimos años el campo de arquitecturas de hardware para computación de alto desempeño (HPC, por su sigla en inglés) ha cambiado de forma drástica. Las GPUs han evolucionado para convertirse en parte fundamental de los sistemas de HPC modernos, siendo capaces de ejecutar miles de hilos concurrentemente, y acelerando de forma notable la resolución de problemas en áreas como bases de datos, computación gráfica, computación científica, inteligencia artificial, etc.
Esta evolución ha sido posible gracias a la aparición de CUDA (2007), que marcó un cambio de paradigma en la arquitectura de hardware, el modelo de programación, y el modelo de ejecución de estos dispositivos.
Por aproximadamente una década, el modelo de programación de CUDA ha proporcionado una única forma de sincronización y cooperación entre hilos, que consiste en una barrera para los hilos agrupados bajo un mismo bloque. La sincronización entre distintos bloques de hilos no era soportada por el lenguaje, aunque distintos autores han utilizado mecanismos basados en operaciones atómicas sobre variables globales con este objetivo. Adicionalmente, grupos de 32 hilos llamados warps, se encuentran sincronizados implícitamente (de hecho comparten el Program Counter) y la divergencia en la ejecución de hilos pertenecientes a un mismo warp es simulada por el hardware. Asimismo, la sincronzación entre subgrupos dentro de un warp no era soportada.
A partir de CUDA 9 se realizó un cambio en el modelo de programación de CUDA, por medio de una extensión del lenguaje denominada “Cooperative Groups”. Esta extensión tiene como objetivo flexibilizar y expandir los mecanismos de sincronización entre hilos de la GPU, por ejemplo aportando primitivas para particionar bloques de hilos y coordinar la ejecución de dichas particiones, habilitando la sincronización entre bloques e incluso entre GPUs. El cambio en el modelo de programación fue acompañado por cambios en el hardware, a partir de la arquitectura Volta, entre los cuales se destaca la introducción de un Program Counter para cada hilo.
Estos avances habilitan el uso de patrones de paralelismo y cooperación entre hilos que hasta ahora no eran posibles, o cuya complejidad de implementación los hacía susceptibles a errores de concurrencia. Sin embargo, por tratarse de una característica nueva, su poder y el comportamiento en distintas arquitecturas de GPU no ha sido explorado a fondo.
El proyecto busca avanzar en el conocimiento de este nuevo paradigma aplicado a la resolución de problemas de álgebra lineal numérica, adaptando algoritmos existentes y diseñando nuevas estrategias basadas en estos cambios.
La solución de una secuencia de sistemas lineales duales es frecuente en distintos problemas de la ciencia y la ingeniería, especialmente en el área de control y reducción de modelos. En estos casos, es atractivo utilizar el método del gradiente biconjugado (BiCG), ya que proporciona naturalmente la solución del sistema dual. Cuando se trata de una secuencia de sistemas, es posible aplicar una variante llamada Reciclyng BiCG (RBiCG), que intenta “reciclar” el subespacio de Krylov generado para un par de sistemas duales en el siguiente par. El RBiCG está en el centro de otros métodos numéricos de interés, como por ejemplo el Iterative Rational Krylov Algorithm (IRKA) para reducción de modelos, que requiere resolver secuencias de sistemas lineales duales que varían lentamente. En los últimos años, en la Facultad de Ingeniería hemos trabajado en el desarrollo de una versión eficiente del algoritmo BiCG capaz de ejecutar en distintas configuraciones de hardware heterogéneo. En particular, se desarrollaron implementaciones de la versión precondicionada del método, para sistemas de cómputo con una o dos tarjetas gráficas.
El proyecto plantea tomar los desarrollos mencionados anteriormente como punto de partida para elaborar variantes eficientes de los métodos RBiCG e IRKA capaces de explotar el poder de cómputo de las GPUs.
La evolución de la computación ha sido acompañada por un aumento de la demanda de poder computacional. En la medida que se dispone de mayor poder de cómputo la comunidad científica intenta abordar problemas de mayor escala o nivel de precisión. En este contexto, es realmente importante el uso de plataformas de computación de alto desempeño (HPC por su sigla en inglés).
Además de los grandes supercomputadores, en los últimos años se ha desarrollado de manera notable el uso de plataformas paralelas altamente potentes, pero de acotado costo económico y consumo energético. En especial, los aceleradores de hardware, entre los que se destacan los procesadores gráficos o GPUs (por su sigla en inglés), ofrecen capacidades de cómputo impresionantes en comparación con los procesadores tradicionales, integrando miles de cores a un costo económico y energético muy atractivo. El éxito de este tipo de dispositivos propició también el desarrollo de otras plataformas, de características similares o complementarias, como son los FPGAs, los procesadores ARM y las recientemente lanzadas TPU de Google, de manera que hoy se cuenta con una amplia gama de hardware y software para satisfacer distintas necesidades de cómputo.
Este proyecto plantea avanzar en la recopilación y desarrollo de herramientas (benchmarks) que permitan evaluar este tipo de plataformas de hardware de manera sistemática. Específicamente, se busca disponer de un conjunto de benchmarks que permitan identificar las diferentes características de las plataformas de hardware antes mencionadas y su efecto práctico en el desempeño computacional a la hora de usar dichas plataformas para ejecutar aplicaciones científicas.
Área temática: Inteligencia Artificial y Robótica
Supervisor responsable y contacto: Martín Pedemonte
Descripción del proyecto:
La detección de comunidades en redes ha cobrado gran interés por su aplicación al análisis de redes sociales, como por ejemplo en la influencia en la opinión pública de grupos radicales (radicalización) y antivacunas. El problema de detección de comunidades consiste en la identificación de agrupamientos de los nodos de la red (a los que se llama comunidades), a partir de la topología de la red.
Existen múltiples formulaciones del problema, incluyendo variantes con solapamiento entre las comunidades (un nodo puede pertenecer a más de una misma comunidad), costos asociados a las aristas del grafo y también centradas en el análisis de la evolución de las comunidades con el paso del tiempo. Esta familia de problemas presenta suele tener que lidiar con grandes volúmenes de datos (por ejemplo, el análisis podría estar basado en el uso de datos extraídos de Twitter).
El objetivo de este proyecto consiste en la utilización de técnicas de inteligencia computacional de la familia de los algoritmos evolutivos para resolver el problema de detección de comunidades en escenarios grandes. El enfoque estará basado fundamentalmente en considerar este aspecto en el diseño del algoritmo de resolución, aunque no se descarta la utilización de técnicas de computación de alto desempeño.
En la última década se ha producido una explosión en el uso de las redes neuronales (NN por su sigla en inglés) sustentada en el éxito que han demostrado especialmente las NN profundas para la resolución de una amplia variedad de problemas. El auge de las NN ha impulsado la adaptación de plataformas de propósito general ya existentes, así como el desarrollo de hardware específico para dar un soporte eficiente a las funcionalidades requeridas por estas técnicas. Hoy en día, existe un abanico amplio de dispositivos de hardware diseñados para el procesamiento de NNs. Cada una de estas plataformas, entre otras las GPUs, FPGAs y TPUs, cuenta con características particulares de funcionamiento, ofreciendo beneficios en contextos diferentes.
En este proyecto se busca, por un lado, caracterizar las diferentes técnicas de NN profundas en base al tipo de cálculos que realizan, y por otro lado, estudiar el desempeño de estas clases de Nns en distintas plataformas de hardware. Esto permitirá avanzar hacia una herramienta capaz de predecir el desempeño esperable de cierta NN sobre cierto tipo de hardware, o capaz de seleccionar el hardware más adecuado para cada red neuronal.