UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

Sistema de programación matemática en paralelo empleando tarjetas gráficas. Autor: Alfredo G. Escobar Portillo Director: Jesús Mª Latorre Canteli Resumen: El presente proyecto intenta comprobar la eficacia de las tecnologías GPGPU en su aplicación a algoritmos matriciales y vectoriales. Para ello se ha elegido el método Símplex Revisado como punto de partida, sobre el que se ha implementado una versión con ejecución pura en CPU junto con otra versión de ejecución mixta en CPU y GPU. De entre todas las tecnologías GPGPU existentes se ha elegido CUDA de la compañía NVidia como la más apropiada para llevar a cabo el proyecto, debido a su mayor madurez y a su mayor rendimiento. Después del proceso de desarrollo de las dos versiones, una fase de pruebas sirve para contrastar el rendimiento de cada una de las versiones y comparar los rendimientos obtenidos entre ellas. De esta forma se pretende demostrar que el uso de las tecnologías GPGPU es beneficioso tanto en entornos científicos, corporativos e incluso domésticos. C laves: Símplex, CUDA, GPGPU, optimización. Introducción: Existen en el ámbito científico y matemático multitud de algoritmos y métodos que se pueden expresar de forma vectorial o matricial. La ejecución de este tipo de algoritmos en un ordenador, precisamente por la característica de poder expresarse de esa forma, es paralelizable en la mayoría de los casos de forma relativamente sencilla. Este interés por paralelizar algoritmos viene de lejos, y de forma común se ha llevado a cabo utilizando procesadores vectoriales y más recientemente haciendo uso de computación distribuida (GRID). De unos años a esta parte, la tecnología empleada para la fabricación de las tarjetas gráficas ha evolucionado de una manera mucho más significativa que otras áreas del mundo tecnológico, debido a las cada vez mayores demandas de potencia que solicitan aplicaciones de tipo CAD, modelado 3D, diseño gráfico o juegos. Las tarjetas gráficas de hace años tenían todas las funciones implementadas en el propio hardware, totalmente inamovibles, situación que cambió hace ya años con el lanzamiento de la GeForce 3, primera tarjeta con shaders programables. La idea de usar esa potencia para otros menesteres se denomina GPGPU (General Purpose computation on Graphics Processing Units) o GPU Computing. En el 1

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

momento en el que las tarjetas gráficas permiten que se programen funciones sobre su hardware, se comienza a hacer uso de GPGPU. Al principio era necesario utilizar los lenguajes propios enfocados a la visualización en pantalla (como OpenGL) para realizar otros cálculos para nada relacionados con la visualización. Esto implicaba el uso de unas cabeceras predefinidas, con entradas y salidas de funciones muy poco flexibles, lo que hacía que la labor de programar para tal fin fuese realmente tediosa. Para facilitar el uso de las tarjetas gráficas para cualquier uso no vinculado con los gráficos, NVidia desarrolló toda una tecnología alrededor de la tarjeta y que permitía usar la misma para cualquier tarea: CUDA. ATI, un poco más tarde haría lo propio lanzando su propia tecnología: Stream. Debido a la mayor madurez de la tecnología CUDA sobre el resto de tecnologías, ésta ha sido la elegida para llevar a cabo este proyecto, con el objetivo de intentar demostrar sus ventajas (e inconvenientes) mediante la comparación de un algoritmo matricial sobre el que se han implementado dos versiones: una que se ejecuta en CPU y otra que ejecuta en GPU (realmente es ejecución mixta CPUGPU). Como algoritmo se ha elegido el método Símplex Revisado, método que sirve para optimizar problemas de programación lineal, de tal forma que minimiza una función objetivo cuyas variables están sujetas a unas restricciones (y puede que a unas cotas). Estos problemas pueden ser de muy variados tamaños, pudiendo contener desde unas pocas hasta millones de variables y restricciones. Se suelen almacenar en archivos MPS, con los que habrá que tratar a lo largo del proyecto. Desar rollo: Para la consecución de los objetivos del proyecto ha sido necesario conocer de primera mano los detalles del método Símplex Revisado, comprendiendo su funcionamiento y buscando mejoras aplicables a la programación dentro de lo posible. El método es iterativo y dada una solución inicial, es capaz de mejorar esta solución iteración a iteración hasta llegar a obtener el resultado óptimo para el problema que se esté intentando solucionar, obteniendo el mínimo de la función objetivo. Conocido el problema a solucionar, se ha llevado a cabo un diseño modular de la aplicación a desarrollar, la cual consta de cuatro módulos: módulo de preproceso y control, módulo de input, módulo de proceso (núcleo Símplex) y módulo de inversión de matrices (ver Figura 1). Una vez conocido el funcionamiento exacto del algoritmo se ha desarrollado una versión del mismo con ejecución pura en CPU. Todos y cada uno de los módulos se ejecutan en CPU. La aplicación se ha programado en C puro. A continuación es necesario conocer los entresijos de la arquitectura que ofrece CUDA y las tarjetas gráficas NVidia en particular para poder realizar la transformación de la versión CPU a la versión GPU. Para ello se ha realizado un estudio de dicha arquitectura que incluye diferentes aspectos como pueden ser el 2

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

