Programación concurrente

Advertisement
Documentos relacionados
Taxonomía de las arquitecturas

Con estas consideraciones, Flynn clasifica los sistemas en cuatro categorías:

Programación Concurrente y Paralela. Unidad 1 Introducción

Granularidad y latencia

Ejecución serial: las tareas/instrucciones de un programa son ejecutadas de manera secuencial, una a la vez.

MULTIPROCESADORES TIPOS DE PARALELISMO

Arquitectura de Computadoras. Clase 9 Procesamiento paralelo

Arquitectura de Computadoras para Ingeniería

Concurrencia. Concurrencia

PARADIGMA y LENGUAJES DE PROGRAMACIÓN

Clústeres y procesamiento en paralelo XE1GNZ J O R G E F BARBOSA J ACOBO F E B R E R O DE 20 17

Introducción a los Sistemas Multiprocesadores

TEMA 10 INTRODUCCIÓN A LOS SISTEMAS OPERATIVOS DISTRIBUIDOS. Introducción Hardware Software Aspectos de diseño

TEMA 9. SISTEMAS OPERATIVOS DISTRIBUIDOS

Diseño de Sistemas Distribuidos Máster en Ciencia y Tecnología Informática Curso Presentación e introducción

Modelos de computadores paralelos

Proceso. Threads, SMP, and Microkernels. Multithreading. Proceso

En este video vamos a examinar los distintos tipos de ordenadores que podemos encontrar hoy en día.

Sistemas Distribuidos. Prog. Distribuida bajo Internet

1. Introducción 2. S.O. de Red. NFS 3. S.O. Distribuidos 4. Características de Diseño. Tema5: Sistemas Operativos Distribuidos

Facultad de Ingeniería Industrial y de Sistemas v1.0 MA781U PROCESOS DISTRIBUIDOS

ARQUITECTURAS PARA PROCESAMIENTO PARALELO

Tema 1: PROCESADORES SEGMENTADOS

Intel lanza su procesador Caballero Medieval habilitado para Inteligencia Artificial

CDI Arquitecturas que soportan la concurrencia. granularidad

Sistemas Operativos Distribuidos. Sistemas Operativos Una visión aplicada

6. Enumere tres ventajas de los ULT frente a los KLT.

6.1 Base De Datos Centralizada

COMPUTACIÓN DE ALTA PERFORMANCE

COMPARACIÓN DE MODELOS DE SINCRONIZACIÓN EN PROGRAMACIÓN PARALELA SOBRE CLUSTER DE MULTICORES

Análisis automático de prestaciones de aplicaciones paralelas basadas en paso de mensajes

Instrumentación n / Ing. Quirino Jimenez D.

Sistemas Complejos en Máquinas Paralelas

Bases de Datos Paralelas. Carlos A. Olarte BDII

Trabajo de investigación Paralelismo en el procesador

Paralelismo en el procesador

DISEÑO E IMPLEMENTACIÓN DE APLICACIONES EMPRESARIALES CON MOVILIDAD.

Fecha de entrega: Miércoles 4 de Septiembre. Campus: Villahermosa. Carrera : Ingeniería en Sistemas Compuacionales. Nombre del maestro: Carlos Castro

Sistemas Distribuidos. Soporte de Sistemas Operativos

Procesamiento Paralelo

Lusitania. Pensando en Paralelo. César Gómez Martín

07 y 08 Sistemas distribuidos y paralelos y tarea 02

Ingeniería en Computación

Modelos de Programación Paralela Prof. Gilberto Díaz

