martes, 18 de junio de 2013

Computación Paralela

 Computación Paralela

• Tradicionalmente, los programas han sido escritos para cómputo secuencial  (serial):
              o Para ser ejecutados en un único computador que posee un único CPU.
              o Los problemas son resueltos por una serie de instrucciones ejecutada una después de la otra por                                    
                el CPU. Sólo una instrucción puede ser ejecutada en un instante de tiempo.

• La computación paralela es el uso simultáneo de múltiples recursos computacionales para resolver un problema computacional.

• Los recursos computacionales pueden incluir:

              o Un único computador con múltiples procesadores
              o Un número arbitrario de computadores conectados por una red
              o Una combinación de ambos.

• El problema computacional posee características tales como:

              o Ser particionado en partes discretas de trabajo que pueden ser resultas simultáneamente
              o Ejecutar múltiples instrucciones del programa en cualquier instante de  tiempo
              o Ser resuelto en un menor tiempo con múltiples recursos computacionales que con un único  
                 recurso computacional.
• Tradicionalmente, la computación paralela ha sido motivada por simulaciones numéricas de sistemas complejos, tales como:

              o Modelaje de clima
              o Reacciones químicas y nucleares
              o Bioinformática y genoma humano
              o Geología y Sísmica
              o Petróleo
              o Biomedicina
              o Manufactura

• En la actualidad, aplicaciones comerciales requieren el desarrollo de computadores más rápidos. Estas aplicaciones requieren el procesamiento de grandes cantidades de datos de diferentes maneras. Ejemplos: 

             o Base de datos paralelas, minería de datos 
             o Exploración de crudo 
             o Servicios de negocios basados en la WEB 
             o Diagnóstico asistido por computador 
             o Computación gráfica

Arquitectura de Von Neumann 

• Un computador de Von Neumann usa el concepto de programa-almacenamiento. El CPU ejecuta un programa que específica una secuencia de operaciones de  lectura y escritura en la memoria.


• Diseño Básico:

               o Memoria es usada para almacenar el programa y las instrucciones sobre los datos
               o Instrucciones del Programa son datos codificados que le dice al computador que hacer
               o Los datos es simplemente información a ser usada por el programa
               o La unidad de procesamiento central (CPU) obtiene instrucciones y/o datos de la memoria,        
                  decodifica las instrucciones y secuencialmente ejecuta éstas.

Taxonomía de Flynn 

• Existen diferentes maneras para clasificar los computadores paralelos. La clasificación más usada desde 1966 es llamada taxonomía de Flynn.
• La taxonomía de Flynn distingue la arquitectura computacional de los  multiprocesadores de acuerdo a como éstos pueden ser clasificados a través de  dimensiones independientes de Instrucciones y Datos. Cada una de estas  dimensiones puede tener sólo uno de dos posibles estados: Single o Multiple.
• La siguiente matriz define las cuatro posibles clasificaciones de acuerdo a Flynn.









Single Instruction, Single Data (SISD):

• Un computador serial (no-paralelo)
• Single instruction: Sólo un flujo de instrucción está actuando en el CPU durante cualquier ciclo de reloj
• Single data: Sólo un flujo de dato está siendo usado como entrada durante cualquier ciclo de reloj
• Ejecución Determínistica
• Ejemplos: muchos PCs y workstations de un sólo CPU




Single Instruction, Multiple Data (SIMD):

• Un tipo de computador paralelo
• Single instruction: Todas las unidades de procesamiento ejecutan la misma instrucción en cualquier ciclo de reloj
• Multiple data: Cada unidad de procesamiento puede operar en datos diferentes
• Conveniente para problemas caracterizados por un alto grado de regularidad, tal como procesamiento de imágenes
• Dos variedades: Arreglo de Procesadores y Vectorial
• Ejemplos:

          o Arreglo de Procesadores: Connection Machine CM-2, Maspar MP-1, MP-2
          o Vectorial: IBM 9000, Cray C90, Fujitsu VP, NEC SX-2, Hitachi S820



Multiple Instruction, Single Data (MISD):

• Pocas clases de este tipo de computadores
• Algunos ejemplos:
            o Filtros de múltiple frecuencia operando en una única señal
            o Múltiples algoritmos de criptografía actuando en un mensaje codificado.

Multiple Instruction, Multiple Data (MIMD):

• Actualmente, el tipo más común de computador paralelo
• Multiple Instruction: cada procesador puede ejecutar un flujo de instrucción  diferente
• Multiple Data: cada procesador puede estar trabajando con un flujo de datos diferentes
• Ejemplos: supercomputadores actuales, redes de computadoras "grids", multiprocesadores SMP - incluyendo algunos tipos de PCs.



Arquitectura de la Memoria en Computadores Paralelos

Memoria Compartida (Shared Memory) 

Características generales:

• Computadores de memoria compartida tienen en común la capacidad que todos los procesadores pueden acceder a la memoria como un espacio de direccionamiento global.