modelo de ejecución, funcionamiento de la memoria o transferencia de datos entre CPU y GPU.

F igura 1Modelo del sistema.

El siguiente paso ha consistido en transformar la versión que ya se ha desarrollado en una nueva versión que se ejecute en GPU. Realmente, no toda la nueva versión se ejecuta en GPU, ya que no es posible portar todos los módulos a CUDA. Los módulos de input y de preproceso y control no se han modificado en absoluto, siendo los otros módulos los que sufren importantes cambios (ver Figura 1). La función principal del módulo de proceso (núcleo Símplex) se ejecuta sobre la CPU, la cual guiará todo el proceso. Serán las funciones que se vayan llamando durante todo el proceso las que se vayan ejecutando en GPU, manteniendo una estructura similar a la versión CPU con el objetivo de que los tiempos obtenidos en cada una de las fases sean comparables entre versiones (ver Figura 2). El desarrollo de las dos versiones ha sido la parte que más tiempo ha llevado en el proyecto, y conseguidas las dos versiones se ha procedido a la fase de pruebas con problemas reales.

3

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

F igura 2Función principal del módulo de proceso.

Método de prueba: Para probar las dos versiones y observar las diferencias en cuanto a tiempos de ejecución entre versiones se han realizado una serie de pruebas. Para ello, se han seleccionado una serie de problemas procedentes de los repositorios de NETLIB, en concreto 36 problemas de diversos tamaños. La plataforma de pruebas consiste en un equipo que consta de una CPU Intel Core 2 Duo E8500 con una frecuencia de trabajo de 3.16 GHz y 6 MB de memoria caché (L2). Este procesador servirá para comprobar los tiempos de ejecución de la versión en CPU. Cada uno de los problemas se ha ejecutado diez veces, para después realizar la media entre los tiempos de las diez ejecuciones. Se pretende de esta forma que los resultados no estén influidos por circunstancias que pudieran alterar los resultados y así obtener resultados más exactos. Para probar la versión en GPU, se ha dotado al mismo sistema anterior con dos *38¶V 19LGLD DPEDV FRPSDWLEOHV FRQ &8'$ XQD *H)RUFH *7;  GH  núcleos CUDA y una GTX 480 de 480 núcleos CUDA. Esto permite realizar pruebas con las dos tarjetas de forma independiente, obteniendo al final de las pruebas tres series de pruebas comparables entre ellas. 4

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

Las pruebas para cada una de las tarjetas se han realizado de forma similar a la versión en CPU, es decir, diez ejecuciones por problema y obtención de la media de las ejecuciones. Resultados: Puesto que se han probado una gran cantidad de problemas, no es posible reproducir los resultados de todos ellos en este resumen, por lo que se exponen los casos más significativos.

F igura 3Tiempos problema GANG E S (milisegundos)

El problema GANGES (Figura 3) es uno de los que más beneficiado sale por la versión con ejecución en GPU, y a la vez es uno de los mayores en términos de restricciones (1309). Se puede observar cómo la versión ejecutada en la tarjeta 260GTX soluciona el problema en casi la mitad de tiempo total (TOTAL en el gráfico), mientras que la tarjeta 480GTX llega a solucionarlo en menos de la 5

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

