Practica 8

Paso de Mensajes a través de la API “MPI”

La generación de una versión paralelizada básica del intérprete de Python es una tarea sencilla. Es suficiente con proveer la inicialización de MPI (con MPI Init()), la llamada al interprete (con la función Py_Main() de la librería de Python), y la finalizacion de MPI (con MPI Finalize()).

Ejemplo:

#include <Python.h> #include <mpi.h>

int main(int argc, char **argv) {

int status;

/* initialize MPI */ MPI_Init(&argc, &argv);

/* call Python main */ status = Py_Main(argc, argv);

/* finalize MPI */ MPI_Finalize();

return status;

}

MPI

Este módulo provee una aproximación orientada a objetos para paso de mensajes. Está basado en la sintaxis de la especificacion MPI-2 para C++. Por lo tanto, cualquier usuario que conozca la sintaxis estándar de MPI para C++ puede utilizar este módulo sin necesidad de conocimientos adicionales. El diseño es simple y efectivo. El módulo MPI consiste de código escrito en Python que define constantes, funciones y una jerarquía de clases. Este código llama a un módulo de soporte escrito en C, el cual provee acceso a las constantes y funciones de la especificacion MPI-1. Los objetos a comunicar se serializan utilizando el módulo estándar cPickle de Python. Luego, la representación serializada del objeto (en realidad, una cadena de caracteres) es transmitida apropiadamente (utilizando el tipo MPI CHAR). Finalmente, el objeto original se recupera a partir del mensaje recibido. Si bien la serializacion de objetos con cPickle impone algunos costos adicionales en tiempo y memoria, la estrategia es completamente general, y permite la comunicación los diversos tipos de objetos de Python en forma totalmente trasparente para el usuario.

Ejemplo de Spawn() broadcast() y reduce()

Ejemplo de send() y recv()

Ejemplo de scatter()

Ejemplo de gather()

Ley de Gustafson

LEY DE GUSTAFSON

La ley de Gustafson (también conocida como ley de Gustafson-Barsis) es una ley que establece que cualquier problema suficientemente grande puede ser eficientemente paralelizado.

La ley de Gustafson está muy ligada a la Ley de Amdahl, que pone límite a la aceleración que se puede obtener gracias a la paralelización, dado un conjunto de datos de tamaño fijo, ofreciendo así una visión pesimista del procesamiento paralelo. Por el contrario la ley de Gustafson ofrece un nuevo punto de vista y así una visión positiva de las ventajas del procesamiento paralelo. John L. Gustafson enunció por primera vez la ley que lleva su nombre en 1988.

De acuerdo a la fórmula que vimos antes, la mejora de velocidad, o speedup está dada por

Speedup = 1 / (s + p / N)

Donde:

·         s es el tiempo en la parte serial

·         p es el tiempo que toma 1 procesador en la parte paralela del problema, y N es la cantidad de procesadores.

Gustafson notó que para un valor de s entre 0,4% y 0,8% obtenía valores de speedup de 1020 ó 1016, usando un hipercubo con 1024 procesadores.

Si hacen los cálculos verán que eso no se ajusta a lo predicho por la Ley de Amhdal (para s = 0,4% el valor speedup es = 1 / (0,004 + 0,996/1024) = 201,099).

Gustafson se dió cuenta que Amdahl asume que la parte paralelizable p es independiente del valor N, o sea, de la cantidad de procesadores, esto casi nunca se da, de acuerdo a Gustafson, en la práctica el tamaño del problema escala con la cantidad de procesadores.

Gustafson propuso una ley distinta para los problemas en que la parte paralela p’ depende linealmente de la cantidad de procesadores N.

Scaled Speedup = N + (1 - N ) s’

Paradigmas Programacion Paralela

Agregar una capa de lenguaje Paralelo encima de un lenguaje secuencial existente

La programación paralela tiene dos capas:
1.-La capa inferior contiene el núcleo del cómputo, donde un proceso manipula su parte de los datos para producir su parte del resultado.
2.-La capa superior controla la creación y sincronización de los procesos y la partición de los datos entre los procesos.
El compilador sería responsable de traducir estas dos capas del programa paralelo en código listo para su ejecución sobre una computadora paralela.

Definir totalmente un nuevo lenguaje paralelo así como su compilador

Consiste en desarrollar un lenguaje de programación desde cero. El lenguaje de programación OCCAM (desarrollado por el Inglés David May) es un ejemplo famoso de este enfoque. Cuenta con una sintaxis totalmente diferente de los lenguajes tradicionales, este lenguaje soporta tanto la ejecución de procesos en paralelo como secuenciales, así como la comunicación y la sincronización entre ellos.

Una desventaja de este enfoque es el hecho de que al agregar instrucciones paralelas a un lenguaje de programación existente o crear por completo un nuevo lenguaje de programación paralelo requiere el desarrollo de nuevos compiladores. El desarrollo de un compilador nuevo de alta calidad normalmente lleva años de trabajo.

Algunos lenguajes paralelos, tales como C*, no fueron adoptados como estándar. En esta situación muchos vendedores en competencia decidieron no proporcionar compiladores para el lenguaje en sus máquinas. Cuando esto pasa, la portabilidad de códigos se encuentra severamente en peligro.

Arquitecturas Paralelas

SISD (Single Instruction, Single Data)

