jueves, 25 de febrero de 2016

Ley de Gustafson



La ley de Gustafson (1988) viene a compensar el pesimismo dejado por la ley de Amdahl. Ésta se refería a problemas con volumen de cálculo fijo en que se aumenta el número de procesadores. Sin embargo, en la práctica, el volumen del problema no es independiente del número de procesadores, ya que con mayor número de procesadores se pueden abordar problemas de mayores dimensiones. Por ello, la ley de Gustafson se refiere al crecimiento del volumen de cálculo necesario para resolver un problema. Cuando el volumen del problema crece, lo hace sólo en su parte paralela, no en su parte secuencial. Ello hace que el cuello de botella secuencial tienda a cero cuando el volumen  del problema aumenta.
La razón de que cierto tipo de problemas adquieran gran volumen de calulo es la disminución del tamaño de la malla de cálculo o también el aumento la extensión espacio-temporal del problema. Esto hace que el número de puntos aumente de forma cúbica respecto al grado  de disminución en la malla, si el problema es tridimensional. Hay muchos problemas en que, además de las tres dimensiones del espacio, también interviene el tiempo, por lo que el  aumento del volumen de cálculo es todavía mayor. Evidentemente, esto afecta, en general, a la parte paralelizable del problema y no a su parte secuencial, o al menos no en la misma medida. Si suponemos que el número de procesadores crece indefinidamente de la misma forma que las dimensiones del problema tendremos que

Siendo s y p, respectivamente, las partes secuencial y paralela del problema antes de ser aumentado en relación al número de procesadores (por ejemplo, incrementando el número de puntos de la malla).

Con estas premisas, podremos calcular ahora la ganancia de velocidad para esta nueva situación (la parte paralela del problema ha crecido en la misma proporción que el número de procesadores). Para calcular la ganancia de velocidad supondremos que el tiempo que se tardaría en ejecutar el programa (ya incrementado) en un monoprocesador  es:

Y en un sistema paralelo seria:

Donde N es el numero de procesadores; por tanto, la ganacia en velocidad vendrá dada por:

Que teniendo en cuenta la definición de la fracción no paralelizable dada por:

Se podrá escribir como:

Podría pensarse que hay una aparente contradicción entre las leyes de Amdahl y Gustafson. Esto no es  así  debido a  que las  premisas de  ambas leyes son distintas: la  ley de  Amdahl  se refiere a procesos con un volumen de calculo fijo mientras que la ley de Gustafson se refiere a problemas cuyo volumen de calculo puede aumentar según el numero de procesadores (esto se suele denominar escalado del problema).



Referencias:

viernes, 12 de febrero de 2016

Programación de computadoras paralelas

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



La mayoría de código que existe en la actualidad es correcto y sirve para resolver unos problemas dados. Este código pude ser ejecutado en varios multiprocesadores no necesita cambiar en su mayoría, tan solo añadirle algunas características de sincronización. De hecho, la mayoría de los errores en programación concurrente aparecen en la sincronización o partición de los datos. Por lo tanto, una posible solución es usar un pequeño lenguaje-compilador para expresar la estructura paralela del programa, dejando que el resto del código se exprese en un lenguaje convencional (Fortran o C).

Esta solución tiene sus inconvenientes. Uno de los mas importantes se refiere a la depuración de programas, ya que debido a la existencia de un pre-procesador es difícil detectar donde esta el fallo cometido.


Definir totalmente un nuevo lenguaje paralelo asi como su compilador


Se trata sin lugar a dudas de la mas radical de las cuatro vías mencionadas. Esta es la mas cara y la que exige mas labor de desarrollo. Como contrapartida, la mayoría de los problemas que se han expuesto hasta ahora se pueden solucionar mediante un diseño adecuado del sistema lenguaje/compilador.

Los avances realizados hasta la fecha se han orientado en el área de los lenguajes funcionales, como FP o SISAL. Las principales características de diseño de estos lenguajes son mejora la claridad de la concurrencia, sin requerir que el programador maneje la sincronización, así como permitir que no dependan de la arquitectura objeto sobre la que se van a implementar.

Otra de las grandes ventajas aparece desde el punto de vista de la depuración de programas. Por contra de los mayores inconvenientes descansan en la construcción del compilador. Este requiere técnicas muy sofisticadas para realizar con eficacia las funciones que tiene encomendadas, como particionar, mapear y sincronizar el programa. En la actualidad se tienen problemas debido a que estas implementaciones requieren grandes cantidades de memoria.

Principales lenguajes de programación paralelos:


  • HWLOC, Portable Hardware Locality, http://www.open-mpi.org/projects/hwloc/
  • CUDA, http://www.nvidia.es/object/cuda home new es.html
  • TBB, Threading Building Blocks, http://www.threadingbuildingblocks.org/
  • PLASMA, Parallel Linear Algebra for Scalable Multi-core Architectures, http://icl.cs.utk.edu/plasma/ ForestGOMP, An OpenMP platform for hierarchical architectures, http://runtime.bordeaux.inria.fr/forestgomp/
  • UPC, Unified Parallel C, http://upc.gwu.edu/
  • OpenCL, The open standard for parallel programming of heterogeneous systems, http://www.khronos.org/opencl/