cuarta parte de tiempo. Sin duda es una gran ganancia de tiempo, pasando de unos 75 segundos de ejecución en CPU a menos de 20 segundos en la tarjeta más rápida. Se puede ver de la misma forma las partes del algoritmo que marcan la diferencia a favor de las versiones GPU, siendo éstas las que corresponden al cálculo de matrices inversas (INVE1 e INVE2) y al cálculo de la columna del pivote (FTRAN1 y FTRAN2). No es casualidad que estas partes sean básicamente multiplicaciones matriz-matriz o matriz-vector, mientras que el resto de fases cuentan con otros tipos de cálculos entre los que además de éstos se incluyen otros no tan paralelizables.

F igura 4Tiempos problema ADLITTLE (milisegundos)

El problema ADLITTLE (Figura 4) es uno de los problemas más pequeños de todos los probados en cuanto a restricciones (56). Se puede observar cómo la

6

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

versión CPU es infinitamente más rápida que la versión GPU en ambas tarjetas gráficas. Este comportamiento se observa en todos los problemas con pocas restricciones, de tal forma que cuanto mayor sea el número de restricciones con las que está modelado un problema, mayor es su rendimiento en GPU frente a la CPU. En problemas pequeños, incluso el tiempo de inicialización de la tarjeta es significativo, reflejándose ese tiempo en la fase TRANS1 (porque ahí está la primera llamada a la API CUDA de la aplicación), que debería tener un tiempo muy parecido al de la fase TRANS2. Obviamente esta inicialización solamente se lleva a cabo en la versión GPU y en cuanto los problemas crecen en tamaño, se convierte en un dato completamente irrelevante ya que la inicialización es del orden de milisegundos (entre 30 y 50 dependiendo de problema y tarjeta).

F igura 5Mejora obtenida en GPU frente a CPU.

Esta relación directa entre mejora y restricciones se puede ver de forma clara en la Figura 5, donde se encuentran representados todos los problemas que se han probado. En la figura se puede ver cómo evoluciona la mejora de rendimiento de la versión GPU con el aumento de restricciones del problema (en las dos GPU probadas). En particular, con el problema más grande se obtiene una ganancia de rendimiento con un coeficiente de más de 4,6. Conclusiones: La relación entre la diferencia de rendimiento entre versiones y el número de restricciones vista en el punto anterior se justifica porque el número de 7

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

restricciones marca el tamaño de la matriz de la base usada en los cálculos (número de restricciones al cuadrado), entre otras matrices y vectores. Esta matriz se usa en muchos de los cálculos por lo que al aumentar mucho su tamaño, la versión CPU tenderá a tardar mucho más tiempo, mientras que la versión en GPU, al aprovechar la paralelización no se ve tan afectada por el tamaño de la matriz de la base. Como conclusiones finales a la realización de este proyecto destaca el pobre rendimiento de la versión GPU con problemas pequeños (con menos de 600 restricciones según se ha determinado de forma empírica) frente a la cada vez mayor ganancia de rendimiento frente a la CPU conforme aumenta el número de restricciones del problema. Como consecuencia de esto no es aconsejable el uso de la GPU para problemas menores de esas 600 restricciones, siendo sin embargo muy aconsejable su uso para problemas realmente grandes. Este resultado es extrapolable a cualquier otro algoritmo paralelizable, de forma que siempre habrá un punto a partir del cual merezca la pena su paralelización mediante la tecnología CUDA, no siendo aconsejable por debajo de este margen, que será específico para cada algoritmo. Aun así, CUDA es una tecnología con mucho futuro en diversos ámbitos ya que se pueden obtener resultados sorprendentes incluso en el ámbito doméstico, donde FDGDYH]VHFXHQWDFRQ*38¶VPiVSRWHQWHV

