Arquitecturas Paralelas (ejemplos)

SISD (Single Instruction, Single Data)

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, Multiple Data)

Arreglo de procesadores. Cada procesador sigue el mismo conjunto de instrucciones; diferentes elementos de información son asignados a cada procesador. Utilizan memoria distribuida. 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.

Existe controversia acerca de si realmente existen equipos de tipo MISD. Hay quienes argumentan que estos equipos no existen. Otras personas consideran que un grupo de equipos que trabaja sobre un solo dato se puede considerar como un sistema de tipo MISD.

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

Ejemplos:

o Thinking Machines CM-2

o MassPar computers

o Procesador MMX

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.

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.

Ejemplos:

o SGI/Cray Power Challenge Array

o SGI/Cray Origin-2000

o HP/Convex SPP-2000

MISD (Multiple Instruction, Single Data)

No son usadas, y no son significativas.

 Fuente de consulta: http://rubmarin.galeon.com/sisd.htm

Practica 8

Paso de mensajes con Python

El paso de mensajes es una técnica empleada en programación concurrente para aportar sincronización entre procesos y permitir la exclusión mutua. Define la sintaxis y la semántica de las funciones contenidas en una biblioteca de paso de mensajes diseñada para ser usada en programas que exploten la existencia de múltiples procesadores.

Los elementos principales que intervienen en el paso de mensajes son el proceso que envía, el que recibe y el mensaje.

MPI para Python 

MPI , [-MPI utilizando] [MPI-ref] la Message Passing Interface, es un sistema de paso de mensajes estandarizados y portátil diseñado para funcionar en una amplia variedad de computadoras paralelas. La norma define la sintaxis y la semántica de las rutinas de biblioteca y permite a los usuarios escribir programas portables en los principales lenguajes de programación científica (Fortran,Python, C o C ++).

Desde su lanzamiento, la especificación MPI [MPI-STD1] [MPI-STD2] se ha convertido en el principal estándar para las bibliotecas de paso de mensajes para computadoras paralelas. Implementaciones están disponibles de vendedores de ordenadores de alto rendimiento y de proyectos de código abierto bien conocidos como MPICH [MPI-mpich] , abierto MPI [MPI-openmpi] o LAM [MPI-lammpi] .

Para programar aplicaciones con MPI, se utiliza un runtime llamado OpenMPI, el cual es la versión libre y que además funciona con el lenguaje de programación C, en entorno Unix únicamente. Aunque existe un binding entre Python y MPI, llamado PyMPI, con el cual podemos utilizar las bondades de un lenguaje dinámico en conjunto con la programación de aplicaciones en paralelo.

Hay por lo menos cinco intentos conocidos de aplicar MPI para Python: mpi4py, PyPar, PyMPI, MYMPI, y en el submódulo ScientificPython MPI.

PyMPI es notable porque se trata de una variante de python intérprete multi-nodo de la aplicación de la propia intérprete, más que el código se ejecuta el intérprete. Implementa la mayor parte de la especificación MPI y trabaja automáticamente con el código compilado que necesita para hacer llamadas MPI.

PyPar, MYMPI, y el módulo ScientificPython están diseñados para trabajar como un típico módulo realizando una declaración de importación.

Hacen el trabajo del codificador para decidir cuándo y dónde pertenece la llamada a MPI_Init.

Ejemplos de CODIGO

Spawn ()

Send ()

from mpi4py import MPI

 import numpy

comm = MPI.COMM_WORLD

rank = comm.Get_rank()

# passing MPI datatypes explicitly

if rank == 0:

data = numpy.arange(1000, dtype='i')

 comm.Send([data, MPI.INT], dest=1, tag=77)

elif rank == 1:

data = numpy.empty(1000, dtype='i')

comm.Recv([data, MPI.INT], source=0, tag=77)

# automatic MPI datatype discovery if rank == 0:

data = numpy.arange(100, dtype=numpy.float64)

comm.Send(data, dest=1, tag=13)

elif rank == 1:

data = numpy.empty(100, dtype=numpy.float64)

 comm.Recv(data, source=0, tag=13)

Recv()

from mpi4py import MPI

import numpy

comm = MPI.COMM_WORLD

 rank = comm.Get_rank()

# passing MPI datatypes explicitly

 if rank == 0:

data = numpy.arange(1000, dtype='i')

 comm.Send([data, MPI.INT], dest=1, tag=77)

elif rank == 1:

data = numpy.empty(1000, dtype='i')

 comm.Recv([data, MPI.INT], source=0, tag=77)

# automatic MPI datatype discovery if rank == 0:

data = numpy.arange(100, dtype=numpy.float64)

Broadcast ()