En esta unidad vamos a hablar acerca de cómo los equipos utilizan las redes para trabajar juntos. Hay varios modelos ( que en algunos casos son

Introduccion a Sistemas Operativos. Ej: Linux

ARQUITECTURAS. Carlos Reveco D. IN73J Arquitectura, Diseño y Construcción de un Negocio con Apoyo TI.

Jorge De Nova Segundo

UNIDAD II Metodología de programación paralela. Lic. Jesús Germán Andrés PAUTSCH - FCEQyN - UNaM

Sistemas de Información

Conceptos generales de sistemas distribuidos

Guillermo Román Díez

Threads, SMP y Microkernels. Proceso

EVOLUCIÓN DE LOS PROCESADORES

Diseño arquitectónico 1ª edición (2002)

Evolución del software y su situación actual

Un importante problema para sistemas de la nueva generación

Clasificación de las Arquitecturas

Taller de Programación Paralela

Modelado de los computadores paralelos

PROGRAMA DE ESTUDIO Área de Formación : Fecha de elaboración: 28 de mayo de 2010 Fecha de última actualización:

Introducción a los sistemas operativos. Ing Esp Pedro Alberto Arias Quintero

Taller de Programación Paralela

Aplica para todas las sedes de la Universidad de Santander.

Tema 1: Introducción a los Sistemas Operativos

Programación Distribuida y Tiempo Real

ESCUELA DE INGENIERIA Informática Y Sistemas

Procesos y Threads Procesos y Threads. Rendimiento Rendimiento (paralelismo) (paralelismo) Productividad Productividad

Sistemas Operativos. Introducción. Tema 6

Unidad VII Optimización. M.C. Juan Carlos Olivares Rojas

de Gran Canaria Centro de Tecnología Médica Programación Concurrente

Diseño: Arquitectura de Software. IF 7100 Ingeniería del Software

Tipos de Diseño. Ing. Elizabeth Guerrero V.

Fecha de elaboración: Agosto de 2004 Fecha de última actualización: Julio de 2010

MULTIPROCESADORES (MIMD)

ARQUITECTURAS DE SOFTWARE

MINUTA: Taller en UAEMEX, Toluca. Construcción de Tecnología HPC

Universidad Autónoma de Baja California Facultad de Ciencias Administrativas Unidad Mexicali

Tema 04: Lenguajes de programación y el lenguaje C

Diseño de algoritmos paralelos

Arquitecturas de Altas Prestaciones y Supercomputación

TEMA 2: DEFINICIONES Y CONCEPTOS. Ing. Jonathan Quiroga Tinoco Conalep Tehuacán P.T.B. en SOMA

USO DE THREADS PARA LA EJECUCIÓN EN PARALELO SOBRE UNA MALLA COMPUTACIONAL

Procesamiento Paralelo

Introducción a los sistemas de Multiprocesamiento Prof. Gilberto Díaz

1. Almacenamiento redundante

Diseño de Sistemas Operativos. Capítulo 10 Introducción a los Sistemas Operativos Distribuidos

Sistemas Operativos Distribuidos

Las optimizaciones pueden realizarse de diferentes formas. Las optimizaciones se realizan en base al alcance ofrecido por el compilador.

Aplicaciones Web paraa Trabajo Colaborativo Diseño y prototipo de un software para la replicación de ficheros

Análisis de rendimiento de algoritmos paralelos

PATRONES DE DISEÑO FRAMEWORKS

UNIDAD I. Universidad del Zulia Costa Oriental del Lago. Conceptos Básicos

Especificación de requisitos de software

Nociones básicas de computación paralela

COMPONENTES DEL PC LEONARDO OLIVARES VILLA MATEO CARDONA ARENAS

1.4.1 Inicio de la computadora por primera vez Hay problemas Causas, síntomas y soluciones a posibles averías...

Concurrencia de Procesos

Características Ventajas Desventajas Tipo de Núcleo Shell Gui. Para algunas cosas se debe de saber usar UNIX, muchos juegos no corren en Linux.

Tipos Abstractos de Datos (TAD) Lección 1

Advertisement
Transcripción:

Programación concurrente Josep Jorba Esteve Remo Suppi Boldrito P07/M2106/02841

FUOC P07/M2106/02841 2 Programación concurrente

FUOC P07/M2106/02841 Programación concurrente Índice Introducción... 5 Objetivos... 7 1. Conceptos y definiciones... 9 1.1. Ámbitos de computación concurrente... 11 1.2. Cómputo científico... 12 1.3. Soporte de la programación concurrente a los sistemas distribuidos... 15 2. Clasificaciones arquitecturales... 17 2.1. Taxonomía de Flynn... 17 2.2. Por control y comunicación... 19 2.3. Clusters y grid... 21 3. Descomposición de problemas... 24 3.1. Una metodología básica... 24 3.2. Modelos de descomposición... 26 3.2.1. Memoria compartida... 26 3.2.2. Paralelismo de datos... 27 3.2.3. Paso de mensajes... 28 3.3. Estructuras de programación... 29 3.3.1. Master-worker... 30 3.3.2. SPMD... 30 3.3.3. Pipelining... 31 3.3.4. Divide and conquer... 31 3.3.5. Paralelismo especulativo... 31 4. Modelos de Interacción... 32 4.1. Cliente-servidor... 33 4.2. Servicios multiservidor y grupos... 39 4.3. Arquitecturas basadas en mensajes... 43 4.4. Servidores proxy... 45 4.5. Código móvil... 46 4.6. Procesamiento peer-to-peer... 48 4.7. Arquitecturas orientadas a servicios... 51 5. Paradigmas de programación... 54 5.1. Paso de mensajes... 55 5.1.1. Ejemplos de programación... 58 5.1.2. Message-oriented middleware (MOM)... 61 5.2. RPC... 62

FUOC P07/M2106/02841 Programación concurrente 5.2.1. Ejemplos de programación... 63 5.3. Memoria compartida. Modelos de hilos (threading).... 65 5.3.1. MultiThreading... 65 5.3.2. OpenMP... 69 5.4. Objetos distribuidos... 72 5.5. Modelos de componentes... 78 5.5.1. Java Beans... 79 5.6. Web Services... 82 5.6.1. Un ejemplo de programación con JAX-WS... 83 6. Casos de uso: paradigmas y complejidad... 89 6.1. Algoritmo Merge Bitonic... 91 6.2. Algoritmo de la burbuja... 92 6.3. Algoritmo Radix... 93 6.4. Conclusiones... 94 Glosario... 97 Bibliografía... 99

FUOC P07/M2106/02841 5 Programación concurrente Introducción Como consecuencia del rápido desarrollo de Internet, la programación distribuida está haciéndose rápidamente popular día a día. Internet provee de los primeros mecanismos básicos para una infraestructura global en las aplicaciones distribuidas, un espacio de nombres global (basado en las URL) y protocolos de comunicación globales (TCP/IP). La mayoría de las plataformas de sistemas distribuidos toman esta base para poder implementar diferentes modelos de aplicaciones y de sus usos. Por otro lado, cuando generalizamos hacia el concepto de concurrencia, como habilidad de ejecutar múltiples actividades en paralelo o simultáneas, introducimos diferentes tipos de programación, como la paralela, la distribuida y la de memoria compartida. El conjunto de las cuales (lo denominaremos programación concurrente) se aplica en mayor o menor medida a diferentes sistemas distribuidos según el ámbito de aplicación. En cuanto examinamos la programación concurrente, nos damos cuenta de su importancia actual, y de la prospección de futuro que tiene, ya sea desde el desarrollo de Internet y sus aplicaciones, o desde el nuevo hardware de las CPU (por ejemplo, en la forma de multicores), que nos introducirá la programación concurrente como un elemento básico para todo desarrollador de aplicaciones. Los ambientes donde se desarrolla la programación concurrente, ya sea hoy o en un futuro próximo, están incrementándose paulatinamente, desde las ya mencionadas CPU multicore, y las tarjetas gráficas con sus procesadores concurrentes (y en este sentido, el campo del software en la programación de videojuegos), a las redes inalámbricas, y/o redes de sensores trabajando cooperativamente, pasando a las aplicaciones a nivel Internet, con los sistemas de compartición de información basados en mecanismos peer-to-peer (P2P). También son aplicables a los diferentes ámbitos de aplicación, ya sean científicos (principalmente con computación en cluster, grid, o mediante hardware de máquinas paralelas o supercomputación) o en ambientes empresariales mediante diferentes arquitecturas por capas, y/o basadas en componentes o invocación remota de objetos, mediante las diferentes arquitecturas software empresariales. La evolución de los sistemas distribuidos en los diferentes modelos arquitecturales ha creado un gran conjunto de posibilidades para la programación concurrente, que ha hecho surgir un gran número de paradigmas de programación.

FUOC P07/M2106/02841 6 Programación concurrente Entendiendo estos paradigmas como clases de algoritmos que nos permiten solucionar diferentes problemas pero disponiendo de una misma estructura de control o concepción base. Cada uno de ellos está mejor o peor adaptado a los diferentes ambientes distribuidos y/o paralelos, o más o menos especializado en arquitecturas de sistema concretas. En este capítulo pretendemos observar los diferentes paradigmas, así como tener los conceptos teóricos y prácticos de los diferentes ambientes de programación para los sistemas concurrentes (distribuidos y/o paralelos), así como diferentes consideraciones de prestaciones a tener en cuenta en la implementación de las soluciones según los modelos arquitecturales, de interacción (comunicaciones), o de paradigmas de programación utilizados. Un objetivo en especial es examinar las diferentes técnicas utilizadas en los diferentes ambientes distribuidos, ya sean computaciones de tipo distribuida, paralela, o grid. Daremos detalles, pero no entraremos en el debate, que no dispone de amplio consenso en la comunidad científica, sobre las diferencias de cada tipo de computación, distribuida, paralela, grid, o de memoria compartida (shared memory). Ya que hoy en día cada vez se difuminan más las diferencias, y en muchos casos la construcción de un sistema distribuido (y/o paralelo) conlleva el uso de uno o más modelos de computación, llevándonos a modelos híbridos dependiendo del ámbito de la aplicación. En este sentido, consideramos la programación de tipo multithread, paralela y distribuida, como el ámbito de estudio del presente modulo, para proporcionar bases para el diseño e implementación de las aplicaciones dentro del ámbito de los sistemas distribuidos.

FUOC P07/M2106/02841 7 Programación concurrente Objetivos Los objetivos que tiene que conseguir el estudiante en este modulo didáctico son los siguientes: 1. Conocer los conceptos básicos de la programación concurrente, distribuida y paralela. 2. Conocer diferentes clasificaciones arquitecturales de los sistemas distribuidos. 3. Conocer los modelos de interacción en los sistemas distribuidos. 4. Conocer los diferentes paradigmas de programación utilizados en los sistemas distribuidos. 5. Conocer detalles de algunas de las técnicas de programación. 6. Conocer cómo adecuar cada paradigma de programación al uso o tipo de aplicación deseado. 7. Conocer cómo aplicar consideraciones de prestaciones para aumentar el rendimiento de los sistemas distribuidos.

FUOC P07/M2106/02841 9 Programación concurrente 1. Conceptos y definiciones La programación a la que estamos más acostumbrados, la secuencial, estuvo en sus inicios fuertemente influenciada por las arquitecturas de único procesador, en las cuales disponíamos como características base: de un único procesador (CPU), de los programas y los datos que están almacenados en memoria RAM, y de los procesadores, que se dedican básicamente a obtener un determinado flujo de instrucciones desde la RAM. Ejecutando una instrucción por unidad de tiempo En este sentido los programas secuenciales son totalmente ordenados, éstos nos indican en qué orden serán ejecutadas las instrucciones. Y una particularidad importante, los programas secuenciales son deterministas: mediante una misma secuencia de datos de entrada, se ejecutará la misma secuencia de instrucciones y se producirá el mismo resultado (salvo errores de ejecución causados por causas externas). Esta afirmación no es cierta para la programación concurrente. La programación concurrente nos permite desarrollar aplicaciones que pueden ejecutar múltiples actividades de forma paralela o simultánea. La programación concurrente es necesaria por varias razones: Ganancia de procesamiento, ya sea en hardware multiprocesador o bien en un conjunto dado de computadoras. Mediante la obtención de ganancias en recursos, en capacidad de cómputo, memoria, recursos de almacenamiento, etc. Incremento del throughput de las aplicaciones (solapamiento E/S con cómputo). Incrementar la respuesta de las aplicaciones hacia el usuario, poder atender estas peticiones frente al cómputo simultáneo. Permitiendo a los usuarios y computadores, mediante las capacidades extras, colaborar en la solución de un problema. Es una estructura más apropiada para programas que controlan múltiples actividades y gestionan múltiples eventos, con el objetivo de capturar la estructura lógica de un problema.

FUOC P07/M2106/02841 10 Programación concurrente Da un soporte específico a los sistemas distribuidos (como analizaremos más adelante). En particular como posibilidad de enlazar y hacer trabajar de forma conjunta a dispositivos físicamente independientes. Otro punto con cierta controversia, ya que no hay acuerdo específico, son las diferencias entre los términos de programación concurrente, distribuida, paralela, y multithread. Todos ellos son usados en mayor o menor medida en la construcción de sistemas distribuidos y/o paralelos. En este material usaremos la palabra programación concurrente como marco global a los diferentes tipos de programación distribuida, paralela y multithread, tendencia que viene siendo habitual en la literatura del campo distribuido. Aun así, hay una serie de diferencias que hay que puntualizar: Concurrencia frente a paralelismo: en paralelismo hay procesamiento de cómputo simultáneo físicamente, mientras en concurrencia el cómputo es simultáneo lógicamente, ya que el paralelismo implica la existencia de múltiples elementos de procesamiento (ya sean CPU, o computadores enteros) con funcionamiento independiente; mientras que la concurrencia no implica necesariamente que existan múltiples elementos de procesamiento, ya que puede ser simulada mediante las capacidades de multiprocesamiento del sistema operativo sobre la CPU. Un caso típico es la programación multithread, la existencia de múltiples hilos de ejecución en una misma aplicación compartiendo memoria, pudiendo ser esta ejecución paralela si se ejecuta en una máquina multiprocesador, o simplemente concurrente, lógicamente si se ejecuta en un solo procesador. Aun existiendo estas diferencias, en la práctica las mismas técnicas son aplicables a ambos tipos de sistemas. La palabra paralelismo suele asociarse con connotaciones de altas prestaciones en cómputo científico en una determinada plataforma hardware, habitualmente en supercomputadores, aunque cada vez se desplaza más a plataformas basadas en clusters locales (computadoras enlazadas por redes de propósito general, o bien redes de alta velocidad optimizadas para procesamiento paralelo). Típicamente, estas computadoras están físicamente en un mismo armario o sala de cómputo. La palabra distribuido se ha referido típicamente a aplicaciones, ejecutándose en múltiples computadoras (normalmente se implica además heterogeneidad de recursos), que no tenían por qué estar físicamente en un mismo espacio. Este término también relaja su significado debido a la extensión de los modelos paralelos, a ambientes como multicluster (múltiples clusters enlazados), o grid, que, aun siendo generalmente considerados como paralelos, se acercan más a los sistemas distribuidos. En general estos términos son ampliamente difundidos, y usados en diferentes comunidades con significados diferentes, aunque las distinciones tienden a

FUOC P07/M2106/02841 11 Programación concurrente desaparecer, en especial cuando se consideran cada vez sistemas más potentes de multiprocesamiento en sobremesa, y la fusión de sistemas paralelos y distribuidos aumenta con entornos como grid. Llegando en la mayoría de los casos actuales, en general, a sistemas híbridos donde se integran los tres tipos de programación (o de sistemas) para resolver un problema determinado. Podemos asimismo partir de una definición de sistema distribuido de computación como: Una colección de elementos de cómputo autónomos, ejecutándose en uno o más computadores, enlazados por una red de interconexión, y soportados por diferentes tipos de comunicaciones que permiten observar la colección como un sistema integrado. La mayoría de sistemas distribuidos operan sobre redes de computadoras, pero también puede construirse un sistema distribuido que tenga sus elementos funcionando en un computador simple de tipo multitarea. Como hemos mencionado, además de algunos esquemas clásicos de sistema distribuido basados únicamente en redes, también pueden incluirse a día de hoy los computadores paralelos, y especialmente los servidores en cluster. Además de otros ambientes como las redes wireless, y las redes de sensores. Por otro lado, como vimos previamente a este módulo, la computación grid abarca coordinación de recursos que no están sujetos a control centralizado mediante el uso de protocolos e interfaces abiertas, de propósito general, para proporcionar diferentes servicios. Uno de los parámetros más interesantes a la hora de enfocar la programación concurrente sobre un determinado sistema distribuido es conocer los diferentes estilos arquitectónicos en los que se basa, así como su modelo de interacción y organización interna de los componentes. Cuestiones que iremos desarrollando en las siguientes secciones del módulo. En esta primera sección del módulo, examinaremos las formas en que se presentan las plataformas de programación concurrente, así como casos específicos de uso de la programación concurrente en el ámbito científico. Finalmente, observaremos qué soporte nos ofrece para la construcción, y el tratamiento de las problemáticas de los sistemas distribuidos. 1.1. Ambientes de computación concurrente En la programación concurrente, los lenguajes suelen usar construcciones específicas para la concurrencia. Éstas pueden acarrear diferentes soportes a: multithread, soporte para computación distribuida, paso de mensajes, uso de recursos compartidos, etc.

FUOC P07/M2106/02841 12 Programación concurrente En el caso de la programación concurrente, son usadas diferentes aproximaciones para el desarrollo del entorno de programación: API de desarrollo: normalmente, como serie de librerías añadidas a un lenguaje específico (en principio sin soporte concurrente). Estas librerías dan el soporte necesario al lenguaje para la implementación de diferentes paradigmas de programación. En algunas ocasiones, las librerías pueden traer alguna serie de servicios adicionales o utilidades que permiten la gestión de los sistemas distribuidos y/o paralelos creados, o ciertas modificaciones en los compiladores para el soporte necesario (como TBB, OpenMP, HPF, UPC). También podrían citarse las librerías de sockets para comunicaciones básicas TCP/IP, o bien las API para diferentes lenguajes para el soporte del paradigma de servicios web. En algunos casos de última generación, las API han sido integradas en la especificación del lenguaje, casos como Java y C# tienen soporte multithread nativo, así como paso de mensajes, e invocación remota de objetos, entre otras. Bibliotecas añadidas a un lenguaje específico Un ejemplo típico son las librerías de threads como POSIX (pthreads), para el soporte añadido de tipo multithreading. O APIs de paso de mensajes como MPI o PVM. Middleware: es una capa software distribuida que se sitúa sobre el sistema operativo (de red) y antes de la capa de aplicación, abstrayendo la heterogeneidad del entorno. Normalmente, provee de un entorno distribuido integrado con el objetivo de simplificar la tarea de programación y gestión de las aplicaciones distribuidas, generalmente se proporcionan una serie de servicios de valor añadido, como servicios de nombres, transacciones, etc., como mecanismos para facilitar el desarrollo de aplicaciones distribuidas. El objetivo principal es la integración e interoperabilidad de las aplicaciones y los servicios ejecutándose en plataformas heterogéneas y/o dispositivos de comunicaciones. Como ejemplos basados en diferentes paradigmas, podemos citar casos como CORBA, DCOM y RMI, que ofrecen modelos de programación de alto nivel. O en otros casos como SOAP (en web services) puede considerarse otro middleware (basado en XML), que permite a las aplicaciones intercambiar datos estructurados y tipados en la web. Otros ejemplos de diversos modelos, podrían ser Jini, JavaSpaces, Enterprise JavaBeans (EJBs), y los MOM (message oriented middleware). Lenguajes específicos: en algunos casos, sobre todo en diferentes trabajos de investigación, se han desarrollado lenguajes de programación en los que la concurrencia juega un rol importante, o han sido pensados directamente para soportar tareas concurrentes. Ejemplos de lenguajes específicos Podemos citar algunos ejemplos más conocidos como: ADA, Eiffel, Erlang Limbo, Linda, Occam. 1.2. Cómputo científico La constante evolución del cómputo de altas prestaciones ha permitido que su uso se extienda a un amplio rango de campos de aplicación, tanto científicos

FUOC P07/M2106/02841 13 Programación concurrente como comerciales. El constante avance en el hardware disponible (unido a la reducción en su coste) y la mejora de los paradigmas de programación han permitido disponer de entornos muy flexibles para atacar algunos de los grandes problemas de cómputo antes inabordables. La computación paralela y/o distribuida de altas prestaciones comporta también unas implicaciones económicas y sociales importantes. Sus avances se reflejan a menudo en la competición industrial para producir mejores productos, y en algunos campos científicos como biología, química y medicina, por el bien social común en la mejor comprensión de mecanismos de enfermedades, drogas y medicamentos. También se ha iniciado el camino para grandes hitos futuros, como la exploración del conocimiento de los mecanismos del ADN humano, el análisis de la estructura de proteínas, y otros campos como la predicción de desastres naturales, terremotos, inundaciones, etc. La situación actual y las posibles mejoras en el cómputo de altas prestaciones nos abren una nueva serie de caminos para la ciencia, economía, ciencias sociales, etc. Al campo ya clásico, en esta aproximación, de la supercomputación, se le ha añadido (dentro del mundo científico) en las últimas décadas, la computación distribuida, que ha puesto a disposición de un gran número de instituciones académicas y comerciales las capacidades de cómputo de altas prestaciones. Y en particular, las soluciones de cómputo basadas en clusters de ordenadores personales o servidores optimizados, ampliamente disponibles por ser soluciones de bajo coste. En la mayoría de las ocasiones, estos avances de computación se han debido únicamente al avance en la tecnología del hardware, quedando relegado a un segundo término el software de sistemas, ya sea el propio sistema operativo o los paradigmas de programación usados. En la última década, la aparición de implementaciones de los paradigmas de paso de mensajes para la programación de altas prestaciones, como los entornos de PVM y MPI, ha permitido incorporar esta programación a toda la gama de entornos hardware disponibles, desde las soluciones basadas en supercomputación hasta las más modestas basadas en clusters de variado tamaño (en número y capacidad de las máquinas que forman sus nodos). También recientemente, la disposición de máquinas de sobremesa con multicore, ha traído al escenario los paradigmas de programación para memoria compartida, en especial los modelos de multithreading (multihilo), y diversas implementaciones como los threads POSIX, Intel TBB o variaciones de lenguajes específicos como OpenMP. Estas agrupaciones de paradigmas, tanto por paso de mensajes como de memoria compartida, han permitido atacar la resolución de diversos problemas que se implementan mejor en uno o en otro método, o con aproximaciones híbridas mediante clusters con nodos distribuidos, donde éstos son multiprocesador o multicore. Nota Figura 1. Un supercomputador basado en cluster con 10.240 procesadores PVM y MPI son ejemplos de API basados en paradigmas de pago de mensajes. Los thread POSIX, Intel TBB, y OpenMP son casos de paradigma de memoria compartida.

FUOC P07/M2106/02841 14 Programación concurrente Pero tanto en un caso como en otro, hay que tener en cuenta que, para obtener las capacidades de cómputo que esperamos de estos entornos, hay que asegurar que las aplicaciones han sido correctamente diseñadas y que sus prestaciones son satisfactorias. En el caso científico, esto implica, especialmente en el caso de altas prestaciones, que las tareas del desarrollador no acaban con aplicaciones libres de fallos funcionales, sino que es necesaria la realización de un análisis de prestaciones y la sintonización adecuada para alcanzar los índices esperados de rendimiento. Un ciclo de vida típico del desarrollo en este ámbito podría ser: Figura 2 Ya sea como evolución lógica o debido a la necesidad de abordar problemas con mayores requisitos de cómputo, en los últimos tiempos se ha complementado la evolución en el hardware, con el análisis de prestaciones de los entornos software para intentar extraer de ellos los máximos picos de cómputo, o los mejores rendimientos de la relación cómputo/prestaciones presentes en los paradigmas de paso de mensajes, o la mejor eficiencia de cores o procesadores en paradigmas de memoria compartida, o bien para aumentar la escalabilidad hardware/software de la solución empleada. Por desgracia, cumplir estos requisitos en las aplicaciones distribuidas/paralelas no es fácil. Las razones de estas limitaciones de las aplicaciones (y de sus desarrolladores) están en las complejas interacciones que las aplicaciones soportan con el sistema físico donde se ejecutan, el software de sistema (operativo y librerías), las interfaces de programación usadas (cada vez de más alto nivel) y los algoritmos implementados. Comprender todas estas interacciones y cómo mejorarlas es crucial para optimizar las prestaciones que podamos obtener de las aplicaciones, alcanzando

FUOC P07/M2106/02841 15 Programación concurrente una mejor utilización y productividad de los recursos hardware disponibles, para maximizar las prestaciones de los sistemas disponibles. 1.3. Soporte de la programación concurrente a los sistemas distribuidos En general, la programación concurrente es usada en la computación distribuida para dar solución a los diferentes problemas que aparecen en la concepción de sistemas distribuidos de cómputo: Heterogeneidad: el acceso a servicios, o la ejecución de aplicaciones, comporta un gran conjunto de heterogeneidad en computadores y redes. Aplicándose desde las propias redes al hardware del computador, a los sistemas operativos y a los lenguajes de programación que pueden encontrarse en el sistema final. Tolerancia a fallos: como habilidad de recuperar el sistema desde fallos de sus componentes sin perder la estabilidad del sistema. Alta disponibilidad: reducción al mínimo tiempo de parada de un sistema, cuando éste se está reconfigurando o ajustando, de manera que se minimice el tiempo que no está disponible de cara a sus clientes. Continua disponibilidad: capacidad de proporcionar servicio de forma ininterrumpida. Recuperabilidad: capacidad de recuperarse de los fallos reactivando los elementos del sistema, e incorporarlos de nuevo después de los fallos. Consistencia: habilidad para coordinar múltiples acciones en múltiples elementos, en presencia de concurrencia y fallos. En cierta forma, puede verse como comparación a un sistema no distribuido, y cómo conseguir comportarse como éste. Escalabilidad: habilidad para que el sistema se siga comportando correctamente a pesar de que diferentes aspectos del sistema crezcan en tamaño u otras características. Podemos observar la escalabilidad desde diferentes factores, aumento de capacidad de cómputo, de capacidad de red, de número de clientes del sistema, etc. Lo que nos obliga a tomar consideraciones de cómo afectarán al sistema estos cambios. Seguridad: capacidad de proteger los datos, servicios y recursos frente a ataques de usuarios malintencionados. Privacidad: protección de la identidad y localización de los usuarios del sistema, así como de los contenidos con datos sensibles de usos no autorizados.

FUOC P07/M2106/02841 16 Programación concurrente Prestaciones predecibles: garantizar que el sistema obtiene unas prestaciones acordes con las expectativas, como por ejemplo la ratio de datos producida o tratada, latencias controladas en caminos críticos, peticiones procesadas por unidad de tiempo, u otras. Actualidad de los datos: en especial en sistemas con restricciones temporales, asegurar que las acciones sean tomadas en los límites temporales pertinentes, y que sean realizadas con la sincronización temporal suficiente entre los elementos del sistema distribuido. Abertura (openness): es la característica que nos permite extender un sistema o reimplementarlo en diferentes formas. En el caso distribuido, podemos verlo como la facilidad con la que nuevos recursos pueden ser añadidos y puestos a disposición. En particular un sistema abierto se caracterizará por disponer de interfaces conocidas y publicadas, con mecanismos comunes conocidos de intercomunicación normalmente basados en estándares reconocidos. Estos sistemas abiertos pueden ser construidos desde hardware y software heterogéneo proveniente de diferentes fuentes. Pero debe cumplirse el seguimiento de las serie de estándares para que cada elemento pueda ser testado y verificado de forma que se compruebe su adecuación al sistema y correcto funcionamiento.

FUOC P07/M2106/02841 17 Programación concurrente 2. Clasificaciones arquitecturales Para la concepción de sistemas concurrentes y sus paradigmas de programación, hay que tener en cuenta que tanto en el caso distribuido, como en el paralelo los sistemas disponen de múltiples procesadores, que son capaces de trabajar conjuntamente en una o varias tareas para resolver un problema computacional. Existen muchas formas diferentes de construir y clasificar en diferentes taxonomías los sistemas distribuidos y paralelos. Presentaremos varias clasificaciones basadas en diferentes conceptos. 2.1. Taxonomía de Flynn Ésta es una clasificación de sistemas arquitecturales muy usada en paralelismo y en cómputo científico, que nos sirve para identificar tipos de aplicaciones y sistemas en función de los flujos de instrucciones (ya sean threads, procesos o tareas) y los recursos disponibles para ejecutarlos. Figura 3 Taxonomía de Flynn

FUOC P07/M2106/02841 18 Programación concurrente En función de los conjuntos de instrucciones y datos, y frente a la arquitectura secuencial que denominaríamos SISD (single instruction single data), podemos clasificar las diferentes arquitecturas paralelas (o distribuidas) en diferentes grupos: SIMD (single instruction multiple data), MISD (multiple instruction single data) y MIMD (multiple instruction multiple data), con algunas variaciones como la SPMD (single program multiple data). SIMD: un solo flujo de instrucciones es aplicado a múltiples conjuntos de datos de forma concurrente. En una arquitectura SIMD, unos procesos homogéneos (con el mismo código) sincrónicamente ejecutan la misma instrucción sobre sus datos, o bien la misma operación se aplica sobre unos vectores de tamaño fijo o variable. El modelo es válido para procesamientos matriciales y vectoriales, siendo las máquinas paralelas con procesadores vectoriales un ejemplo de esta categoría. MISD: el mismo conjunto de datos se trata de forma diferente por los procesadores. Son útiles en casos donde sobre el mismo conjunto de datos se deban realizar muchas operaciones diferentes. En la práctica no se han construido máquinas de este tipo por las dificultades en su concepción. MIMD: paralelismo funcional y/o de datos. No sólo distribuimos datos, sino también las tareas a realizar entre los diferentes procesadores/nodos. Varios flujos (posiblemente diferentes) de ejecución son aplicados a diferentes conjuntos de datos. Esta categoría no es muy concreta, ya que existe una gran variedad de arquitecturas posibles con estas características, incluyendo máquinas con varios procesadores vectoriales o sistemas de centenares de procesadores o bien con unos pocos. SPMD: en paralelismo de datos, utilizamos mismo código con distribución de datos. Hacemos varias instancias de las mismas tareas, cada uno ejecutando el código de forma independiente. SPMD puede verse como una extensión de SIMD o bien una restricción del MIMD. A veces suele tratarse más como un paradigma de programación, en el cual el mismo código es ejecutado por todos los procesadores (u nodos) del sistema, pero en la ejecución se pueden seguir diferentes caminos en los diferentes procesadores. Esta clasificación (taxonomía de Flynn) de modelos arquitecturales se suele ampliar para incluir diversas categorías de ordenadores que no se ajustan totalmente a cada uno de estos modelos. Una clasificación extendida de Flynn podría ser la siguiente: En esta clasificación (ver figura 4), se ha extendido la clásica para incluir desarrollos de máquinas con diseños arquitectónicos concretos (más relacionados con máquinas paralelas). En particular, comentar la inclusión de las computadoras vectoriales en la categoría SIMD. Estas máquinas incorporan una CPU clásica (bajo el modelo von Neumann), pero con vectores como tipo de datos

FUOC P07/M2106/02841 19 Programación concurrente primitivo. Tenemos instrucciones del repertorio que permiten operar sobre todas las componentes del vector. Estas máquinas con uno o más procesadores vectoriales (en algunos casos MIMD), son las que clásicamente se han conocido con la denominación de supercomputadores (en particular las computadoras vectoriales del fabricante Cray), aunque algunas de las características de procesamiento vectorial comienzan a estar disponibles en las recientes arquitecturas de procesadores de sobremesa (en especial para proceso multimedia). Figura 4 2.2. Por control y comunicación Otra extensión de las clasificaciones anteriores de los modelos arquitecturales es la basada en los mecanismos de control y la organización del espacio de direcciones en el caso de las arquitecturas MIMD, las de más amplia repercusión hoy en día (y que se ajusta bien a diferentes sistemas distribuidos): MIMD con memoria compartida (shared memory, MIMD), o también denominados multiprocesadores: En este modelo, los procesadores comparten el acceso a una memoria común. Existe un único espacio de direcciones de memoria para todo el sistema, accesible a todos los procesadores. Los procesadores se comunican a través de esta memoria compartida. Los desarrolladores no tienen que preocuparse de la posición actual de almacenamiento de los datos, y todos los procesadores tienen el mismo espacio de acceso a los mismos. En particular, cabe destacar la denominación comercial de sistemas SMP (symetric multiprocessing), refiriéndose a la combinación de MIMD y memoria (físicamente) compartida. Sus principales limitaciones son el número de procesadores dependiendo de la red de interconexión,

FUOC P07/M2106/02841 20 Programación concurrente siendo habitual sistemas entre 2-4 a 16 procesadores, incluidos en una misma máquina. Aunque también existe la opción, por parte de varios fabricantes, de unir algunos de estos sistemas (formando un sistema híbrido), en lo que se conoce como SPP (scalable parallel processing) o CLUMP (clusters of multiprocessors), para formar un sistema mayor. Como resumen, podemos decir que estas máquinas (SMP y SPP) ofrecen flexibilidad y fácil programación (por el esquema de memoria compartida), a costa de complejidad adicional en el hardware. Sistemas MIMD con memoria distribuida (distributed memory, MIMD), o también llamados multicomputadores: En este modelo, cada procesador ejecuta un conjunto separado de instrucciones sobre sus propios datos locales. La memoria no centralizada está distribuida entre los procesadores (o nodos) del sistema, cada uno con su propia memoria local, en la que poseen su propio programa y los datos asociados. El espacio de direcciones de memoria no está compartido entre los procesadores. Una red de interconexión conecta los procesadores (y sus memorias locales), mediante enlaces (links) de comunicación, usados para el intercambio de mensajes entre los procesadores. Los procesadores intercambian datos entre sus memorias cuando se pide el valor de variables remotas. También podemos observar unas subdivisiones de este modelo MIMD de memoria distribuida, Por un lado: a) Una extensión natural de este modelo sería el uso de una red de computadoras (evidentemente con una latencia más grande que la que presenta una red de interconexión dedicada en una máquina paralela). En este caso, cada nodo de la red es en sí mismo una computadora completa, pudiendo incluso operar de forma autónoma del resto de nodos. Dichos nodos pueden, además, estar distribuidos geográficamente en localizaciones distintas. A estos sistemas se les suele denominar clusters, y los analizaremos con más detalle posteriormente. b) Comercialmente, es habitual denominar a los sistemas MIMD con memoria físicamente distribuida y red de interconexión dedicada, especialmente diseñada, sistemas MPP (massive parallel processing). En éstos, el número de procesadores puede variar desde unos pocos a miles de ellos. Normalmente, los procesadores (de un sistema MPP) están organizados formando una cierta topología (tanto física como lógica, como: anillo, árbol, malla, hipercubo, etc.), disponiendo de un red de interconexión entre ellos de baja latencia y gran ancho de banda. En esta última clasificación, es necesario tener en cuenta la diferenciación de la organización de la memoria, entre la organización física y la lógica. Podemos, por ejemplo, disponer de una organización física de memoria distribuida, pero lógicamente compartida. En el caso de los multiprocesadores, podríamos realizar una subdivisión más entre sistemas fuertemente o débilmente acoplados.

