Title: Procesamiento Secuencial y Concurrente.
Analizar la resolución secuencial y mono-procesador (UNA máquina) de la fabricación de un objeto compuesto por N partes o módulos. La solución secuencial nos fuerza a establecer un estricto orden temporal. Al disponer de sólo una máquina el ensamblado final del objeto sólo se podrá realizar luego de N pasos de procesamiento o fabricación.
Title: Procesamiento Secuencial y Concurrente.
Ahora supongamos que tenemos N máquinas, una por componente o módulo a fabricar para ensamblar el objeto. Si no hubiera dependencia de la materia prima, cada una de las N máquinas puede trabajar al mismo tiempo===>MENOR tiempo para completar el proceso===>Paralelismo del hardware. Dificultades: Distribución de la carga de trabajo, Necesidad de compartir recursos, Necesidad de esperarse en puntos clave, Necesidad de comunicarse, Dificultad con las fallas aisladas, Asignación de una de las N máquinas para efectuar el ensamblado final (Cual??). Un concepto importante que surge de este ejemplo es el de Speed-Up.
Title: Procesamiento Secuencial y Concurrente.
Hemos visto la solución secuencial directa y la solución paralela (multiplicando el hardware) en el problema de la fabricación de un objeto (sistema) de múltiples componentes (módulos). Ahora supongamos otro enfoque: una sóla máquina le dedica una parte del tiempo a cada componente del objeto final===> Concurrencia sin paralelismo de hardware===> Menor speed-up. Dificultades: Distribución de la carga de trabajo, Necesidad de compartir recursos, Necesidad de esperarse en puntos clave, Necesidad de comunicarse, Dificultad con las fallas de software aisladas, Necesidad de recuperar el “estado” de cada proceso al retomarlo. La concurrencia es un concepto de software no restringido a una arquitectura particular de hardware ni a un número determinado de procesadores.
Title: Programa Concurrente
Un programa concurrente especifica dos o más programas secuenciales que pueden ejecutarse concurrentemente en el tiempo como tareas o procesos. Un proceso o tarea es un elemento concurrente abstracto que puede ejecutarse simultáneamente con otros procesos o tareas, si el hardware lo permite. (recordar los TASKs de ADA). Un programa concurrente puede tener N procesos habilitados para ejecutarse concurrentemente y un sistema concurrente puede disponer de M procesadores cada uno de los cuales puede ejecutar uno o más procesos.
Title: Objetivos de los sistemas concurrentes
Ajustar el modelo de arquitectura de hardware y software al problema del mundo real a resolver. Incrementar la perfomance, mejorando los tiempos de respuesta de los sistemas de procesamiento de datos, a través de un enfoque diferente de la arquitectura física y lógica de las soluciones. Algunas ventajas que merecen comentarse son la velocidad de ejecución que se puede alcanzar, la mejor utilización de la CPU de cada procesador, y la explotación de la concurrencia inherente a la mayoría de los problemas reales.
Title: Areas de estudio en Programación Concurrente
ELECCION DE LA GRANULARIDAD : Significa optimizar (para una dada aplicación) la relación entre el número de procesadores y el tamaño de la memoria total. MANEJO DE LOS RECURSOS: Asignación de recursos compartidos, métodos de acceso a los recursos, bloqueo y liberación de recursos, seguridad y consistencia de los recursos. SINCRONIZACIÓN: Se debe asegurar el orden correcto (incluyendo el tiempo) de las acciones que los procesos ejecutan. Este orden es dinámico e interdependiente.El objetivo de la sincronización es restringir las “historias”o “threads” de un programa concurrente sólo a las permitidas.
Title: Sincronización en Programación Concurrente
Sincronización por exclusión mútua Significa asegurar que sólo un proceso tenga acceso a un recurso compartido en un instante de tiempo. Si el programa tiene “secciones críticas” que pueden compartir más de un proceso, la exclusión mútua evita que dos o más procesos puedan encontrarse en la misma sección crítica al mismo tiempo. Sincronización por condición: Debe permitir bloquear la ejecución de un proceso hasta que se cumpla una condición dada. Ejemplos de los dos mecanismos de sincronización en un problema de utilización de un área de memoria compartida (buffer limitado con productores y consumidores).
Title: Comunicación y Prioridad en Programación Concurrente
La comunicación entre procesos concurrentes indica el modo en que se organiza y trasmiten datos entre tareas concurrentes. Esta organización requiere especificar protocolos para controlar el progreso y corrección de la comunicación. Los protocolos deben contemplar la posibilidad de pérdida de información. Un proceso que tiene mayor prioridad puede causar la suspensión (pre-emption) de otro proceso concurrente. Análogamente puede tomar un recurso compartido, obligando a retirarse a otro proceso que lo tenga en un instante dado.
Title: Conceptos relacionados con la Programación Concurrente
Dos o más procesos pueden entrar en deadlock, si por un error en la programación concurrente ambos se quedan esperando que el otro libere un recurso compartido.La ausencia de deadlock es una propiedad necesaria en los procesos concurrentes. Una propiedad deseable en los sistemas concurrentes es el equilibrio en el acceso a los recursos compartidos por todos los procesos (fairness). Dos situaciones NO deseadas en los programas concurrentes son la inanición de un proceso (no logra acceder a los recursos compartidos) y el overloading de un proceso (la carga asignada excede su capacidad de procesamiento).
Title: Desventajas de la Programación Concurrente
En Programación Concurrente los procesos no son completamente independientes y comparten recursos. La necesidad de utilizar mecanismos de exclusión mútua y sincronización agrega complejidad a los programas ===> menor confiabilidad. Los procesos iniciados dentro de un programa concurrente pueden NO estar “vivos”. Esta pérdida de la propiedad de liveness puede indicar deadlocks o una mala distribución de recursos. La comunicación y sincronización produce un overhead de tiempo, inútil para el procesamiento ? Perder perfomance Hay un no determinismo implícito en el interleaving de los procesos concurrentes. Esto significa que dos ejecuciones del mismo programa no necesariamente son idénticas ===> dificultad para la interpretación y debug.
Title: Problemas asociados con la Programación Concurrente
La mayor complejidad en la especificación de los procesos concurrentes significa que los lenguajes de programación tienen requerimientos adicionales. ===> mayor complejidad en los compiladores y sistemas operativos asociados. Aumenta el tiempo de desarrollo y puesta a punto respecto de los programas secuenciales. También puede aumentar el costo de los errores ===> mayor costo de los ambientes y herramientas de Ingeniería de Software de sistemas concurrentes. Para obtener una real mejora de perfomance, se requiere adaptar el software concurrente al hardware paralelo. La paralelización de algoritmos secuenciales NO es un proceso directo, que resulte fácil de automatizar.
Title: Mecanismos de comunicación y sincronización entre procesos.
Memoria compartida: Los procesos intercambian mensajes sobre la memoria compartida o actúan coordinadamente sobre datos residentes en ella. Lógicamente los procesos no pueden operar simultáneamente sobre la memoria compartida, lo que obligará a BLOQUEAR y LIBERAR el acceso a la memoria. La solución más elemental será una variable de control tipo “semáforo” que habilite o no el acceso de un proceso a la memoria compartida. Pasaje de Mensajes: Es necesario establecer un “canal” (lógico o físico) para trasmitir información entre procesos. También el lenguaje debe proveer un protocolo adecuado. Para que la comunicación sea efectiva los procesos deben “saber” cuando tienen mensajes para leer y cuando deben trasmitir mensajes.
Title: Mecanismos de comunicación y sincronización entre procesos.
Independientemente del mecanismo de comunicación / sincronización entre los procesos, los lenguajes de programación concurrente deberán proveer primitivas adecuadas para la especificación e implementación de las mismas. De un lenguaje de programación concurrente se requiere: Indicar las tareas o procesos que pueden ejecutarse concurrentemente. Mecanismos de exclusión mútua. Mecanismos de comunicación entre los procesos.
Recordar el ejemplo de ADA.
Title: Resumen de conceptos
La Concurrencia es un concepto de software. La Programación Paralela se asocia con la ejecución concurrente en múltiples procesadores que pueden tener memoria compartida. La Programación Distribuída es un “caso” de concurrencia con múltiples procesadores y sin memoria compartida. En Programación Concurrente la organización de procesos y procesadores constituyen la arquitectura del sistema concurrente. Especificar la concurrencia es esencialmente especificar los procesos concurrentes, su comunicación y sincronización.
Title: Paradigmas de resolución de programas concurrentes
Si bien el número de aplicaciones es muy grande, en general los “patrones” de resolución concurrente son pocos: 1-Paralelismo iterativo, 2-paralelismo recursivo, 3-productores y consumidores, 4-clientes y servidores, 5-pares que interactúan. En el paralelismo iterativo un programa tiene un conjunto de procesos (posiblemente idénticos) cada uno de los cuáles tiene uno o más loops. Es decir cada proceso es un programa iterativo. La idea es que si estos procesos cooperan para resolver un único problema (ejemplo un sistema de ecuaciones) pueden trabajar independientemente y sincronizar por memoria compartida o envío de mensajes.
Title: Paralelismo iterativo: multiplicación de matrices.
La solución secuencial: double a[n,n], b[n,n], c[n,n]; for [i = 0 to n-1] { for [j = 0 to n-1] { # compute inner product of a[i,*] and b[*,j] c[i,j] = 0.0; for [k = 0 to n-1] c[i,j] = c[i,j] + a[i,k]*b[k,j]; } } El loop interno (índice k) calcula el producto interior de la fila i de la matriz a por la columna j de la matriz b y obtiene c[i,j]. Acciones paralelas posibles…
Title: Multiplicación de matrices. Paralelismo por filas o columnas.
co [i = 0 to n-1] { # Calcula las filas en paralelo for [j = 0 to n-1] { c[i,j] = 0.0; for [k = 0 to n-1] c[i,j] = c[i,j] + a[i,k]*b[k,j]; } } co [j = 0 to n-1] { # Calcula las columnas en paralelo for [i = 0 to n-1] { c[i,j] = 0.0; for [k = 0 to n-1] c[i,j] = c[i,j] + a[i,k]*b[k,j]; } }
Title: Multiplicación de matrices. Ahora con n2 procesos.
co [i = 0 to n-1, j = 0 to n-1] { # TODAS las filas y columnas c[i,j] = 0.0; for [k = 0 to n-1] c[i,j] = c[i,j] + a[i,k]*b[k,j]; }
co [i = 0 to n-1] { # FILAS en paralelo co [j = 0 to n-1] { # COLUMNAS en paralelo c[i,j] = 0.0; for [k = 0 to n-1] c[i,j] = c[i,j] + a[i,k]*b[k,j]; } }
Title: Multiplicación de matrices. P procesadores con N/P > 1.
Un procesador WORKER se encargará de un subconjunto de filas o columnas de la matriz resultado. El tamaño del “strip” óptimo es un problema muy interesante para balancear costo de procesamiento con costo de comunicaciones. process worker[w = 1 to P] { # strips en paralelo int first = (w-1) * n/P; # Primer fila del strip int last = first + n/P – 1; # Ultima fila del strip for [i = first to last] { for [j = 0 to n-1] { c[i,j] = 0.0; for [k = 0 to n-1] c[i,j] = c[i,j] + a[i,k]*b[k,j]; } } }
Title: Aspectos de la Programación Secuencial
Toda la Programación Secuencial se puede expresar con 3 clases de instrucciones básicas: ASIGNACIÓN, ALTERNATIVA (decisión) e ITERACION (repetición con condición).
? asignación simple: x = e, ? sentencia compuesta asignación: x = x + 1; y = y – 1; z= x+y; ? swap: v1 :=: v2 ? skip Termina inmediatamente y no tiene efecto sobre ninguna variable de programa.
| Página siguiente |