Nuestra experiencia en el uso de un clúster informático de 480 GPU AMD RX 480 para resolver problemas matemáticos. Como problema, tomamos la prueba del teorema de un artículo del profesor A. Chudnov "
Descomposiciones cíclicas de conjuntos que separan los dígrafos y las clases de juegos cíclicos con una recompensa garantizada ". La tarea es encontrar el número mínimo de participantes en una coalición en los juegos de coalición de tipo Nim, lo que garantiza la victoria de uno de los partidos.
Desarrollo de CPU
El primer procesador que realmente obtuvo distribución masiva es 8086 de Intel, desarrollado en 1978. La velocidad del reloj de 8086 era de solo 8 MHz. Unos años más tarde, aparecieron los primeros procesadores dentro de los cuales había 2, 4 e incluso 8 núcleos. Cada núcleo permitió que su código se ejecutara independientemente de los demás. A modo de comparación, el moderno procesador Intel Core i9-7980XE funciona a una frecuencia de 2.6 GHz y contiene 18 núcleos. Como puede ver, ¡el progreso no se detiene!
Desarrollo de GPU
Simultáneamente con el desarrollo de procesadores centrales, también se desarrollaron tarjetas de video. Básicamente, sus características son importantes para los juegos de computadora, donde las nuevas tecnologías son especialmente coloridas y la representación de imágenes en 3D se acerca gradualmente a la calidad fotográfica. Al comienzo del desarrollo de los juegos de computadora, el cálculo de la imagen se realizó en la CPU, pero pronto se alcanzó la inventiva de los desarrolladores de gráficos 3D, que lograron optimizar incluso las cosas obvias (
InvSqrt () es un buen ejemplo). Entonces, los coprocesadores con un conjunto especial de instrucciones para realizar cálculos en 3D comenzaron a aparecer en las tarjetas de video. Con el tiempo, el número de tales equipos creció, lo que, por un lado, permitió trabajar de manera más flexible y eficiente con la imagen, y por otro lado, complicó el proceso de desarrollo.
Desde 1996, comenzaron a producirse los aceleradores gráficos S3 ViRGE, 3dfx Voodoo, Diamond Monster y otros. En 1999, nVidia lanzó el procesador GeForce 256, introduciendo el término GPU, un procesador de gráficos. Ya es universal, puede manejar cálculos geométricos, transformar coordenadas, colocar puntos de iluminación y trabajar con polígonos. La diferencia entre la GPU y otros chips gráficos era que, además de los comandos especializados, había un conjunto de comandos estándar con los que podía implementar su propio algoritmo de representación. Esto dio una ventaja significativa, ya que permitió agregar efectos especiales, y no solo aquellos que ya están programados en la tarjeta de video. Comenzando con la GeForce 8000/9000, los procesadores de flujo aparecieron en la GPU, computadoras ya completas. Su número oscilaba entre 16 y 128 según el modelo. En la terminología moderna, se denominan unidades sombreadas unificadas, o simplemente unidades sombreadoras. ¡Las GPU AMD Vega 64 fabricadas hoy contienen 4096 unidades de sombreado, y la frecuencia de reloj puede alcanzar 1536 MHz!
¿Qué contiene una GPU?
La arquitectura de la GPU difiere de la CPU en una gran cantidad de núcleos y un conjunto minimalista de instrucciones destinadas principalmente a la computación vectorial. A nivel de arquitectura, se han resuelto los problemas de operación paralela de un gran número de núcleos y acceso simultáneo a la memoria. Las GPU modernas contienen de 2 a 4 mil unidades de sombreado, que se combinan en unidades informáticas (Unidad de cómputo). En computación paralela, el problema del acceso simultáneo a la memoria es especialmente grave. Si cada uno de los procesadores de flujo intenta escribir en la celda de memoria, estos comandos terminarán en el bloqueo y deberán colocarse en cola, lo que reducirá en gran medida el rendimiento. Por lo tanto, los procesadores de flujo ejecutan instrucciones en pequeños grupos: mientras un grupo realiza los cálculos, el otro carga los registros, etc. También puede combinar los núcleos en grupos de trabajo con memoria compartida y mecanismos de sincronización internos.
Otra característica importante de la GPU es la presencia de registros de vectores y ALU de vectores, que pueden realizar operaciones simultáneamente para varios componentes del vector. Esto es principalmente necesario para los gráficos 3D, pero como nuestro mundo es tridimensional, nada nos impide usarlo para muchos cálculos físicos. En presencia de ALU de vector libre, también se pueden usar para calcular cantidades escalares.
Son muy diferentes, CPU y GPU
Para el funcionamiento completo del sistema informático, ambos tipos de dispositivos son importantes. Por ejemplo, estamos ejecutando un programa paso a paso, un cierto algoritmo secuencial. No hay forma de realizar el quinto paso del algoritmo, por lo que los datos se calculan en el paso cuatro. En este caso, es más eficiente usar una CPU con un caché grande y una alta velocidad de reloj. Pero hay clases enteras de tareas que se prestan bien a la paralelización. En este caso, la efectividad de la GPU es obvia. El ejemplo más común es calcular los píxeles de una imagen renderizada. El procedimiento para cada píxel es casi el mismo, los datos sobre objetos 3D y texturas se encuentran en la RAM de la tarjeta de video, y cada procesador de flujo puede calcular independientemente su propia parte de la imagen.
Aquí hay un ejemplo de una tarea moderna: entrenar una red neuronal. Es necesario entrenar una gran cantidad de neuronas idénticas, es decir, para cambiar los coeficientes de peso de cada neurona. Después de tales cambios, es necesario pasar secuencias de prueba a través de la red neuronal para entrenar y obtener vectores de error. Dichos cálculos son adecuados para la GPU. Cada procesador de flujo puede comportarse como una neurona y durante el cálculo no será necesario construir la solución de manera secuencial, todos nuestros cálculos se realizarán simultáneamente. Otro ejemplo es el cálculo de flujos aerodinámicos. Es necesario averiguar el posible comportamiento del puente diseñado bajo la influencia del viento, simular su estabilidad aerodinámica, encontrar los sitios de instalación óptimos para los carenados para ajustar el flujo de aire o calcular la resistencia a la resonancia del viento. ¿Recuerdas el famoso "puente de baile" en Volgogrado? Creo que nadie querría estar en ese momento en el puente ...
El comportamiento del flujo de aire en cada punto puede describirse mediante las mismas ecuaciones matemáticas y resolver estas ecuaciones en paralelo en un gran número de núcleos.
GPU en manos de programadores
Para realizar cálculos en la GPU, se utiliza un lenguaje especial y un compilador. Existen varios marcos para realizar la computación general de GPU: OpenCL, CUDA, C ++ AMP, OpenACC. Los dos primeros fueron ampliamente utilizados, pero el uso de CUDA está limitado solo por las GPU de nVidia.
OpenCL fue lanzado en 2009 por Apple. Más tarde, Intel, IBM, AMD, Google y nVidia se unieron al Grupo Khronos y anunciaron su apoyo al estándar común. Desde entonces, aparece una nueva versión del estándar cada uno y medio o dos años y cada uno trae mejoras cada vez más serias.
Hasta la fecha, el lenguaje OpenCL C ++ versión 2.2 cumple con el estándar C ++ 14, admite la ejecución simultánea de varios programas dentro del dispositivo, la interacción entre ellos a través de colas y tuberías internas, y permite una administración flexible de buffers y memoria virtual.
Tareas reales
Un problema interesante de la teoría de los juegos, en cuya solución participamos, es la prueba del teorema de un artículo del profesor A. Chudnov "
Descomposiciones cíclicas de conjuntos que separan los dígrafos y las clases de juegos cíclicos con una recompensa garantizada ". La tarea es encontrar el número mínimo de participantes en una coalición en los juegos de coalición de tipo Nim, lo que garantiza la victoria de uno de los partidos.
Desde un punto de vista matemático, esta es una búsqueda de una secuencia cíclica de soporte. Si representa la secuencia en forma de una lista de ceros y unos, entonces la verificación de soporte puede implementarse mediante operaciones lógicas bit a bit. Desde el punto de vista de la programación, dicha secuencia es un registro largo, por ejemplo, 256 bits. La forma más confiable de resolver este problema es clasificar todas las opciones excepto las imposibles por razones obvias.
Los objetivos de resolver el problema son cuestiones de procesamiento efectivo de señales (detección, sincronización, medición de coordenadas, codificación, etc.).
La complejidad de resolver este problema es clasificar una gran cantidad de opciones. Por ejemplo, si estamos buscando una solución para n = 25, entonces esto es 25 bits, y si n = 100, entonces esto ya es 100 bits. Si tomamos el número de todas las combinaciones posibles, entonces para n = 25 es 2 ^ 25 = 33 554 432, y para n = 100 ya es 2 ^ 100 = 1 267 650 600 228 229 401 496 703 205 376 combinaciones. ¡El aumento de la complejidad es simplemente colosal!
Esta tarea está bien paralelizada, lo que significa que es ideal para nuestro clúster de GPU.
Programadores vs Matemáticas
Inicialmente, los matemáticos resolvieron este problema en Visual Basic en Excel, por lo que lograron obtener soluciones primarias, pero el bajo rendimiento de los lenguajes de secuencias de comandos no nos permitió avanzar mucho. La decisión de n = 80 tomó un mes y medio ... Inclinamos nuestras cabezas frente a estas personas pacientes.
La primera etapa, implementamos el algoritmo de tarea en C y lo lanzamos en la CPU. En el proceso, resultó que mucho se puede optimizar cuando se trabaja con secuencias de bits.
A continuación, optimizamos el área de búsqueda y eliminamos la duplicación. Además, un análisis del código ensamblador generado por el compilador y la optimización del código para las características del compilador dieron un buen resultado. Todo esto hizo posible lograr un aumento significativo en la velocidad de los cálculos.
La siguiente etapa de optimización fue la elaboración de perfiles. La medición del tiempo de ejecución de varias secciones del código mostró que en algunas ramas del algoritmo la carga en la memoria aumentó significativamente, así como se reveló una ramificación excesiva del programa. Debido a esta falla "pequeña", casi un tercio de la potencia de la CPU no se utilizó.
Un aspecto muy importante para resolver estos problemas es la precisión de la escritura del código. Nadie sabe las respuestas correctas a este problema y, en consecuencia, no hay vectores de prueba. Solo existe la primera parte de la gama de soluciones que los matemáticos han encontrado. La fiabilidad de las nuevas soluciones solo puede garantizarse mediante la precisión de la escritura del código.
Por lo tanto, la etapa de preparación del programa para la solución en la GPU ha llegado y el código se ha modificado para funcionar en varios subprocesos. El programa de control ahora se dedica a despachar tareas entre subprocesos. ¡En un entorno de subprocesos múltiples, la velocidad de cálculo ha aumentado 5 veces! Esto se logró debido a la operación simultánea de 4 hilos y la combinación de funciones.
En esta etapa, la decisión hizo los cálculos correctos hasta n = 80 en 10 minutos, mientras que en Excel, ¡estos cálculos tomaron un mes y medio! Pequeña victoria!
GPU y OpenCL
Se decidió utilizar OpenCL versión 1.2 para garantizar la máxima compatibilidad entre diferentes plataformas. La depuración inicial se realizó en la CPU de Intel, luego en la GPU de Intel. Luego cambiaron a la GPU de AMD.
El estándar OpenCL 1.2 admite variables enteras de 64 bits. La dimensión de 128 bits es limitada por AMD, pero se compila en dos números de 64 bits. Por razones de compatibilidad y para optimizar el rendimiento, se decidió presentar un número de 256 bits como un grupo de números de 32 bits, operaciones lógicas en bits que se realizan en la GPU ALU interna lo más rápido posible.
Un programa OpenCL contiene un núcleo, una función que es el punto de entrada de un programa. Los datos para el procesamiento se descargan de la CPU a la RAM de la tarjeta de video y se transfieren al kernel en forma de buffers, punteros a una matriz de datos de entrada y salida. ¿Por qué una matriz? Realizamos informática de alto rendimiento, necesitamos muchas tareas que se realizan simultáneamente. El kernel se ejecuta en el dispositivo en varias instancias. Cada núcleo conoce su identificador y toma su propia entrada de un búfer compartido. El caso cuando la solución más simple es la más efectiva. OpenCL no es solo un lenguaje, sino también un marco integral en el que todos los detalles de la informática científica y de juegos están completamente pensados. Esto hace la vida más fácil para el desarrollador. Por ejemplo, puede iniciar muchos hilos, el administrador de tareas los colocará en el propio dispositivo. Las tareas que no comenzaron la ejecución inmediata se pondrán en cola y se lanzarán a medida que las unidades informáticas se liberen. Cada instancia de kernel tiene su propio espacio en el búfer de salida, donde coloca la respuesta al finalizar el trabajo.
La tarea principal del administrador de OpenCL es garantizar la ejecución paralela de varias instancias del núcleo. Aquí se aplica la experiencia científica y práctica acumulada durante décadas. Mientras que algunos núcleos cargan datos en registros, otra parte en este momento funciona con memoria o realiza cálculos; como resultado, el núcleo de la GPU siempre está completamente cargado.
El compilador de OpenCL hace un buen trabajo de optimización, pero es más fácil para un desarrollador influir en el rendimiento. La optimización de la GPU va en dos direcciones: acelerar la ejecución del código y la posibilidad de paralelizarlo. La forma en que el compilador paraleliza el código depende de varias cosas: la cantidad de registros de memoria virtual ocupados (que se encuentran en la memoria de GPU más lenta, global), el tamaño del código compilado (debe caber en 32 kb de caché), la cantidad de registros vectoriales y escalares utilizados.
GPU ComBox A-480 o un millón de núcleos
Esta es la parte más interesante del proyecto, cuando cambiamos de Excel a un clúster informático que consta de 480 tarjetas gráficas AMD RX 480. Grande, rápido y eficiente. Completamente listo para cumplir la tarea y obtener esos resultados que el mundo nunca antes había visto.
Me gustaría señalar que en todas las etapas de mejora y optimización del código, comenzamos la búsqueda de una solución desde el principio y comparamos las respuestas de la nueva versión con las anteriores. Esto nos permitió asegurarnos de que la optimización y las mejoras del código no introdujeran errores en las soluciones. Aquí debe comprender que no hay respuestas correctas al final del libro de texto y que nadie en el mundo las conoce.
El lanzamiento en el clúster confirmó nuestras suposiciones sobre la velocidad de las soluciones: la búsqueda de secuencias para n> 100 tomó aproximadamente una hora. Fue sorprendente ver cómo las nuevas soluciones estaban en el clúster ComBox A-480 en minutos, mientras que en la CPU tomó muchas horas.
En solo dos horas del clúster informático, obtuvimos todas las soluciones hasta n = 127. Una verificación de las soluciones mostró que las respuestas obtenidas son confiables y corresponden a los teoremas del profesor A. Chudnov establecidos en el artículo
Evolución de la velocidad
Si observa la ganancia de rendimiento durante la solución del problema, los resultados fueron aproximadamente los siguientes:
- un mes y medio a n = 80 en Excel;
- una hora para n = 80 en Core i5 con un programa optimizado de C ++;
- 10 minutos para n = 80 en Core i5 usando subprocesamiento múltiple;
- 10 minutos a n = 100 en una GPU AMD RX 480;
- 120 minutos para n = 127 en el ComBox A-480.
Perspectivas y futuro
Muchas tareas en la intersección de la ciencia y la práctica están pendientes para mejorar nuestras vidas. El mercado de alquiler de energía informática está emergiendo y la necesidad de computación paralela continúa creciendo.
Posibles aplicaciones de la computación paralela:
- tareas de control automático de vehículos y drones;
- cálculos de características aerodinámicas e hidrodinámicas;
- reconocimiento de voz e imágenes visuales;
- entrenamiento de redes neuronales;
- tareas de astronomía y astronáutica;
- análisis estadístico y de correlación de datos;
- compuestos de proteína-proteína plegables;
- diagnóstico temprano de enfermedades con IA.
Una dirección separada es la computación en la nube en la GPU. Por ejemplo, gigantes como Amazon, IBM y Google arriendan su potencia informática a la GPU. Hoy podemos decir con confianza que el futuro de la computación paralela de alto rendimiento pertenecerá a los clústeres de GPU.