FUOC P07/M2106/02841 21 Programación concurrente En un sistema fuertemente acoplado, el sistema ofrece un mismo tiempo de acceso a memoria para cada procesador. Este sistema puede ser implementado a través de un gran módulo único de memoria, o por un conjunto de módulos de memoria de forma que se pueda acceder a ellos en paralelo por los diferentes procesadores. El tiempo de acceso a memoria (a través de la red de interconexión común) se mantiene uniforme para todos los procesadores. Tenemos un acceso uniforme a memoria (UMA). En un sistema ligeramente acoplado, el sistema de memoria está repartido entre los procesadores, disponiendo cada uno de su memoria local. Cada procesador puede acceder a su memoria local y a la de los otros procesadores, pero el tiempo de acceso a las memorias no locales es superior a la de la local, y no necesariamente igual en todas. Tenemos un acceso no uniforme a la memoria (NUMA). Por último, analizamos en esta sección, como caso que merece especial atención, los clusters, que pueden verse como un tipo especial de sistema MIMD de memoria distribuida (DM-MIMD), los cuales tienen una amplia repercusión en el desarrollo de sistemas de alta disponibilidad y alta fiabilidad. 2.3. Clusters y grid Los clusters consisten en una colección de ordenadores (no necesariamente homogéneos) conectados por red ya sea Gigabit u Ethernets de menor velocidad, Fiber Channel, ATM, u otras tecnologías de red para trabajar concurrentemente en tareas del mismo programa. Un cluster está controlado por una entidad administrativa simple (normalmente centralizada), que tiene el control completo sobre cada sistema final. Como modelo de arquitectura, son sistemas MIMD de memoria distribuida, aunque la interconexión puede no ser dedicada, y utilizar mecanismos de interconexión simples de red local, o incluso a veces no dedicados exclusivamente al conjunto de máquinas. Básicamente, es un modelo DM-MIMD, pero las comunicaciones entre procesadores son, habitualmente, varias órdenes de magnitud más lentas, que las que se producirían en una máquina paralela. Figura 5 Ejemplo de configuración de un cluster

