Paralelismo Y Distribucion

NETWORKING CENTER®

Paralelismo y Distribución Autor:

Miguel Angel Pérez (iceman)

Edición:

Octubre, 2001

Índice de Contenidos:

Introducción.

3

Concurrencia y Paralelismo.

4

Concurrencia y Distribución.

5

Mecanismos de Programación.

6

Mecanismos de Programación, II.

7

Ingeniería del Software. Grado de Acoplamiento.

8

Parallel Virtual Machine.

9

Parallel Virtual Machine.

10

Créditos.

11

Las opiniones vertidas en este artículo pertenecen únicamente a su autor, y no vinculan en modo alguno a Networking Center(R). Este texto está protegido por las leyes de la propiedad intelectual. Queda autorizada a todo individuo la reproducción para uso personal y sin objeto de lucro de este artículo, con la condición de que sea reproducido integralmente, incluida esta nota de copyright. Cualquier entidad o empresa que desee su reproducción deberá ponerse en contacto con el autor para solicitar su uso y llegar a un acuerdo mutuo sobre el mismo. Networking Center(R) posee la autorización de uso como grupo de Usuarios sin animo de lucro.

Paralelismo y Distribución Miguel Angel Pérez

Networking Center®, 2001

NETWORKING

CENTER®

Introducción Conforme avanzan las necesidades, y el desarrollo crece, la carga computacional se ve incrementada, hasta unos limites que hacen el plantearse la idea de trabajo en grupo. Existe una necesidad imperiosa de obtener un mejor rendimiento conforme nuestras necesidades y problemas aumentan, y nuestras situaciones se hacen cada vez mas complejas. Para ello, disponemos de una serie de métodos y medios que nos permiten escoger las vías requeridas con el fin de dar una mejor solución a nuestro problema. En este documento, trataremos de forma breve, los métodos de concurrencia, paralelismo y distribución de aplicaciones, basándonos en la teoría previamente expuesta de Procesamiento Paralelo. Se trataran diversos aspectos de la programación orientada a sistemas multiprocesador, multinodo y concurrentes. Por ello, recomiendo al lector se remita ante cualquier posible duda o laguna en este contenido que voy a exponer a los anteriores artículos y documentos publicados, donde sin duda, obtendrá la respuesta que busca. Así mismo, acato una cierta base en lo que a métodos de programación se refiere, dado que este tipo de temática va mas allá de una simple visión de programadores de aplicaciones. Durante el documento se podrán ir analizando diferentes sitios web según corresponda o se considere necesario, permitiendo así un mejor entendimiento y ampliación de conocimientos al lector. Sin mas preámbulos, comencemos :-)

Paralelismo y Distribución Miguel Angel Pérez

Networking Center®, 2001

NETWORKING

CENTER®

Concurrencia y Paralelismo Cuando nos referimos a un programa concurrente, sin duda hablamos de aquel que tiene mas de una línea lógica de ejecución; existe una segmentación del problema y se permite una ejecución de tareas simultáneamente, otorgando a varias secciones diferentes de programa la posibilidad actuar a la vez. El uso de una programación concurrente es de gran ayuda en lo que al programador de la aplicación se refiere. El usuario final también se vera beneficiado, sin bien obtendrá respuestas por parte del computador mas eficientes. Debemos tener en cuenta la diferencia existente entre paralelizar una aplicación, y que esta sea o no concurrente. Esto implica que un programa pueda correr simultáneamente en varios procesadores, mientras que en lo referente a concurrencia, solo se asegura la mejora otorgada por este mecanismo de programación. Los sistemas paralelos, tanto como los distribuidos, pueden ser concurrentes; un sistema concurrente no puede ser paralelo ni distribuido. Esta relación es de vital importancia a la hora de producir cambios en la estructura de un programa (paralelizarlo o distribuirlo). El hecho de ejecutar una serie de subtareas concurrentes de forma paralela nos otorgaría una mejora en lo que a rendimiento se refiere. Obtendríamos una mejor capacidad computacional. Debemos tener en cuenta que 20 procesadores del tipo A son mucho mas baratos que otro procesador con una capacidad computacional 20 veces superior a la de A. Utilizando este concepto, podríamos pensar en seccionar nuestra aplicación, y producir un equilibro de carga entre los procesadores, resultando así una mejora significativa en relación calidad-precio-capacidad, lo cual nos define el rendimiento frente al coste. Evidentemente un procesador 20A es mucho mas caro y potente que 20 procesadores A; seamos sensatos y pensemos que no llegaremos a igualar al 20A, pero si podremos incrementar escalarmente nuestro rendimiento. Como ejemplos de porque esto es así, tenemos la comunicación entre procesadores, de ámbito lento a muy lento y la comparición de áreas de memoria (cuando corresponda). Se recomienda en este punto al lector analice los diferentes tipos de arquitecturas multiprocesador en el documento de Arquitecturas Paralelas. Además, por lo general, el coste no podemos aumentarlo a gusto propio, por lo que sigue siendo un factor de estimable consideración. Aunque no obtengamos el rendimiento del 20A, como habíamos comentado, nuestro precio a la hora de aumentar procesadores es mucho menor. Este tipo de maquina llevan también incorporadas un numero de inconvenientes, no todo el monte es orégano, y por ello no son de un uso tan extendido como se desearía. Son sistemas excesivamente complejos de programar, así como de analizar, verificar y testar. Paralelismo y Distribución Miguel Angel Pérez

