UNIVERSIDAD NACIONAL DE SAN ANTONIO ABAD DEL CUSCO

FACULTAD DE INGENIERÍA ELÉCTRICA, ELECTRÓNICA, INFORMÁTICA Y

MECÁNICA

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

“IMPLEMENTACION DEL ALGORITMO DE INTEGRACION USANDO CUDA”

CURSO: Programación Concurrente y Paralela

DOCENTE: Ing. Iván Cesar Medrano Valencia

TRABAJO PRESENTADO POR:

 HUAMAN QUISPE YHERSON ANTONI 131357

 JARA QUISPE LUIS MANUEL 110595
 MOLLINEDO PEÑA YERALDO LUIS 110601
 ZEGARRA CORIMANYA MARCO AURELIO 103181
 ZEGARRA CORIMANYA CRISTEL DAYANA 151831

CUSCO - PERÚ

2018
PRESENTACIÓN

El presente trabajo de investigación muestra el desarrollo de una aplicación que

aprovecha el uso del GPU de nuestra tarjeta gráfica para así lograr un procesamiento
de mayor velocidad del que se podría conseguir mediante el uso de programas
desarrollados La GPU (Unidad de Procesamiento Gráfico) ha emergido en los últimos
años como una plataforma alternativa para el procesamiento paralelo a costo
accesible. Es una arquitectura manycore caracterizada por un número masivo de
procesadores simples, cuyo uso avanzó en otros campos además del procesamiento
de imágenes. Las GPUs modernas pueden ser descriptas como un vector de
procesadores que ejecutan la misma instrucción sobre diferentes datos de forma
paralela. El presente trabajo se encuentra organizado en tres capítulos, los cuales se
mencionan a continuación:

En el capítulo I, se abordan los aspectos generales, como el planteamiento del

problema, definición de los objetivos, limitaciones, la justificación que será necesaria
para el proyecto.

En el capítulo II, se describe que y como funciona CUDA y que metodología

implementamos para nuestro proyecto.

En el capítulo III, se plantea el desarrollado el programa haciendo uso de CUDA

y como es el desempeño en nuestro computador.

Finalmente, se presentan las conclusiones y un análisis de los resultados

obtenidos, que servirán de apoyo para poder comprender el funcionamiento de CUDA.

i
INTRODUCCIÓN

Las computadoras modernas tienen ahora procesadores que son muy poderosos.
Muchos de ellos tienen más de un núcleo, lo cual quiere decir que pueden hacer
multiprocesos, es decir, ejecutar instrucciones de diferentes programas “al mismo
tiempo”. De hecho, muchas tarjetas gráficas, como las Nvidia, tienen muchos núcleos
gráficos, para acelerar los procesos de despliegue gráfico en la computadora. Y que
conste, hablamos de decenas de núcleos para hacer procesamiento gráfico en
paralelo.

Con esto en mente a más de uno se le ha ocurrido hacer proceso en paralelo en

la computadora. El problema es que un programa por sí mismo solamente puede
exhibir paralelismo en algunas partes del programa. Por ejemplo, si estamos
procesando una imagen, podemos hacer en paralelo el mismo proceso (como cuando
queremos filtrar la imagen, por ejemplo) y así obtendremos el resultado más
rápidamente. Sin embargo, para ello el lenguaje de aplicación debería soportar
paralelismo y eso no se ve en general en las características de los lenguajes de
programación.

La razón de esto es que hay una solución más eficiente y alternativa al problema
planteado. En lugar de implementar el paralelismo en cada lenguaje de programación,
lo que podemos hacer es hacer una biblioteca de funciones que permitan hacer el
paralelismo en las funciones y procedimientos susceptibles de ello.