FUOC P07/M2106/02841 22 Programación concurrente Esta combinación (homogénea o heterogénea) de máquinas podemos utilizarla como computador paralelo/distribuido, gracias a la existencia de paquetes software que permiten ver el conjunto de nodos disponibles como una máquina paralela virtual, ofreciendo una opción práctica, económica y popular hoy en día para aproximarse al cómputo paralelo. Algunas de las ventajas que podemos encontrar en estos sistemas son las siguientes: Cada máquina del cluster es en sí misma un sistema completo, utilizable para un amplio rango de aplicaciones de usuario. Pero estas aplicaciones normalmente no consumen de forma constante un tiempo apreciable de CPU. Una posibilidad es usar las máquinas del cluster, aprovechando estos tiempos (o porcentajes de tiempo) muertos para utilizarlos en las aplicaciones paralelas, sin que esto perjudique a los usuarios convencionales de las máquinas. Esto también nos permite diferenciar entre los clusters dedicados (o no), dependiendo de la existencia de usuarios (y por tanto de sus aplicaciones) conjuntamente con la ejecución de aplicaciones paralelas. Asimismo, también podemos diferenciar entre dedicación del cluster a una sola o varias aplicaciones paralelas simultáneas en ejecución. El aumento significativo de la existencia de los sistemas en red con un amplio mercado y su comercialización ha hecho que el hardware para estos sistemas sea habitual y económico, de manera que podemos montar una máquina paralela virtual a bajo coste. A diferencia de las máquinas SMP y otros superordenadores, es más fácil conseguir buenas relaciones de coste y prestaciones. De hecho, buena parte de los sistemas actuales de altas prestaciones son sistemas en cluster, con redes de interconexión más o menos dedicadas. Los podríamos situar como una alternativa intermedia entre los sistemas comerciales basados en SMP y MPP. Sus prestaciones van mejorando en la medida en que se desarrolla software específico para aprovechar las características de los sistemas en cluster, al tiempo que se introducen mejoras en las tecnologías de red local y de medio alcance. La computación en cluster es bastante escalable (en hardware). Es fácil construir sistemas con centenares o miles de máquinas. Por el contrario, las SMP suelen estar limitadas en número de procesadores. De hecho, en los clusters, en la mayor parte de las ocasiones, la capacidad se ve limitada por las tecnologías de red, debiendo ser las redes de interconexión las que puedan soportar el número de máquinas que queramos conectar, ya sea utilizando tecnologías de red generales (Ethernet, fast o giga ethernet, ATM, etc.) o bien redes de altas prestaciones dedicadas (Myrinet, SCI, etc.). Además, los entornos software para cluster ofrecen una gran escalabilidad desde cómputo en pequeños clusters, como los sistemas de paso de mensajes, hasta sistemas de cómputo conectados a través de Internet, como con los sistemas grid.

