Procesamiento Paralelo

4 Procesamiento paralelo.

Es un proceso empleado para acelerar el tiempo de ejecución de un programa dividiéndolo en múltiples trozos que se ejecutarán al mismo tiempo, cada uno en su propios procesadores.

4.1 Aspectos básicos de la computación paralela.

La computación paralela o procesamiento en paralelo consiste en acelerar la ejecución de un programa mediante su descomposición en fragmentos que pueden ejecutarse de forma simultánea, cada uno en su propia unidad de proceso.

Normalmente, los problemas no pueden dividirse perfectamente en partes totalmente independientes y se necesita, por tanto, una interacción entre ellas que ocasiona una disminución de la velocidad computacional.

En este sentido se habla de mayor o menor grado de paralelismo en la medida en que un algoritmo sea más o menos divisible en partes independientes con igual coste computacional.

Entre las interacciones hay que considerar principalmente las dos siguientes:

a) La transferencia de datos.

b) La sincronización de los cálculos de los diferentes procesadores.

El concepto de computador paralelo, como es de esperar, no es una idea nueva. Por ejemplo, Gill ya escribió acerca de la programación paralela en 1958, y un año después Holland planteó la posibilidad de que un computador pudiera ejecutar un número arbitrario de subprogramas simultáneamente. En 1963Conway describe el diseño de un computador paralelo y su programación, y40 años más tarde se siguen encontrando numerosísimos artículos con títulos y planteamientos similares a los que ya apuntaban estos precursores del campo de la computación paralela.

4.2 Tipos de computación paralela

4.2.1 Taxonomía de las arquitecturas paralelas

Las diferentes posibilidades existentes para desarrollar sistemas paralelos hacen que una clasificación definitiva sea complicada, y seguramente estéril. Por ello, en primer lugar se recuerdan las características básicas del modelo secuencial, con el fin de delimitar los aspectos básicos que son comunes o diferentes de los sistemas paralelos.

Seguidamente se muestra una clasificación clásica propuesta por Flynn, que se basa en el flujo de instrucciones y en el flujo de datos, es decir, el mecanismo de control utilizado. Sin embargo, existe una gran cantidad de criterios, aunque no todos mutuamente excluyentes entre sí, para establecer una clasificación de las distintas arquitecturas paralelas.

4.2.2 Arquitectura de los computadores secuenciales

Como es bien sabido, los computadores secuenciales, también denominados computadores serie, se basan en la arquitectura de J. von Neumann. En este modelo se considera una única secuencia de instrucciones que tratan una única secuencia de datos. Por ello se conocen como computadores SISD.

4.2.2.1 Taxonomía de Flynn

La taxonomía de Flynn es una clasificación de arquitecturas de computadoras propuesta por Michael J. Flynn en 1972.

Las cuatro clasificaciones definidas por Flynn se basan en el número de instrucciones concurrentes (control) y en los flujos de datos disponibles en la arquitectura:

• Single Instruction, Single Data = Una instrucción, un dato (SISD)

Un único procesador interpreta una única secuencia de instrucciones, para operar con los datos almacenados en una única memoria. Los computadores monoprocesador caen en esta categoría.

Computador secuencial que no explota el paralelismo en las instrucciones ni en flujos de datos. Ejemplos de arquitecturas SISD son las máquinas con uni-procesador o monoprocesador tradicionales como el PC o los antiguos mainframe.

• Single Instruction, Multiple Data= Una instrucción, múltiples datos (SIMD)

Una única instrucción de máquina controla paso a paso la ejecución simultánea y sincronizada de un cierto número de elementos de proceso. Cada elemento de proceso tiene una memoria asociada, de forma que cada instrucción es ejecutada por cada procesador, con un conjunto de datos diferentes. Los procesadores matriciales y vectoriales pertenecen a esta categoría.

Un computador que explota varios flujos de datos dentro de un único flujo de instrucciones para realizar operaciones que pueden ser paralelizadas de manera natural. Por ejemplo, un procesador.

