1. Taxonomía de Flynn y Descomposición de Problemas PDF

Preview

Summary

Modulo 4 - lectura 1...

Description

Taxonomía de Flynn y Descomposición de Problemas

Algoritmos Concurrentes y Paralelos

1. La taxonomía de Flynn Una computadora paralela es un conjunto de procesadores que pueden trabajar de manera cooperativa para resolver un problema computacional. Esta definición es lo suficientemente amplia como para incluir supercomputadoras paralelas que tienen cientos o miles de procesadores, redes de estaciones de trabajo, estaciones de trabajo con múltiples procesadores y sistemas integrados. Las computadoras paralelas son interesantes porque ofrecen la posibilidad de concentrar los recursos computacionales, ya sean procesadores, memoria o ancho de banda, en problemas computacionales importantes. Michael Flynn propuso una clasificación de arquitecturas de computadora basada en el número de flujos de instrucciones (o control) concurrentes y en el flujo de datos usados para procesar la información. Esta clasificación es conocida en la actualidad como la taxonomía de Flynn. Figura 1: Taxonomía de Flynn

Fuente: elaboración propia.

Su importancia se debe a que este sistema de clasificación se ha usado como herramienta en el diseño de procesadores modernos y sus funcionalidades. Desde la proliferación de procesadores (CPU [en inglés, unidad central de procesamiento]) de multiprocesamiento, tanto el contexto de multiprogramación como el sistema de clasificación han evolucionado. El desafío del procesamiento paralelo radica en las CPU, en función de la cantidad de instrucciones y flujos de datos que se pueden procesar simultáneamente. Flynn definió cuatro clasificaciones que se basan en el

2

número de flujos de instrucciones (o control) concurrentes y en el flujo de datos disponibles en la arquitectura. Estas clasificaciones son: 

Single instruction stream, single data stream o SISD (una instrucción, un dato): una computadora SISD es una máquina con un solo procesador que es capaz de ejecutar una sola instrucción, por cuanto opera en un solo flujo de datos en cada ciclo de reloj. En la clasificación SISD, las instrucciones de la máquina se procesan de manera secuencial y las computadoras que adoptan este modelo se denominan popularmente computadoras secuenciales. La mayoría de las computadoras convencionales tienen arquitectura SISD. Todas las instrucciones y datos por procesar deben almacenarse en la memoria primaria. La velocidad de la CPU en el modelo SISD depende de la velocidad a la que la computadora puede transferir información internamente. Un claro ejemplo de esta arquitectura era el de las computadoras de escritorio, antes de que utilizaran procesadores con múltiples núcleos.



Single instruction stream, multiple data streams o SIMD (sistemas de instrucción única, datos múltiples): una computadora SIMD es una máquina multiprocesador capaz de ejecutar la misma instrucción en todos los procesadores, pero operando en diferentes flujos de datos en forma sincronizada. Las máquinas basadas en SIMD son adecuadas para la computación científica, ya que implican muchas operaciones vectoriales y matriciales. Para que la información se pueda pasar a todas las unidades de procesamiento, los elementos de datos organizados en vectores se pueden dividir en conjuntos múltiples (conjuntos N para sistemas N unidades de procesamiento) y cada unidad de procesamiento puede procesar un conjunto de datos. Los equipos que utilizaron esta arquitectura fueron los supercomputadores Cray. Una variante es la arquitectura single instruction, multiple threads o SIMT (instrucción única, subprocesos múltiples). Se trata de un modelo de ejecución utilizado en computación paralela donde la instrucción única, datos múltiples (SIMD) se combina con multihilo. Esta no es una clasificación distinta en la taxonomía de Flynn, es decir, es subconjunto de SIMD. Sin embargo, fabricantes de procesadores específicos (procesadores gráficos) comúnmente usan el término en sus materiales de marketing como si fuera una categoría distinta.

3



Multiple instruction streams, single data stream o MISD (sistemas de instrucción múltiple y datos únicos): respecto de la arquitectura MISD, hablamos de una máquina multiprocesador capaz de ejecutar diferentes instrucciones en diferentes unidades de procesamiento, pero operando en el mismo conjunto de datos. Así, por ejemplo: Z = sin(x) + cos(x) + tan(x), es decir que el sistema realiza diferentes operaciones en el mismo conjunto de datos. Las máquinas construidas con el modelo MISD no son útiles en la mayoría de las aplicaciones. Se construyen algunas máquinas de este tipo, aunque no están disponibles comercialmente. Ejemplos de su uso son las computadoras de control de vuelo del transbordador espacial y las usadas en la navegación aérea, donde es necesario contar con sistemas redundantes de respaldo.

Figura 2: Taxonomía de Flynn. Relación de unidades de procesamiento con el pool de instrucciones y el pool de datos

Fuente: elaboración propia.