FUOC P07/M2106/02841 23 Programación concurrente Aunque no es habitual disponer de hardware tolerante a fallos (como es el caso de SMP y supercomputadores), normalmente se incorporan mecanismos software/hardware que invalidan (y/o sustituyen por otro) el recurso que ha fallado. Pero también hay una serie de problemas relevantes a considerar: Con contadas excepciones, el hardware de red no está diseñado para el procesamiento paralelo. La latencia típica es muy alta, y el ancho de banda es relativamente bajo comparado con sistemas SMP o supercomputadores. El software suele diseñarse para máquinas personales. Tal es el caso del sistema operativo, y normalmente no ofrece posibilidades de control (y gestión) de clusters. En estos casos, es necesario incorporar una serie de capas de servicios middleware sobre el sistema operativo, para proporcionar sistemas en cluster que sean eficaces. En sistemas a mayor escala, es necesario incluir toda una serie de mecanismos de control y gestión adicionales, para el scheduling y monitorización de los sistemas, como es el caso en los sistemas grid. En general, esto supone una complejidad muy grande del software de sistema, que aumenta sensiblemente la complejidad total, y tiene una repercusión significativa sobre las prestaciones en estos sistemas.

FUOC P07/M2106/02841 24 Programación concurrente 3. Descomposición de problemas La descomposición de los problemas a resolver plantea diferentes retos a nivel distribuido y paralelo, las aplicaciones distribuidas y/o paralelas consisten en una o más tareas que pueden comunicarse y cooperar para resolver un problema. Por descomposición entendemos la división de las estructuras de datos en subestructuras que pueden distribuirse separadamente, o bien una técnica para dividir la computación en computaciones menores, que pueden ser ejecutadas separadamente. Las estrategias más comúnmente usadas incluyen: Descomposición funcional: se rompe el cómputo en diferentes subcálculos, que pueden: a) realizarse de forma independiente; b) en fases separadas (implementándose en pipeline); c) con un determinado patrón jerárquico o de dependencias de principio o final entre ellos. Descomposición geométrica: el cálculo se descompone en secciones que corresponden a divisiones físicas o lógicas del sistema que se está modelando. Para conseguir un buen balanceo, estas secciones deben ser distribuidas de acuerdo a alguna regla regular o repartidas aleatoriamente. Normalmente, es necesario tener en cuenta cierta ratio de cómputo-comunicación, para realizar un balanceo más o menos uniforme. Descomposición iterativa: romper un cómputo en el cual una o más operaciones son repetidamente aplicadas a uno o más datos, ejecutando estas operaciones de forma simultánea sobre los datos. En una forma determinística, los datos a procesar son fijos, y las mismas operaciones se aplican a cada uno. En la forma especulativa, diferentes operaciones son aplicadas simultáneamente a la misma entrada hasta que alguna se complete. En cuanto a la creación de las aplicaciones distribuidas o paralelas, basándose en las posibles descomposiciones, no hay una metodología claramente establecida ni fija, debido a la fuerte dependencia de las arquitecturas de las máquinas que se usen, y los paradigmas de programación usados en su implementación. 3.1. Una metodología básica Una metodología simple de creación de aplicaciones paralelas y/o distribuidas podría ser la que estructura el proceso de diseño en cuatro etapas diferentes:

FUOC P07/M2106/02841 25 Programación concurrente partición, comunicación, aglomeración y mapping (a veces a esta metodología se la denomina con el acrónimo PCAM). Las dos primeras etapas se enfocan en la concurrencia y la escalabilidad, y se pretende desarrollar algoritmos que primen estas características. En las dos últimas etapas, la atención se desplaza a la localidad y las prestaciones ofrecidas. Partición: el cómputo a realizar y los datos a operar son descompuestos en pequeñas tareas. El objetivo se centra en detectar oportunidades de ejecución concurrente. Para diseñar una partición, observamos los datos del problema, determinamos particiones de estos datos y, finalmente, se asocia el cómputo con los datos. A esta técnica se la denomina descomposición del dominio. Una aproximación alternativa consiste en la descomposición funcional, asignando diferentes cómputos o fases funcionales a las diferentes tareas. Las dos son técnicas complementarias que pueden ser aplicadas a diversos componentes o fases del problema, o bien aplicadas al mismo problema para obtener algoritmos distribuidos o paralelos alternativos. Comunicación: se determinan las comunicaciones necesarias (en forma de estructuras de datos necesarias, protocolos, y algoritmos), para coordinar la ejecución de las tareas. Aglomeración: las tareas y estructuras de comunicación de las dos primeras fases son analizadas respecto de las prestaciones deseadas y los costes de implementación. Si es necesario, las tareas son combinadas en tareas mayores, si con esto se consigue reducir los costes de comunicación y aumentar las prestaciones. Mapping: cada tarea es asignada a un procesador/nodo, de manera que se intentan satisfacer los objetivos de maximizar la utilización del procesador/nodo, y minimizar los costes de comunicación. El mapping puede especificarse de forma estática, o determinarlo en ejecución mediante métodos de balanceo de carga. El resultado de esta metodología, dependiendo de los paradigmas y las arquitecturas físicas, puede ser una aplicación distribuida y/o paralela, con un mapping estático entre tareas y procesadores/nodos a la hora de iniciar la aplicación, o bien una aplicación que crea tareas (y las destruye) de forma dinámica, mediante técnicas de balanceo de carga. Alternativamente, también podemos utilizar estrategias de tipo SPMD que crea exactamente una tarea por procesador/ nodo, asumiendo que la etapa de aglomeración ya combina las tareas de mapping. Una de las decisiones más significativas en las aplicaciones distribuidas o paralelas, como resultado de las tareas anteriores, es precisamente el paradigma de programación que usaremos. Con cada uno de los paradigmas de programación, nos estamos refiriendo a una clase de algoritmos que tienen la misma

