PDF de programación - Análisis de rendimiento de algoritmos paralelos

Análisis de rendimiento de algoritmos paralelos

Joaquín Andrés López Molina Daniel Mauricio Rodríguez Alpizar

[email protected] [email protected]

Estudiantes de Ingeniería en Computación

Tecnológico de Costa Rica, Sede San Carlos, Escuela de Computación



RESUMEN



El desarrollo de aplicaciones de software de
alta calidad, en una era de competitividad, es
cada día más importante. Uno de los
aspectos más relevantes a considerar son los
tiempos de respuesta, tomando esto en
cuenta, este artículo pretende mostrar
mediante ejemplos, el comportamiento que
presentan los algoritmos paralelos y la
eficiencia obtenida
implementar
algoritmos sobre sistemas multicore. Cabe
aclarar que el mismo no es una investigación
sobre paralelismo, por lo tanto no describe
conceptos relacionados con el tema, sino
más bien es un análisis de rendimiento para
destacar
tiempos de
ejecución respecto al enfoque secuencial,
mostrando al lector su indiscutible potencial.

la diferencia en

al



Palabras clave: algoritmos paralelos,
sistemas
programación
concurrente, paralelismo, programación
multinúcleo, enfoque paralelo.

multicore,

INTRODUCIÓN

con

las

Debido a
la gran demanda a nivel
computacional por la miniaturización de los
procesadores, mejorando la capacidad de
procesamiento, es que actualmente se
cuenta
de
multiprocesamiento, ejemplos de ellas son
los nuevos procesadores para computadoras
que compañías como Intel y AMD han
desarrollado [1][2],
los
teléfonos móviles cuentan con procesadores
multinúcleo, es por tal razón que resulta
sumamente importante obtener el mayor

inclusive hasta

tecnologías

la cual puede cambiar

provecho de las prestaciones brindadas por
la tecnología actual. Esto se puede lograr
la programación paralela o
utilizando
concurrente,
la
estructura de un problema, pero puede llegar
a marcar grandes diferencias a nivel
computacional en comparación con el
enfoque secuencial, por lo tanto el objetivo
principal de este escrito es demostrar las
diferencias en los tiempos de respuesta entre
ambas implementaciones. Así todas aquellas
personas que están familiarizadas con el
desarrollo del software, podrán notar las
eventuales mejoras en el rendimiento de la
aplicación, y de esta manera incentivar la
programación paralela, puesto que en la
actualidad, a pesar de contar con dichas
tecnologías, en el momento de programar se
sigue utilizando una
implementación
secuencial.

MATERIALES Y MÉTODOS

Para llevar a cabo este análisis, se trabajará
con dos diferentes algoritmos desarrollados
en C# , uno de ellos es un método de
encriptación de datos, básicamente este
método toma el valor numérico de la tabla
ASCII de cada carácter del texto y lo
combina con el valor proveniente de una
clave, obteniendo un nuevo valor numérico,
el cual sustituirá al original, transformando
el carácter inicial en otro completamente
diferente, los textos utilizados serán los
siguientes libros convertidos en archivos de
texto: El Origen de las especies de Charles
Darwin, este se considera de tamaño grande,
cuenta con 1.148.064 caracteres, Hidden

por mezcla.

sobre

ejecutados

ordenamiento

Treasures de Harry A. Lewis de tamaño
mediano con 674.033 caracteres y por último
se tiene el libro Metamorphosis de Franz
Kafka considerado de tamaño pequeño, este
posee 118.368 caracteres aproximadamente
[3]. El otro programa que se utilizará es uno
de los métodos de ordenamiento de arreglos
más utilizados, el MergeSort,
también
conocido
Ambos algoritmos están implementados de
forma concurrente y secuencial, los mismos
serán
diferentes
computadoras, la primera es una Toshiba
con un procesador Core i3 (2.40 GHz) con 4
núcleos y 4GB de memoria RAM, luego
sobre una computadora de escritorio con un
procesador Core i7 (3.40 GHz) con 8
núcleos y 8GB de RAM. Para comprender
mejor el comportamiento del enfoque
concurrente, se tomará como ejemplo el
algoritmo
su
implementación secuencial toma el texto
completo y lo analiza línea por línea, hasta
encriptarlo completamente, todo esto sobre
un solo núcleo del procesador, como se
muestra en la siguiente imagen.

encriptación,

de

Figura 1. Método de encriptación.

[ Enfoque concurrente ]



Por otro lado, el enfoque paralelo divide el
texto original, como se cuenta con una
computadora de 4 núcleos, el programa fue
diseñado tomando en cuenta este dato, por lo

tanto el texto fue dividido en 4 segmentos,
posteriormente para aprovechar
los 8
núcleos del procesador Core i7 se realizó una
modificación al código, dividiendo el texto
en 8 segmentos, de esta manera la aplicación
valorará el número de núcleos con que
cuenta el ordenador, permitiendo al usuario
ejecutar el programa tanto para 4 núcleos
como para 8. En
implementación
concurrente se ejecuta simultáneamente
cada segmento sobre cada núcleo del
procesador, como se puede apreciar en la
siguiente figura.

