PDF de programación - Introducción a la Programación Paralela (primera parte)

1

José Luis Gordillo
Leobardo Itehua

Julio César Clemente

Coordinación de Supercómputo

DGTIC - UNAM

2

3

Introducción

o  Uno de los propósitos principales de escribir un
programa paralelo suele ser conseguir un modelo
computacional que permita estudiar algún fenómeno de
forma más rápida

o  Se necesitan programas paralelos:

§  Eficientes
§  Escalables
§  Portables
§  Flexibles

4

Introducción

o  Seminarios/talleres típicos de IPP cubren conceptos ne-

cesarios para hacer programas eficientes

o  Si el problema es trivialmente paralelizable, los

conceptos se aplican de forma trivial
§  Pero la mayoría de las aplicaciones interesantes no son triviales
§  Seminarios/talleres típicos de IPP cubren aplicaciones triviales y

no triviales de estos conceptos

5

Introducción

o  Modelos de programación/arquitectura de computadoras

paralelas
§  ¿Cómo son y cómo se programan las computadoras paralelas?

(1)

o  Reparto de carga

§  ¿Cómo se utilizan simultáneamente los procesadores de una

computadora paralela?(2)

o  Comunicaciones

§  ¿Cómo se definen, estructuran y miden las comunicaciones entre

procesos? (3)

6

Introducción

o  Balance de carga

§  ¿Qué dificultades se pueden encontrar al repartir la carga entre

procesadores y qué efectos tiene una carga mal repartida? (4)



o  Validación del programa

§  ¿Cuál es la fuente de las diferencias de resultados entre la versión

secuencial y la paralela? (5)



o  Evaluación de rendimiento/eficiencia

§  Speedup, eficiencia, speedup superlineal, speedup escalado,

granularidad, paralelismo, concurrencia (6)

7

Introducción

o  Sin embargo, los participantes sin experiencia en progra-

mación paralela se quedan en (1) o en (2)
§  Los casos complejos son difíciles de asimilar, ya que no se ha

experimentado con casos triviales



o  Nuestra estrategia es dividir el trabajo en dos

§  Que el estudiante aprenda a hacer programas paralelos (versión

completa de este seminario)

§  Que el estudiante aprenda conceptos y herramientas para hacer
buenos programas paralelos (versión completa de IPP segunda
parte)

8

¿Por qué hacer programas paralelos?

9

o  A mediados de 1990’s, los fabricantes de supercom-
putadoras determinaron que era más fácil y barato cons-
truir máquinas con muchos procesadores en vez de
construir procesadores más potentes


o  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
§  Prácticamente ya no se fabrican procesadores de un solo “core”

¿Por qué hacer programas paralelos?

10

o  Las supercomputadoras han pasado en estos 15 años de
unos cuantos miles de procesadores a más de 100,000
“cores”

•  En servidores existen procesadores con 12 “cores” y se
espera que este número se siga incrementando año con
año
•  ¿Qué se puede hacer con tantos “cores” ?

•  Correr muchos programas distintos simultáneamente
La cantidad de trabajo por unidad de tiempo aumenta
•  High Throughput Computing

• 

•  Correr un solo programa usando todos los cores disponibles



•  High Performance Computing

¿Por qué hacer programas paralelos?

11

o  Nota: ¿es lo mismo “core” que “procesador”?

§  En procesadores que se usan en equipos de escritorio y en
servidores (Opteron, Athlon, Xeon, PowerPC), son equivalentes
desde el punto de vista de programación
•  Los cores son procesadores completos incrustados en un mismo “chip”
•  Las diferencias tienen que ver con la forma en que se comunican cores

de un mismo chip vs cores en distintos chips (Segundo seminario)

§  En el caso de otro tipo de dispositivos, como GPUs o

procesadores Cell, son distintos
•  Se programan de forma distinta

¿Qué son los programas paralelos?

12

o  Crear un programa paralelo significa hacer un programa
que utiliza de forma coordinada más de un elemento de
procesamiento
§  Procesadores, cores, etc.


o  Todo programa realiza una cierta cantidad de “trabajo”

§  Una secuencia de instrucciones/operaciones en uno o más

conjuntos de datos

o  Un programa paralelo reparte ese trabajo entre los varios

elementos de procesamiento que se pretende utilizar
§  El hecho de repartir el trabajo se conoce como “partición” o

“descomposición”

13

Reparto de carga

o  Si se reparten las intrucciones/operaciones, se conoce

como “partición funcional”
§  Poco usada, ya que en la mayoría de los casos las funciones que

pueden realizarse simultáneamente son pocas



o  Si se reparten los datos, se conoce como “partición de