Una de las herramientas más populares para ellos es CUDA – Compute Unified
Device Architecture (Arquitectura Unificada de Dispositivos de Cómputo), que hace
referencia tanto a un compilador como a un conjunto de herramientas de desarrollo
creadas por Nvidia, que permiten a los programadores codificar sus algoritmos y sacar
provecho de los núcleos de las tarjetas gráficas. Y de hecho, gracias a una técnica
llamada wrappers, se puede usar CUDA en Python, Fortran y Java, en lugar de usar
necesariamente C/C++. Se plantea en un futuro agregar esta funcionalidad también a
FORTRAN, OpenGL y Direct3D.

CUDA busca explotar las ventajas de las GPU frente a las CPU de propósito
general utilizando el paralelismo que ofrecen sus múltiples núcleos, que permiten el
lanzamiento de un altísimo número de hilos simultáneos (threads). Por ello, si una
aplicación está diseñada utilizando numerosos hilos que realizan tareas
independientes (que es lo que hacen las GPU al procesar gráficos, su tarea natural),
una GPU podrá ofrecer un gran rendimiento en campos que podrían ir desde la
biología computacional a la criptografía, entre otros ejemplo.

iii
ÍNDICE

PRESENTACIÓN ........................................................................................................................................ II
INTRODUCCIÓN ...................................................................................................................................... III
CAPÍTULO I: ASPECTOS GENERALES ..................................................................................................... - 1 -
1.1. DESCRIPCIÓN DEL PROBLEMA .................................................................................................................. - 1 -
1.2. OBJETIVOS .......................................................................................................................................... - 1 -
1.2.1 Objetivo general ....................................................................................................................... - 1 -
1.2.2 Objetivos específicos ................................................................................................................ - 1 -
1.3. LIMITACIONES ...................................................................................................................................... - 1 -
1.4. JUSTIFICACIÓN ..................................................................................................................................... - 1 -
1.5. METODOLOGÍA .................................................................................................................................... - 2 -
CAPÍTULO II: MARCO TEÓRICO ............................................................................................................ - 3 -
2.1. PROGRAMACIÓN PARALELA .................................................................................................................... - 3 -
2.2. ARQUITECTURAS EN PARALELO ................................................................................................................ - 4 -
2.3. ARQUITECTURAS GPU .......................................................................................................................... - 4 -
2.4. ARQUITECTURA CUDA .......................................................................................................................... - 5 -
CAPÍTULO III: DESARROLLO DEL PROYECTO ......................................................................................... - 8 -
3.1. ANÁLISIS DEL PROGRAMA PARALELO PARA EL ALGORITMO DE INTEGRACIÓN. .................................................... - 8 -
3.2. CONSTRUCCIÓN DE UN CLÚSTER EN PELICAN HPC....................................................................................... - 9 -
3.3. DISEÑO. ........................................................................................................................................... - 13 -
3.4. PRUEBAS. ......................................................................................................................................... - 13 -
CONCLUSIONES ..................................................................................................................................- 15 -
BIBLIOGRAFIA .....................................................................................................................................- 16 -

iii
INDICE DE FIGURAS
Figura 1.Programación en paralelo ____________________________________________________________ - 3 -
Figura 2. Abstracción Arquitectura GPU vs. Arquitectura CPU_______________________________________ - 4 -
Figura 3. Arquitectura general de una GPU _____________________________________________________ - 5 -
Figura 4. Arquitectura CUDA _________________________________________________________________ - 6 -
Figura 5. Modelo de ejecución en CUDA ________________________________________________________ - 7 -

iii
CAPÍTULO I: ASPECTOS GENERALES

1.1. Descripción del problema

El presente trabajo se basa en una solución al problema integrar la ecuación

que se nos fue dada, la integración de esta ecuación puede ser una tarea que
demande una cantidad de procesamiento y tiempo elevada si se desarrolla usando
un método convencional para su programación.

1.2. Objetivos

1.2.1 Objetivo general

Desarrollar un programa en C++ que permita la ejecución del algoritmo de

Integración de forma paralela utilizando la potencia de la GPU para proporcionar
un incremento considerable en el rendimiento del procesamiento.

1.2.2 Objetivos específicos

- Comprender y documentar la base teórica de la programación paralela