from mpi4py import MPI

comm = MPI.COMM_WORLD

rank = comm.Get_rank()

if rank == 0:

data = {'key1' : [7, 2.72, 2+3j],

'key2' : ( 'abc', 'xyz')}

else:

data = None

data = comm.bcast(data, root=0)

Scatter ()

from mpi4py import MPI

comm = MPI.COMM_WORLD size = comm.Get_size()

rank = comm.Get_rank()

if rank == 0:

data = [(i+1)**2 for i in range(size)]

else:

data = None

data = comm.scatter(data, root=0) assert data == (rank+1)**2

Gather ()

from mpi4py import MPI

comm = MPI.COMM_WORLD size = comm.Get_size()

rank = comm.Get_rank()

data = (rank+1)**2

data = comm.gather(data, root=0) if rank == 0:

for i in range(size):

assert data[i] == (i+1)**2

else:

assert data is None

Fuente

https://pythonhosted.org/mpi4py/usrman/index.html

https://mpi4py.scipy.org/docs/usrman/tutorial.html

http://pythonhosted.org/mpi4py/

Ley de Gustafson

Antecedentes

La ley de Amdahl es un modelo matemático que describe la relación entre la aceleración esperada de la implementación paralela de un algoritmo y la implementación serial del mismo algoritmo

Según demuestra matemáticamente, llegados a un punto el rendimiento de un sistema no está relacionado con el número de procesadores instalados, sino con la eficiencia de los algoritmos empleados. 

En 1988 John Gustafson cuestionó la validez del argumento de Amdahl. En ese tiempo este investigador usaba supercomputadores en los laboratorios de alta energía Sandia Labs, y descubrió que los tiempos que medía no calzaban con lo predicho por la Ley de Amdahl.

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).

Ley de Gustafson

La ley de Gustafson (también conocida como ley de Gustafson-Barsis) es una ley en ciencia de la computación 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 mejora 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.

Donde P es el número de procesadores, S es el speedup, y   la parte no paralelizable del proceso.

La ley de Gustafson aborda las limitaciones de la Ley de Amdahl, la cual no escala la disponibilidad del poder de cómputo a medida que el número de máquinas aumenta. La ley de Gustafson propone que los programadores establezcan el tamaño de los problemas para utilizar el equipamiento disponible en su solución en un tiempo práctico. Por consiguiente, si existe equipamiento más rápido disponible, mayores problemas se pondrán resolver en el mismo tiempo.

Fuentes de consulta.

https://es.wikipedia.org/wiki/Ley_de_Gustafson

http://www.lnds.net/blog/2009/09/el-problema-de-paralelizar-2.html

http://sistemasod.blogspot.mx/2012/10/ley-de-amdahl_17.html

Tarea número 2

 PROGRAMACIÓN PARALELA EN DOS CAPAS.

Imaginemos que la programación paralela tiene dos capas: 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, mientras que 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.

Dos ejemplos de este enfoque son:

CODE (Computationally Oriented Display Environment): es un lenguaje de programación visual el cual permite al usuario convertir programa secuenciales a paralelos.

HENCE (Heterogeneous Network Computing Environment): es un programa diseñado para asistir al usuario en el desarrollo de programas paralelos que funcionen en una red de computadoras.

Este enfoque requiere que el programador aprenda y use un nuevo sistema de programación paralelo, lo cual puede ser la razón por la que no ha captado mucha atención en la comunidad de programación paralela.

 CREACIÓN DE UN LENGUAJE PARALELO

Tal como suena, la creación de un lenguaje paralelo consiste en desarrollar un lenguaje de programación desde cero. El lenguaje de programación OCCAM (desarrollado por el Inglés David May).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 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.

Otra barrera para la adopción de nuevos lenguajes de programación es la resistencia del usuario. Cuando nuevas construcciones paralelas se agregan a un lenguaje de programación, los programadores deben aprender cómo usar estas nuevas construcciones. Muchos programadores están renuentes a tomar esta transición.

Fuentes de consulta

http://es.wikipedia.org/wiki/Computaci%C3%B3n_paralela

http://es.wikipedia.org/wiki/Occam_%28lenguaje_de_programaci%C3%B3n%29

https://www.blogger.com/blogger.g?blogID=6860943626991356751#editor/target=post;postID=7745528328264479416

Arquitecturas Paralelas

SISD (Single Instruction, Single Data)

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, Multiple Data)

Arreglo de procesadores. Cada procesador sigue el mismo conjunto de instrucciones; diferentes elementos de información son asignados a cada procesador. Utilizan memoria distribuida. 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.

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.

Ejemplos:

o SGI/Cray Power Challenge Array

o SGI/Cray Origin-2000