Referencias:
  • http://es.slideshare.net/neztooor7/presentacin-lenguajes-paralelos
  • el paralelismo. Una manera de mejorar la eficiencia de los ordenadores. Jose Ma. Carrasco y Fco. Jose Quiles Flor.


miércoles, 10 de febrero de 2016

Arquitecturas de computadoras paralelas


SISD 

Cuyas siglas significa Single Instruction, Single Data.

Se refiere a las computadoras convencionales de Von Neuman.
En esta categoría SISD se encuentran la gran mayoría de las computadoras existentes.



Características


  • 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.
  • Flujo único de instrucciones.
  • Flujo único de datos.
  • Corresponde al modelo estructural básico, con un procesador de instrucciones y un procesador de datos.
  • Tiene una única vía de acceso a la memoria principal.
  • 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.

 



  • Un procesador capaz de realizar acciones secuencialmente, controladas por un programa el cual se encuentra almacenado en una memoria conectada al procesador. 
  • Este hardware esta diseñado para dar soporte al procesamiento secuencial clásico, basado en el intercambio de datos entre memoria y registros del procesador, y la realización de operaciones aritméticas en ellos.
  • Algunas máquinas secuenciales “modernas” no corresponden estrictamente al modelo SISD. 
  • A partir de la introducción de los procesadores RISC se comenzó a utilizar varios conceptos de las arquitecturas paralelas, como pipelining, ejecución paralela de instrucciones no dependientes, prefetching de los datos, etc., para lograr un incremento en la cantidad de operaciones por ciclo de instrucción.


 SIMD

Cuyas siglas significa Single Instruction, Multiple Data.

Se lo conoce como un arreglo de procesadores.
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.


Características


• Estos sistemas tienen un único flujo de instrucciones que operan sobre múltiples flujos de datos. Como por ejemplo:

  • Máquinas vectoriales con hardware escalar.
  • Maquinas vectoriales con hardware vectorial.

• El procesamiento es sincrónico
• La ejecución de las instrucciones sigue siendo secuencial, es decir que todos los elementos realizan una misma instrucción pero sobre una gran cantidad de datos. Por este motivo existirá concurrencia de operación, es decir es el origen de la máquina paralela.
• Diferentes elementos de información son asignados a cada procesador.
• Utiliza memoria distribuida.
• Tiene una sola unidad de control y 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.



MISD

 

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.
•Modelo de múltiple instrucción, un solo dato (MISD, del inglés Multiple Instruction Single Data).
•Modelo teórico de una maquina que realiza un número de operaciones diferentes con el mismo dato.
• También pertenecen los computadoras 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.


MIMD

Cuyas siglas significa Multiple Instruction, Multiple Data.

Es un sistema con un flujo de múltiples instrucciones que operan sobre múltiples datos.
Estos sistemas empezaron a utilizarse a principios de los 80.
Se las conoce como múltiples computadoras y multiprocesadores. Se puede decir que MIMD es un súper conjunto de SIMD. 



Características

  • Son sistemas con memoria compartida que permite ejecutar varios procesos simultáneamente (sistema multiprocesador)
  • La diferencia con estos sistemas es que MIMD es asíncrono.
  • No tiene un reloj central.
  • Cuando las unidades de proceso reciben datos de una memoria no compartida estos sistemas reciben el nombre de Múltiple SISD (MSISD).
  • Los procesadores pueden ejecutar la misma o instrucción o diferentes instrucciones y tener sus propios datos
  • 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.
  • Pueden ser utilizadas en aplicaciones con información en paralelo o con tareas en paralelo.
  • Cada procesador tiene su propia unidad de control y su propia unidad funcional. 


Los sistemas MIMD se clasifican en: 
  • Sistemas de Memoria Compartida.
  • Sistemas de Memoria Distribuida.
  • Sistemas de Memoria Compartida Distribuida.





Sistemas de Memoria Compartida.



En este tipo de sistemas cada procesador tiene acceso a toda la memoria, es decir hay un espacio de direccionamiento compartido. 
Las computadoras MIMD con memoria compartida son sistemas conocidos como de multiprocesamiento simétrico (SMP) donde múltiples procesadores comparten un mismo sistema operativo y memoria.

Ejemplos son: SGI/Cray Power Challenge, SGI/Cray C90, SGI/Onyx, ENCORE, MULTIMAX, SEQUENT y BALANCE, entre otras.

 Multiprocesador


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. 

 Arquitectura del procesador AMD Opteron Quad Core