y su utilización en el algoritmo de Integración.
- Instalar las librerías necesarias en nuestro computador para el uso de
CUDA.
- Ejecutar el algoritmo de Integración en su versión paralela y mostrar la
comparación que tiene con un algoritmo secuencial.

1.3. Limitaciones

 Falta de acceso a computadoras que posean tarjetas Nvidia para el

aprovechamiento de sus GPU.

1.4. Justificación

El presente trabajo de investigación es importante porque permitirá la

implementación del algoritmo de Integración en una versión paralela, que además
de cumplir con el objetivo de optimizarlo nos ayuda a entender como los sistemas
informáticos están pasando de realizar un “procesamiento central” en la CPU a
realizar “coprocesamiento” repartido entre la CPU y la GPU. También sirve para
poder hacer un uso práctico de los conocimientos aprendidos en las clases
teóricas.

-1-
1.5. Metodología

El desarrollo de la presente investigación, no depende de un solo método, sino

de la aplicación de métodos cuantitativos y cualitativos en las diferentes fases por
las cuales debe seguir cualquier persona que desee implementar un programa de
manera paralela, y de la referencia de diferentes instituciones y autores en sus
diferentes fases.

-2-
CAPÍTULO II: MARCO TEÓRICO

2.1. Programación paralela

La programación paralela consiste en dividir un problema en sub-problemas,

con el fin de optimizar el tiempo que tarda el mismo problema en ser resuelto como
un todo. Para tal propósito fueron creadas las arquitecturas paralelas. Existen
varias formas de clasificar el procesamiento paralelo. Puede considerarse a partir
de la organización interna de los procesadores o desde el flujo de información a
través del sistema.

En el procesamiento en paralelo, se puede ejecutar múltiples hilos (threads),

en la actualidad del orden de entre 8 y 12. Sin embargo, lo que realmente están
haciendo, es fragmentar las aplicaciones secuenciales en pequeños fragmentos de
código y asignando su ejecución a los diferentes cores del procesador.

Por ejemplo, si en una aplicación que se ejecuta secuencialmente sobre un

procesador con múltiples cores, y el desarrollador decidió que algún fragmento se
distribuya entre diferentes cores, la aplicación se ejecutará por partes secuenciales
en cores diferentes. Hasta que alguna parte termine su trabajo, la siguiente no
iniciará. Esto significa que el paralelismo que consigue, en general, un procesador
multicore, representa un paralelismo que se ejecuta sobre múltiples aplicaciones
en paralelo, pero que normalmente, no ejecuta múltiples secciones de la aplicación
en paralelo.

Para conseguir mejorar este objetivo, las GPUs integran lógicas de control más
simples y que pretenden ejecutar el máximo de threads en paralelo. Integran
memorias cache de menor tamaño, compartidas por diferentes unidades de
proceso para evitar tener que acceder a la memoria principal, pero siguen
manteniendo una mayor superficie dedicada a las unidades de procesado. Así
mismo, integran buses de comunicación de mayor ancho de banda que las CPUs
(del orden de 10 veces más rápidos que las CPUs).

Figura 1.Programación en paralelo

-3-
 Cada vez más desarrolladores de software, tendrán que hacer frente a distintas
plataformas de computación paralela y tecnologías que suministren experiencias
nuevas y nutridas, dirigidas a crear una base moderna y refinada, destinada a los
usuarios.

2.2. Arquitecturas en paralelo

Michael J. Flynn propuso en 1966 una taxonomía (considerando sistemas con

uno o varios procesadores) que se basa en el flujo que siguen los datos dentro de
la máquina y de las instrucciones sobre esos datos. Tomando en cuenta que la
operación normal de una computadora es recuperar instrucciones de la memoria y
ejecutarlas en el procesador, se define como flujo de instrucciones a la secuencia
de instrucciones leída de la memoria y como flujo de datos a las operaciones
ejecutadas sobre los datos en el procesador.