Referencias: x www.gpgpu.org. Julio 2010. x ³,QYHVWLJDFLyQGH2SHUDFLRQHV´+LOOLHU)(GLFLyQ x ³0RGLILFDWLRQDQG,PSOHPHQWDWLRQRI7ZR-3KDVH6LPSOH[0HWKRG´ Stokovic, Nebojsa. 2005. x www.netlib.org/lp/data/. Noviembre 2010. x ³19LGLD&8'$&3URJUDPPLQJ*XLGH´. NVidia Corporation año 2010. x www.gpgpu.org. Julio 2010. x ³7KH)LQDO1(7/,%-/3UHVXOWV´.RFK7

8

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

Mathematical programming system using graphic cards Author: Alfredo G. Escobar Portillo Director: Jesús Mª Latorre Canteli A bstract: This project aims to test the effectiveness of GPGPU technologies in their application to matrix and vector algorithms. Revised Simplex method has been chosen as a starting point on which it has been implemented pure CPU execution version and another version with mixed CPU and GPU execution. Among all the existing GPGPU technologies, NVidia CUDA has been chosen because it is the best suited to carry out the project due to its greater maturity and performance. After the development process of the two versions, a testing phase has served to obtain the performance of different versions and to compare the results obtained from them. This project is intended to demonstrate that the use of GPGPU technology is beneficial in scientific, corporate and even domestic environments. K ey words: Simplex, CUDA, GPGPU, optimization. Introduction: There are a lot of scientific and mathematic algorithms that can be expressed in a matricial or vectorial way. The implementation of such algorithms in a computer is parallelizable in most cases in a relatively easy manner, just because it is possible to express them in that way. For a long time there has been a lot of interest in parallel computation, and in the classic way it has been solved using vector processors, and in the last years there has been a lot of progress in distributed computing (GRID). For a few years now, the technology applied in graphic cards manufacturing has evolved in a much more significant way than the rest of technology areas, due to the increasing performance demands of CAD applications, 3D modeling applications, graphic design applications or games. Old graphic cards used to have hardware implemented functions that were completely fixed. This situation changed some years ago with the development of the GeForce 3 series, the first graphic card with programmable shaders. The idea of using that power with a different purpose is called GPGPU (General Purpose computation on Graphics Processing Units), also known as GPU Computing. GPGPU has been used from the moment in which modern cards became programmable. At first it was necessary to make use of languages focused on screen visualization (such as OpenGL) to execute calculations not related to the display. This involved 1

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

the use of not flexible predefined headers, input and output in every function, making programming a very tedious work. To facilitate the use of graphic cards for any purpose not connected with graphics, NVidia developed a new technology over the card that allowed using it for any task: CUDA. ATI would do the same thing later by launching its own technology: Stream. Due to the greater maturity of CUDA technology over other technologies, it has been chosen to carry out this project with the aim of proving its advantages (and disadvantages) by comparing the matrix algorithm on which it has been implemented two versions: one that runs on CPU and another one that runs on GPU (in fact, mixed CPU-GPU execution). The chosen algorithm is called Revised Simplex method, which is used to optimize linear programming problems in such a way that minimizes an objective function whose variables are subject to some constraints (and maybe some bounds). These problems can be of very different sizes and may contain from some few to millions of variables and constraints. LP are typically stored in MPS files, with which it has been necessary to deal throughout the project. Development: To achieve the objectives of the project it has been necessary to know firsthand the details of the Revised Simplex method, understanding how it works and looking for applicable improvements that could be useful along the programming phase. It is an iterative method and it is capable of obtaining the minimum of an objective function by beginning with an initial solution, improving this solution iteration by iteration until it finds the optimal solution for the problem it is trying to solve. Once it is known the problem to be developed, it has been carried out a modular design of the application, which contains four modules: preprocessing and control module, input module, processing module (Simplex core) and matrix inversion module (see Figure 1). In order to know the exact operation of the algorithm, it has been developed a version with pure CPU execution. Each and every one of the modules runs on CPU. The application has been programmed in standard C. Then it is necessary to know the details of CUDA architecture, and NVidia graphic cards in particular, to make the conversion from the CPU version to the GPU version. With this goal in mind, it has been undertaken a study about the architecture that includes various aspects such as execution model, memory or data transfer between CPU and GPU.

2

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

F igure 1 System model.

The next step has been transforming the already developed version (CPU version) into a new version that runs on GPU. Actually, not all of the new code runs on GPU, because it is not possible to port all the modules to CUDA. Input modules and preprocess and control module have not changed at all, being just the other modules the ones affected by the changes (see Figure 1). The main function of the process module (Simplex core) runs on the CPU, which will guide the entire process. This function will make the appropriate calls to GPU functions, while maintaining a similar structure with CPU version. This makes it possible to obtain comparable results between versions (see Figure 2). The development of the two versions has been the most time taking phase of the project, and once the two versions have been developed it has been carried out the testing phase using real problems.

3

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

F igure 2 S implex core diagram.

T est method: To test the two versions and see the differences in execution time between them it has been made a series of tests. To this end, it has been selected a number of problems taken from NETLIB repositories, specifically 36 problems with various sizes. The test platform consists of a machine equipped with an Intel Core 2 Duo E8500 with a working frequency of 3.16 GHz and 6 MB of cache (L2). This processor will be the one which will run the CPU version. Each problem has been run ten times, and then it has been calculated the average time of those ten executions. The reason for doing things this way is to make sure that the results are not affected by circumstances that could alter them, and to get more accurate results. 4

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

To test the GPU version, the same machine as before has been added two NVIDIA GPUs, both CUDA capable GPUs: a GeForce GTX 260 with 192 CUDA cores, and a GTX 480 with 480 CUDA cores. This allows testing with both cards independently. Therefore, it has been obtained three series of comparable data. Results: Since it has been tested a lot of problems, it is not possible to reproduce all the results in this document. Therefore, the most significant cases have been selected.

F igure 3 GANG E S execution time (ms)

The problem called GANGES (Figure 3) is one of the most favored by the version running on GPU, and it is also one of the largest in terms of constraints (1309). It can be observed how the version running on the 260GTX card solves the problem in less than a half of CPU time, while the 480GTX card comes to make it in less 5

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

than a quarter of CPU time. It is certainly a great gain of time, going from about 75 seconds of CPU execution to less than 20 seconds on the fastest card. It can be seen in the same way the parts of the algorithm that make the difference between versions, these being the corresponding to the calculation of inverse matrices (INVE1 and INVE2) and the calculation of the pivot column (FTRAN1 and FTRAN2) . It is not a coincidence that these pieces of code are basically matrix-matrix or matrix-vector multiplications, while the other pieces of code have other types of calculations not so parallelizable.

F igure 4 ADLITTLE execution time (ms).

The problem called ADLITTLE (Figure 4) is one of the smallest problems of all. It contains only 56 constraints. It can be seen how the CPU version is definitely faster than the version executed on both graphics cards.

6

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

This behavior is observed in all the problems with few constraints, showing that the larger the number of constraints that a problem has, the greater GPU performance against the CPU is. In small problems, even initialization time of the card is significant, reflecting that time in TRANS1 (because the first call to the CUDA API in the application is in that piece of code), which should have a very similar time to TRANS2. Obviously this initialization only takes place on the GPU version, and as problems gets big sized, it becomes a completely irrelevant number, since initialization is in the range of milliseconds (30 to 50 depending on the problem and card).

F igure 5 GPU/CPU gain ratios.

This direct relationship between time improvement and constraints can be seen clearly in Figure 5, where all the problems that have been tested are represented. In that figure it can be seen how the performance of the GPU version improves if the number of constraints of the problem are increased (in both GPU tested). In particular, the biggest problem gets a performance gain ratio of over 4.6. Conclusions: Relationship between the performance difference among versions and the number of constraints seen in the previous section is justified because the number of 7

UNIVERSIDAD PONTIFICIA COMILLAS Escuela Técnica Superior de Ingeniería (ICAI) Ingeniería Informática

constraints marks the size of the base matrix used in the calculations, and other matrices and vectors. This matrix is used in many of the calculations, and if its size increases very much, CPU version takes considerably longer to finish the task, while the GPU version, taking advantage of parallelization, is not so affected by the size of the base matrix. As final conclusion of this project, it shows the poor performance of the GPU version with small problems (less than 600 constraints as determined through simulation) but as the number of constraints is increased, the gain ratio of the GPU version also gets higher. As a result of this, it is not advisable to use GPU to solve problems with less than 600 constraints, and it is strongly recommended its use for really big problems. This result can be extrapolated to any other parallelizable algorithm, so there will always be a point at which using CUDA parallelization will be worth, which will be specific to each algorithm. Still, CUDA is a technology with a promising future in various environments because it can achieve amazing results even in the domestic scope, where it is easy to find very powerful graphic cards nowadays. References: x www.gpgpu.org. July 2010. x ³Introduction to Operation Research´+LOOLHU)(GLtion. 2001. x ³0RGLILFDWLRQDQG,PSOHPHQWDWLRQRI7ZR-3KDVH6LPSOH[0HWKRG´ Stokovic, Nebojsa. 2005. x www.netlib.org/lp/data/. November 2010. x ³19LGLD&8'$&3URJUDPPLQJ*XLGH´. NVidia Corporation 2010. x www.gpgpu.org. July 2010. x ³7KH)LQDO1(7/,%-/3UHVXOWV´.RFK7

8