• Multiple Instruction, Single Data= Múltiples instrucciones, un dato (MISD)

Se transmite una secuencia de datos a un conjunto de procesadores, cada uno de los cuales ejecuta una secuencia de instrucciones diferente. Esta estructura ha sido implementada sólo con fines de investigación.

Poco común debido al hecho de que la efectividad de los múltiples flujos de instrucciones suele precisar de múltiples flujos de datos. Sin embargo, este tipo se usa en situaciones de paralelismo redundante, como por ejemplo en navegación aérea, donde se necesitan varios sistemas de respaldo en caso de que uno falle. También se han propuesto algunas arquitecturas teóricas que hacen uso de MISD, pero ninguna llegó a producirse en masa.

• Multiple Instruction, Multiple Data= Múltiples instrucciones, múltiples datos (MIMD)

Un conjunto de procesadores ejecuta simultáneamente secuencias de instrucciones diferentes con conjuntos de datos diferentes. Los clusters son ejemplos de esta categoría.

Varios procesadores autónomos que ejecutan simultáneamente instrucciones diferentes sobre datos diferentes. Los sistemas distribuidos suelen clasificarse como arquitecturas MIMD; bien sea explotando un único espacio compartido de memoria, o uno distribuido.

4.2.2.2 Organización del espacio de direcciones de memoria

El intercambio de información entre procesadores depende del sistema de almacenamiento que se disponga. Atendiendo a este criterio se obtiene una nueva clasificación de las arquitecturas paralelas en:

• Sistemas de memória compartida o multiprocesadores.

Los procesadores de los sistemas con memoria compartida se caracterizan por compartir físicamente la memoria, es decir, todos acceden al mismo espacio de direcciones. Un valor escrito en memoria por un procesador puede ser leído directamente por cualquier otro. En principio, en esta arquitectura la memoria es igualmente accesible por todos los procesadores a través de la red de interconexión.

Así se desarrollaron los primeros computadores de esta arquitectura, tales como el

NYUUltracomputer.

La mayoría de los sistemas de memoria compartida incorporan una memoria cache local en cada procesador, y del mismo modo que en los computadores secuenciales, sirve para aumentar el ancho de banda entre el procesador y la memoria local. Análogamente puede existir una memoria cache para la memoria global. Cuando se utilizan memorias cache es fundamental asegurar la coherencia de la información en la memoria cache.

• Sistemas de memória distribuida o multicomputadores.

En los sistemas de memoria distribuida cada procesador dispone de su propia memoria, denominada local o privada, independiente del resto y accesible sólo por su procesador. La comunicación se realiza por paso de mensajes, es decir, para que un dato que reside en la memoria de un procesador pase a la de otro, el primero debe construir un mensaje por software, enviarlo a través de una red de interconexión y el segundo debe recibirlo.

4.3 Sistemas de memoria compartida: Multiprocesadores

La organización de un sistema multiprocesador puede clasificarse como sigue:

• Bus de Tiempo Compartido o Común

• Memoria multipuerto

• Unidad de control central

4.3.1 Redes de interconexión dinámicas o indirectas

La red de interconexión es eficaz u óptima cuando la capacidad de cálculo del sistema está equilibrada con respecto a la capacidad de transmisión de la red de interconexión. Cuando la capacidad de cálculo se incrementa, las características de la red deben mejorarse en sintonía con ella.

LIMITACIONES:

• En primer lugar el coste es mayor

• Limitaciones físicas, como los retrasos inherentes a todo sistema de comunicación.

Los factores de la red de interconexión que más influyen en el rendimiento del sistema son fundamentalmente cuatro:

• La topología

• El mecanismo de conmutación

• El control de flujo

• El algoritmo de encaminamiento

4.3.1.1 Redes de medio compartido

Una red Ethernet se comporta como un medio compartido, es decir, sólo un dispositivo puede transmitir con éxito a la vez y cada uno es responsable

...