la

Figura 2. Método de encriptación.



[ Enfoque secuencial ]



la

de

ejecución

Esto se puede lograr utilizando algunas
instrucciones del lenguaje C#, tales como el
uso del Parallel.Invoke(), Parallel.For() y
Parallel.ForEach() [4][5], de igual manera
JAVA también cuenta con librerías que
permiten
tareas
concurrentemente, sin embargo son un poco
más difíciles de percibir. Por otra parte, el
método de ordenamiento con el MergeSort,
tiene una implementación similar [6][7],
normalmente el algoritmo de ordenamiento
divide el arreglo original en pequeños
arreglos, hasta el menor punto posible, luego
cuando todo está dividido, se empiezan a
ordenar los pequeños arreglos gradualmente,
hasta volver a conformar el arreglo, pero esta
vez ordenado, tal como se muestra en la

figura 3. Partiendo de este hecho, la solución
que se le dio a este algoritmo para poder
ejecutarlo sobre un sistema multicore, fue
dividir el arreglo principal en cuatro
arreglos,
el MergeSort
simultáneamente
listas,
posteriormente se unen los cuatro arreglos
una vez que estén ordenados, siendo esta la
etapa final del ordenamiento.

aplicándole

cuatro

a

las



Figura 3. Ordenamiento MergeSort.



Tomado de http://geeksquiz.com/merge-sort/

RESULTADOS

las grandes ventajas de

El paralelismo divide el problema en
subproblemas y los resuelve al mismo
tiempo,
esto puede marcar grandes
diferencias en los tiempos de respuesta, en
comparación con el método secuencial, en la
tabla 1 se muestra la duración que tomó la
ejecución del método de ordenamiento sobre
las dos computadoras, donde se pueden
apreciar
la
programación paralela, en el mejor de los
casos se logró obtener una reducción del
53% aproximadamente en la Core i3, por
otro lado con la Core i7, se obtuvo una
reducción de tiempo del 71%. En las figuras
4 y 5, mediante los gráficos, se puede
apreciar de forma más representativa como
varían los tiempos de respuesta del método
MergeSort
enfoque
utilizado. La tabla 2 al igual que la anterior,
posee
la
duración del método de encriptación, las
figura 6 y 7 corresponden a los gráficos que
muestran
la ejecución del método de
encriptación sobre ambas arquitecturas.

los datos correspondientes a

dependiendo

del

Arquitectura Tamaño del Array



Secuencial

Paralelo

Reducción

Core i 3

(4 Núcleos)

47,88%
52,99%
52,62%
63,16%
68,35%
71,53%
Tabla 1. Tiempos de ejecución del algoritmo de ordenamiento MergeSort (HH:MM:SS).

1.000.000 00:00:00.5180296 00:00:00.2700154
10.000.000 00:00:05.9023376 00:00:02.7751588
100.000.000 00:01:03.4186273 00:00:30.0527189
1.000.000 00:00:00.2964005 00:00:00.1092001
10.000.000 00:00:03.4008060 00:00:01.0764018
100.000.000 00:00:37.8612665 00:00:10.7796189

(8 Núcleos)

Core i 7

Arquitectura Tamaño del Texto

Core i 3

(4 Núcleos)

Core i 7

(8 Núcleos)

Texto Pequeño
Texto Mediano
Texto Grande
Texto Pequeño
Texto Mediano
Texto Grande

Secuencial

Paralelo

Reducción



00:00:07.6504376 00:00:01.0740617
00:04:18.1804534 00:00:43.1340757
00:13:27.5510183 00:02:48:5716417
00:00:04.4460078 00:00:01.0296018
00:02:23.8946528 00:00:14.3052251
00:07:40.6144092 00:00:44.9436789

86,02%
83,30%
79,20%
77,03%
90,07%
90,25%



Tabla 2. Tiempos de ejecución del algoritmo de encriptación de datos (HH:MM:SS).



Con la encriptación de datos se puede
observar resultados aún más sobresalientes,
pasar de 13 minutos aproximadamente, a
poco más de 2 minutos es un gran logro,
considerando los 13 minutos como el 100%
del tiempo de respuesta, vemos como la
implementación paralela, reduce el tiempo
de ejecución a un 20% aproximadamente,
ejecutando el mismo algoritmo sobre la Core
i7, los tiempos se reducen aún más, gracias
al poder de computo de este procesador, y a
la modificación del programa (dividir el
texto en 8 segmentos) para sacar el provecho
de los 8 núcleos, en el mejor de los casos
hubo una reducción del 90,25% con
respecto al enfoque secuencial.


Core i3 (4 núcleos)

Secuencial

Paralelo

s
o
d
n
u
g
e
S

70

60

50

40

30

20

10

0

1.000.000

10.000.000 100.000.000

Tamaño del arreglo



Computador Core i3

Figura 4. Comportamiento del MergeSort



Core i7 (8 núcleos)
Paralelo

Secuencial

40

s
o
d
n
u
g
e
S

35

30

25

20

15

10

5

0

1.000.000

10.0