El procesamiento paralelo puede ocurrir en el flujo de instrucciones, en el flujo

de datos o en ambos.

2.3. Arquitecturas GPU

La función principal de estas unidades de procesamiento es el manejo de

imagen-video permitiendo reducir carga al procesador y presentar un mejor
resultado en pantalla.

En la actualidad a las funciones de gráficos 3D se agrega el procesamiento de

propósito general que es posible gracias al paralelismo inherente a la arquitectura
usada para el manejo de gran cantidad de información de imágenes.

Figura 2. Abstracción Arquitectura GPU vs. Arquitectura CPU

Las GPUs se componen básicamente de varias y pequeñas unidades de

control y memorias cach; además una memoria DRAM para mover, manipular y
presentar en pantalla la información de video que para el caso de video juegos es
de 60 veces por segundo en cada escena 3D para obtener realismo. Las funciones
bases de este manejo de gráficas incluyen la descripción de la escena, iluminación,
reflejos, posición y orientación.

-4-
 Figura 3. Arquitectura general de una GPU

2.4. Arquitectura CUDA

CUDA es una tecnología desarrollada por la empresa NVIDIA. CUDA es una

arquitectura de cálculo paralelo que aprovecha la gran potencia de las GPUs
(unidad de procesamiento gráfico) para proporcionar un incremento extraordinario
del rendimiento del sistema.

Esto trata, ni más ni menos, en usar las tarjetas que siempre se han dedicado
al juego a otros campos, como son, el procesamiento de vídeo e imágenes, la
biología y la química computacional, la simulación de la dinámica de fluidos, la
reconstrucción de imágenes de TC, el análisis sísmico o el trazado de rayos, entre
otras.

Los distintos niveles hardware con los que trabaja CUDA son los que se ve en
la Figura 4, en ella, se ve como se interconecta el host y los distintos componentes
hardware de la gráfica, también se ven los diferentes bloques en los que divide los
streaming multiprocessor (SM), y como estos están formados por múltiples
procesadores que acceden a la misma memoria compartida.

-5-
 Figura 4. Arquitectura CUDA

2.5. Computación paralela usando CUDA

La característica principal de la programación en CUDA (10) es que permite

combinar la implementación de código serie en el host con la implementación de
código paralelo en el dispositivo, como ya se habló en el apartado ¿Qué es
CUDA? De esta manera se consigue entrelazar ejecuciones serie con
ejecuciones paralelas en los kernel. De forma visual se refleja en la Figura 5.

La ejecución del programa se lanza en el host (equipo nativo donde está

instalada la tarjeta gráfica), en él se copian o generan los datos con los que
trabajará en el device (el término device se refiere a la tarjeta gráfica), una vez
copiados se lanza el kernel que ejecuta los hilos de forma paralela, con los
resultados calculados se recuperan estos desde el device hacia el host y una vez
allí estos se devuelven o se analizan. La ejecución en la parte del dispositivo se
realiza por un conjunto finito de threads paralelos que actúan sobre una parte
diferente de los datos. De esta forma se define un kernel como un conjunto
determinado de muchos threads concurrentes, donde sólo un kernel es ejecutado
al mismo tiempo en el dispositivo, y muchos threads participan en la ejecución del
kernel.

-6-
 Figura 5. Modelo de ejecución en CUDA

En cada kernel cada thread tiene su propio identificador para poder realizar un
paralelismo transparente sobre los datos. Los threads se agrupan en bloques, de
esta forma se amplía el concepto kernel a un grid de bloques de threads, como se
ve en la Figura 18. Cada uno de esos bloques será ejecutado en un Streaming
Multiprocessor (SM) en forma independiente. Si hay suficientes SMs disponibles,
todos los bloques de un grid son ejecutados en paralelo.

-7-
CAPÍTULO III: DESARROLLO DEL PROYECTO

3.1. Análisis del programa paralelo para el algoritmo de integración.

Requerimientos