datos”
§  Es la más utilizada, ya que los conjuntos de datos suelen ser
bastante grandes, y las operaciones que se realizan sobre ellos se
pueden hacer de forma simultánea
•  Átomos en simulaciones de dinámica molecular

o  Los mecanismos para repartir datos dependen de la

arquitectura y del modelo de programación paralela

14

Arquitecturas de computadoras

paralelas

Computadoras paralelas

15


Una computadora paralela está compuesta de
procesadores, memoria, sistemas de entrada/sali-
da y sistemas de interconexión.



16

Fujitsu K

17

GPGPU

FireStream 9370

Tesla M2090

Dispositivos con varios núcleo



18

Computadoras paralelas

19

El procesador carga y ejecuta instrucciones de un
programa, esta ejecución implica cálculos lógicos
y aritméticos, accesos a memoria y mantener el
orden de ejecución del programa.

El sistema de memoria almacena el estado actual
de los cálculos y mantiene la consistencia de los
datos cuando varios procesadores hacen uso de la
memoria concurrentemente.

Computadoras paralelas

20

Estos nodos requieren de redes de interconexión
que les permitan colaborar en la solución de un
único problema de gran magnitud.



Las redes de interconexión también conectan los
nodos con dispositivos de entrada/salida.



El sistema de Entrada/Salida da soporte a
sistemas periféricos como son unidades de cinta,
discos y redes externas.


Computadoras paralelas

21


El desempeño de todos estos sistemas deter-
minan el rendimiento general de la computadora
paralela.



Computadoras paralelas

22

Es importante el estudio de los elementos que
componen una computadora paralela para
entender lo que sucede con el flujo de los datos e
instrucciones entre la memoria y las unidades de
procesamiento.
De otra manera se tendrá dificultad en entender
las técnicas de optimización y la información que
proporcionan las herramientas para mejorar su
desempeño.



Taxonomía de arquitecturas

23

o Existen diferentes tipos de máquinas paralelas
o Existen varias formas de clasificarlas

§  Taxonomía de Flynn
§  Por mecanismos de comunicación

Nota: varios sistemas son una mezcla de estos enfoques y no corresponden
exactamente a las clasificaciones.

Taxonomía de Flynn
(Instrucción/Datos)

24


La clasificación de Flynn (1966) está basada en el
número de flujos de instrucciones y de datos que
pueden ser procesados simultáneamente.

SISD

(una instrucción, un dato)

25

o  La definición clásica de un solo procesador.

o  Ejemplos de arquitecturas SISD son las máquinas con
uni–procesador o monoprocesador tradicionales como
algunos PC o los antiguos mainframe.

SIMD

(una instrucción, múltiples datos)

26

o  Como ejemplo de este caso podemos citar al procesador

vectorial.

27

MIMD

(múltiples instrucciones, múltiples datos)

o  Cubre el rango de sistemas multiprocesadores.
o  Los sistemas distribuidos suelen clasificarse como
arquitecturas MIMD; bien sea explotando un único
espacio compartido de memoria o uno distribuido.

MISD

(múltiples instrucciones, un dato)

28



o  Poco común debido al hecho de que la efectividad de los
múltiples flujos de instrucciones suele precisar de
múltiples flujos de datos.

Taxonomía de Flynn

29

Esta clasificación es útil por su simplicidad y amplio uso,
sin embargo, existen severas críticas a la clasificación,
particularmente porque contiene modelos inexistentes
(MISD) y fue bastante amplio para la clasificación de
sistemas multiprocesadores.

Mecanismos de comunicación

30

La categoría de multiprocesadores MIMD está dividida en
dos subtipos:

o  Memoria compartida
o  Memoria distribuida

Memoria compartida

31

Un multiprocesador MIMD de memoria compartida tiene
sólo una memoria que puede ser accedida por todos los
procesadores.

Un problema importante en este tipo de máquinas es la
escalabilidad, ésta es la facilidad para incrementar el
número de procesadores y otros elementos de HW
significativamente con un correspondiente incremento en el
rendimiento.

Memoria compartida

32

Memoria compartida

33


Conforme se incrementa el número de procesadores de
igual manera aumenta el tráfico en el bus que conecta a
los procesadores con la memoria compartida.

Incrementando el ancho de banda del bus se soluciona
parcialmente el problema, de cualquier manera, muchos
programas requieren el uso de variables comunes para la
mayoría de los procesadores.



Memoria distribuida

34


Cada uno de los procesadores individuales de un
multiprocesador de memoria distribuida tiene asociado
directamente a él una unidad de memoria; esto es, cada
procesador tiene su propia memoria local. Un procesador
junto con su memoria es llamado nodo y está conectado a
los otros nodo