Networking Center®, 2001

NETWORKING

CENTER®

Paralelismo vs. Distribución Son sistemas excesivamente complejos de programar, así como de analizar, verificar y testar. Así pues, su coste solo se ve amortizado en aplicaciones que realmente requieran una gran carga computacional, como pueden ser grandes SGBDs, algoritmos de cálculos extremadamente potentes y pesados, el data minning, o en grandes operaciones de búsqueda. Actualmente tiene gran cabida en aspectos científico-tecnológicos de ámbito físico, químico y electrónico, así como de ingeniera y diseño. Como comentábamos previamente, la complicación de la programación de un sistema paralelo es una de las principales pegas ante el uso de este tipo de maquinas; pero quizás el peor de sus inconvenientes sea su coste. Una maquina paralela es excesivamente costosa. Podríamos entrar en comparaciones de maquinas paralelas frente a sistemas distribuidos, pero no es el caso, si bien se trato en su momento en los artículos de Arquitecturas Paralelas I y II. Un conjunto de maquinas de mínima - media capacidad computacional, en una arquitectura adecuada, siempre será mucho menos costosa que su casi equivalente sistema paralelo mas cercano. Eso sí, van a existir una serie de factores de vital importancia, que influirán:

?

La lentitud de la red local frente a un bus de procesador-memoria paralelo. Esto va a hacer necesaria la inclusión de mayor numero de procesadores de mínima potencia computacional equilibrar el rendimiento.

?

Necesitamos mecanismos portables de programacion para adaptar nuestro programa a las especificaciones de nuestro sistema distribuido. Estos son los sockets. A pesar de ser un planteamiento de coste mínimo, incrementa su complejidad a medida que aumentamos las especificaciones del sistema distribuido, ya que aumenta el trafico de comunicación entre maquinas.

?

La velocidad de transmisión siempre es menor que la del bus procmem, aun reduciendo al mínimo la velocidad del bus, o haciendo la red lo mas rápida posible.

?

Se requiere métodos para la abstracción de capas a la hora de realizar un diseño a trabes de socketing. Hay librerías que actualmente lo hacen, como puede ser la PVM.

Paralelismo y Distribución Miguel Angel Pérez

Networking Center®, 2001

NETWORKING

CENTER®

Mecanismos de Programación En la actualidad existen 4 métodos para la resolución de problemas de índole concurrente. El cuarto, que veremos en breve, lleva incorporado poco tiempo a este grupo. Analizaremos el caso y crearemos una taxonomía que comienza desde la base del problema. A.

Compilación Paralelizada.– El programador diseña su aplicación de forma secuencial, y a la hora de compilar, es el propio compilador quien tratara de explotar el paralelismo del programa. Esto tiene un efecto optimo a efectos del programador, pero no siempre la respuesta final es la esperada. Otro de los problemas es la escasa existencia de este tipo de compiladores, sola mente diseñados para lenguajes como Fortran o HPF. Además están diseñados para arquitectura paralelas excesivamente caras y de carácter bastante restringi do. Un ejemplo de este tipo de compiladores es Bert77, de dominio publico. http://http://www.plogic.com/bert.html

B.

