PDF de programación - Evaluación del rendimiento de Algoritmos Paralelos y/o Concurrentes

UNIVERSIDAD AMERICANA

Programación concurrente

Evaluación del
rendimiento de
Algoritmos Paralelos
y/o Concurrentes

Recopilación de teoría referente a la materia

Ing. Luis Müller
2011

Esta es una recopilación de la teoría referente a la asignatura Programación
Concurrente, a ser estudiada en clases con los alumnos, y que servirá como base
para su aplicación también en clases en ejercicios prácticos en el lenguaje de
programación Java.




Tabla de contenido
Definiciones ............................................................................................................................................. 4

Rendimiento ............................................................................................................................................ 4

Escalabilidad ............................................................................................................................................ 4

Granularidad ............................................................................................................................................ 4

Métricas de Rendimiento ......................................................................................................................... 5

Aceleración (Speedup) ............................................................................................................................. 5

1. Aceleración Relativa ..................................................................................................................... 5

2. Aceleración Real ........................................................................................................................... 5

La ley de Amdahl ..................................................................................................................................... 5

Ley de Gustafson-Barsis ........................................................................................................................... 6

Implementación de la ley de Gustafson ................................................................................................... 7

Eficiencia ................................................................................................................................................. 8

Escalabilidad ............................................................................................................................................ 8

Fuente de Overhead en los programas paralelos ...................................................................................... 8

Cómo medimos el tiempo de ejecución de un programa paralelo y/o concurrente? ............................. 9

Escalabilidad con Problemas de tamaño fijo ....................................................................................... 11

Escalabilidad con tamaño de problema escalable ............................................................................... 11

Superlinealidad .................................................................................................................................. 12



2

Evaluación del Rendimiento de Algoritmos Paralelos y/o Concurrentes



Para poder evaluar el desempeño de un sistema de computación y así poder compararlo

respecto a otro necesitamos definir y medir su rendimiento. Pero, ¿Qué queremos decir con

rendimiento?, ¿En base a qué parámetros podemos expresar o medir el rendimiento? ¿Cómo podemos

establecer un mecanismo que nos permita comparar dos sistemas de computación?

Para poder cuantificar el rendimiento, necesitamos determinar los factores que influyen en el

desempeño del equipo de cómputo y así definir una expresión que caracterice este rendimiento. Se

denomina medida al valor obtenido mediante un instrumento de medición confiable. Una medida

“proporciona una indicación cuantitativa de extensión, cantidad, dimensiones, capacidad y tamaño de

algunos atributos de un proceso o producto”

El desempeño de un computador puede tener diferentes medidas de elección para diferentes

usuarios. Para un usuario individual que está ejecutando un único programa, el computador con mayor

rendimiento es aquel que complete la ejecución de su programa en menor tiempo. Sin embargo, para el

administrador de un centro de cómputos, que tiene múltiples tareas que realizar a la vez, la de mayor

rendimiento es la que le realice más tareas en menor tiempo. Como elemento común, sin embargo, se

evidencia que la medida del rendimiento del computador es el tiempo. El computador que ejecute los

programas en menor tiempo es la que tiene mejor rendimiento.

Un algoritmo secuencial es evaluado por su tiempo de ejecución como función del tamaño del

problema. El comportamiento asintótico del tiempo de ejecución es idéntico en cualquier plataforma

secuencial. En cambio, el tiempo de ejecución de un programa paralelo y/o concurrente depende del

tamaño del problema, del número de procesadores y de ciertos parámetros de comunicación de la

plataforma. Es por ello que los algoritmos paralelos y/o concurrentes deben ser evaluados y analizados

teniendo en cuenta también la plataforma.

Además, en el mundo paralelo y/o concurrente, adicional al tiempo de ejecución como medida

de rendimiento también encontramos otras métricas como la aceleración (speedup), eficiencia

(efficiency) , etc.



3

Definiciones

Rendimiento

