EAP: INGENIERÍA DE SISTEMAS E INFORMÁTICA ASIGNATURA: ARQUITECTURA DE COMPUTADORAS DOCENTE: CARLOS GUERRA CORDERO TEMA:
Views 73 Downloads 0 File size 2MB
EAP: INGENIERÍA DE SISTEMAS E INFORMÁTICA ASIGNATURA: ARQUITECTURA DE COMPUTADORAS DOCENTE: CARLOS GUERRA CORDERO
TEMA: PROGRAMACION PARALELA CICLO: VIII ESTUDIANTE: MONDOÑEDO TORRES Marlene Valerie PEREZ SOTO Juan VASQUEZ ALVAREZ Esteban VASQUEZ SILVA Jonnel DEDICATORIA
UNIVERSIDAD NACIONAL DEL SANTA
El presente trabajo va dedicado a las personas que nos acompañan día a día, a nuestras familias, a nuestros amigos, a las personas que con sus consejos, con su orientación y con su cariño nos motivan a ser mejores y no rendirnos ante las adversidades. Para aquellos quienes sus deseos de aprender son más grandes que las limitaciones que puedan tener, y son capaces de convertir los obstáculos en herramientas que los impulsen más lejos.
ATTE El Grupo
AGRADECIMIENTO INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
2
UNIVERSIDAD NACIONAL DEL SANTA
1. La finalización de este trabajo se debe gracias a la valiosa ayuda de algunas personas, para quienes va dirigido nuestro agradecimiento especial. 2. A nuestros padres, por brindarnos su orientación y su apoyo incondicional. 3. A nuestros docentes de la Universidad Nacional de Santa, quienes con sus conocimientos transmitidos posibilitaron la realización del presente trabajo. 4. En general a todas las personas que aportaron con ideas o con acciones, para el desarrollo de este informe.
PRESENTACIÓN INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
3
UNIVERSIDAD NACIONAL DEL SANTA
El presente trabajo fue realizado con la intención de dar a conocer a nuestros compañeros acerca del tema “Programación Paralela”, la cual posee una explicación detallada y resumida del tema. A través del contenido del presente informe esperamos poderles dar a conocer todos los conceptos básicos de este tema y que les sea de mucha utilidad en el futuro. Esperamos que gracias a este material el lector puede entender mejor acerca de la Programación Paralela, y pueda satisfacer su necesidad de conocimiento.
INDICE I.
INTRODUCCIÓN: INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
4
UNIVERSIDAD NACIONAL DEL SANTA
II.
PROGRAMACIÓN PARALELA: 1. MODOS DE PROGRAMACIÓN 1.1 HERRAMIENTAS PARA OBTENER PROGRAMAS PARALELOS 1.2 COMO OBTENER UN PROGRAMA PARALELO 2. ALTERNATIVAS DE PROGRAMACIÓN PARALELA 2.1 ANCHO DE BANDA: 2.2 PROBLEMAS TÍPICOS EN LA PROGRAMACIÓN PARALELA 2.3 VARIANTES DE LA PROGRAMACIÓN PARALELA 2.4 PARALELA.
ACTUALIDAD Y AVANCES EN LA PROGRAMACIÓN
3. ESTILOS DE PROGRAMACIÓN PARALELA 4. ESTRUCTURAS DE PROGRAMACIÓN PARALELA 5. PROCESO DE PARALELIZACION III.
LINKOGRAFÍA
INTRODUCCIÓN La PROGRAMACIÓN PARALELA consiste en usar múltiples recursos simultáneamente para resolver un problema dado:
Hace uso de un ordenador con varias CPUs
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
5
UNIVERSIDAD NACIONAL DEL SANTA
El programa es dividido en partes independientes Cada parte es dividida en un conjunto de instrucciones Las instrucciones son ejecutadas secuencialmente Las partes son resueltas simultáneamente
La programación paralela es la evolución natural de programación en serie.
Programación en serie:
Funcionan en un ordenador con una única CPU. Un problema es dividido en un conjunto de instrucciones. Las instrucciones son ejecutadas secuencialmente. Únicamente una instrucción es ejecutada cada vez.
Los PROGRAMAS PARALELOS implican crear un programa que utilice de forma coordinada más de un elemento de procesamiento a la vez (procesador, core, etc). Como sabemos, todos los programas realizan una cierta cantidad de “trabajo”, ya sea una secuencia de instrucciones u operaciones en uno o más conjuntos de datos. Un programa paralelo el capaz de repartir ese trabajo entre los varios elementos de procesamiento que se pretende utilizar, lo que se conoce como partición o descomposición. ¿Por qué hacer programas paralelos?
A mediados de
1990’s, los fabricantes de
supercomputadoras
determinaron que era más fácil y barato construir maquinas con muchos
procesadores en vez de construir procesadores más potentes. A mediados de 2000’s, los fabricantes de procesadores determinaron que es más eficiente usar procesadores con muchos cores en vez de construir procesadores más rápidos.
PROGRAMACIÓN PARALELA INTRODUCCIÓN: Si queremos entender el funcionamiento y/o construcción de un programa paralelo podemos partir de: INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
6
UNIVERSIDAD NACIONAL DEL SANTA
a. Un código Secuencial que resuelve el problema y sobre este código de alto nivel, buscar la paralelización.
Ejemplo: Si tenemos una aplicación escrita en C que requiere realizar el cálculo del número π para luego utilizarlo en otro bloque de código (método, función, procedimiento, etc). La versión paralela va a depender de la descripción del problema que se ha utilizado en la versión secuencial de partida. Ventajas de la conversión al paralelismo: Se conoce el tiempo de ejecución real de las diferentes funciones o tareas que consta la aplicación, lo que facilita la distribución equilibrada de la carga de trabajo entre procesadores. Permite encontrar las partes de la aplicación que requieren más esfuerzo de paralelización (Suponen más tiempo). b. Y por definición de la
aplicación: Es decir, volver atrás en la
elaboración del programa y buscar una descripción clara del problema y llevar su desarrollo hacia un camino que admita la paralelizacion, es decir, reelaborar el programa secuencial y construirlo (re build) como un programa con ejecución paralela. Para facilitar el trabajo, podemos apoyarnos en programas paralelos que aprovechen las características de la arquitectura y en bibliotecas de funciones paralelas.
PROGRAMACIÓN PARALELA Tradicionalmente, los programas se han escrito para el cómputo en serie. Para resolver un problema, se construye un algoritmo y se implementa como un flujo en serio de instrucciones. Estas instrucciones se ejecutan en una unidad central de procesamiento (CPU). Solo puede ejecutarse una
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
7
UNIVERSIDAD NACIONAL DEL SANTA
instrucción a la vez y un tiempo después de que la instrucción ha terminado, se ejecuta la siguiente. La computación en paralelo en cambio utiliza simultáneamente múltiples elementos de procesamiento para resolver un problema. Esto se logra mediante la división del problema en partes independientes de modo que cada elemento de procesamiento pueda ejecutar su parte del algoritmo de manera simultánea con los otros. Los elementos de procesamiento son diversos e incluyen recursos tales como: computadoras con multiples
procesadores,
computadoras procesadores
con multi-core,
o
varios ordenadores en red. La programación paralela, respecto a la programación secuencial, genera un conjunto de problemas nuevos al programador: división en unidades de computo independientes (Tareas), agrupación de tareas o carga de tareas (código, datos) y asignación a procesadores, así como sincronización y comunicación. Para el programador lo más sencillo es la utilización de compiladores que extraen paralelismo automáticamente, pero estos compiladores no generan código eficiente para cualquier programa. La
utilización de métodos que conducen de forma
sistemática a una
versión paralela para una aplicación para alcanzar una implementación más eficiente, legible y mantenible. A continuación vamos a abordar
estilos de programación que se usan
ampliamente en la computación paralela, como paso de mensajes, variables compartidas o paralelismo de datos. Se comprenden algunos tipos de paralelismo:
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
8
UNIVERSIDAD NACIONAL DEL SANTA
Paralelismo a nivel de instrucción Un programa de ordenador es, en esencia, una secuencia de instrucciones ejecutadas por un procesador. Estas instrucciones pueden reordenarse y combinarse en grupos que luego son ejecutadas en paralelo sin cambiar el resultado del programa. Esto se conoce como paralelismo a nivel de instrucción. Los avances en el paralelismo a nivel de instrucción dominaron la arquitectura de computadores desde mediados de 1980 hasta mediados de la década de 1990.
PARALELISMO DE DATOS El paralelismo de datos es el paralelismo inherente en programas con ciclos, que se centra en la distribución de los datos entre los diferentes nodos computacionales que deben tratarse en paralelo. «La paralelización de ciclos conduce a menudo a secuencias similares de operaciones —no necesariamente idénticas— o funciones que se realizan en los elementos de una gran estructura de datos». Muchas de las aplicaciones científicas y de ingeniería muestran paralelismo de datos. Una dependencia de terminación de ciclo es la dependencia de una iteración de un ciclo en la salida de una o más iteraciones anteriores. Las dependencias de terminación de ciclo evitan la paralelización de ciclos. Por ejemplo, considere el siguiente pseudocódigo que calcula los primeros números de Fibonacci:
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
9
UNIVERSIDAD NACIONAL DEL SANTA
1: 2: 3: 4: 5: 6: 7:
PREV1 := 0 PREV2 := 1 do: CUR := PREV1 + PREV2 PREV1 := PREV2 PREV2 := CUR while (CUR < 10)
Este bucle no se puede paralelizar porque CUR depende de sí mismo (PREV2) y de PREV1, que se calculan en cada iteración del bucle. Dado que cada iteración depende del resultado de la anterior, no se pueden realizar en paralelo. A medida que el tamaño de un problema se hace más grande, la paralelización de datos disponible generalmente también lo hace.
PARALELISMO DE TAREAS El paralelismo de tareas es la característica de un programa paralelo en la que «cálculos completamente diferentes se pueden realizar en cualquier conjunto igual o diferente de datos». Esto contrasta con el paralelismo de datos, donde se realiza el mismo cálculo en distintos o mismos grupos de datos. El paralelismo de tareas por lo general no escala con el tamaño de un problema.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
10
UNIVERSIDAD NACIONAL DEL SANTA
1. MODOS DE PROGRAMACIÓN: Se pueden distinguir dos modos de programación: A. Modo SPMD ( Single Program Multiple Data): Llamado también Paralelismo de Datos. Se escribe un solo programa y todos los procesadores ejecutaran el mismo programa. Multiples Datos significa que los datos se dividen en pedazos y se asignan a cada procesador. Los resultados obtenidos al final son aglomerados (juntados), a pesar de ejecutar todos el mismo programa (instrucción) los resultados serán distintos debido a los datos que usan al ejecutar dicho programa. Principales caracteristicas:
Todas las unidades ejecutan la misma instrucción. Cada unidad de procesamiento puedes operar con datos distintos. Todas las unidades operan simultáneamente. No debe existir dependencia entre los datos de los diferentes procesadores.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
11
UNIVERSIDAD NACIONAL DEL SANTA
B. Modo MPMD ( Multiple Programs Multiple Data) Los códigos que se ejecutan en paralelo se obtienen compilando programas independientes. En este caso la aplicación a ejecutar (o código secuencial inicial) se divide en unidades independientes. Cada unidad trabaja con un conjunto de datos y se asigna a un procesador distinto. Características del modelo MPMD: Cada unidad ejecuta una instrucción distinta. Cada unidad procesa un dato distinto. Todas las unidades operan simultáneamente. Es el modelo más popular en la actualidad.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
12
UNIVERSIDAD NACIONAL DEL SANTA
C. Modo Mestro-Esclavo En los programas paralelos se pueden utilizar combinaciones MPMD y SPMD. La programación
dueño – esclavo (master-slave), se
puede considerar una variante del modo MPMD). En este modo, hay un programa dueño que se encarga de distribuir trabajo (tareas) entre procesos esclavos
y recolectar los resultados que estos
generan combinándolos en un solo resultado. Si todos los esclavos tienen el mismo código, este dueño-esclavo seria una combinación de los modos MPMD y SPMD.
PROGRAMACION PARA COMPUTADORAS PARALELAS 1. Programación para memoria compartida En los sistemas multiprocesadores, cada procesador puede acceder a toda la memoria, es decir, hay un espacio de direccionamiento compartido.
Todos
los
procesadores
se
encuentran
igualmente
comunicados con la memoria principal y pueden acceder por medio de un dicto común. En esta configuración se debe asegurar que los INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
13
UNIVERSIDAD NACIONAL DEL SANTA
procesadores no accedan de manera simultanea a las regiones de memoria de tal manera que provoque un error. Por ejemplo, si dos o mas procesadores desean actualizar una variable compartida se deben establecer procedimientos que permitan acceder a los datos compartidos como exclusión mutua. Esto se logra mediante el uso de candados o semáforos.
2. Programación con paso de mensajes Si la memoria está distribuida entre los procesadores, es decir, cada procesador tiene acceso a su propia memoria, entonces la programación es más compleja que cuando los datos a usar por un procesador están en el espacio de direcciones de otro, será necesario solicitarla y transferirla a través de mensajes. De este modo es necesario impulsar la localidad de los datos para minimizar la comunicación entre procesadores y obtener un buen rendimiento.
1.1
HERRAMIENTAS DE PROGRAMACION PARALELA Las herramientas para obtener programas paralelos deben permitir la realización de las siguientes tareas: INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
14
UNIVERSIDAD NACIONAL DEL SANTA
Crear procesos finitos. Localizar paralelismo. Distribuir carga de trabajo entre procesos. Comunicación y sincronización entre procesos. Asignación de procesos a procesadores. Determinar la comunicación entre procesadores.
COMO OBTENER UN PROGRAMA PARALELO A. BIBLIOTECA DE FUNCIONES PARA
PROGRAMACIÓN
PARALELA Utilización de un lenguaje secuencial, y una biblioteca de funciones, la cual requiere mayor implicación del programador, con lo que se hace explicito el paralelismo.
Esta alternativa que
sitúa al
programador en el nivel de abstracción más bajo. El cuerpo de los procesos y hebras se escribe con lenguaje secuencial. Ventajas: Los programadores están familiarizados
con los lenguajes
secuenciales Las bibliotecas están disponibles para todos los sistemas paralelos Las bibliotecas están más cerca al hardware y dan al programador un control a más bajo nivel. Se pueden utilizar a la vez bibliotecas para programar con hebras y bibliotecas para programar con procesos. Ejemplos de bibliotecas son: Pthread, MPI, PVM y OpenMP.
B. PARALELIZACION AUTOMATICA La paralelización automática de un programa secuencial por un compilador es el santo grial de la computación paralela. A pesar de décadas de trabajo por parte de los investigadores, la paralelización automática ha tenido un éxito limitado. Los principales lenguajes de programación en paralelo permanecen explícitamente paralelos o en el mejor de los casos parcialmente implícitos, en los que un programador le da al INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
15
UNIVERSIDAD NACIONAL DEL SANTA
compilador directivas de paralelización. Existen pocos lenguajes de programación paralelos totalmente implícitos.
C. COMPILADORES PARALELOS
Los compiladores paralelos buscan automáticamente el paralelismo implícito en un programa secuencial y lo hacen explicito, evitando la intervención del programador. Para ello, realizan análisis de dependencias entre bloques de código: entre iteraciones de un ciclo o entre funciones. Ejemplo: Supongamos dos bloques de código a analizar: B1 y B2, de forma que B1 se encuentre antes de B2 en el flujo secuencial del programa. Las dependencias que detecta el análisis el análisis entre estos dos bloques son: Dependencia RAW (Read After Write): ocurre si el bloque B1 produce un dato que consume B2. Dependencia WAW (Write After Write): ocurre si B1 escribe
en
una posición de memoria en la que también escribe B2. Dependencia WAR (Write After Read): ocurre si B1 lee una posición de memoria que modifica B2.
Los compiladores paralelos están limitados a aplicaciones que exhiben un paralelismo regular, como los cálculos a nivel de bucle.
2. ALTERNATIVAS
DE
PROGRAMACIÓN
PARALELA Nosotros sabemos que los procesadores actuales son paralelos son paralelos y es muy habitual tener en los procesadores normales tener 4 núcleos, 6 núcleos ya se están anunciando los procesadores que tendrán 12 núcleos. INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
16
UNIVERSIDAD NACIONAL DEL SANTA
Además de esto, podemos decir que durante los últimos 10 años, las tendencias en computación apuntan a la presencia continua de la computación paralela, dado que las redes de interconexión continúan avanzando significativamente en términos de velocidad de comunicación y ancho de banda.
2.1. ANCHO DE BANDA: A. Programación OpenMP: OpenMP
es una API (Application
Program Interface) que posibilita la programación paralela en entornos multiprocesador con memoria compartida, como es el caso de la mayoría de los procesadores actualmente en el mercado. Utilizando modificaciones en los compiladores, esta tecnología permite el desarrollo incremental de aplicaciones paralelas a partir de código fuente serie. Esta norma está definida por un consorcio que reúne importantes fabricantes de hardware y software. B. Programación
MPI:
MPI:
(acrónimo
de
Message
Passing
Interface) es una propuesta de estándar para un interface de paso de mensajes para entornos paralelos, especialmente aquellos con memoria distribuida. En este modelo, una ejecución consta de uno o más procesos que se comunican llamando a rutinas de una biblioteca para recibir y enviar mensajes entre procesos. La metodología consistirá en presentar una introducción con los conceptos teóricos de la programación en MPI, seguida por una descripción de cómo preparar un entorno computacional para el desarrollo de aplicaciones. C. Programación Híbrida: Las aplicaciones en clusters se pueden programar para utilizar paso de mensajes entre todos los procesadores. Pero es posible obtener mejores prestaciones si se utiliza un modelo híbrido de comunicación con compartición de INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
17
UNIVERSIDAD NACIONAL DEL SANTA
información por memoria compartida y con memoria distribuida, a través de la fusión de MPI con OpenMP. El objetivo de este módulo será la presentación de ejemplos de programación MPI+OpenMP en sistemas híbridos.
2.2. PROBLEMAS
TÍPICOS
EN
LA
PROGRAMACIÓN
PARALELA Los problemas típicos que se abordan con la programación paralela son: problemas de alto coste, o problemas de no tan alto coste pero de gran dimensión, o problemas de tiempo real, en los que se necesita la respuesta en un tiempo máximo. La computación paralela se ha convertido en el paradigma dominante en la arquitectura de computadores, procesadores
principalmente multinúcleo.
Sin
en
los
embargo,
recientemente, el consumo de energía de los ordenadores paralelos se ha convertido en una preocupación.
A. PROCESADOR MULTINUCLEO: Aunque los procesadores son cada vez más rápidos, existen numerosas aplicaciones para las que la velocidad de cálculo de un único procesador resulta insuficiente. La alternativa adecuada para esas aplicaciones es el uso de paralelismo. INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
18
UNIVERSIDAD NACIONAL DEL SANTA
Paralelismo en los sistemas de Computadores Actuales Una vez que hemos visto la importancia que tiene el paralelismo para aumentar las prestaciones de los sistemas computacionales, nos planteamos los tipos de sistemas paralelos que tenemos en la actualidad a nuestro alcance. Algunos de ellos son:
Podemos disponer de varios procesadores en un chip. Esta posibilidad se ha universalizado recientemente, al haber sustituido en la práctica los sistemas multinúcleo a los monoprocesadores como sistema universal de cómputo, ya que en la actualidad los procesadores duales se comercializan como procesador básico, y es posible adquirir sin mucho coste también tetraprocesadores. Todas las marcas (Intel, SUN, AMD, CELL...) disponen de bi
y
tetraprocesadores (o sistemas con más núcleos), y en el futuro la tendencia es que el número de núcleos vaya subiendo. Estos sistemas son de memoria compartida, y se programan utilizando threads, normalmente con OpenMP. El estilo de programación se prevé que siga siendo de este tipo, quizás con herramientas específicas de desarrollo.
En las redes de ámbito local (Local Area Networks, LAN) se conectan varios procesadores por medio de una red de conexión de alta
velocidad,
formándose
un
cluster,
que
se
utiliza
con
programación por paso de mensajes, pero puede llegar a poderse utilizar OpenMP si se desarrollan versiones eficientes que distribuyan automáticamente
los
datos
en
la
memoria
y
generen
las
comunicaciones necesarias para acceder a los datos. En muchos casos los procesadores básicos son procesadores multinúcleo, que se pueden programar con el paradigma de memoria compartida, y se obtiene así un sistema híbrido en el que se combina la memoria compartida y el paso de mensajes.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
19
UNIVERSIDAD NACIONAL DEL SANTA
Se
habla
de
supercomputación para referirse a la resolución en los sistemas computacionales
más
potentes
(supercomputadores)
de
los
problemas que demandan de más computación (meteorología, estudio del genoma, simulación de moléculas...) Tradicionalmente estas computaciones se han venido haciendo en grandes centros de supercomputación, pero cada vez más se está trasladando la resolución de este tipo de problemas a sistemas distribuidos, por lo que se puede considerar la red como el mayor supercomputador actual.
La Computación Distribuida y el Grid Computing es computación con procesadores geográficamente distribuidos. Estos procesadores constituyen una red, pero para su utilización se requiere de unas herramientas más sofisticadas que en el caso de redes locales.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
20
UNIVERSIDAD NACIONAL DEL SANTA
Con la Web Computing se ve la red como un recurso computacional, de manera que se puede solicitar en la web la resolución de un problema, y este se asigna a algún o algunos sistemas para su resolución. Se puede tener Computación P2P o sistemas tipo, donde los usuarios o los laboratorios de computación ponen sus sistemas a disposición de los usuarios para ofrecer recursos computacionales, siempre con algunas restricciones de seguridad, uso...
Recientemente, nos referimos con Cloud Computing a una computación paralela donde se distribuyen los recursos de todo tipo: INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
21
UNIVERSIDAD NACIONAL DEL SANTA
es posible tener unos determinados centros de computación, otros de almacenamiento, otros se servicios software..., de manera que un usuario podría solicitar un determinado software de un centro, tomar almacenar datos en otro centro, y requerir de otro que resolviera el
problema con que esté trabajando. La combinación de todos estos elementos (Grid, web, P2P, Cloud computing, móviles...) y a la vez con sistemas lógicos distintos (compiladores, librerías, software básico...), hace que surja la necesidad de herramientas que permitan la virtualización, que consiste en la ejecución simulada en un Sistema de la computación que se realizaría en otro de características distintas, y los sercicios por demanda.
Se tiene de esta manera sistemas que son heterogéneos (tienen distinta velocidad de computación, capacidad de almacenamiento, distinta forma de representación de los datos...) y que están INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
22
UNIVERSIDAD NACIONAL DEL SANTA
organizados de forma jerárquica (en computación distribuida tendríamos varios sistemas geográficamente distribuidos, pudiendo ser estos sistemas de distinto tipo, unos de memoria compartida y otros redes de área local, compuestas a su vez por nodos que sean procesadores
multinúcleo
o
procesadores
gráficos).
Algunos
sistemas combinan una CPU y varios núcleos en una GPU; siendo la CPU más veloz, disponiendo de más memoria y con mayor precisión en la representación de los datos. Por otro lado, las GPU son mucho más baratas y más rápidas si se utilizan muchos elementos computacionales
que
permiten
trabajar
a
muchos
threads
simultáneamente. La tendencia es que también en los sistemas de memoria compartida encontremos sistemas heterogéneos, con núcleos de distinta arquitectura en un mismo chip.
Se está investigando en la utlización para computación
de
sistemas
no
convencionales: en la Computación Cuántica se utilizan las propiedades computación,
cuánticas y
en
la
de
las
partículas
Computación
para
Biológica
acelerar se
la
utilizan
propiedades de sistemas biológicos, como moléculas, células, cadenas de ADN... Esta computación también sería paralela al realizarse al mismo tiempo varias de las acciones que en un procesador convencional hay que realizar una tras otra, pero el tipo de paralelismo es
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
23
UNIVERSIDAD NACIONAL DEL SANTA
totalmente distinto del paralelismo tradicional que estudiamos en este curso.
2.3.
VARIANTES DE LA PROGRAMACIÓN PARALELA Dada la complejidad de los sistemas paralelos, en este seminario nos centramos en el estudio de las nociones básicas de la programación paralela, que son utilizadas en el desarrollo de programas paralelos en todos estos sistemas, aunque en muchos casos se necesita de herramientas y tecnología adicional que nos permita desarrollar y ejecutar sobre ellos los programas paralelos que se diseñen. También hay varios tipos de algoritmos y programación paralela, y en algunos casos sería necesario pensar los algoritmos de una manera alternativa al enfoque que usamos en el curso si se quiere obtener las máximas prestaciones en el sistema en el que se trabaje. Algunos tipos de programación paralela son:
Se habla de Programación Concurrente para referirse al caso en que varios procesos o threads colaboran en la resolución de un problema. Estos procesos pueden compartir el uso de un mismo procesador, en cuyo caso no hablaríamos de programación paralela.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
24
UNIVERSIDAD NACIONAL DEL SANTA
Para nosotros será programación paralela la que se hace usando varios procesadores para acelerar la resolución de los problemas con que trabajemos. Trabajaremos con algoritmos paralelos, donde se especifica la forma en que los distintos elementos de proceso comparten los datos, y cómo colaboran en la resolución de los problemas. En general consideraremos que los procesadores son todos del mismo tipo, con lo que tendremos sistemas paralelos homogéneos.
En los sistemas heterogéneos los componentes básicos pueden tener distinta velocidad, capacidades de memoria diferentes, o incluso la representación de los datos ser distinta. Los mismos programas de paso de mensajes utilizados en otros sistemas se pueden utilizar aquí, pero las prestaciones vendrán marcadas por la velocidad del procesador más lento. Para sacar el máximo rendimiento de un sistema heterogéneo habrá que desarrollar algoritmos heterogéneos, que tengan en cuenta la velocidad de los procesadores para asignarles cantidades distintas de datos en función de su velocidad.
En los sistemas híbridos también serán válidos los programas de paso de mensajes, que pueden ejecutarse tanto con memoria compartida como distribuida, pero la combinación de MPI con OpenMP puede dar lugar a programas con mejores prestaciones.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
25
UNIVERSIDAD NACIONAL DEL SANTA
En sistemas de carga variable la capacidad de cómputo de los nodos no es siempre la misma (quizás porque es un sistema multiusuario
y
los
trabajos
que
otros
usuarios
mandan
dinámicamente hacen que durante la ejecución de nuestro programa las condiciones del sistema cambien), y se requiere de algoritmos adaptativos, que serán heterogéneos pero en los que además habrá que evaluar periodicamente las condiciones del sistema para cambiar la distribución del trabajo en función de las velocidades en cada momento. o Por ejemplo La CPU y la GPU
A. PROGRAMACIÓN EN OPEN MP Analizaremos la programación paralela básicamente
con para
OpenMP, sistemas
homogéneos, aunque este tipo de programación también se usa como base para los otros sistemas mencionados, y analizaremos algún ejemplo de combinación de OpenMP y MPI para programación híbrida.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
26
UNIVERSIDAD NACIONAL DEL SANTA
B. PROGRAMACIÓN EN MPI
MPI
(acrónimo de
Message
Passing
Interface)
es
propuesta estándar
una de
para
un
interface de paso de mensajes para entornos paralelos, especialmente aquellos con memoria distribuida. En este modelo, una ejecución consta de uno o más procesos que se comunican llamando a rutinas de una biblioteca para recibir y enviar mensajes entre procesos. El objetivo de este módulo será la presentación de las nociones básicas de programación MPI. La metodología consistirá en presentar una introducción con los conceptos teóricos de la programación en MPI, seguida por una descripción de cómo preparar un entorno computacional para el desarrollo de aplicaciones.
C. PROGRAMACIÓN HÍBRIDA Las aplicaciones en clusters se pueden programar para utilizar paso de mensajes entre todos los procesadores. Pero es posible obtener mejores prestaciones si se utiliza un modelo híbrido de comunicación con compartición de información por memoria compartida y con memoria distribuida, a través de la fusión de MPI con OpenMP. INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
27
UNIVERSIDAD NACIONAL DEL SANTA
El objetivo de este módulo será la presentación de ejemplos de programación MPI+OpenMP en sistemas híbridos.
2.4 ACTUALIDAD Y AVANCES EN LA PROGRAMACIÓN PARALELA. Ya no estará el CPU y el GPU solos, se les une el PPU Hay un nuevo tipo de hardware para la PC, ya que no bastaba con el CPU y el GPU (Unidad de Procesamiento gráfico) ahora hay que preocuparse por el PPU (Physics Processing Unit o Unidad de Proceso Físico)... Al parecer este hardware fue concebido para juegos con físicas de alta complejidad como Unreal 3, los cuales soportarán este chip llamado AGEIA PhysX
Una Unidad de procesamiento físico (en Inglés PPU) es un microprocesador diseñado especialmente para manejar cálculos físicos en computación. Su uso esta particularmente extendido en el campo de los motores físicos y los video juegos. Algunos ejemplos de cálculos realizados por unidades de procesamiento físico son cálculos de dinámica de cuerpos rígidos, detección de colisiones, dinámica de fluidos, simulación de vestuario y cabello (en computación gráfica), análisis de elementos finitos y fractura de objetos. El propósito de estas
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
28
UNIVERSIDAD NACIONAL DEL SANTA
unidades de procesamiento físico es liberar de carga (de procesamiento) a las CPU haciendo dichas operaciones. A. HYPER TREADING HyperThreading (también conocido como HT Technology) es una marca registrada de la empresa Intel para denominar su implementación de la tecnología Multithreading Simultáneo también conocido como SMT. Permite a los programas preparados para ejecutar múltiples hilos (multithreaded) procesarlos en paralelo dentro de un único procesador, incrementando el uso de las unidades de ejecución del procesador. Esta tecnología consiste en simular dos procesadores lógicos dentro de un único procesador físico. El resultado es una mejoría en el rendimiento del procesador, puesto que al simular dos procesadores se pueden aprovechar mejor las unidades de cálculo manteniéndolas ocupadas durante un porcentaje mayor de tiempo.
B. INTEL TURBO BOOST La tecnología Intel® Turbo Boost ofrece aún más desempeño cuando se lo necesita en los sistemas equipados con los procesadores Intel® Core™ de tercera generación. La tecnología Intel® Turbo Boost 2.0 incrementa de forma automática la velocidad de procesamiento de los núcleos por encima de la frecuencia operativa básica si no se han alcanzado los límites especificados de energía, corriente y temperatura. INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
29
UNIVERSIDAD NACIONAL DEL SANTA
C. AUMENTO DINÁMICO DEL DESEMPEÑO La tecnología Intel® Turbo Boost 2.0 se activa cuando el sistema operativo (SO) solicita el estado de máximo desempeño del procesador (P0). La frecuencia máxima de la tecnología Intel Turbo Boost 2.0 depende de la cantidad de núcleos activos. El tiempo durante el cual el procesador se mantiene en el estado de la tecnología Intel Turbo Boost 2.0 depende de la carga de trabajo y del entorno operativo. Cualquiera de los siguientes factores puede definir el límite superior de la tecnología Intel Turbo Boost 2.0 con una determinada carga de trabajo:
Cantidad de núcleos activos
Consumo estimado de corriente
Consumo estimado de energía
Temperatura del procesador
Cuando el procesador funciona por debajo de estos límites y la carga de trabajo del usuario exige mayor desempeño, la frecuencia del procesador aumentará de forma dinámica hasta alcanzar su límite superior. La tecnología Intel Turbo Boost 2.0 posee varios algoritmos que funcionan en paralelo para administrar la corriente, energía y temperatura, a fin de maximizar el desempeño y la eficiencia energética. Nota: La tecnología Intel Turbo Boost 2.0 permite que el procesador funcione a un nivel de energía mayor que el límite nominal superior (TDP) durante períodos breves, a fin de maximizar el desempeño.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
30
UNIVERSIDAD NACIONAL DEL SANTA
3. ESTILOS DE PROGRAMACIÓN PARALELA Las aplicaciones paralelas deben ser escritas siguiendo un estilo o paradigma de programación. Existen muchos estilos de programación paralela y los más usados son paso de mensajes, variables compartidas y paralelismo de datos. Las arquitecturas paralelas se diferencian en el estilo de programación que más favorece su implementación hardware: paso de mensajes para multicomputadores, variables compartidas para multiprocesadores y paralelismo de datos para procesadores matriciales. A. PASOS DE MENSAJES En este estilo se define un conjunto de procesos con su propio espacio de memoria, pero que pueden comunicarse con otros procesos mediante el envío y la recepción de mensajes a través de la red de interconexión. El paradigma asume que cualquier proceso puede enviar un mensaje a cualquier otro. La implementación de esta metodología se suele realizar utilizando librerías añadidas a los lenguajes de programación estándar, fundamentalmente C y Fortran.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
Gráfico - Estilo de Paso de Mensajes.
31
UNIVERSIDAD NACIONAL DEL SANTA
De la gráfica se puede decir que: Las OPERACIONES y los DATOS se descomponen en PROCESOS. Los procesos sólo tienen acceso directo a los datos privados (locales). Los datos no locales se acceden mediante intercambio de mensajes entre los procesos (enviando y recibiendo mensajes). La transferencia de data requiere operaciones cooperativas para ser ejecutada por cada proceso (una operación de envío debe tener una operación de recepción).
Gráfico – Procesos y Canales. INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
32
UNIVERSIDAD NACIONAL DEL SANTA
En el paradigma de paso de mensajes, un programa paralelo se ve como un conjunto de procesos que se intercambian información a través de canales. a. HERRAMIENTAS DE SOFTWARE DE PASOS DE MENSAJE Para redactar código paralelo basado en paso de mensajes, se dispone de diversas herramientas software: como los lenguajes de programación antes mencionados, así como Ada u Occam; o bibliotecas de funciones que actúan de interfaz al sistema de comunicaciones, como MPI (Message Passing Interface - Interfaz de Paso de Mensajes) y PVM (Parallel Virtual Machine - Máquina Virtual Paralela). Actualmente se utilizan más las bibliotecas de funciones. Los fabricantes de supercomputadores suelen ofrecer implementaciones de lenguajes y bibliotecas para la programación, que sacan partido de la arquitectura abstracta y concreta de sus máquinas. La parte 1 de MPI se desarrolló en 1994, y la parte 2, en 1996. En su desarrollo se tuvo en cuenta la experiencia con PVM; la versión 3 de PVM apareció en marzo de 1993. b. COMUNICACIÓN DE PASOS DE MENSAJE Las funciones básicas de comunicación que ofrecen las herramientas software para paso de mensajes han de permitir, al menos, comunicación entre dos procesos (uno-a-uno). Para ello se utilizan dos funciones: una para enviar y otra para recibir: Send (destino, datos), funciona para enviar datos. Recieve (fuente, datos), función apara recibir datos. Generalmente, en la función para enviar, se especifica el proceso destino y la variable a enviar; y en la función de recepción se especifica la fuente y la variable en la que se ubicaran los datos que se reciben. Nos podemos encontrar, por lo general, con transmisiones síncronas o asíncronas. Si se implementa una transmisión síncrona, el proceso que ejecuta un send queda bloqueado hasta que el destino ejecute la función receive correspondiente; igualmente, el proceso que ejecuta receive queda bloqueado hasta que se realice el send correspondiente. De esta forma los procesos fuente y destino se sincronizan antes de realizar la transferencia de datos y la Comunicación es más rápida y eficiente. INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
33
Gráfica – Transmisión Síncrona en Paso de Mensajes
UNIVERSIDAD NACIONAL DEL SANTA
En una transmisión asíncrona la Comunicación es más lenta, ya que send no deja bloqueado el proceso que lo ejecuta; generalmente se ofrece una implementación de receive que deja bloqueado el proceso hasta que se realice el correspondiente send. Este bloqueo del receive permite sincronizar procesos. Para el send puede ser “no bloqueante” es necesario utilizar un buffer en el que ubicar los datos que se envían al destino. Este buffer no es necesario en comunicaciones síncronas, en estas la transferencia de datos la realiza el sistema de comunicación entre la variable del proceso fuente especificada en send y la variable del destino especificada en receive.
Gráfica – Transmisión Asíncrona en Paso de
B. VARIABLES COMPARTIDAS Los programas paralelos ejecutados en sistemas de variables compartidas se descomponen en varios procesos (tareas) que comparten los datos asociados a una porción de su espacio de direcciones. Cada proceso puede llevar a cabo la ejecución de un subconjunto de iteraciones de un lazo común, o bien, de forma más general, cada proceso puede obtener sus tareas de una cola compartida. INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
34
UNIVERSIDAD NACIONAL DEL SANTA
La programación más eficiente, aunque dificultosa, se establece a través de construcciones de bajo nivel tales como barreras de sincronización, regiones críticas, locks, semáforos, etc.
De la gráfica se puede decir que: Las operaciones se descomponen en tareas. Los datos son compartidos por todas las tareas. La sincronización es -obtenida la escritura y lectura a las Gráfico Estilo controlando de Variables Compartidas. a. HERRAMIENTAS DE SOFTWARE DE VARIABLES COMPARTIDAS Hay diversas herramientas software para redactar código paralelo basado en variables compartidas: Ada 95 (tipos protegidos) y Java; o bibliotecas de funciones, como Pthread (POSIX-Thread) u OpenMP, y alternativas que usan lenguaje secuencial más directivas dl compilador, como OpenMP. POSIX-Pthread es un estándar, introducido en 1996 por el comité de estándares del IEEE, basado en funciones. OpenMP es una biblioteca de funciones, directivas y variables, desarrollado por un grupo representativo de vendedores de hardware y software [OpenMP Home]. Las herramientas software de variables compartidas ofrecen mecanismos para implementar sincronización tales como: cerrojos, semáforos, variables condicionales, monitores u otras construcciones que implementan secciones críticas o accesos a variables en exclusión mutua. Con respecto a la sincronización, en Ada 95 se añadieron los tipos protegidos, que son similares a los monitores; con POSIX-Thread se dispone de cerrojos, semáforos y variables condicionales. OpenMP dispone de cerrojos y barreras, y construcciones para INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
35
UNIVERSIDAD NACIONAL DEL SANTA
implementar secciones críticas, o acceso a variables atómico. También permite utilizar funciones colectivas. C. PARALELISMO DE DATOS Es un paradigma de programación claramente heredado de las máquinas SPMD y se utiliza principalmente para simplificar la programación de sistemas de memoria distribuida. En esta aproximación, un programa secuencial en un lenguaje estándar es complementado con directivas o anotaciones insertadas en el programa para guiar al compilador en su tarea de distribuir los datos y las computaciones. Actualmente los lenguajes de paralelismo de datos más populares son CM-Fortran (Connection Machine Fortran), Fortran D, Craft, Vienna Fortran] y especialmente el considerado como estándar HighPerformance Fortrun (HPF).
Gráfico - Estilo de Variables Compartidas.
De la gráfica se puede decir que:
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
36
UNIVERSIDAD NACIONAL DEL SANTA
Distintos procesos aplican las mismas operaciones a una parte diferente de la misma estructura de datos. Usa un enfoque Single Program, Multiple Data (SPMD). Es una modificación del algoritmo secuencial. a. HERRAMIENTA DE SOFTWARE DE PARALELISMO DE DATOS Los lenguajes con paralelismo de datos, como C* (C start), aparecieron ligados a procesadores matriciales. Estas máquinas son arquitecturas SPMD. Desde su aparición en 1960 los procesadores matriciales se han encontrado dentro de la gama de los supercomputadores, pero en 1997 dejaron de aparecer en la lista TOP500. No obstante, actualmente, la mayor parte de los computadores de altas prestaciones tienen compiladores para lenguajes con paralelismo de datos, como Fortran 90 y HPF. Fortran 90, basado en Fortran 77, permite al programador implementar paralelismo de datos utilizando operaciones con vectores y matrices. La primera versión de HPF apareció en 1992, es una ampliación de Fortran 90.
4. ESTRUCTURA DE PROGRAMACIÓN PARALELA Analizando la estructura (grafo) de las tareas (unidad de trabajo de la aplicación) y de los procesos (unidades de código en ejecución) de múltiples programas paralelos, se puede encontrar que hay ciertos patrones que se repiten en distintos programas y dentro de un programa. En estas estructuras de las relaciones entre las tareas o entre procesos representan comunicaciones. En estas estructuras están: Maestro – esclavo (Master-Slave) o granja de tareas (Task-Farming). Descomposición de datos Divide y vencerás (divide and conquer) o descomposición recursiva
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
37
UNIVERSIDAD NACIONAL DEL SANTA
Hay estructuras entre las que no hay un límite totalmente claro. Por otra parte, nos podemos encontrar dentro de un mismo programa paralelo varias de estas estructuras en diferentes niveles.
A. Maestro – esclavo (Master-Slave) o granja de tareas (Task-Farming). En este caso, en la estructura de procesos se distingue un proceso Maestro y múltiples esclavos. El proceso Maestro se encarga de distribuir las tareas de un conjunto (granja) entre el grupo de esclavos, y de ir recolectando los resultados parciales que van calculando los esclavos, con los que el Maestro obtiene el resultado final. Usualmente no hay comunicación entre los esclavos. Si todos los esclavos ejecutan el mismo código, la aplicación se puede implementar con dos programas, uno para el Maestro y otro para los esclavos (modo mixto MPMD-SPMD). No obstante, también se puede hacer un único programa con el código del Maestro y del esclavo (SPMD).
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
38
UNIVERSIDAD NACIONAL DEL SANTA
MAESTRO ESCLAVO
Maestro Esclavo
Esclavo
P
P E/S
Esclavo
M
E/S
M
Red de Interconexión
E/S
M P
E/S
M P
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
39
UNIVERSIDAD NACIONAL DEL SANTA
B. Descomposición de datos Esta alternativa es muy utilizada para obtener tareas paralelas en problemas en los que se opera con grandes estructuras de datos. La estructura de datos de entrada o la estructura de datos de salida o ambas, se dividen en partes. A partir de esta división se derivan las tareas paralelas. Estas generalmente realizan operaciones similares, aunque hay descomposiciones en las que las tareas no realizan exactamente las mismas operaciones. Nos podemos encontrar aplicaciones en las que se pueden realizar distintas descomposiciones de datos alternativas. Los algoritmos con imágenes, por ejemplo, fácilmente admiten a una descomposición de datos. Una estructura de procesos para esta alternativa seria la representada en la figura. Los procesos pueden englobar varias tareas. Los diferentes procesos ejecutan típicamente el mismo código (SPMD), aunque cada uno trabaja sobre un conjunto de datos distintos. INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
40
UNIVERSIDAD NACIONAL DEL SANTA
Como ilustra la figura, puede haber comunicaciones entre los diferentes procesos. Si no hay ninguna interacción entre procesos, sería una aplicación embarazosamente paralela (embarrassingly parallel computation). Otra posible estructura es la que cambia las estructuras de las figuras.
DESCOMPOSICIÓN DE DATOS
P
P E/S P1
P2
P3
E/S
M
M
P4 Red de Interconexión
E/S
E/S
M
P
P
C. Divide y vencerás (divide and conquer) o descomposición recursiva Esta estructura se utiliza cuando un problema se puede dividir en dos o más sub-problemas de forma que cada uno se puede resolver independientemente, combinándose los resultados para obtener el resultado final. Si los sub-problemas son instancias más pequeñas del original, entonces se podrían subdividir a su vez recursivamente. Las tareas presentan una estructura en forma de árbol. Los programas secuenciales recursivos tienen una implementación paralela divide y vencerás (paralelismo de tareas). También podemos encontrar esta estructura descomponiendo los datos de un problema recursivamente (paralelismo de datos). Por ejemplo un vector cuyo componentes se van a sumar se puede descomponer recursivamente en dos vectores, hasta llegar a vectores de dos componentes. En la figura la suma de los vectores A de 8 componentes (a0, a1,…, a7), se ha descompuesto en sumas de dos componentes. Fácilmente se obtiene un implementación SPMD para divide y vencerás. A INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS B
a0 a11 a2
a3
C a4
a5
M
a6
a7
41
DIVIDE Y VENCERAS UNIVERSIDAD NACIONAL DEL SANTA
a0 a1 a2 a3
a4
a5 a6 a7
P3
P2
P1
5. PROCESO DE PARALELIZACIÓN ¿Para quién es importante? o o P0
Diseñadores de Algoritmos Diseñar algoritmos que corran bien en sistemas reales. Programadores Comprender dónde radican las claves del rendimiento para obtener el
mejor posible en un sistema dado. o Arquitectos Comprender las cargas, las interacciones, y la importancia de los
grados de libertad. Importante para el diseño y la evaluación.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS Malla 2x2
42
UNIVERSIDAD NACIONAL DEL SANTA
Importancia de la programación: Diseñamos máquinas para que ejecuten programas. Así pues, éstos: Ayudan a tomar decisiones en el diseño hardware; Ayudan a evaluar los cambios en los sistemas. Son la clave que dirige los avances en la arquitectura uniprocesador. Caches y diseño del conjunto de instrucciones. Mayor importancia en multiprocesadores. Nuevos grados de libertad. Mayor penalización si hay desacoplo entre programas y arquitectura. Más espacio para optimaciones en software. Aun desde el punto de vista arquitectónico, necesitamos abrir la “caja
o o o o o
negra” del software. o Aunque un problema disponga de un buen algoritmo secuencial, paralelizarlo no es trivial. o Hay que ser capaces de Extraer el paralelismo y Combinarlo con las prestaciones ofrecidas por la arquitectura.
Algunos conceptos importantes Tarea: o Orden de trabajo que no puede descomponerse en subórdenes ejecutables en paralelo. o Se ejecuta secuencialmente; la concurrencia solo se da entre tareas. o Granularidad fina frente a granularidad gruesa, dependiendo de la cantidad de trabajo que suponga la realización de la tarea.
Proceso (thread o hebra): o Entidad abstracta que ejecuta las tareas que le son asignadas. o Un programa paralelo está constituido por “muchos procesos cooperando”. o Hay una comunicación y sincronización en los procesos para la ejecución de las tareas.
Procesador: o Elemento físico en el que se ejecutan los procesos. o Los procesos constituyen la máquina virtual para el programador. INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
+ 43 + +
+ +
UNIVERSIDAD NACIONAL DEL SANTA
Primero se escribe el programa en términos de procesos y después de mapea a los procesadores.
Fases Del Proceso de Paralelización:
5.1. Descomposición: o División del programa en tareas que serán distribuidas entre los procesos. o Las tareas pueden estar dispuestas para ejecución dinámicamente. INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
44
UNIVERSIDAD NACIONAL DEL SANTA
El número de tareas disponibles puede variar con el tiempo. Identificar la concurrencia y decidir a qué nivel se va a explotar. o Objetivo: Suficientes tareas para mantener ocupados los procesos pero no demasiadas. El número de tareas disponibles en un momento define el límite del speedup que podemos conseguir.
5.2. Asignación: o Mecanismo específico para dividir el trabajo entre procesos. Junto con la descomposición recibe el nombre de partición. Objetivos: o equilibrar la carga; o minimizar comunicación y coste de la gestión de la asignación. o Aproximarse a las estructuras suele ser buena idea. Inspección del código (paralelizar bucles). Existen procesos heurísticos ya establecidos. Asignación estática frente a asignación dinámica. o La partición es la primera preocupación del programador. Generalmente independiente de la arquitectura o el modelo de
programación. Pero el coste y complejidad de las primitivas usadas puede afectar a la decisión.
5.3. Escribir el código: o Para ejecutar las tareas asignadas, los procesos necesitan mecanismos para: referirse y acceder a los datos; intercambiar datos con otros procesos (comunicación); sincronizar las actividades. o Las decisiones tomadas en la redaccion del código son muy dependientes INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
45
UNIVERSIDAD NACIONAL DEL SANTA
del modelo de programación; de la eficiencia con que las primitivas del modelo están implementadas.
o En esta parte se incluyen, entre otras cosas: cómo organizar las estructuras de datos; cómo planificar temporalmente las tareas asignadas a un proceso
para explotar la localidad de datos; cómo organizar la comunicación entre procesos resultantes de la
asignación. o Objetivos Reducir el coste de comunicación y sincronización. Preservar las referencias a datos locales (organización de las
estructuras de datos). Programar las tareas para satisfacer rápidamente las
dependencias. Reducir la sobrecarga que introduce el paralelismo. o Cercanos a la Arquitectura (y al modelo de programación) La elección depende mucho de la comunicación, eficiencia y las
primitivas. La arquitectura debe proporcionar las primitivas adecuadas de manera eficiente.
5.4. Evaluación: o Después de escribir el código ya tenemos un programa paralelo. o Dos aspectos del mapeado: Qué procesos se ejecutarán en el mismo procesador. Qué procesos se ejecutan en un procesador determinado.
El mapeado se realiza en una topología determinada.
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
46
UNIVERSIDAD NACIONAL DEL SANTA
LINKOGRAFÍA
- http://ocw.uc3m.es/ingenieriainformatica/arquitectura-de-computadoresii/materiales-de-clasee/mc-f-002-ii - http://www.fing.edu.uy/inco/cursos/hpc/materi al/clases/Criba.pdf - http://atc2.aut.uah.es/~rduran/Areinco/pdf/n_t ema5.pdf - http://www.cs.buap.mx/~mtovar/doc/ProgCon c/ProgramacionParalela.pdf - http://www.qft.iqfr.csic.es/curso_paralelo.pdf
INGENIERIA DE SISTEMAS E INFORMATICA – ARQUITECTURA DE COMPUTADORAS
47