Lenguajes Concurrentes.– Si la posibilidad de paralelizar el compilador, como hemos visto, nos resulta costosa, podemos tratar de paralelizar el lenguaje. Los mas comunes se basan en el estudio de traspaso de mensajes propuesto por Dijkstra. Ejemplos son el L2||O2 y Occam. http://archive.comlab.ox.ac.uk/occam.html http://dmoz.org/Computers/Programming/Languages/Occam/ Estos lenguajes son de especial carácter complejo y lioso, por lo cual no son de especial interés para los programadores. Además, su estructura gramatical es también diferente, lo cual dificulta mas su uso y comprensión.

C.

Biblioteca Concurrentes.– Dado que la idea del compilador queda desechada, y que la de paralelizar el lenguaje, tampoco es un camino de rosas, podemos echar mano a una biblioteca concurrente y hacer que el programador se ocupe de todo el desarrollo de la concurrencia a mano. Es aquí donde se mostrara de verdadera eficiencia del programador. Utilizara técnica de memoria compartida y paso de mensajes.

Paralelismo y Distribución Miguel Angel Pérez

Networking Center®, 2001

NETWORKING

CENTER®

Mecanismos de Programación D.

Sistemas Operativos adaptados a varios Procesadores.– Son sistemas operativos con la capacidad de ocultar el paralelismo a los procesos que corren bajo ellos. Compone una nueva capa de abstraccion en el diseño software. La idea es poder diseñar secuencialmente los programas, pero que estos puedan correr sin problema alguno bajo el sistema paralelo. Será el sistema operativo el encargado de asignar procesos a los procesadores de forma abstracta al progre mador y al proceso. Si analizamos este aspecto desde un punto de vista totalmente teórico, seria efi caz completamente. Pero desgraciadamente no es así. Normalmente no pode mos forzar el uso de uno u otro procesador para un proceso, si bien tampoco es muy acertado el mecanismo de equilibro de carga entre los procesadores. Como ya tratamos en la anterior charla de Arquitecturas Paralelas, un ejemplo de es te tipo es el soporte SMP de Linux para sistemas duales.

E.

Algoritmos Concurrentes y Computación Neuronal.– Las redes neuronales y los algoritmos genéticos nos ofertan un grado de concurrencia bastante elevado. Ademas de esto, nos proporcionan un bajo nivel de acoplamiento. De cualquier manera, son modelos que no están extendidos debido a su aun carácter teórico/experimental.

Paralelismo y Distribución Miguel Angel Pérez

Networking Center®, 2001

NETWORKING

CENTER®

Grados de Acoplamiento Cuando hablamos de grado de acoplamiento, nos referiremos íntegramente a aspectos de Ingeniería del Software. Grado de Acoplamiento es la medida mediante la cual vamos a calibrar la cantidad de información que se comparte entre procesos. Mientras mas grande es el acoplamiento, mas información hace falta gestionar para los procesos entre sí, dando lugar a un mayor trafico de información. La mayoría de algoritmos concurrentes, y sobre todo aquellos para aplicaciones matemáticas complejas, necesitan un alto grado de acoplamiento. Es importante indicar, que a mayor grado de acoplamiento, mejor rendimiento del sistema obtenemos. Los sistemas concurrentes de alto grado de acoplamiento nos indican altas tasas de rendimiento, mientas que los sistemas distribuidos, esta magnitud desciende de forma caótica. Toda esta valoración, sin tener en cuenta aspectos de la red local, donde el bloqueo debido a colisiones no permiten el correr programas con tiempos de ejecución esperados. Es aquí donde se plantea otro de nuestros dilemas de diseño: grado de acoplamiento frente a topología y arquitectura de nuestro sistema. Sabemos que el grado de acoplamiento es una solución cómoda pero hemos de tomar en consideración aspectos de la red local también. Cuando hablamos de computación paralela, disponemos del mismo esquema, solo variante los nodos de la red, de nodos a procesadores utilizando como medio un bus compartido. Los mecanismos como topologías de hipercubo en el diseño evitan bloqueos de red, pero escalan el coste del sistema. Es entonces concluyente decir que: 1.

Utilizaremos algorítmica con bajo carácter de acoplamiento en diseños de sistemas distribuidos, con el fin del mejor aprovechamiento de la red.

2.

Utilizaremos algoritmos con alto carácter de acoplamiento en diseños de sistemas paralelos, con el fin de aprovechar el rendimiento que en este ti po de maquinas nos ofrecen.

Se recomiendan las siguientes direcciones web: http://www.orcero.org/irbis/disertacion/node245.html http://www.inei.gob.pe/cpi/bancopub/libfree/lib612/CAP0641.HTM