No es sencillo definir qué es rendimiento. Por ejemplo la tarea de los ingenieros de software es

diseñar e implementar programas que satisfagan los requerimientos del usuario relacionados con ser

correcto y su rendimiento. Si ejecutamos un programa en dos computadores distintos, ustedes dirían

que el computador más rápido es aquel que termina primero la ejecución del programa. Si tienen un

centro de computación que dispone de dos plataformas computacionales distintas que ejecutan trabajos

de muchos usuarios, dirían que el sistema más rápido es aquel que ejecuta y completa más trabajos por

día. Como usuario, a usted le interesa reducir el tiempo de respuesta y el tiempo de ejecución de su

programa. Por lo tanto su percepción de rendimiento puede cambiar dependiendo de la situación.

Vamos a usar el término de

Rendimiento

como una medida de que tan

“bien” un

sistema, o los componentes que lo constituyen, lleva a cabo las tareas asignadas.



Escalabilidad

Otro término importante es el de Escalabilidad. Este término se refiere al estudio del cambio en

las medidas de rendimiento de un sistema cuando una o varias características del sistema son variadas.

Una de las características que generalmente se cambia es el número de procesadores. Otra

característica relacionada con paralelismo que puede ser modificada es la granularidad del problema.



Granularidad



Granularidad consiste en la cantidad de cómputo con relación a la comunicación. En

Granularidad Fina o Fine-grained, las tareas individuales son relativamente pequeñas en término de

tiempo de ejecución. La comunicación entre los procesadores es frecuente.

En cambio en Granularidad gruesa o Coarse-grained, la comunicación entre los procesadores

es poco frecuente y se realiza después de largos periodos de ejecución.



4

Métricas de Rendimiento

Aceleración (Speedup)

La medición de rendimiento en ambientes paralelos y/o concurrentes es más complejo por

nuestro deseo de conocer cuánto más rápido ejecuta una aplicación en un computador paralelo. Es

decir, nos interesa conocer cuál es el beneficio obtenido cuando usamos paralelismo y cuál es la

aceleración que resulta por el uso de dicho paralelismo.

Existen diversas formas de expresar la aceleración que dependen de la forma en que se defina lo

que es el Tiempo de Ejecución Secuencial y Paralelo y/o concurrente.

1. Aceleración Relativa. El Tiempo de Ejecución Secuencial usado es el

tiempo total de ejecución del programa paralelo y/o concurrente cuando éste es ejecutado

sobre un único procesador del computador paralelo.

2. Aceleración Real. El Tiempo de Ejecución Secuencial usado es el tiempo

del mejor programa secuencial para resolver el problema.

Formalmente la aceleración es la relación entre el tiempo de ejecución sobre un procesador

secuencial y el tiempo de ejecución en múltiples procesadores.

La ley de Amdahl

Un aspecto importante a considerar es que todo programa paralelo y/o concurrente tiene una

parte secuencial que eventualmente limita la aceleración que se puede alcanzar en una plataforma

paralela. Por ejemplo, si el componente secuencial de un algoritmo es 1/s de su tiempo de ejecución,

entonces la aceleración máxima posible que puede alcanzar en el computador paralelo es s.

Según la ley de Amdahl, si un programa tiene un 5% de componente secuencial entonces la

aceleración máxima que se puede alcanzar es de 20.

La ley de Amdahl tiene varias implicaciones:

• Para una carga dada, la aceleración máxima tiene una cota superior de 1/s. Al aumentar s, la

aceleración decrecerá proporcionalmente.

• Para alcanzar buenas aceleraciones, es importante reducir s

5

En los primeros tiempos de la computación paralela, se creyó que el efecto capturado por la ley

de Amdahl limitaría la utilidad de la computación paralela a un grupo pequeño de aplicaciones. Sin

embargo, ciertas experiencias prácticas han demostrado que esta forma de ver los programas con una

parte estrictamente secuencial tiene poca relevancia en los problemas reales.