FUOC P07/M2106/02841 26 Programación concurrente estructura de control, y que pueden ser implementados usando un modelo genérico de programación. Más adelante veremos diferentes paradigmas. 3.2. Modelos de descomposición En las próximas secciones introduciremos los modelos más relevantes usados de programación distribuida/paralela. Para los modelos de programación, remarcamos cómo solucionan la distribución de código y la interconexión entre las unidades de ejecución y las tareas. Cualquiera de estos modelos de programación puede ser usado para implementar los paradigmas de programación. Pero las prestaciones de cada combinación resultante (paradigma en un determinado modelo) dependerán del modelo de ejecución subyacente (la combinación de hardware, red de interconexión y software de sistema disponibles). 3.2.1. Memoria compartida En este modelo los programadores ven sus programas como una colección de procesos accediendo a variables locales y un conjunto de variables compartidas. Cada proceso accede a los datos compartidos mediante una lectura o escritura asíncrona. Por tanto, como más de un proceso puede realizar las operaciones de acceso a los mismos datos compartidos en el mismo tiempo, es necesario implementar mecanismos para resolver los problemas de exclusiones mutuas que se puedan plantear, mediante mecanismos de semáforos o bloqueos. En este modelo, el programador ve la aplicación como una colección de tareas que normalmente son asignadas a threads de ejecución en forma asíncrona. Los threads poseen acceso al espacio compartido de memoria, con los mecanismos de control citados anteriormente. En cuanto a los mecanismos de programación utilizados, pueden usarse las implementaciones de threads en diferentes operativos, y los segmentos de memoria compartida, así como paralelismo implícito en algunos casos. En este último, se desarrollan aplicaciones secuenciales, donde se insertan directivas que permiten al compilador realizar distribuciones o paralelizaciones de código en diversas secciones. OpenMP es una de las implementaciones más utilizadas para programar bajo este modelo en sistemas de tipo SMP (o SH-MIMD). OpenMP (open specifications for multi processing) define directivas y primitivas de librería para controlar la paralelización de bucles y otras secciones de un código en lenguajes como Fortran, C y C++. La ejecución se basa en la creación de thread principal, juntamente con la creación de threads esclavos cuando se entra en una sección paralela. Al liberar la sección, se reasume la ejecución secuencial. OpenMP, que normalmente se implementa a partir librerías de bajo nivel de threads.