Las características principales a nivel de arquitectura de estos procesadores son: 4 núcleos independientes (con frecuencia variable e independiente en cada núcleo). Cache L1 + L2 (512 KB) independientes en cada núcleo. Cache L3 de 6 MB compartida entre los 4 núcleos. Controladora de memoria DDR2 independiente del bus principal para un acceso más rápido a la memoria principal. Sistema Hyper Transport que sustituye a los buses antiguos y permite la conexión de hasta 3 dispositivos con un mayor ancho de banda (hasta 8GB/s). Se puede observar que, aunque la memoria cache de nivel 1 y 2 son independientes en cada procesador, la memoria cache de nivel 3 ya aparece como compartida, como una manera de reducir la latencia de la memoria compartida principal.

Procesador Vectorial

El cálculo de cada resultado es independiente de los cálculos de los resultados anteriores, permitiendo un gran nivel de segmentación sin generar ningún riesgo por dependencia de datos. Los riesgos por dependencias de datos los ha resuelto el compilador o el programador que ha decidido que sea una operación vectorial.
Una simple instrucción vectorial especifica una gran cantidad de trabajo (equivalente a ejecutar un bucle completo). El requerimiento de anchura de banda de las instrucciones es reducido y el cuello de botella de Flynn se reduce considerablemente.
Las instrucciones vectoriales que acceden a memoria tienen un patrón de acceso conocido. Si los elementos del vector son todos adyacentes, extraer el vector de un conjunto de bancos de memoria entrelazados funciona muy bien. Además se obtiene un alto rendimiento en la jerarquía de memoria.
Como se sustituye un bucle completo por una instrucción vectorial cuyo comportamiento está predeterminado, los riesgos de control que normalmente podían surgir del salto del bucle son inexistentes.

Por todas las razones anteriores, las operaciones vectoriales pueden hacerse más rápidas que una secuencia de operaciones escalares sobre el mismo número de elementos de datos.

Hay dos tipos principales de arquitecturas vectoriales:
  1. Máquina vectorial con registros: Responden al modelo de ejecución registro– registro (excepto en las operaciones de carga y almacenamiento) c Son el equivalente vectorial de una arquitectura escalar de carga / almacenamiento. Son las que han tenido mayor éxito, por necesitar menor ancho de banda que las de memoria – memoria. De este tipo son: las máquinas de Cray Research (CRAY-1, CRAY-2, X-MP e Y-MP), los supercomputadoras japoneses (NEC SX/2, Fujitsu VP200 y el Hitachi S820) y los minisupercomputadoras (Convex C-1 y C-2).
  2. Máquina vectorial memoria – memoria:  Responden al modelo de ejecución memoria – memoria. Las primeras máquinas vectoriales fueron de este tipo (las máquinas de CDC). No han tenido éxito (Demasiado gasto de tiempo en el arranque).

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

Ejemplos:      procesamiento digital de señales,
                        procesamiento digital de imágenes,
                        multiplicación de matrices,
                        evaluación de polinomios
                        etc.
Rápidos en estas operaciones, sin embargo están limitados a estas aplicaciones, para otras operaciones no son prácticos.

 Multicomputadoras

 La característica más importante de estos sistemas es que tienen la memoria distribuida. Esta arquitectura también es conocida como arquitectura basada en el paso de mensajes, ya que los procesos deben realizar comunicaciones (mensajes) a través de la red de interconexión para poder compartir datos. Estas máquinas, por consiguiente, no están limitadas por el ancho de banda de memoria, sino más bien por el de la red de interconexión.

Son sistemas grandes, en comparación con un sistema CMP, pero que no suelen tener un número muy elevado de CPU debido al coste económico que supondría mantener una red de interconexión de altas prestaciones. En general, son sistemas difícilmente escalables. Las características principales de los sistemas MPP son:
  • Hardware específico para el desarrollo de algun proceso concreto.
  • La red de interconexión que incorporan es propietaria, especialmente diseñada, con muy baja latencia y un ancho de banda elevado.
  • Suelen venir con software propietario y librerías para gestionar la comunicación.
  • Tienen una capacidad de almacenamiento de entrada/salida elevada, ya que se suelen utilizar para trabajar con grandes volúmenes de datos que se han de procesar y almacenar.
  • Tienen mecanismos de tolerancia de fallos del hardware.



Fuentes consultadas:


  • Multiprocesadores y  multicomputadores. Disponible en: https://www.exabyteinformatica.com/uoc/Informatica/Arquitecturas_de_computadores_avanzadas/Arquitecturas_de_computadores_avanzadas_(Modulo_2).pdf
  • Computadores vectoriales. Disponible en: http://www.uhu.es/josem.bravo/AeIC/Tema4.pdf
  • Sistemas multiprocesadores. Disponible en: http://m0640064.blogspot.mx/2009/07/sistemas-multiprocesadores-un.html
  • Computacion de alta performance. Disponible en: http://www.fing.edu.uy/inco/cursos/hpc/material/clases/Clase2-2010.pdf
  • SISD, SIMD, MIMD. Disponible en: http://arqordenadores.wiki-site.com/index.php/SISD,_SIMD,_MIMD