El programa para su correcto funcionamiento necesita lo siguiente:

 Tener instalado el compilador de C++.

 Contar con las librerías de MPICH2 en su versión más actual.
 Tener como entorno de ejecución el Sistema Operativo Pelican de
distribución Linux en todas las computadoras que conformarán el Cluster.
 Tener configurada una red local.

Funciones o Métodos

Procedimiento Paralelo

 Un proceso maestro -> distribuye las distintas tareas al resto de procesos.

 Varios procesos worker -> calcula un cierto número de filas de la matriz
resultante y reenvía el resultado parcial al proceso maestro.

Num_workers = num_procesos -1

-8-
 Fase de envío:

MPI_send

Fase de recepción:

MPI_recv

3.2. Construcción de un clúster en Pelican HPC.

- Arrancar Pelican HPC.

-9-
- Aceptar para cargar Pelican HPC.

- Accedemos con el usuario user y la contraseña modifica previamente.

- 10 -
 - Iniciamos la interfaz gráfica con el comando startx.

- Abrimos un terminal, digitamos pelican_setup, y continuamos.

- 11 -
- Ejecutamos el progama

- 12 -
3.3. Diseño.

En el diseño se describen los pasos que sigue el algoritmo de Integración en

su versión paralela para su correcta ejecución y obtención de resultados.

3.4. Pruebas.

En este apartado se muestran las pruebas del funcionamiento del programa.

AMBIENTE DE PRUEBAS

Para la realización de las pruebas se construyó una red con tres computadoras
de distintas características interconectadas entre sí por medio de una LAN Ethernet
sencilla como se muestra en la figura.

- 13 -
 Las características de las cuatro computadoras pueden observarse en la Tabla.

Característica PC 1 PC 2 PC 3 PC4

Memoria (GB) 8 GB 8 GB 8 GB 4 GB

Procesador Intel Intel Intel Intel

(Ghz) Core i7 Core i5 Core i5 Core i3

Tabla 1. Características más resaltantes de las computadoras utilizadas

durante las pruebas realizadas.

- 14 -
CONCLUSIONES

 Para el objetivo principal se concluye que el desarrollo del programa paralelo

para el algoritmo de integración se realizó de forma exitosa utilizando las
librerías de MPICH2, teniendo en cuenta que la parte de distribución de
procesamiento de dicho algoritmo es limitada.
 Para el cumplimiento del primer objetivo específico se recompiló información
para la comprensión de la programación paralela y su importancia en la
optimización de algoritmos, así mismo se hizo lo propio para el algoritmo de
Integración.
 Para el cumplimiento del segundo objetivo específico se creó una red local con
la utilización de un switch, se hizo la instalación del Sistema Operativo Pelican
en 4 computadoras para la construcción de un Cluste, todo ello de forma
exitosa.
 Para el cumplimiento del tercer objetivo específico se ejecutó el algoritmo de
Integración en el cluster construido distribuyendo el procesamiento de dicho
algoritmo de forma equitativa entre las computadoras que conformaron el
cluster, todo ello de forma exitosa y obteniendo resultados satisfactorios.

- 15 -
BIBLIOGRAFIA

Repositorio institucional. (2016). Obtenida de

http://riubu.ubu.es/bitstream/10259/3933/1/Programacion_en_CUDA.pdf

T. T. Zygiridis, “High-Order Error-Optimized FDTD Algorithm With GPU

Implementation,” IEEE Trans. Magn., vol. 49, no. 5, pp. 1809–1812, 2013

Cuesta Arvizu, H. (2016). Programando para el GPU con CUDA. Recuperado de

https://sg.com.mx/revista/programando-para-el-gpu-cuda

Manuel López Michelone (2013). Porque debería importarte la programación

paralela. Obtenido de https://www.nvidia.es/object/cuda-parallel-computing-
es.html

T. Cheng, “Accelerating universal Kriging interpolation algorithm using CUDA-

enabled GPU,” Comput. Geosci., vol. 54, pp. 178–183, 2013.

- 16 -