o HP/Convex SPP-2000

 

MISD (Multiple Instruction, Single Data)

No son usadas, y no son significativas.

Es un tipo de arquitectura computacional(particularmente de computación paralela) donde muchas unidades funcionales realizan diferentes operaciones en los mismos datos. Las arquitecturas segmentadas pertenecen a este tipo, aunque en un extremo se podría llegar a decir que los datos son diferentes después de ser procesados por cada etapa en el pipeline, con lo cual no entraría en esta categoría.

Las máquinas tolerantes a fallos ejecutan la misma instrucción redundantemente para detectar y corregir errores, utilizando task replication, son consideradas de este tipo. No existen muchos ejemplos de esta arquitecura dado que las técnicas más comunes de procesamiento de datos en paralelo suelen ser más apropiadas para MIMD y SIMD. Específicamente, facilitan el escalamiento y el uso de recursos computacionales mejor que MISD.

Procesador Vectorial

Las características principales de los procesadores vectoriales son:

·       La capacidad de aplicar una instrucción a un conjunto de datos, en otras palabras un vector, de una sola vez. Los procesadores vectoriales consiguen esto a través de las áreas en la memoria especialmente diseñadas llamadas registros vectoriales los cuales pueden ser llenados con las instrucciones vectoriales, devolviendo resultados mucho más rápidos que los tradicionales procesadores escalares.

·       Unidades de función profundamente encauzadas para alto rendimiento total, ciclos de reloj muy cortos.

·        Abundancia de registros vectoriales largos para alimentar las unidades de función y recibir los resultados.

·   Rutas de transferencia de datos de gran ancho de banda entre memoria y registros vectoriales.

Multiprocesador (UMA,COMA,NUMA) 

  

   Un multiprocesador puede verse como un computador paralelo compuesto por varios procesadores interconectados que comparten un mismo sistema de memoria.
Los sistemas multiprocesadores son arquitecturas MIMD con memoria compartida. Tienen un único espacio de direcciones para todos los procesadores y los mecanismos de comunicación se basan en el paso de mensajes desde el punto de vista del programador.
Dado que los multiprocesadores comparten diferentes módulos de memoria, pudiendo acceder a un mismo módulo varios procesadores, a los multiprocesadores también se les llama sistemas de memoria compartida.Dependiendo de la forma en que los procesadores comparten la memoria, se clasifican en sistemas multiprocesador UMA, NUMA y COMA.

Multicomputadoras

Los sistemas de memoria distribuida o multicomputadoras pueden ser de dos tipos básicos. El primer de ellos consta de un único computador con múltiples CPUs comunicadas por un bus de datos mientras que en el segundo se utilizan múltiples computadores, cada uno con su propio procesador, enlazados por una red de interconexión más o menos rápida.

Sobre los sistemas de multicomputadoras de memoria distribuida, se simula memorias compartidas. Se usan los mecanismos de comunicación y sincronización de sistemas multiprocesadores.

Un clúster es un tipo de arquitectura paralela distribuida que consiste de un conjunto de computadores independientes interconectados operando de forma conjunta como único recurso computacional sin embargo, cada computador puede utilizarse de forma independiente o separada.

En esta arquitectura, el computador paralelo es esencialmente una colección de procesadores secuenciales, cada uno con su propia memoria local, que pueden trabajar conjuntamente.

· Cada nodo tiene rápido acceso a su propia memoria y acceso a la memoria de otros nodos mediante una red de comunicaciones, habitualmente una red de comunicaciones de alta velocidad.

·  Los datos son intercambiados entre los nodos como mensajes a través de la red.

·Una red de ordenadores, especialmente si disponen de una interconexión de alta velocidad, puede ser vista como una multicomputadora de memoria distribuida y como tal ser utilizada para resolver problemas mediante computación paralela.

 Arreglo Sistolico

Una arquitectura y un paradigma aplicables a la computación en paralelo. Los algoritmos paralelos sistólicos exhiben un flujo direccional por el cual los datos se dividen y quedan en cola para pasar por iguales secuencias de procesamiento al moverse de un proceso al siguiente. La metáfora del flujo de sangre ha servido para caracterizar el flujo de datos a lo largo del proceso.

BIBLIOGRAFÍA

http://users.dcc.uchile.cl/~rbaeza/cursos/proyarq/choviedo/comp_uma_numa.html

http://itcv-arquitectura-de-computadoras.blogspot.mx/2014/11/44-sistemas-de-memoria-distribuida.html

http://www.oocities.org/ohcop/systolic.html

http://rubmarin.galeon.com/sisd.htm

http://arqui-g1.wikispaces.com/Procesadores+Vectoriales