La programación y computación en Paralelo - 4ta Parte

Siguiendo con la programación y computación en paralelo, tocaremos un poco el tema historico dando algunos concepto importantes.

Sea G un problema computacional arbitrario que debe ser resuelto por una computadora. Normalmente, el primer objetivo es diseñar un algoritmo para resolver el problema G. Es fácil darse cuenta que la clase de todos los algoritmos es infinita, sin emabrgo, podemos dividirla en dos subclases, la clase de todos los algoritmos secuenciales y la clase de todos los algoritmos paralelos.

Mientras que un algoritmo secuencial realiza una operación en cada paso, un algoritmo paralelo puede realizar múltiples operaciones en un solo paso, de está manera el objetivo es diseñar un algoritmo paralelo para G.

---

---

Sea P un algoritmo paralelo arbitrario. El paralelismo en P puede ser explotado por varios tipos de computadores paralelos. Por ejemplo, múltiples operaciones de P pueden ser ejecutadas simultáneamente por múltiples unidades de procesamiento de un computador paralelo C₁; o, tal vez, pueden ser ejecutadas por múltiples unidades funcionales canalizadas de un computador de un solo procesador C₂.

Después de todo, P siempre puede ser ejecutado secuencialmente en un computador de un solo procesador C₃, simplemente ejecutando las operaciones potencialmente paralelas de P una por una en sucesión.

Sea C(p) un computador paralelo del tipo C que contiene p unidades de procesamiento. Naturalmente, esperamos que el rendimiento de P en C(p) dependa tanto de C como de p. Por lo tanto, debemos distinguir claramente entre el paralelismo potencial de P, por un lado, y la capacidad real de C(p) para ejecutar, en paralelo, múltiples operaciones de P, por otro. Así, el rendimiento del algoritmo P en el computador paralelo C(p) depende de la capacidad de C(p) para explotar el paralelismo potencial de P.

Es por ello que debemos definir sin ambigüedad lo que realmente queremos decir con el término rendimiento de un algoritmo paralelo P. Intuitivamente, el rendimiento podría significar el tiempo requerido para ejecutar P en C(p); esto se llama el tiempo de ejecución paralelo de P en C(p), que denotaremos por T_par.

_{Imagen de Pixabay}

Alternativamente, podemos elegir el rendimiento para significar cuántas veces es la ejecución paralela de P en C(p) más rápida que la ejecución secuencial de P; esto se llama el speedup de P en C(p), y se define como:

Por lo tanto, la ejecución paralela de P en C(p) es S veces más rápida que la ejecución secuencial de P. Ahora si estamos interesados en qué parte del aumento de velocidad S se debe, en promedio, a cada una de las unidades de procesamiento. Dicho de otro modo, el término rendimiento podría entenderse como la contribución media de cada una de las p unidades de procesamiento de C(p) al aumento de velocidad; esto se denomina la eficiencia de P en C(p), y viene dada por la siguiente ecuación:




Dado que sabemos que



se deduce que el aumento de velocidad está acotado por encima de p y la eficiencia está acotada por encima de 1.

Esto significa que, para cualquier C y p, la ejecución paralela de P en C(p) puede ser como máximo p veces más rápida que la ejecución de P en un solo procesador. Y la eficiencia de la ejecución paralela de P en C(p) puede ser como máximo. (Esto es cuando cada unidad de procesamiento está continuamente ocupada en la ejecución de P, contribuyendo así 1/p-ésimo a su speedup).

---

---

A partir de las definiciones anteriores vemos que tanto el speedup como la eficiencia dependen de T_par, el tiempo de ejecución paralelo de P en C(p). Esto plantea nuevas interrogantes:

Estas son preguntas generales importantes sobre la computación paralela que deben responderse antes de embarcarse en un diseño y análisis práctico de algoritmos paralelos. La forma de responder a estas preguntas es modelar adecuadamente la computación paralela.

---

_{Imagen de Pixabay}

---

Si quedastes fascinado con este apasionante tema de la computación y programación en paralelo, no te pierdasd la próxima publicación sobre este tema, si deseas ampliar más te invito a leer las siguientes referencias:

• Atallah, M., Blanton, M. (eds.): Algorithms and Theory of Computation Handbook, Chapman and Hall, Boca Raton (2010).
• Chandra, R., Menon, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J.: Parallel Programming in OpenMP. Morgan Kaufmann, Burlington (2000).
• Foster, I.: Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Addison-Wesley Longman Publishing Co., Inc, Boston (1995).