Multiple instruction streams, multiple data streams o MIMD (sistemas de instrucción múltiple, datos múltiples): un sistema MIMD es una máquina multiprocesador que es capaz de ejecutar múltiples instrucciones en múltiples conjuntos de datos. Cada unidad de procesamiento en el modelo MIMD tiene instrucciones y flujos de datos diferentes; por lo tanto, las máquinas construidas con este modelo son capaces de cualquier tipo de aplicación. A diferencia de

4

las máquinas SIMD y MISD, las unidades de procesamiento en las máquinas MIMD funcionan de forma asíncrona. Las máquinas MIMD, según la forma en que las unidades de procesamiento se acoplan a la memoria principal, se subclasifican en las siguientes: o MIMD de memoria compartida (sistemas multiprocesadores estrechamente acoplados): todas las unidades de procesamiento están conectadas con una única memoria global y todas tienen acceso a ella. La comunicación entre las unidades de procesamiento se realiza a través de la memoria compartida y la modificación de los datos almacenados en la memoria global por una unidad de procesamiento es visible para todas las demás unidades de procesamiento. Ejemplos de sistemas representativos MIMD de memoria compartida son las máquinas Silicon Graphics y SMP de Sun IBM (multiprocesamiento simétrico). o MIMD de memoria distribuida (sistemas multiprocesadores con acoplamiento flexible): todas las unidades de procesamiento tienen una memoria local. La comunicación entre las unidades de procesamiento se realiza a través de la red de interconexión (el canal de comunicación entre procesos o IPC). La red que conecta las unidades de procesamiento puede configurarse para árbol, malla o de acuerdo con el requisito. La arquitectura MIMD de memoria compartida es más fácil de programar, pero es menos tolerante a las fallas y más difícil de extender con respecto al modelo MIMD de memoria distribuida. Los fallos en un MIMD de memoria compartida afectan a todo el sistema, mientras que no es el caso del modelo distribuido, en el que cada unidad de procesamiento puede aislarse fácilmente. Además, las arquitecturas MIMD de memoria compartida tienen menos posibilidades de escalar, debido a que la adición de más unidades de procesamiento conduce a la contención de la memoria. Esta es una situación que no ocurre en el caso de la memoria distribuida, en la que cada unidad de procesamiento tiene su propia memoria. Como resultado de los resultados prácticos y los requisitos del usuario, la arquitectura MIMD de memoria distribuida es superior a los otros modelos existentes. A partir de 2006, las diez principales y la mayoría de las supercomputadoras TOP500 están basadas en la arquitectura MIMD. Es por eso que algunos dividen aún más la categoría MIMD en otras dos categorías:

5



Single program, multiple data streams o SPMD (programa único, múltiples flujos de datos): se trata de múltiples procesadores autónomos ejecutan simultáneamente el mismo programa con datos diferentes (en puntos independientes, en lugar de hacerlo en el bloqueo que impone SIMD). También se lo denomina proceso único, datos múltiples: el uso de esta terminología para SPMD es técnicamente incorrecto, ya que SPMD es un modelo de ejecución paralelo y supone que varios procesadores cooperan ejecutando un programa. SPMD es el estilo más común de programación paralela. El modelo SPMD y el término fueron propuestos por Frederic Darema. Gregory Pfister era gerente del proyecto RP3 y Darema era parte del equipo RP3.



Multiple programs, multiple data streams o MPMD (múltiples programas, múltiples flujos de datos): se trata de múltiples procesadores autónomos que operan simultáneamente, al menos dos programas independientes. Por lo general, estos sistemas seleccionan un nodo para que sea el host (modelo de programación del host, nodo explícito) o el administrador (estrategia managerworker), que ejecuta un programa que distribuye datos a todos los demás nodos, donde todos los nodos ejecutan un segundo programa. Esos otros nodos devuelven sus resultados directamente al administrador. Un ejemplo de esto sería la consola de juegos Sony PlayStation 3, con su procesador SPU/PPU.

6

2. Descomposición de problemas Para desarrollar un producto complejo o un sistema de ingeniería grande, es una práctica común descomponer el problema de diseño en subproblemas más pequeños que puedan manejarse más fácilmente. Si alguno de los subproblemas es todavía demasiado complejo, puede descomponerse nuevamente. Esta descomposición nos plantea desafíos, dado que, desde un punto de vista de sistemas, un sistema distribuido o paralelo consiste en varios subsistemas que se comunican y cooperan para un objetivo común, a la vez que nos permite analizar cada subsistema como un sistema en sí mismo. Para poder lograr esa división de un gran sistema en muchos subsistemas existen distintos enfoques, donde los más comunes son: 

Descomposición iterativa: algunos sistemas están basados en la ejecución de un bucle, donde cada iteración puede ser procesada de forma independiente. En otras palabras, permite partir de la ejecución de un proceso sobre los recursos computacionales y ejecuta estas operaciones de forma simultánea sobre los datos. Los datos por procesar son estáticos y las mismas operaciones se aplican a cada uno.



