Programación paralela. Lenguajes y modelos de programación paralela (página 2)

Partes: 1, 2

Paso de mensajes
Extensiones básicas: Son extensiones en los lenguajes secuenciales para soportar el paso de mensajes.

Existen dos primitivas básicas de comunicación: SEND y RECEIVE.
La forma general de send es:
SEND (message, messagesize, target, type, flag)
message contiene los datos que se envían,
messagesize indica el tamaño en bytes,
target es la etiqueta del procesador o procesadores destino,
type es una constante con la que se distingue entre varios tipos de mensajes, y
flag indica si la operación del SEND es bloqueante o no-bloqueante.

Paso de mensajes
La primitiva RECEIVE lee un mensaje del buffer de comunicación en la memoria.
Su forma general es:
RECEIVE (message, messagesize, source, type, flag)
messsage indica el lugar donde se almacenan los datos,
messagesize indica el número máximo de bytes a poner en mensaje,
source indica la etiqueta del procesador cuyo mensaje se va a leer,
type especifica el tipo de mensaje que se va a leer. Puede haber más de un mensaje en el buffer de comunicación de los procesadores fuente. El parámetro type selecciona un determinado mensaje para leer,
flag especifica si la operación de recibir es bloqueante o no bloqueante.

Paso de mensajes

Ejemplo: nCUBE 2

? MIMD desarrollado por nCUBE Corporation

? Red de interconexión hipercubo. Hasta 8192 procesadores

? Utiliza extensiones de los lenguajes C y FORTRAN.

Sólo define un send no-bloqueante:

C: int nwrite (char *message, int messagesize, int target, int type, int *flag)

Fortran: integer function nwrite (message, messagesize, target, type, flag)
dimension message (*)
integer messagesize, target, type, flag
Paso de mensajes

Define un receive bloqueante:

C: int nread(char *message, int messagesize, int *source,
int *type, int *flag)

Fortran: integer function nread (message, messagesize, source, type, flag)
dimension message (*)
integer messagesize, source, type, flag
Paso de mensajes

Se emula un receive no-bloqueante llamando a una función para testear la existencia de un mensaje en el buffer de comunicación:

C: int ntest (int *source, int *type)

Fortran: integer function ntest (source, type)
integer source, type

Paso de mensajes

Ejemplo: iPSC 860

MIMD con red de interconexión hipercubo y hasta 128 procesadores

Utiliza modelo nodo-host y sin-host, con extensiones para el C y fortran.

Las mismas extensiones se utilizan en el Intel Paragon XP/S que es una malla.
Paso de mensajes

Sólo existen un send no-bloqueante:
C: csend (long type, char *message, long messagesize, long target, long flag)

Receive bloqueante:
C: crecv (long type, char *message, long messagesize)

Receive no-bloqueante: devuelve un número que se usa para chequear el estado de la operación recibir.
C: int irecv(long type, char *message, long messagesize)
Paso de mensajes

Lenguajes de paralelismo de datos: facilitar al programador la tarea de expresar el paralelismo disponible en un programa de manera independiente de la arquitectura.

Características:
Se genera una sola cadena de instrucciones.
Ejecución síncrona de instrucciones. Más fácil escribir y depurar programas de paralelismo de datos puesto que los bloqueos son imposibles.
El programador especifica el paralelismo en el código.
Asocia un procesador virtual con una unidad fundamental de paralelismo. El programador expresa la computación en términos de las operaciones realizadas por los procesadores virtuales.
Permite que cada procesador tenga acceso a las posiciones de memoria de otros procesadores.
Paralelismo de datos

Los compiladores para los lenguajes de paralelismo de datos deben mapear los procesadores virtuales en procesadores físicos, generar código para comunicar datos y esforzarse para la ejecución síncrona de instrucciones.
Los procesadores virtuales son emulados por procesadores físico. Si el número de procesadores virtuales es mayor que el número de procesadores físicos, cada procesador físico emula varios procesadores virtuales.
Algunos lenguajes de paralelismo de datos contienen primitivas que permiten al programador especificar el mapeo deseado de los procesadores virtuales en los físicos.
Paralelismo de datos

Ejemplo: C*

Lenguaje de programación para paralelismo de datos. Extensión del lenguaje C, diseñado por Thinking Machines Corporation para el computador CM-2.

Incluye un método para describir el tamaño y la forma de los datos paralelos y crear variables paralelas. Incluye operadores y expresiones para los datos paralelos.
Paralelismo de datos

Variables:

variables escalares: idéntica a una variable ordinaria. Se asignan en el host.

variables paralelas:
Se asignan en todos los nodos.
Tienen tantos elementos como número de procesadores.
Una variable paralela tiene una "forma" además de un tipo.
Una "forma" es una plantilla para los datos paralelos, o sea una forma de configurar los datos lógicamente.
Define cuántos elementos paralelos existen y cómo están organizados.
Una "forma" tiene un número de dimensiones, rango, con un número de procesadores o posiciones en cada dimensión.
Paralelismo de datos

shape [1024] ring
shape [1024][1024] mesh

int flag flag
int ring:a a
int mesh:b b