Este es el modelo tradicional de computación secuencial donde una unidad de procesamiento recibe una sola secuencia de instrucciones que operan en una secuencia de datos.

Se refiere a las computadoras convencionales de Von Neuman. Ejemplo: PC’s.

En la categoría SISD están la gran mayoría de las computadoras existentes. Son equipos con un solo procesador que trabaja sobre un solo dato a la vez. A estos equipos se les llama también computadoras secuenciales.

SIMD (Single Instruction, Single Data)

A diferencia de SISD, en este caso se tienen múltiples procesadores que sincronizadamente ejecutan la misma secuencia de instrucciones, pero en diferentes datos.

El tipo de memoria que estos sistemas utilizan es distribuida.

Arreglo de procesadores. Cada procesador sigue el mismo conjunto de instrucciones; diferentes elementos de información son asignados a cada procesador. Típicamente tienen miles procesadores simples. Son utilizadas en redes neuronales.

Las computadoras SIMD tienen una sola unidad de control y múltiples unidades funcionales. La unidad de control se encarga de enviar la misma instrucción a todas las unidades funcionales. Cada unidad funcional trabaja sobre datos diferentes. Estos equipos son de propósito específico, es decir, son apropiados para ciertas aplicaciones particulares, como por ejemplo el procesamiento de imágenes.

Un ejemplo sería un conjunto de equipos que trata de factorizar un número primo muy grande utilizando diferentes algoritmos.

MIMD (Multiple Instruction, Multiple Data)

Múltiples computadoras y multiprocesadores. Las piezas de código distribuidas entre los procesadores. Los procesadores pueden ejecutar la misma o instrucción o diferentes instrucciones. Se puede decir que MIMD es un super conjunto de SIMD.

Diferentes elementos de información se asignan a diferentes procesadores. Pueden tener memoria distribuida o compartida.

Cada procesador MIMD corre casi independientemente de los otros.

Las computadoras MIMD pueden ser utilizadas en aplicaciones con información en paralelo o con tareas en paralelo.

En la categoría MIMD están los equipos con varios procesadores completos. Cada procesador tiene su propia unidad de control y su propia unidad funcional. Esta categoría incluye varios subgrupos: Equipos de memoria compartida, equipos de memoria distribuida y redes de computadores. Los equipos MIMD son de propósito general.

MISD (Multiple Instruction, Single Data)

Varias unidades funcionales ejecutan diferentes operaciones sobre el mismo conjunto de datos.

• Las arquitecturas de tipo pipeline pertenecen a esta clasificación

• aunque no puramente, ya que pueden modificar los datos sobre los que operan.

• Systolic arrays, FPGA celulares.

• También pertenecen los computadores tolerantes a fallos que utilizan ejecución redundante para detectar y enmascarar errores.

• No existen otras implementaciones específicas.

• Los modelos MIMD y SIMD son más apropiados para la aplicación del paralelismo tanto a nivel de datos como de control.

Procesadores Vectoriales

Orientados a ejecutar eficientemente algoritmos numéricos sobre estructuras regulares de un gran número de elementos

Incluyen en su repertorio de instrucciones, instrucciones capaces de procesar vectores, aparece un nuevo tipo de dato “vector”.

Cada vez que una instrucción es ejecutada, se ejecuta idealmente sobre todos los componentes del vector Las operaciones sobre vectores pueden realizarse más rápido que una secuencia de operaciones escalares sobre el mismo número de elementos.

Es necesario realizar una selección de aplicaciones, datos y compiladores

Arreglo Sistolico

Un arreglo sistólico es un conjunto de procesadores dispuestos de una manera regular (por lo general rectangular) donde los datos fluyen sincrónicamente a través del arreglo entre sus vecinos.

Cada procesador toma en cada paso toma datos de sus vecinos (por lo general Norte y Oeste), los procesa y se los entrega a sus procesadores vecinos (por lo general Sur y Este).

Arquitectura Multiprocesador memoria compartida

UMA = Uniform Memory Access

– Acceso uniforme (todos los procesadores acceden a la memoria en el mismo tiempo).

– Multiprocesadores simétricos (SMP).

– Pocos procesadores (32, 64, 128, por problemas de ancho de banda del canal de acceso).

NUMA = Non-Uniform Memory Access.

– Colección de memorias separadas que forman un espacio de memoria direccionable.

– Algunos accesos a memoria son más rápidos que otros, como consecuencia de la disposición física de las  memorias (distribuidas físicamente).

– Multiprocesadores masivamente paralelos (MPP).

Multicomputadores

La principal característica de los multicomputadores es que los procesadores, al más bajo nivel, ya no pueden compartir datos a través de loads/stores, sino que lo tienen que hacer por medio de mensajes. Es por eso por lo que en este tipo de sistemas no hay problemas de coherencia de caché ni de consistencia de memoria. Aquí, la sincronización se hace explícita con los mensajes, tal y como muestra la figura 40, con primitivas estilo send y receive. En el send se especifíca el buffer a enviar y a quién se envía. Por el otro lado, el receive debe especificar el buffer de recepción y de quién lo recibe. Los buffer del send y del receive están en espacios de direcciones diferentes, suponiendo que son procesos diferentes. Opcionalmente, también se puede especificar una etiqueta o tag al mensaje, para recibir un mensaje concreto de un procesador concreto, cumpliéndose la matching rule.