Descomposición de dominio o paralelismo algorítmico: se centra en paralelizar el flujo de los datos de entrada, es decir que los datos son divididos en partes de aproximadamente el mismo tamaño y las partes son asignadas a diferentes procesadores. Cada procesador trabaja solo con la parte de datos que le son asignados.



Descomposición geométrica: en esta estrategia, el dominio del problema se divide en pequeños subdominios y cada procesador ejecuta el algoritmo en la parte del subdominio que le corresponde. Para conseguir un buen balanceo, estos subdominios deben ser distribuidos de acuerdo con algunas reglas regulares o repartidas aleatoriamente.



Descomposición especulativa: en esta estrategia se intentan N técnicas de solución en forma simultánea y (N - l) de ellas se eliminan tan pronto como una de ellas devuelve una respuesta correcta. Descomposición funcional: el sistema se divide en distintas fases y, a su vez, cada fase ejecuta una parte diferente del algoritmo para



7

resolver el problema. De modo que partimos el problema en diferentes subcálculos, los cuales, al mismo tiempo, pueden: a) realizarse independientemente, b) en fases separadas (implementándose en pipeline), c) aplicando un patrón jerárquico o de dependencias de principio o final entre ellos. 

Descomposición maestro-esclavo: el sistema posee un proceso maestro, que es el responsable de descomponer el problema entre sus procesos esclavos. A su vez, el proceso maestro luego será responsable de colectar los resultados que le envían los procesos esclavos para ordenarlos y obtener el resultado final.



Descomposición recursiva o divide y vencerás: el sistema divide el problema en distintos subproblemas que se resuelven de forma independiente para luego combinar sus resultados parciales y obtener el resultado final.

2.1 Arquitecturas Contamos con las siguientes arquitecturas: 

SIMD (instrucción única, datos múltiples): es una técnica que utiliza una clase de computadoras paralelas en la taxonomía de Flynn. Aquí se poseen computadoras con múltiples elementos de procesamiento que realizan la misma operación en múltiples puntos de datos en forma simultánea. Estas máquinas explotan el paralelismo a nivel de datos, pero no la concurrencia: hay cálculos simultáneos (paralelos), pero solo un proceso (instrucción) en un momento dado. SIMD es particularmente aplicable a tareas comunes, tales como ajustar el contraste en una imagen digital o ajustar el volumen de audio digital. La mayoría de los diseños de CPU modernas incluyen instrucciones SIMD para mejorar el rendimiento del uso multimedia. El primer uso de las instrucciones SIMD fue en el ILLIAC IV, que se completó en 1966. SIMD fue la base de los supercomputadores vectoriales de principios de la década de 1970, como el CDC Star-100 y el Texas Instruments ASC, que podían operar en un vector de datos con una sola instrucción. El procesamiento de vectores fue especialmente popularizado por Cray en los años 70 y 80.



SPMD (programa único, datos múltiples): es una técnica empleada para lograr el paralelismo, en donde las tareas se dividen y se ejecutan simultáneamente en varios procesadores con diferentes entradas para obtener resultados más rápido. SPMD es el estilo más común de programación paralela. Esta técnica fue propuesta en 1983 por Michel Auguin y François Larbey en la computadora paralela

8

Opsila y luego en 1984 por Frederic Darema en IBM para máquinas altamente paralelas como el RP3. 

MIMD (multiple instruction, multiple data o instrucción múltiple, datos múltiples): es una técnica empleada de paralelismo, en donde las computadoras que utilizan MIMD tienen varios procesadores que funcionan de forma asíncrona e independiente. Los procesadores pueden estar ejecutando diferentes instrucciones en diferentes datos en cualquier momento dado. Las computadoras que usan MIMD se pueden usar en una serie de áreas de aplicación, tales como diseño asistido por computadora CAD, fabricación asistida por computadora CAM, simulación y modelado, etcétera. Las computadoras MIMD pueden ser de memoria compartida o de categorías de memoria distribuida. Las computadoras de memoria compartida pueden ser de tipo jerárquico, basadas en bus, extendidas o jerárquicas, mientras que las computadoras de memoria distribuida pueden tener esquemas de interconexión de hipercubos o malla.



SIMT (single instruction, multiple thread o instrucción única, subproceso múltiple): es una técnica o modelo de ejecución utilizado en computación paralela, donde la instrucción única, datos múltiples (SIMD) se combina con subprocesamiento múltiple. Los procesadores de una computadora ejecutan más tareas a la vez que el número de procesadores que tiene. Esto se logra porque cada procesador tiene varios subprocesos (o elementos de trabajo o secuencia de operaciones de carriles SIMD), los cuales se ejecutan en pasos de bloqueo y son análogos a los carriles SIMD. El modelo de ejecución SIMT se ha implementado en varias GPU (en inglés, unidades de procesamiento gráfico) y es relevante para la computación de propósito general en unidades de procesamiento de gráficos (en inglés, GPGPU). Algunas supercomputadoras combinan CPU con GPU.

9...