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

in GEMS2 months ago


Portada.png
La imagen de fondo de la portada es una imagen de libre uso tomada de Pixabay y editada por @abdulmath con Inkscape


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.



waves.png



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 C1; o, tal vez, pueden ser ejecutadas por múltiples unidades funcionales canalizadas de un computador de un solo procesador C2.

Después de todo, P siempre puede ser ejecutado secuencialmente en un computador de un solo procesador C3, 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 Tpar.


cyber.png
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:


Eq01.png


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:

Eq02.png


Dado que sabemos que

Eq03.png

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).



music-5734445_1280.png



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


Preguntas.png


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.



waves.png
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).


HiveFirma.png
cervantes.png

Sort:  

Congratulations @abdulmath! You have completed the following achievement on the Hive blockchain and have been rewarded with new badge(s) :

You received more than 25000 upvotes.
Your next target is to reach 30000 upvotes.

You can view your badges on your board and compare yourself to others in the Ranking
If you no longer want to receive notifications, reply to this comment with the word STOP

Check out the last post from @hivebuzz:

Hive Power Up Day - March 1st 2021 - Hive Power Delegation