Paralelismo de datos

C* no permite que el programador especifique explícitamente el mapeo virtual a físico. C* mapea los procesadores virtuales en procesadores físicos de forma que los procesadores virtuales vecinos se mapean en procesadores físicos vecinos.
C* permite especificar a través de qué dimensiones de la "forma" se hacen comunicaciones más a menudo. El compilador usa esta información para reducir costos de comunicación.
Después de que se ha especificado una forma, se pueden declarar variables paralelas de esa "forma". Las variables paralelas tienen un tipo, una clase de almacenamiento, y una forma.
Paralelismo de datos

Operaciones paralelas
Si los operandos de una operación son escalares, el código C* es igual que el código C y la operación se realiza en el host.

Si los operandos son variables paralelas,
x+=y donde x e y son variables paralelas. Esta asignación añade el valor de y en cada posición de la "forma" al valor de x en la posición correspondiente de la forma. Todas las sumas tienen lugar en paralelo. x e y deben ser de la misma "forma".
x=a, donde a es una variable escalar, el valor de a se almacena en cada posición de x. Esto es similar a una operación de broadcast. a =[4]x es válida y asigna a a el valor de x de la cuarta posición de la forma.
a+=x suma todos los valores de x y los almacena en a.
Paralelismo de datos

Fijar el contexto. Con la declaración where se restringen las posiciones de las variables paralelas sobre las que se realizan las operaciones, llamadas posiciones activas. Seleccionar las posiciones activas de una "forma" se denomina fijar el contexto. Por ejemplo, la declaración where en el siguiente código evita dividir por cero.
with (ring) {
where (z!=0)
x=y/z;
}

Se pude incluir else para complementar la fijación de posiciones activas
with (ring){
where (z!=0)
x=y/z;
else
x=y;
}
Paralelismo de datos

Comunicación. C* soporta dos métodos de comunicación interprocesador:

comunicación en red: las variables paralelas del mismo tipo pueden comunicarse en patrones regulares. Es bastante eficiente.

comunicación general: el valor de cualquier elemento de una variable paralela se puede enviar a cualquier otro elemento aunque las variables paralelas no sean de la mismo "forma".
Paralelismo de datos

La comunicación paralela en C* usa Indexación paralela a la izquierda. Un índice paralelo a la izquierda ordena los elementos de la variable paralela basándose en los valores almacenados en los elementos de los índices paralelos. El índice debe ser de la "forma" actual.

dest=[index]source [index]dest=source
0 1 2 3 4 5 0 1 2 3 4 5
source 20 40 5 10 0 30 20 40 5 10 0 30

index 3 2 1 5 4 0 3 2 1 5 4 0

dest 10 5 40 30 0 20 30 5 40 20 0 10
Paralelismo de datos

Para la comunicación en red, C* usa una nueva función llamada pcoord. Los datos se pueden enviar sólo a una distancia fija a lo largo de cada dimensión.
dest1d=[pcoord(0) +1]source1d
source1d=(6,4,1,9,2,8) destsd=( ,6,4,1,9,2)
dest1d=[pcoord(0)-2]source1d
source1d=(6,4,1,9,2,8) destsd=(1,9,2,8, , )
dest2d=[pcoord(0)+1][pcoord(1)+1]source2d
source2d=(9,4,1, dests2d=( , , ,
6,5,15, ,9,4,
13,2,12) ,6,5)
dest2d=[(pcoord(0)+1)%%4][(pcoord(1)+1)%%3]source2d
source2d=(9,4,1, dests2d=( 7,8,3,
6,5,15, 1,9,4,
13,2,12, 15,6,5,
8,3,7) 12,13,2)
Paralelismo de datos

Primitivas para asignar variables compartidas.
Existen dos tipos de variables: compartidas (shared) y locales (private)

Primitivas para la exclusión mutua y sincronización.
Una sección crítica contiene código que sólo puede ser ejecutado por un procesador en un momento determinado. Los lenguajes proporcionan llaves (locks) para ayudar al programador a cumplir la exclusión mutua en la ejecución de secciones críticas.
Las primitivas de sincronización de barreras (barrier synchronization) se usan cuando los procesos necesitan sincronizarse antes de que acabe la ejecución. Cada proceso espera en la barrera a los otros procesos, y después de la sincronización todos los procesos continúan con su ejecución.

Espacio de direcciones compartido

Primitivas para la creación de procesos
Se realiza mediante una llamada al sistema que crea procesos idénticos al proceso padre. Estos procesos comparten las variables declaradas "compartidas" por los procesos padre así como las llaves declaradas e inicializadas por los procesos padre. En la mayoría de computadores de espacio de direcciones compartido, esta operación se llama fork. Cuando todos los subprocesos terminan, se mezclan usando otra primitiva, normalmente llamada join.
En vez de crear procesos al principio de la ejecución, podemos tener un solo proceso, llamado proceso maestro. Cuando el maestro necesita realizar una tarea en paralelo, crea un número predeterminado de procesos, llamados procesos esclavos. Cuando la tarea se completa, los procesos esclavos terminan y devuelven el control al proceso maestro.
Espacio de direcciones compartido