Paralelismo y Distribución Miguel Angel Pérez

Networking Center®, 2001

NETWORKING

CENTER®

Parallel Virtual Machine PVM - Parallel Virtual Machine - es un conjunto de herramientas que juntas nos permiten resolver un gran tanto por ciento de los problemas que se nos planteaban en lo relativo a programacion paralela de aplicaciones. Reduce magníficamente los costes y permite rentabilizar aun mas el material del que disponemos, y obtener de el un gran rendimiento. PVM es una abstracción de un sistema que no existe, una maquina paralela virtual, que utilizara todos los recursos de todos los sistemas integrados en la red local, pero utilizando un modelo de diseño mas confortable y simplificado. PVM no es un sistema en sí, es un API que modela este tipo de maquina virtual permitiendo al programador diseñar programas para una maquina multiprocesador con carácter escalable, ocultando al mismo la arquitectura de la red y las características del material que la compone. El porqué utilizar un sistema paralelo PVM frente a utilizar un sistema de carácter supercomputador (Vedse Documentos de Arquitecturas Paralelas) se basa en los siguientes aspectos: A.

Generalidad: La posibilidad de aprovechar maquinas de anticuado valor computacional, como maquinas 486, Pentium, con mínimos recursos, nos permitirán el montaje de un supercomputador de carácter paralelo basado en cualquier sistema operativo UNIX, como puede ser Linux o FreeBSD.

B.

Tolerancia a Fallos: Basándonos en los esquemas de diseño de supercomputadores MIMD con memoria distribuida, diremos que la perdida de un nodo en nuestro sistema solo reducirá un pequeño tanto por cierto el rendimiento de la maquina. Es necesario recordar el tipo de escalabilidad de este tipo de sistemas (Véase Arquitecturas Paralelas).

C.

Diversidad: PVM nos da un carácter abstracto en lo que a diseño y topología de red se refiere. Además, nos abstrae conceptos y esquemas como el modelo de organización de los datos, los métodos de gestión y cantidad de memoria, tipo de procesadores en el nodo, etc. Esto nos permite utilizar sistemas sin una homogeneidad, de forma que el aprovechamiento de las diferentes maquinas que actuaran como nodo será plena. Esto no solo es aplicable a casos de hardware, si bien podemos variar las versiones de un sistema operativo o bien utilizar diferentes sistemas por no do.

Paralelismo y Distribución Miguel Angel Pérez

Networking Center®, 2001

NETWORKING

CENTER®

Parallel Virtual Machine D.

Costes: Un grupo de maquinas para conformar un entorno de supercompu tador, siempre será mas barato que un computador paralelo especifico. Existen partes de la red como topología de la red, ancho de banda en ella, etc. que nos podrán encarecer mas o menos el coste, pero aun así, seguirá siendo mas barato y económico. Respecto al tema de repuestos, siempre nos será mas económico reemplazar una o varias piezas de una PVM que llamar al servicio técnico de la empresa diseñadora del sistema paralelo.

PVM como maquina virtual tiene muchísimas ventajas, pero sigue abstrayendo un concepto mas, que es el grado de acoplamiento alto. Sin embargo, compensa la opción de utilizar PVM frente a otros métodos, sobre todo a efecto de los costes de nuestro sistema computador.

Paralelismo y Distribución Miguel Angel Pérez

Networking Center®, 2001

NETWORKING

CENTER®

Paralelismo: Créditos ?

Bibliografía: Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Randy Allen and Ken Kennedy ISBN 1-55860-286-0 Parallel Computing Works! Geoffrey C. Fox, Roy D. Williams, and Paul C. Messina ISBN 1-55860-253-4

?

Enlaces Web: Relativos a PVM: http://www.netlib.org/pvm3/book/pvm-book.html http://www.epm.ornl.gov/pvm/EuroPVM97/ http://students.cecs.csulb.edu/~beowulf/tutorial/ http://www.ece.orst.edu/~dortiz/pvm.html http://www.heliotopos.net/conf/pvm_mpi2001/speakers.htm Relativos a Ingeniería del Software. Grado de Acoplamiento. http://www.orcero.org/irbis/disertacion/node245.html http://www.inei.gob.pe/cpi/bancopub/libfree/lib612/CAP0641.HTM

Paralelismo y Distribución Miguel Angel Pérez

Networking Center®, 2001