• Múltiples procesadores operan independientemente pero comparten los mismos recursos de memoria.
• Cambios en una localización de memoria realizados por un procesador son visibles a todos los otros procesadores.
• La sincronización es obtenida controlando la escritura y lectura a la memoria.
• Las máquinas de memoria compartida pueden ser divididas en dos clases principales basadas en los tiempos de acceso a memoria: UMA y NUMA.

Acceso Uniforme a Memoria (UMA):

• Representadas por multiprocesadores simétricos ( Symmetric Multiprocessor machines, SMP)
• Procesadores idénticos
• Tiempos de acceso igual a la memoria
• Algunas veces llamadas CC-UMA - Cache Coherent UMA. Coherencia de cache significa que si un procesador actualiza una posición en la memoria compartida, todos los otros procesadores conocen acerca de la actualización. La coherencia de cache es a nivel de hardware.

Acceso no Uniforme a Memoria (NUMA):

• Enlazando físicamente dos o más SMPs
• Un SMP puede directamente acceder a la memoria de otro SMP
• No todos los procesadores tienen igual tiempo de acceso a toda la memoria
• El acceso a la memoria es lento
• Si la coherencia de cache es mantenida, son llamados CC-NUMA - Cache Coherent NUMA

Ventajas:

• El espacio de direccionamiento global provee una facilidad de programación al usuario
• El intercambio de datos entre las tareas es rápido y uniforme debido a la proximidad de la memoria a los CPUs

Desventajas:

• La desventaja primaria es la pérdida de escalabilidad entre la memoria y CPUs. Agregar CPUs puede geométricamente aumentar el tráfico en la vía memoría compartida-CPU, y para sistemas con coherencia de cache, geométricamente aumenta el tráfico asociado con la administración de cache/memoria.
• El programador es el responsable para construir la sincronización que asegura un correcto acceso a la memoria global.
• Es costoso diseñar y producir máquinas de memoria compartida con un gran número de procesadores.

Memoria Distribuida (Distributed Memory) 

Características Generales:

• Los sistemas de memoria distribuida requieren una red de comunicación para conectar la memoria de los procesadores.

• Múltiples procesadores operan independientemente pero cada uno tiene su propia memoria
• La data es compartida a través de una red de comunicación usando pases de mensajes
• El usuario es el responsable de la sincronización usando pase de mensajes

• Ventajas

         • La memoria es escalable al número de procesadores. Un aumento de los procesadores, el tamaño
           de la memoria y el ancho de banda aumenta
         • Cada procesador puede rápidamente acceder a su propia memoria sin interferencia

• Desventajas

          • Dificultad para asignar estructuras de datos existentes a esta organización de memoria
          • El usuario es el responsable para enviar y recibir data a través de los procesadores

• Ejemplos:

          • nCUBE Hypercube
          • Intel Hypercube
          • TMC CM-5
          • IBM SP1, SP2
          • Intel Paragon

Memoria Compartida-Distribuida

• Memoria Distribuida
             • MPP - Massively Parallel Processor

• Memoria Compartida
             • SMP - Symmetric Multiprocessor
                                  • Procesadores idénticos
                                  • Acceso igual a la memoria
                                  • Algunas veces llamado UMA - Uniform Memory Access
                                  • o CC-UMA – Coherencia de Cache UMA
                                  • Coherencia de Cache significa que si un procesador actualiza una posición en
                                     la memoria compartida, todos los otros procesadores conocen acerca de la
                                     actualización.

              • NUMA - Non-Uniform Memory Access
                               • Algunas veces llamado CC-NUMA - Coherencia de Cache NUMA
                               • A menudo hecho enlazando dos o más SMPs
                               • Un SMP puede directamente acceder la memoria de otro SMP
                               • No todos los procesadores tienen igual tiempo de acceso a toda la memoria
                               • El acceso de memoria a través del enlace es lento
• Combinaciones
               • Múltiples SMPs son conectados por una red
                              • Los Procesadores dentro de un SMP se comunican vía memoria
                              • Requieren pase de mensajes entre SMPs
                              • Un SMP no puede directamente acceder a la memoria de otro SMP
               • Múltiples procesadores de memoria distribuida conectados a una gran  memoria compartida
                               • La transferencia de memoria local a memoria compartida es  transparente al usuario
                               • Diseño del futuro: con diferentes procesadores y su memoria local alrededor de una
                                 gran memoria compartida en una simple tarjeta.

Paradigmas de la Programación en Paralelo

Existen muchos métodos de programación en computadores paralelos. Lo más usados son pase de mensajes, paralelismo de datos y hebras:

• Pase de mensajes – el usuario hace llamadas a bibliotecas para explícitamente compartir información entre los procesadores.
• Paralelismo de datos – un particionamiento de la data determina el paralelismo
• Memoria compartida - múltiples procesos comparten un espacio de memoria común
• Threads (hebras, hilos)- un proceso teniendo múltiples (concurrentes) trayectorias de ejecución
• Modelo combinado – compuesto de dos o más de los presentados anteriormente

No hay comentarios:

Publicar un comentario