FUOC P07/M2106/02841 27 Programación concurrente En OpenMP se usa un modelo de ejecución paralela denominado fork-join, básicamente el thread principal, que comienza como único proceso, realiza en un momento determinado una operación fork para crear una región paralela (directivas PARALLEL, END PARALLEL) de un conjunto de threads, que acaba mediante una sincronización por una operación join, reasumiéndose el thread principal de forma secuencial, hasta la siguiente región paralela. Todo el paralelismo de OpenMP se hace explícito mediante el uso de directivas de compilación que están integradas en el código fuente (Fortran, o C/C++). En caso de sistemas físicos paralelos de tipo híbrido, que soporten por ejemplo nodos SMP en cluster o de tipo SPP, suele combinarse la programación OpenMP con otros modelos como el de paso de mensajes. 3.2.2. Paralelismo de datos El paralelismo de datos es un paradigma en el cual operaciones semejantes (o iguales) son realizadas sobre varios elementos de datos simultáneamente, por medio de la ejecución simultánea en múltiples procesadores. Este modelo es aconsejable para las aplicaciones que realizan la misma operación sobre diferentes elementos de datos. La idea principal es explotar la concurrencia que deriva de que la aplicación realice las mismas operaciones sobre múltiples elementos de las estructuras de datos. Un programa paralelo de datos consiste en una lista de las mismas operaciones a realizar en una estructura de datos. Entonces, cada operación en cada elemento de datos puede realizarse como una tarea independiente. El paralelismo de datos es considerado como un paradigma de más alto nivel, en el cual, al programador no se le requiere que haga explícitas las estructuras de comunicación entre los elementos participantes. Éstas son normalmente derivadas por un compilador, que realiza la descomposición del dominio de datos a partir de indicaciones del programador sobre la partición de los datos. En este sentido, hemos de pensar que el programa posee una semántica de programa secuencial, y solamente debemos pensar en el entorno paralelo para la selección de la distribución de los datos teniendo en cuenta la ayuda del compilador y las posibles directivas que le podamos proporcionar para guiar el proceso. El modelo de diseño de aplicaciones paralelas PCAM (mencionado previamente) sigue siendo aplicable, aunque en los lenguajes de paralelismo de datos, se realiza la primera fase directamente por medio de construcciones implícitas y otras explícitas proporcionadas por el usuario, de cara a obtener una granularidad fina de computación. Un punto relevante en esta fase es identificar (mediante el compilador y la ayuda proporcionada por el usuario) particiones con

Sitemap