1

6. MULTIPROCESADORES 6.1 Introducción Algunos diseñadores de computadoras han mantenido la ilusión de crear una computadora poderosa simplemente conectando muchas computadoras pequeñas. Esta visión es la base para la creación de sistemas con múltiples procesadores, sistemas escalables tanto en hardware como en software, de manera que los consumidores puedan adquirir un sistema con el número de procesadores que su presupuesto les permita, pero con la posibilidad de incrementar el número de procesadores y en espera de que el software los utilice para incrementar el rendimiento. El software escalable también implica que el sistema pueda continuar operando en presencia de hardware roto, esto es, si un procesador falla en un sistema con n procesadores, el sistema deberá continuar bajo servicio con n – 1 procesadores. Además, los sistemas multiprocesadores deben tener el más alto rendimiento absoluto – deben ser más rápidos que el sistema uniprocesador más rápido. Actualmente el microprocesador es el procesador más efectivo en costo y si se considera que un procesador (un chip-único) puede soportar una carga de trabajo en tiempo compartido, entonces un multiprocesador compuesto de muchos chips-únicos debe ser más efectivo que construir un uniprocesador de alto rendimiento buscando otro tipo de tecnología. Comercialmente para los multiprocesadores usualmente se define un alto rendimiento como una alta productividad para tareas independientes. Esta definición está en contraste si se trata de ejecutar una sola tarea sobre múltiples procesadores. La frase: procesamiento paralelo hace referencia a un programa único que simultáneamente se ejecuta en múltiples procesadores. Algunas preguntas clave para el diseño de multiprocesadores son las siguientes: • ¿Cómo es que los procesadores paralelos comparten datos? • ¿Cómo es que los procesadores paralelos se coordinan? • ¿Cuántos procesadores se pueden conectar? La respuesta a la primera pregunta cae en dos campos principales. Procesadores con un único espacio de direcciones, algunas veces llamados procesadores con memoria compartida, ofrecen al programador un único espacio de direcciones de memoria que todos los procesadores comparten. Los procesadores se comunican a través de variables compartidas en memoria, todos los procesadores tienen acceso a cualquier localidad de memoria a través de cargas y almacenamientos. Cuando los procesadores trabajan en paralelo normalmente compartirán datos, también se requiere que ellos se coordinen cuando operan sobre datos compartidos; de otra manera, un procesador podría iniciar a trabajar sobre los datos antes de que otro este finalizando con eso. Esta coordinación es llamada sincronización. Si se trabaja con un único espacio de direcciones, se debe contar con un mecanismo separado para sincronización. Un enfoque utiliza un candado: Solamente un procesador a la vez puede adquirir el candado, y los otros

2

procesadores interesados en los datos compartidos deben esperar hasta que el procesador original “abra” la variable. Este mecanismo se describe en la sección 6.3. Los multiprocesadores con un único espacio de direcciones vienen en dos estilos. El primero toma el mismo tiempo para accesar la memoria principal, no importa cual procesador lo requiera y tampoco importa la palabra a leer. Tales máquinas son llamadas multiprocesadores con acceso uniforme a memoria (UMA, uniform memory access) o multiptocesadores simétricos (SMP, symmetric multiprocessors). En el segundo estilo, algunos accesos a memoria son más rápidos que otros dependiendo de cual procesador esté accesando y a cual palabra. Tales máquinas son llamadas multiprocesadores con acceso no uniforme a memoria (NUMA, nonuniform memory access). Como podría esperarse, hay mas desafíos de programación para obtener un rendimiento más alto con un multiprocesador NUMA que con un multiprocesador UMA, pero las máquinas NUMA pueden escalar a grandes tamaños y por lo tanto son potencialmente de un rendimiento más alto. El modelo alternativo a la memoria compartida utiliza el paso de mensajes para comunicación entre procesadores. El paso de mensajes es requerido por máquinas con memorias privadas, en contraste a la memoria compartida. Como un ejemplo extremo, los procesadores en diferentes computadoras de escritorio se comunican pasando mensajes sobre una red de área local. Los sistemas tienen rutinas para enviar y recibir mensajes, la coordinación es construida con los mensajes que se envían, dado que un procesador sabe cuando un mensaje es enviado y el procesador receptor sabe cuando un mensaje ha llegado. El procesador receptor puede entonces enviar un mensaje al emisor indicando que el mensaje ha llegado, si el emisor necesita confirmación. Un fenómeno reciente ha sido la prueba del ejemplo extremo anterior – las computadoras conectadas a una red de área local – y hacerlas que actúen como un multiprocesador único grande. Tales grupos de computadoras (clusters) afectan la conmutación de la red de área local requiriendo anchos de banda altos entre las computadoras del grupo. Además de los dos principales estilos de comunicación, los multiprocesadores son construidos en dos organizaciones básicas: procesadores conectados por un único bus y procesadores conectados por una red. El número de procesadores en el multiprocesador tiene mucho que ver con esta elección. Los dos estilos se examinarán a detalle en las secciones 6.3 y 6.4. En la tabla 6.1 se muestra la relación existente entre el número de procesadores en un multiprocesador y la elección de direcciones compartidas contra paso de mensajes para comunicación, y la elección entre bus y red en cuanto a conexión física. Para las direcciones compartidas también se tiene la posibilidad de que el acceso a memoria sea uniforme o no uniforme. Aunque hay muchas posibilidades para algunos números de procesadores, para otras regiones hay un acuerdo generalizado.

3

Categoría Elección Número de Procesadores Paso de mensajes 8 – 256

NUMA 8 – 256 Modelo de Comunicación Direcciones

Compartidas UMA 2 – 64 Red 8 – 256 Conexión

física Bus 2 – 36

Tabla 6.1 Opciones en estilo de comunicación y comunicación física para multiprocesadores de acuerdo al número de procesadores.

En la siguiente sección se revisan algunos tópicos generales en la programación de multiprocesadores. 6.2 Programación de multiprocesadores La mala noticia es que aún habrá que ver cuantas aplicaciones importantes se ejecutarán más rápido sobre multiprocesadores a través de procesamiento paralelo. El obstáculo no es el precio de los uniprocesadores usados para componer los multiprocesadores, las banderas en la topología de redes de interconexión, ni la indisponibilidad de lenguajes de programación apropiados; la dificultad estriba en que pocos programas de aplicación importantes han sido re-escritos para completar tareas mas pronto sobre multiprocesadores. Puesto que es aún mas duro encontrar aplicaciones que puedan tomar ventaja de muchos procesadores, el reto es aún mayor para multiprocesadores a gran escala. Como un resultado de la dificultad de la programación, la mayoría de trabajos con éxito sobre procesamiento paralelo son un resultado del desarrollo de subsistemas paralelos que presentan una interfaz secuencial. Ejemplos incluyen bases de datos, servidores de archivos, paquetes de diseño asistido por computadora y sistemas operativos multiprocesadores. Pero ¿Por qué ocurre esto? ¿Por qué debería de ser mucho más duro desarrollar programas con procesamiento paralelo que programas secuenciales? La primera razón es que se debe obtener un buen rendimiento y eficiencia del programa paralelo sobre el multiprocesador; de otra manera se utilizaría un procesador único donde la programación es más fácil. De hecho, las técnicas de diseño de los procesadores, como la segmentación, toman ventaja del paralelismo al nivel de instrucciones, normalmente sin involucrar al programador. Tales innovaciones reducen la demanda por re-escribir los programas para multiprocesadores. ¿Por qué es difícil escribir programas para multiprocesadores que sean rápidos, especialmente cuando el número de procesadores se incrementa? Como una analogía, pensemos en la comunicación manejada para una tarea hecha por una persona comparada con la manejada por una tarea hecha por un comité, especialmente cuando el comité se incrementa. Aunque n personas tienen el potencial para terminar la tarea n veces más rápido, la comunicación manejada por el grupo puede impedirlo, por lo que es muy poco

4

probable un incremento en velocidad de n. (Imaginemos el cambio en la comunicación manejada si el comité crece de 10 a 1000 personas, o si aumenta a 1, 000,000.) Otra razón por la que es difícil escribir programas con procesamiento paralelo es que el programador debe saber mucho acerca del hardware. Cuando se trabaja con un solo procesador, el programador escribe los programas en alto nivel, ignorando la organización de la máquina, ese es el trabajo del compilador. Pero por otro lado, el programador de procesamiento paralelo requiere de un conocimiento amplio para escribir programas que sean rápidos y capaces de ejecutarse en un número variable de procesadores. Sin embargo, un programa adaptado a un multiprocesador no es transportable a otros multiprocesadores. Además de estas dos razones de la dificultad en el procesamiento paralelo, la ley de Amdahl revela un tercer obstáculo, el cual se muestra mas adelante, después de revisar algunos aspectos del rendimiento con relación al procesamiento paralelo. 6.2.1 El papel del rendimiento

Las medidas de rendimiento permiten saber desde diferentes puntos de vista la mejora que se obtiene al modificar un programa secuencial e implementarlo en paralelo; sin embargo, existen varios factores que pueden afectar el rendimiento. La medida más común es la curva de rapidez, ésta se calcula dividiendo el tiempo usado en computar una solución usando un solo procesador, entre el tiempo empleado en la implementación con N procesadores en paralelo. El cuello de botella de Von Neumann

Las máquinas secuenciales han sido creadas usando el modelo de Von Neumann, quien también desarrolló ciertas ideas sobre algunos obstáculos que tendría la construcción de computadoras paralelas (hizo sus consideraciones basado en cuestiones prácticas de su época). El modelo de Von Neumann consiste de una única unidad de control conectando una memoria a la unidad de procesamiento como se muestra en la figura 6.1. Las instrucciones y datos son obtenidos uno a la vez de la memoria para la unidad de procesamiento. La velocidad de procesamiento del sistema está limitada entonces por la rapidez en que los datos e instrucciones pueden ser transportados desde la memoria hasta la unidad de procesamiento. Esta conexión entre la memoria y la unidad de procesamiento es conocida como el cuello de botella de Von Neumann.

5

Figura 6.1 Cuello de botella de Von Neumann

Este cuello de botella puede ser evitado empleando más de una unidad de procesamiento y muchas memorias, así varios flujos de datos pueden estar activos al mismo tiempo. Finalmente todos los elementos anteriores se pueden interconectar usando una red de interconexión dando lugar a una computadora del tipo ‘no-Von Neuman’ (non-von) ya que no sigue el modelo de Von Neumann (Figura 6.2).

Figura 6.2 Estructura general de una computadora no Von Neumann

La ley de Amdahl

Un número pequeño de operaciones secuenciales puede limitar el factor de aceleración de un algoritmo paralelo, estas operaciones son necesarias para la sincronización de todos los procesadores. Sea f la fracción de operaciones de un algoritmo que deben ser ejecutadas secuencialmente, en donde 0 < f < 1. La máxima aceleración Sp alcanzada usando p procesadores está dada por:

1 (1-f)

Sp ≤

f +p

(1)

6

A partir de esta ley se puede deducir que un pequeño número de operaciones secuenciales en un algoritmo paralelo va a limitar de manera significativa la aceleración alcanzada por el algoritmo. En la figura 6.3 se puede apreciar la aplicación de la ley de Amdahl para f = 0.10 (el 10 % del total de instrucciones son empleadas en la sincronización), note que la curva no puede atravesar el límite de Sp=10. Por lo tanto, independientemente del número de procesadores que se utilicen, la mayor aceleración que se le puede dar al algoritmo es 10.

Ley de Amdahl para f=0.1

0

2

4

6

8

10

12

1 2 4 8 16 32 64 128 256 512 1024

Número de procesadores

Factor de aceleración

(Sp)

Figura 6.3 Aplicación de la Ley de Amdahl

Curvas de velocidad (Speedup curves)

El propósito de estas curvas es comparar el tiempo del programa serial más rápido T1 contra el tiempo del programa paralelo equivalente T(N), donde N es el número de procesadores usados. En la práctica se utiliza T(1) como una aproximación a T1 debido a la dificultad para obtenerlo. Entonces se obtiene S como el cociente de T(1) y T(N):

T(1) T(N)

S ≤

(2)

En la figura 6.4 se muestran las curvas de incremento de velocidad para un problema del tipo trivialmente paralelo, la siguiente curva es para un programa que usa comunicación intensiva y la curva que crece menos es de un programa que usa la estrategia divide y vencerás, todos ellos usando desde 1 hasta 10 procesadores que se muestran en el eje X, el eje Y muestra el valor de S. La estrategia divide y vencerás divide al problema original en dos subproblemas, en forma iterativa o recursiva, hasta encontrar problemas con solución evidente, por lo tanto, como se aprecia en la figura, se obtienen beneficios si se emplean dos procesadores, pero en realidad no hay un beneficio significativo al utilizar mas de dos procesadores.

7

Figura 6.4 Curvas de incremento de velocidad

El incremento del número de procesadores no siempre garantiza la disminución del

tiempo en el que es realizada una determinada tarea. El ejemplo siguiente muestra resultados generados en el Instituto de Supercómputo de Minesota, se hicieron pruebas al modelo de paralelización JavaSpMT (Java Speculative MultiThreading), que es un conjunto de rutinas específicas para la programación de hilos. La aplicación de prueba resuelve sistemas de n x n ecuaciones lineales usando el método de eliminación gausiana. Las pruebas fueron hechas en un sistema multiprocesador IP25 SGI Challenge a 196 MHz con memoria compartida y se emplearon 2, 4 y 8 procesadores MIPS R10000. Los resultados arrojaron las siguientes curvas de incremento de velocidad:

Figura 6.5 Curvas de rapidez al utilizar 2, 4, y 8

procesadores para resolver un sistema de nxn ecuaciones lineales por el método de Gauss [DDDD3].

Como puede observarse, si N ≤ 300 el utilizar dos procesadores resulta más rápido que usar más; mientras que si 300 < N ≤ 750, es mejor utilizar cuatro procesadores. Sin embargo, para un sistema con más de 750 ecuaciones, resultan mejor ocho procesadores. Por lo tanto, en este caso el número adecuado de procesadores está en función del tamaño de la instancia del problema.

8

6.3 Multiprocesadores conectados por un solo bus El alto rendimiento y el bajo costo de los microprocesadores inspiró renovados intereses en los multiprocesadores en los 60’s. Varios microprocesadores pueden colocarse adecuadamente en un bus común por diversas razones: • Cada microprocesador es más pequeño que un procesador multi-chip, de manera que

más procesadores pueden ser situados sobre un bus. • La caché puede reducir el tráfico del bus. • Se tienen los mecanismos para mantener la consistencia entre la caché y la memoria

para multiprocesadores, así como caché y memoria se mantienen consistentes con I/O, por lo tanto se simplifica la programación.

La figura 6.6 muestra un multiprocesador genérico de un solo bus y en la tabla 6.2 se listan algunas características de algunas computadoras comerciales de un solo bus. El tráfico por procesador y el ancho de banda del bus determinan el número útil de procesadores en tales microprocesadores. Las caché s replican datos en sus memorias más rápidas tanto para reducir la latencia a los datos y reducir el tráfico de memoria sobre el bus.

Figura 6.6 Multiprocesadores de un solo bus,

su tamaño típico está entre 2 y 32 procesadores.

9

Nombre Máximo

número de procesadores

Nombre del procesador

Frecuencia de reloj

Máximo tamaño de memoria/Sistema

Razón de comunicación

Compaq ProLiant 5000 4 Pentium Pro 200 MHz 2, 048 MB 540 MB/seg.

Digital AlphaServer 8400 12 Alpha 21164 440 MHz 28, 672 MB 2150 MB/seg.

HP 9000 K460 4 PA-8000 180 MHz 4, 096 MB 960 MB/seg. IBM RS/6000 R4 8 PowerPC 604 112 MHz 2, 048 MB 1800 MB/seg.

SGI Power Challenge 36 MIPS R10000 195 MHz 16, 384 MB 1200 MB/seg.

Sun Enterprise 6000 30 UltraSPARC 1 167 MHz 30, 720 MB 2600 MB/seg.

Tabla 6.2 Características de computadoras con multiprocesadores conectadas por un solo bus,

disponibles en el mercado en 1997. Ejemplo: Programa paralelo (Un solo bus) Se quieren sumar 100, 000 números con una computadora cuyo multiprocesador es de un solo bus. Se asume que cuenta con 10 procesadores. Realizar un programa para esta tarea Respuesta: El primer paso consistiría en dividir el conjunto de números en subconjuntos del mismo tamaño. Dado que hay una memoria única para esta máquina, los subconjuntos tendrán diferentes direcciones de inicio que usará cada procesador. Pn es el número del procesador, entre 0 y 9. Todos los procesadores inician el programa ejecutando un lazo que suma sus subconjuntos de números: Sum[ Pn ] = 0; For ( i = 1000*Pn; i < 1000*(Pn + 1); i = i + 1 ) Sum[ Pn ] = Sum[Pn] + A[i]; /* Suman sus áreas asignadas */ Este lazo utiliza instrucciones de carga para llevar el subconjunto correcto de números a las cachés de cada procesador desde la memoria principal común. El siguiente paso consiste en sumar estas sumas parciales, se aplicará una estrategia del tipo divide y vencerás. La mitad de los procesadores sumará un par de las sumas parciales, después un cuarto sumará un par de cada una de las nuevas sumas parciales, y así hasta obtener una única suma final. Es conveniente que cada procesador tenga su propia versión de la variable de control de lazo i, de manera que se debe indicar que ésta es una variable privada (private). En este ejemplo, los procesadores deben sincronizarse antes de que los procesadores “consumidores” intenten leer el resultado desde la ubicación de la memoria escrito por los

10

procesadores “productores”; en otro caso, el consumidor puede leer los valores anteriores de los datos. El código es el siguiente (half es una variable privada): Half = 10; /* 10 procesadores en un multiprocesador de un bus */ Do { Synch(); /* Espera a que la suma parcial se complete */ If ( Half % 2 != 0 && Pn == 0 ) Sum[0] = Sum[0] + Sum[Half – 1]; Half = Half / 2; /* Línea de división sobre los que suman */ If ( Pn < Half ) Sum[ Pn ] = Sum[ Pn ] + Sum[ Pn + Half ] } while ( Half != 1); /* Termina con la suma final en Sum[0] */ En el código anterior se ha utilizado una primitiva conocida como barrera de sincronización (Synch()); cada procesador espera en la barrera hasta que todos la han alcanzado, entonces proceden. La barrera de sincronización permite a todos los procesadores sincronizarse rápidamente. Esta función puede implementarse a través de software utilizando un candado (que se explicará mas adelante), o con algún hardware especial que combine una señal “listo” de cada procesador en una señal global que todos los procesadores pueden probar. Sin embargo, en un procesador cabe la posibilidad de que existan inconsistencias entre los valores que están en la memoria con respecto a los que están en la caché. Este problema de coherencia de caché también se aplica a multiprocesadores así como con I/O. A diferencia de I/O, la cual raramente usa múltiples copias de datos (una situación que debe ser evitada siempre que sea posible), como la segunda mitad del ejemplo sugiere, múltiples procesadores rutinariamente requieren copias del mismo dato en múltiples cachés. Alternativamente, el acceso a datos compartidos podría ser forzado para que siempre redondee de caché a memoria, pero esto sería demasiado lento además de que requeriría un amplio ancho de banda del bus; el rendimiento de un programa para multiprocesadores depende del rendimiento del sistema cuando los datos son compartidos. Los protocolos para mantener la coherencia para múltiples procesadores son llamados protocolos de coherencia de caché, éstos se revisan en secciones posteriores. Coherencia de caché en multiprocesadores El protocolo mas popular para mantener la coherencia con la caché es conocido como espionaje (snooping). En la figura 6.7 se muestra como la caché accesa a la memoria sobre un bus común. Todas las cachés tienen un control para monitorear, o espiar (snoop), al bus para determinar si se ha hecho una copia de un bloque compartido. El protocolo snooping llegó a ser popular con las máquinas de los 80’s, las cuales utilizaban un bus único para sus memorias principales. Esos uniprocesadores se fueron extendiendo agregando múltiples procesadores sobre ese bus para dar fácil acceso a la memoria compartida. Las cachés se agregaron posteriormente para mejorar el rendimiento de cada

11

procesador, llevando a esquemas para mantener las cachés actualizadas al espiar la información sobre el bus compartido.

Figura 6.7 Multiprocesadores de un solo bus

usando espionaje (snooping) para la coherencia del caché. Para mantener la coherencia se tiene dos componentes: Lectura y escritura. Para la lectura no es un problema que existan múltiples copias, pero un procesador debe tener un acceso exclusivo para escribir una palabra. Los procesadores deben también tener la copia mas reciente cuando están leyendo un objeto, de manera que todos los procesadores deben obtener nuevos valores después de una escritura. Entonces, el protocolo de espionaje debe localizar todas las cachés que comparten un objeto para ser escrito. La consecuencia de una escritura a datos compartidos puede ser para invalidar otras copias o para actualizar las copias compartidas con los valores que están siendo escritos. Los bits de estado en un bloque caché son ampliados para el protocolo de espionaje, y esta información es utilizada para monitorear las actividades del bus. Sobre una lectura fallida, las cachés verifican para ver si tienen una copia del bloque solicitado y entonces toman las acciones apropiadas, tal como suministrar el dato a la caché que lo perdió. Similarmente, sobre una escritura, todas las cachés observan para ver si ellas tienen una copia y entonces actúan, ya sea invalidando o actualizando sus copias con los nuevos valores. Dado que todas las transiciones en el bus verifican las etiquetas de direcciones en las cachés, se podría suponer que ésta interfiere con el procesador. Interferirá solo para duplicar la porción de etiquetas de dirección de la caché (no en la caché completa) para obtener un puerto de lectura extra para el espionaje (ver Figura 6.7). De esta manera, el espionaje rara vez interfiere con el acceso del procesador a la caché. Cuando hubiera interferencia, el procesador probablemente se detendría por que la caché no estaría disponible. Los protocolos de espionaje son de dos tipo, dependiendo de lo que ocurre con una escritura:

12

• Invalidación de Escritura (write-invalidate): La escritura del procesador obliga a que todas las copias en otros caches sean inválidas antes de que cambien su copia local; se tiene la libertad de actualizar los datos locales hasta que otro procesador pregunta por ellos. La escritura del procesador manifiesta una señal de invalidación sobre el bus, y todas las cachés observan para ver si tienen una copia; si es así, ellas deben invalidar al bloque que contenga la palabra. Esto es, este esquema permite múltiples lecturas pero solamente una escritura.

• Actualización de Escritura (write-update): En lugar de que se invaliden los bloques

compartidos, el procesador que escribe emite el nuevo dato sobre el bus; todas las copias son entonces actualizadas con el nuevo valor. Este esquema, también llamado emisión de escritura (write-broadcast), continuamente emite escrituras a datos compartidos, mientras que el método de Invalidación de Escritura borra todas las otras copias de manera que hay solamente una copia local para subsecuentes escrituras.

El protocolo de Actualización de Escritura continuamente escribe sobre el bus para actualizar las copias de los datos compartidos, tiene la ventaja de hacer que los nuevos valores aparezcan en las cachés mas pronto, reduciendo con ello la latencia. El protocolo de Invalidación de Escritura usa el bus solamente en la primera escritura para invalidar las otras copias, por lo que no hay escrituras subsecuentes que resulten en actividad en el bus, en consecuencia se reduce la demanda en el ancho de banda del bus. Comercialmente los multiprocesadores basados en caché usan el protocolo de Invalidación de Escritura por que reduce el tráfico del bus y por lo tanto permite la conexión de mas procesadores en un único bus. Un ejemplo de un protocolo de coherencia de caché Para ilustrar lo problemático de un protocolo de coherencia de caché, en la figura 6.8 se muestra una máquina de estados finitos para un protocolo de Invalidación de Escritura basado sobre una política de retro-escritura (write-back). Cada bloque de caché está en uno de tres estados: 1. Sólo lectura: Este bloque de caché está limpio (no escrito) y puede ser compartido. 2. Lectura/Escritura: Este bloque de caché está sucio (escrito) y no puede ser compartido. 3. Inválido: Este bloque de caché no tiene datos válidos. Los tres estados del protocolo son duplicados en la figura para mostrar las transiciones basadas sobre las acciones de un procesador tan opuestas a las transiciones basadas sobre la operación del bus. Esta duplicación se hace solo con propósitos ilustrativos; realmente hay una sola máquina de estados finitos por caché, con estímulos proviniendo del procesador anexado o del bus.

13

Inválido(bloque decaché noválido)

Solo lectura(limpio)

Lectura/Escritura(sucio)

El Procesador escribe

El Procesadorfalla en la lectura

El procesador escribe(acierta o falla)

El Procesadorfalla en la lectura

El procesador falla en la escritura

(Retro esc

ribe un bloque su

cio a m

emoria)

(Envía una in

validaci

ón si aci

erta)

(a) Transiciones de estados en la caché usando las señales del procesador

Inválido(bloque decaché noválido)

Solo lectura(limpio)

Lectura/Escritura(sucio)

Invalida u otroprocesador tiene

un fallo de escritura para este bloque

(visto sobre el bus)Otro procesador tiene un falloen lectura o un fallo en

escritura para este bloque(visto sobre el bus)

(b) Transiciones de estados en la caché usando las señales desde el bus

Figura 6.9 Un protocolo de Invalidación de Escritura para la coherencia de caché. La parte superior muestra las transiciones entre los estados basada en las acciones asociadas con el procesador asociado con este caché.

La parte inferior muestra las transiciones basadas en las acciones de otros procesadores vistas como operaciones en el bus.

14

Las transiciones en los estados de un bloque de caché ocurren sobre fallos de lectura, fallos de escritura, o escrituras correctas; las lecturas correctas no cambian el estado de la cache. Iniciemos con la falla en lectura; cuando un procesador tiene una falla en una lectura que mapea en un bloque, este cambiará el estado de ese bloque a Solo Lectura, y entonces accesará al bus y retro escribirá el viejo bloque, si el bloque estaba en el estado de Lectura/Escritura (sucio). Todas las cachés en los otros procesadores monitorean la lectura fallida para ver si este bloque está en su caché. Si uno tiene una copia y está en el estado Lectura/Escritura, entonces el bloque es cambiado al estado inválido. (Algunos protocolos cambiarían al estado de Solo Lectura). La lectura fallida es entonces satisfecha leyendo desde la memoria. Ahora probaremos la escritura. Para escribir un bloque, el procesador se apropia del bus, envía una señal de invalidez, escribe dentro del bloque y se coloca en el estado de Lectura/Escritura. Otras cachés monitorean el bus para ver si tienen una copia de ese bloque; si es así, entonces lo invalidan. Hay muchas variaciones de cachés que son mucho mas complicadas que este modelo simple. La que se encuentra en los procesadores Pentium Pro y Power PC es llamada MESI, un protocolo de Invalidación de Escritura cuyo nombre es un acrónimo de los cuatro estados del protocolo: Modificado, Exclusivo, Compartido e Inválido (Modified, Exclusive, Shared, Invalid). El estado modificado es el mismo que el estado Lectura/Escritura de la figura 6.9, y el estado inválido es el mismo también. El estado de Solo Lectura de la figura 6.9 está dividido, dependiendo de que si hay múltiples copias (estado Compartido) o si hay solo una (estado Exclusivo). En cualquier caso, la memoria tiene una versión para actualizar el dato. Este estado extra significa que una escritura de un dato que está en el estado Exclusivo no requiere invalidación dado que hay solo una copia del bloque. Una escritura de un dato en el estado Solo Lectura en la figura 6.9 requeriría una invalidación, dado que puede haber muchas copias. Otras variaciones sobre protocolos de coherencia analizan si las otras cachés intentan suministrar el bloque cuando ellas tienen una copia, si el bloque debe ser invalidado por una lectura fallida, y por supuesto, si se invalida la escritura o se actualizan los datos compartidos. Sincronización Usando Coherencia Uno de los principales requerimientos de un multiprocesador de un único bus es la habilidad para coordinar a los procesadores que están trabajando en una tarea común. Típicamente un programador utiliza variables como candados (también conocidas como semáforos) para coordinar o sincronizar los procesos. El reto para la arquitectura de un multiprocesador es proporcionar un mecanismo para decidir cual procesador obtendrá el candado y para proporcionar la operación que encierre a una variable. El arbitraje es fácil para multiprocesadores con un único bus, dado que el bus es la única ruta a la memoria: el procesador que obtiene el bus lo cierra para los otros procesadores desde la memoria, si el procesador y el bus realizan una operación de intercambio atómico. Los programadores pueden crear candados con semántica propia. Aquí el adjetivo atómico significa indivisible, de manera que un intercambió atómico significa que el procesador puede leer una localidad

15

y ajustarla a un valor encerrado en la misma operación con el bus, evitando que cualquier otro procesador o dispositivo I/O realice una lectura o escritura hasta que el intercambio se complete. En la figura 6.10 se muestra un procedimiento típico para encerrar una variable usando una instrucción de intercambio atómico. Suponemos que 0 significa abierto (unloked, “go”) y 1 significa cerrado (locked, “stop”). Un procesador primero lee la variable lock para probar su estado. Un procesador se mantiene leyendo y probando hasta que el valor de lock indica que esta abierto.

Figura 6.10 Pasos para adquirir un candado o semáforo para sincronizar procesos y después liberar el

candado para salir de la sección encerrada de código. El procesador entonces compite contra los otros procesadores que esperan para ver quien puede encerrar la variable primero. Todos los procesadores usan una instrucción de intercambio atómico que lee el viejo valor y almacena un 1 (“stop”) dentro de la variable lock. El único ganador verá el 0 (“go”), y los perdedores verán un 1 que fue puesto ahí por

16

el ganador. (Los perdedores continuarán con la escritura de la variable con el valor de 1 en el candado, por lo que no cambiarán su valor.) El procesador ganador ejecutará entonces el código que actualiza los datos compartidos. Cuando el ganador termina, escribe 0 (“go”) sobre la variable lock, por lo tanto inicia la competencia de todos nuevamente. Una ventaja del algoritmo de la figura 6.10 es que permite a los procesadores girar en espera de una copia local del candado en sus cachés. Esto reduce la cantidad de tráfico en el bus; en la tabla 6.3 se muestran las operaciones para el bus y caché para multiprocesadores intentando asegurar una variable. Una vez que el procesador con el candado almacena un 0 en su variable lock, todos los demás procesadores ven lo que almacenó e invalidan sus copias de la variable encerrada. Entonces ellos intentan obtener el nuevo valor para lock de 0. (Con los protocolos de Actualización de Escritura para coherencia de caché, las cachés actualizarían sus copias en lugar de primero invalidar y después cargar desde la memoria.) Este nuevo valor inicia la carrera nuevamente para ver quien puede ajustar el candado primero. El ganador obtiene el bus y almacena un 1 en el candado; las otras cachés reemplazan sus copias de la variable lock que contenía 0 con 1. Ellos leen que la variable ya está encerrada y deben regresar a probar y girar. Paso Procesador P0 Procesador P1 Procesador P2 Actividad del bus

1 Tiene el candado Gira, probando si lock = 0

Gira, probando si Lock = 0 Ninguna

2 Ajusta el candado a 0 y envía 0 sobre el bus

Gira, probando si lock = 0

Gira, probando si Lock = 0

Invalidación de Escritura de la variable lock desde P0

3 La caché falla La caché falla El Bus decide servir a P2 por que la caché falló

4 (Espera mientras el bus está ocupado) Lock = 0 Falló en la caché, satisfecho

para P2

5 Lock = 0 Intercambia: Lee el candado y lo ajusta a 1

Falló en la caché, satisfecho para P1

6 Intercambia: Lee el candado y lo ajusta a 1

Valor de intercambio = 0 y envía 1 sobre el bus

Invalidación de Escritura de la variable lock desde P2

7 Valor de intercambio = 1 y envía 1 sobre el bus

Se apropia del candado, de manera que puede actualizar sus datos compartidos

Invalidación de Escritura de la variable lock desde P1

8 Gira, probando si lock = 0 Ninguna

Tabla 6.3 Pasos para la coherencia de caché y tráfico del bus para tres procesadores P0, P1 y P2. En la tabla anterior se supone una coherencia de Invalidación de Escritura. P0 inicia con el candado (Paso 1). P1 y P2 compiten para ver cual lee el valor del candado abierto durante el intercambio (Pasos 3-5). P2 gana y entra a una sección crítica (Pasos 6 y 7), mientras que P1 gira y espera (Pasos 7 y 8). Una sección crítica es el nombre del código entre la cerradura y la apertura. Este esquema tiene la dificultad de escalar a muchos procesadores debido al tráfico que se genera cuando el candado es liberado.

17

6.4 Multiprocesadores conectados a una Red Los diseños de un solo bus son atractivos, pero limitados por que tres características deseables en el bus son incompatibles: Alto ancho de banda, baja latencia y longitud grande. Hay también un límite para el ancho de banda por que se tiene un solo módulo de memoria anexo al bus. Entonces, un bus único impone restricciones prácticas sobre el número de procesadores que pueden ser conectados a él. Para ilustrar, el número más grande de procesadores conectados a un bus en computadoras comerciales es de 36 y este número parece estar disminuyendo sobre el tiempo. Si la meta es conectar muchos procesadores, entonces los diseñadores de computadoras necesitan usar más que un solo bus. En la figura 6.11 se muestra como puede hacerse esta organización, a diferencia de la figura 6.6 (multiprocesador con un solo bus) a cada procesador se le ha anexado su propia memoria y el medio para la comunicación entre procesadores es una red, en lugar de un bus, que se utilizaba como acceso a la memoria. En la tabla 6.4 se listan diferentes máquinas conectadas a través de redes.

Figura 6.11 La organización de un multiprocesador conectado en red.

Nombre Máximo

número de procesadores

Nombre del

procesador

Frecuencia del

procesador

Máximo tamaño de memoria/ sistema

Razón de comunicación Nodo Topología

Cray Research

T3E 2048 Alpha

21164 450 MHz 524, 288 MB 1200 MB/s SMP 4-vías 3D torus

HP/Convex Exemplar X-class

64 PA-800 180 MHz 65, 536 MB 980 MB/s SMP 2-vías

8 vías Travesaño

+ anillo Sequent

NUMA-Q 32 Pentium Pro 200 MHz 131, 072 MB 1024 MB/s SMP

4-vías Anillo

SGI Origin2000 128 MIPS

R10000 195 MHz 131, 072 MB 800 MB/s SMP 2-vías 6-cubo

Sun Enterprise

10000 64 UltraSPAR

C 1 250 MHz 65, 536 MB 1600 MB/s SMP 4-vías

Travesaño 16 vías

Tabla 6.4 Características de computadoras con multiprocesadores conectados en red (a la venta en 1997).

18

Esto conduce a un viejo debate acerca de la organización de la memoria en procesadores paralelos de gran escala. El debate desafortunadamente se centra en una falsa limitación a dos posibilidades: memoria compartida contra memoria distribuida. La memoria compartida rara vez significa un espacio único de direcciones, implicando comunicación implícita con cargas y almacenamientos. El opuesto real de direcciones únicas es múltiples memoria privadas, implicando comunicación explícita con envío y recepción. La memoria distribuida se refiere a localidades físicas de la memoria. Si la memoria físicamente está dividida en módulos, con alguno colocado cerca de cada procesador, como en la figura 6.11, entonces la memoria físicamente está distribuida. El opuesto real de memoria distribuida es memoria centralizada, donde el tiempo de acceso a una localidad de la memoria es el mismo para todos los procesadores por que cada acceso va sobre una interconexión, como en la figura 6.6. En la sección 6.1 se mencionó que, único espacio de direcciones contra múltiples espacios de direcciones, y memoria distribuida contra memoria centralizada son tópicos ortogonales: los multiprocesadores pueden tener un único espacio de direcciones y memoria física distribuida. El debate apropiado involucra las ventajas y desventajas de un único espacio de direcciones, de comunicación explícita y de memoria física distribuida. En máquinas sin un solo bus global de direcciones la comunicación es explícita; el programador o el compilador deben enviar mensajes para mandar datos a otro nodo y deben recibir mensajes para aceptar datos de otro nodo. Ejemplo: Programa paralelo (Paso de mensajes) Se tiene nuevamente el ejemplo de la suma de 100, 000 números, pero ahora considerando un multiprocesador conectado en red con 100 procesadores usando múltiples memorias privadas. Respuesta: Dado que esta computadora tiene múltiples espacios de direcciones, el primer paso es distribuir los 100 subconjuntos en cada una de las memorias locales. El procesador que contiene los 100, 000 números envía el subconjunto a cada uno de los nodos de los 100 procesadores. El siguiente paso es obtener la suma de cada subconjunto. Este paso es simplemente un lazo que cada unidad de ejecución sigue; lee una palabra de memoria local y la suma a una variable local; Sum= 0; For ( i = 1000; i < 1000; i = i + 1 ) /* Lazo sobre el subarreglo local */ Sum = Sum + A[i]; /* Suma los arreglos locales */

19

El último paso consiste en sumar estas 100 sumas parciales. La parte dura de esto es que cada suma parcial está localizada en una diferente unidad de ejecución. Por lo tanto, debemos usar la red de interconexión para enviar las sumas parciales hasta acumular la suma final; en lugar de enviar todas las sumas parciales a un procesador, lo cual resultaría en una suma secuencial de las sumas parciales. Primero, la mitad de las unidades de ejecución enviará su suma parcial a la otra mitad de unidades de ejecución, donde se sumarán las dos sumas parciales. Después, un cuarto de unidades de ejecución (la mitad de la mitad) enviará su nueva suma parcial al otro cuarto de la unidad de ejecución (la restante mitad de la mitad) para la siguiente ronda de sumas. Entonces partiendo a la mitad, enviando y recibiendo continuará hasta que haya una única suma de todos los números. Se utiliza Pn para representar el número de cada unidad de ejecución (de 0 a 99); sea send(x, y) una rutina que envía sobre la red de interconexión a la unidad de ejecución x el valor y, y sea receive() una función que acepta el valor desde la red para esta unidad de ejecución: Limit = 100; /* Límite superior de los procesadores emisores */ Half = 100; /* 100 procesadores */ Do { Half = ( Half + 1) / 2; /* División entre emisores y receptores */ If ( Pn >= half && Pn < Limit ) Send( Pn – half, sum); If ( Pn < (limit/2) ) Sum = Sum + receive(); Limit = Half; /* Nuevo límite */ } while ( Half != 1); /* Termina con la suma final */ Este código divide el total de procesadores en emisores o receptores y cada procesador receptor obtiene solamente un mensaje, de manera que se puede inferir que un procesador receptor se detendrá hasta que recibe un mensaje. Entonces, el envío y recepción pueden ser usados como primitivas para sincronización así como para comunicación, por lo que todos los procesadores están enterados de la transmisión de datos. Direccionamiento de Procesadores Paralelos de Gran Escala La mayoría de procesadores paralelos de gran escala usan memoria que es distribuida; en otro caso resultaría muy difícil o muy caro construir una máquina que pueda escalar a cualquier número de procesadores con cualquier cantidad de módulos de memoria. El siguiente punto que encaran las máquinas con memoria distribuida es la comunicación. Para el diseñador de hardware, la solución mas simple es ofrecer solamente envíos y recepciones en lugar de la comunicación implícita que es posible como parte de cargas y almacenamientos. Envío y recepción también tienen la ventaja de que hace más simple al programador la optimización de la comunicación: Es más simple traslapar código de

20

cómputo con comunicación usando envío y recepción explícita en lugar que cargas y almacenamientos implícitos. Por otro lado, las cargas y almacenamientos normalmente tienen comunicación mucho más lenta por encima del que hacen el envío y recepción. Y algunas aplicaciones tendrán referencias a información remota que es accesada solo ocasionalmente e imprevisiblemente, de manera que es mucho más eficiente usar una dirección a datos remotos solo cuando son demandados en lugar de recuperarlos para que puedan ser utilizados. Tales máquinas tienen una memoria distribuida compartida (DSM, distributed shared memory). Agregar una capa de software para proporcionar un espacio de direcciones único sobre el envío y recepción de mensajes de manera que la comunicación sea posible como parte de alguna carga o almacenamiento es mas duro. Aunque es comparable a la memoria virtual actualmente encontrada en la mayoría de procesadores. En memoria virtual, un procesador único utiliza tablas para determinar si una dirección apunta a un dato en memoria local o sobre el disco; esta traslación debería modificarse para decidir si una dirección apunta a un dato local, a un dato en la memoria de otro procesador o en disco. Aunque esta memoria virtual compartida crea la ilusión de una memoria compartida – así como la memoria virtual crea la ilusión de una memoria muy grande – dado que invoca al sistema operativo, el rendimiento usualmente es más lento que la comunicación en memoria compartida. Las cachés son importantes para el rendimiento no importa como se realice la comunicación, de manera que se desearía que los datos compartidos estuvieran en la cache del procesador propietario de los datos y también en el procesador que solicita los datos. Esto es, la dirección global única en un multiprocesador conectado en red resucita el tópico de coherencia de caché, dado que hay múltiples copias del mismo dato con la misma dirección en diferentes procesadores. Claramente el protocolo de espionaje en el bus descrito en la sección 6.3 no funciona aquí, por que no hay un bus único sobre el cual todas las referencias a memoria son transmitidas. Los diseñadores de la Cray T3E (ver Tabla 6.4) no colocaron un bus para soportar coherencia de caché, tiene un espacio único de direcciones pero no es de caché coherente. Una alternativa al espionaje del bus para la coherencia de caché se denomina directorios. En protocolos basados en directorios, hay lógicamente un único directorio que mantiene el estado de cada bloque en la memoria principal. La información en el directorio puede incluir cual caché tiene copias de los bloques, si este está sucio, etc. Afortunadamente, las entradas al directorio pueden ser distribuidas de manera que diferentes peticiones pueden ir a diferentes memorias, por lo que reducen la controversia y permiten un diseño escalable. Los directorios mantienen la característica que los estados compartidos de un bloque están siempre en una localidad única conocida, haciendo factible un procesador paralelo a gran escala. Los diseñadores de cachés con espionaje y directorios encaran situaciones similares, la única diferencia es el mecanismo que detecta cuando hay una escritura en un dato compartido. En lugar de observar el bus para ver si hay alguna petición que requiera que un bloque de una caché local sea actualizado o invalidado, el controlador del directorio envía

21

comandos explícitos a cada procesador que tiene una copia de los datos. Tales mensajes pueden ser enviados por medio de la red. Notar que con un espacio único de direcciones, los datos podrían ser colocados arbitrariamente en las memorias de diferentes procesadores. Esto tiene dos consecuencias negativas del rendimiento. La primera es que los fallos afectarían mucho mas por que irían sobre la red. La segunda es que el ancho de banda de la red se consumiría moviendo los datos a los procesadores correspondientes. Para programas que tienen una razón baja de fallos, esto puede no ser significativo. Por otro lado, los programas con una alta razón de errores tendrán mucho más bajo rendimiento cuando los datos son asignados de manera aleatoria. Si el programador o el compilador ubican los datos en el procesador que probablemente los usará, entonces este obstáculo en el rendimiento es removido. A diferencia de las organizaciones de memoria privada, esta ubicación necesita ser buena, dado que errores en datos pueden detener su captura. Otra posible solución es agregar un segundo nivel de coherencia a la memoria principal para cada procesador. Este directorio permitiría a los bloques de la memoria principal migrar, relevando al programador o al compilador de la ubicación de la memoria, tan pronto como los bloques de la memoria principal no son embarcados. Frecuentemente regresará y lo hará repetidamente, este esquema puede alcanzar el rendimiento de ubicación inteligente de memoria al costo de hardware considerablemente mas complicado. Este esquema se llama memoria con caché única (cache-only memory). Está migración puede ocurrir al nivel del sistema operativo, o también en hardware.

Figura 6.12 Opciones de coherencia de caché para un espacio único de direcciones.

En la figura 6.12 se resumen las opciones de coherencia de caché para un espacio único de direcciones. El rectángulo sombreado representa a los datos replicados. En (a) la coherencia es al nivel de la caché usando directorios en un multiprocesador conectado en red. Los datos originales están en la memoria y las copias son replicadas solamente en las cachés. En (b) la coherencia es al nivel de la memoria, las copias son replicadas en la memoria remota

22

(en color) y en las cachés. En ambos casos, si los datos de una memoria son invalidados, entonces los bloques correspondientes en la caché deben también invalidarse. Dado que el número de terminales por chip está limitado, no todos los procesadores pueden ser conectados directamente a través de una red. Esta restricción ha inspirado a una variedad de topologías para considerarse en el diseño de una red. En la sección 6.6 se revisan algunas de ellas, pero antes de ello, en la siguiente sección se muestran otras alternativas para conectar las computadoras por redes. En la figura 6.13 se compara el costo y rendimiento de multiprocesadores UMA conectados por un bus con multiprocesadores NUMA conectados en red. La red tiene un costo inicial más pequeño pero después escala para crecer más rápidamente que las máquinas conectadas con un solo bus. El rendimiento para ambas máquinas crece linealmente hasta que el bus alcanza su límite, y entonces el rendimiento se mantiene no importando cuantos procesadores sean utilizados. Cuando estos dos efectos se combinan, se observa que la conexión en red NUMA tiene un rendimiento por unidad de costo constante, mientras que la máquina conectada por un bus tiene una meseta dominante. La meseta sugiere que los consumidores necesitan ser más selectivos con multiprocesadores conectados por un bus que los que están conectados por una red, y los diseñadores de máquinas con bus necesitan ubicar la meseta en un punto que se ajuste con las necesidades de la mayoría de consumidores. 6.5 Clusters (Grupos) Hay muchas aplicaciones de mainframes – tales como bases de datos, servidores de archivos, servidores de Web, simulaciones, y procesamiento por lotes/multiprogramación – accesibles para ejecutarse sobre máquinas pobremente acopladas con coherencia de caché NUMA (vistas en la sección anterior). Estas aplicaciones frecuentemente necesitan estar altamente disponibles, requiriendo alguna forma de tolerancia y resolución ante fallos. Tales aplicaciones – mas la similitud de los nodos multiprocesadores a computadoras de escritorios y la emergencia de alto ancho de banda, redes de área local basadas en Switches – sugiere que el procesamiento a gran escala del futuro puede usar clusters (grupos) de computadoras completas. El ejemplo mas histórico es la victoria de la IBM SP2 – un cluster de 32 nodos muy similar a la estación de trabajo RS/6000 con aceleradores de hardware para la evaluación de tableros de ajedrez – sobre el campeón de ajedrez Kasparov en 1997. Por ejemplo, en 1997 un cluster de 100 computadoras de escritorio UltraSPARC en UC Berkeley, conectadas por switches Myrinet a 160 MB/seg, fue usada para establecer el record mundial en ordenar bases de datos – ordenando 8.6 GB de datos originalmente en disco en un minuto – y en corromper un mensaje encriptado – tomando solo 3.5 horas para descifrar una clave DES de 40 bits.

23

Figura 6.13 Comparación del costo, rendimiento y costo/rendimiento de multiprocesadores UMA conectados

por un bus con multiprocesadores NUMA conectados en red.

En la tabla 6.5 se muestran los clusters vendidos por compañías de computadoras tales como el IBM SP2. Estos clusters diseñados para compañías son normalmente vendidos para proporcionar sistemas altamente disponibles, escalables – esto es, sistemas cuyo objetivo sea escalar tanto en un número grande de procesadores, memoria y disco, y que estén disponibles las 24 horas los 365 días del año.

24

Nombre Máximo

número de procesadores

Nombre del procesador

Frecuencia de reloj del procesador

Máximo tamaño de memoria

de sistema (MB)

Razón de comunicación

(MB/seg) Nodos

Máximo número de

nodos

HP 9000 EPS21 64 PA-8000 180 MHz 65, 536 532 SMP

4-vías 16

IBM RS/6000

ACNP R40 16 PowerPC

604 112 MHz 4, 096 12 SMP 8-vías 2

IBM RS/6000

SP2 512 Power2 SC 135 MHz 1,048,576 150 nodo

16-vías 32

Sun Enterprise

Cluster 6000 HA

60 UltraSPARC 167 MHz 61,440 100 SMP 30-vías 2

Tandem NonStop Himalaya S70000

4096 MIPS R10000 195 MHz 1,048,576 40 SMP

16-vías 256

Tabla 6.5 Características de Clusters comercialmente disponibles en 1997 Una desventaja de los clusters es que el costo de administrar un cluster de N máquinas es casi el mismo que el costo de administrar N máquinas independientes, mientras que el costo de administrar una máquina con un multiprocesador con espacio de direcciones compartido con N procesadores es casi el mismo que el costo de administrar una sola máquina. Otra desventaja es que los clusters usualmente están conectados usando el bus I/O de la computadora, mientras que los multiprocesadores usualmente se conectan por medio del bus de la memoria de la computadora. El bus de la memoria tiene un ancho de banda mas alto, permitiendo a los multiprocesadores manejar la red de conexión a altas velocidades además de que se reducen los conflictos con el trafico de I/O, sobre todo en aplicaciones que hacen uso extensivo de I/O. Un defecto final es la división de la memoria: Un cluster de N máquinas tiene N memorias independientes y N copias del sistema operativo, pero un multiprocesador de direcciones compartidas permite a un único programa usar casi toda la memoria en la computadora. Así un programa secuencial en un cluster tiene 1/N de memoria disponible comparado a un programa secuencial en un SMP. El defecto de las memorias separadas para el tamaño de un programa por otro lado beneficia la disponibilidad y expansibilidad del sistema. Dado que un cluster consiste de computadoras independientes conectadas a través de una red de área local, es posible remplazar una máquina sin apagar a todo el sistema. En una SMP con direcciones compartidas es un trabajo muy complejo aislar a un procesador del sistema operativo para remplazarlo. En cambio en un cluster el software esta en una capa que corre a un nivel superior del sistema operativo local ejecutado en cada computadora, de manera que es mucho más fácil desconectar y remplazar una máquina caída.

25

Dado que los clusters son construidos con computadoras completas e independientes, este aislamiento hace mas fácil expandir al sistema sin dar de baja a la aplicación que corre en el nivel superior del cluster. La alta disponibilidad y la facilidad de expansión hacen a los clusters atractivos para proporcionar servicios para la World Wide Web. Otra diferencia entre las dos tendencias es el precio para la misma potencia de cómputo en máquinas de gran escala. Dado que los multiprocesadores de gran escala tienen volúmenes pequeños, el costo de desarrollo de grandes máquinas debe ser amortizado sobre pocos sistemas, resultando en un alto costo para los consumidores. Dado que los mismos switches vendidos en altos volúmenes para pequeños sistemas pueden ser usados para construir redes grandes para grandes clusters, los switches de las redes de área local tienen las mismas ventajas de economía como las pequeñas computadoras. Como frecuentemente ocurre en diferentes soluciones, cada solución intenta minimizar las desventajas ante las que se encuentra ante la otra solución, para llegar a ser más atractiva. Por un lado, para combatir la desventaja de la alta disponibilidad que no tienen los multiprocesadores, los diseñadores de hardware y desarrolladores de sistemas operativos están intentando ofrecer la habilidad de correr múltiples sistemas operativos sobre porciones de la máquina completa, de manera que un nodo puede fallar o ser actualizado sin apagar al sistema completo. Por otro lado, dado que tanto la administración del sistema y los límites en el tamaño de la memoria son aproximadamente lineales con el número de máquinas independientes, algunos están reduciendo los problemas de los clusters construyendo clusters con base en SMPs de pequeña escala. Por ejemplo, un cluster de 32 procesadores puede ser construido usando 8 SMPs de 4 vías o 4 SMPs de 8 vías. Tales clusters “híbridos” están siendo populares con aplicaciones que cuidan el costo/rendimiento, disponibilidad y expansibilidad. Todos los clusters comercialmente disponibles que describieron en la tabla 6.5 son basados en SMPs. En la siguiente sección se describen topologías de redes que son usadas en clusters y en multiprocesadores. 6.6 Topologías de Red La forma simple de conectar nodos de procesador-memoria consiste en contar con una liga de comunicación directa entre cada nodo. Entre el alto costo/rendimiento de esta red completamente conectada y el bajo costo/rendimiento de un bus están un conjunto de redes que constituyen un amplio rango de posibilidades en costo/rendimiento. El costo de la red incluye el número de switches, el número de ligas (links) sobre un switch para conectar a la red, el ancho (número de bits) por liga, y la longitud de las ligas cuando la red está mapeada dentro de una máquina física. Por ejemplo, en una máquina que escala entre decenas y centenas de procesadores, algunas ligas pueden ser rectángulos metálicos dentro de un chip que tienen unos cuantos milímetros de longitud, y otras pueden ser cables que deben alcanzar varios metros desde un gabinete a otro. El rendimiento de la red es multifacético también. Este incluye la latencia sobre una red descargada para enviar y recibir mensajes, la

26

productividad en términos del número máximo de mensajes que pueden ser transmitidos en un periodo de tiempo dado, retrasos causados por desacuerdo por una porción de la red, y rendimiento variable dependiendo de la modalidad de comunicación. Otra obligación de la red puede ser la tolerancia ante fallos, dado que muchos sistemas grandes pueden requerir operar en la presencia de componentes caídos. Las redes normalmente se dibujan como grafos, con cada arco del grafo representando una liga de comunicación en la red. El nodo procesador- memoria es mostrado como un cuadro negro y el switch es mostrado como un circulo en color. Las ligas son bidireccionales; esto es, la información puede fluir en cualquier dirección. Todas las redes consisten de switches cuyas ligas van a los nodos procesador- memoria o a otros switches. La primera mejora sobre un bus es una red que conecta una secuencia de nodos conjuntamente:

Esta topología es llamada anillo. Dado que algunos nodos no están conectados directamente, algunos mensajes tendrán que brincar a lo largo de nodos intermedios hasta llegar a su destino final. A diferencia de un bus, un anillo es capaz de muchas transferencias simultáneas. Debido a que hay numerosas topologías, son necesarias algunas métricas de rendimiento para distinguir entre diferentes diseños. Dos son populares. La primera es ancho de banda de la red total, la cual es el ancho de banda de una liga multiplicado por el número de ligas. Esto representa al mejor de los casos. Para la red de anillo anterior con P procesadores, el ancho de banda de la red total sería P veces el ancho de banda de una liga; el ancho de banda de la red total para un bus es solo el ancho de banda de ese bus, o una vez el ancho de banda de esa liga. Para balancear este mejor caso, se tiene otra métrica que es cercana al peor de los casos: el ancho de banda bisección. Se calcula dividiendo la máquina en dos partes, cada una con la mitad de nodos. Entonces se suma el ancho de banda de las ligas que cruzan esa línea imaginaría. El ancho de banda bisección de un anillo es dos veces el ancho de banda de una liga, y es una vez el ancho de banda de una liga para un bus. Si una liga es tan rápida como el bus, al anillo es solamente dos veces más rápido que el bus en el peor de los casos, pero es P veces mas rápido en el mejor de los casos. Dado que algunas topologías de red son no simétricas, la pregunta que surge es en donde dibujar la línea imaginaría cuando se está dividiendo la máquina. Esta es una métrica en el peor de los casos, de manera lo mas adecuado es elegir la división que produce el rendimiento de la red mas pesimista; alternativamente establecido, calcular todos los posibles anchos de banda bisección y elegir el más pequeño. Se elige esta perspectiva pesimista por que los programas paralelos frecuentemente están limitados por la peor liga en el canal de comunicación.

27

Muy opuesto a la red tipo anillo se encuentra la red completamente conectada, donde cada procesador tiene una liga bidireccional a cada uno de los otros procesadores. Para redes completamente conectadas, el ancho de banda de la red total es P x ( P – 1 ) / 2, y el ancho de banda bisección es (P/2)2. La tremenda mejora en rendimiento de una red completamente conectada es desplazada por el alto incremento en costo. Esto inspira a los ingenieros a inventar nuevas tecnologías que estén entre el costo de los anillos y el rendimiento de las redes completamente conectadas. La evaluación del éxito depende en gran parte de la naturaleza de la comunicación con cargas de trabajo de programas paralelos corriendo sobre la máquina. El número de diferentes topologías que han sido discutidas en publicaciones sería difícil de contar, pero el número que ha sido usado en procesadores paralelos comerciales es apenas un puñado. En la figura 6.14 se ilustran dos topologías populares. Las máquinas reales frecuentemente agregan ligas extras a estas simples topologías para mejorar el rendimiento y la fiabilidad.

Figura 6.14 Topologías de red que han aparecido en procesadores paralelos comerciales.

(a) Rejilla en 2D o malla de 16 nodos, y (b) Árbol n-cúbico de 8 nodos (8 = 23 de manera que n = 3). Una alternativa a fijar un procesador en cada nodo en una red es dejar solamente un switch en algunos de estos nodos. Los switches son mas pequeños que los nodos procesador-memoria-switch, y estos pueden ser empaquetados mas densamente por lo que se reduce la distancia y se incrementa el rendimiento. Tales redes frecuentemente son llamadas redes multietapas para reflejar los múltiples pasos que un mensaje puede viajar. Los tipos de redes multietapas son tan numerosos como las redes de etapa única; en la figura 6.15 se ilustran dos organizaciones multietapas populares. Una red completamente conectada o de cruce (fig. 6.15-a) permite a cualquier nodo comunicarse con cualquier otro nodo en un paso a través de la red. Una red Omega (fig. 6.15-b) usa menos hardware que una red de cruce (2n log2 n vs. n2 switches), pero pueden ocurrir disputas entre los mensajes, dependiendo de la modalidad de comunicación. Por ejemplo, en la figura 6.15 la red Omega no puede enviar un mensaje de P0 a P6 y al mismo tiempo enviar un mensaje de P1 a P7. Este simple análisis de redes en esta sección ignora importantes consideraciones prácticas en la construcción de una red. La distancia de cada liga afecta el costo de comunicación en una alta frecuencia de reloj. La distancia mas larga es de mayor costo, en distancias cortas es mas fácil asignar mas alambres a una liga, también la potencia que manejan muchos

28

alambres desde un chip es menor si los alambres son cortos. Los alambres cortos son más baratos que los alambres largos. Una limitación práctica final es que los dibujos en tres dimensiones deben ser mapeados en chips y tarjetas que son esencialmente en dos dimensiones. Las líneas inferiores que en las topologías aparecen elegantes cuando son esbozadas en papel, puede ser difíciles de tratar cuando se construyen con chips, cables, tarjetas y cajas.

Figura 6.15 Topologías de red multietapas populares para ocho nodos.

En este caso los switches son más simples por que las ligas son unidireccionales.

Tarea 13 1. Consideremos las siguientes porciones de dos diferentes programas ejecutándose al

mismo tiempo en SMP. Supongamos que antes de este código las variables x y y contenían 0.

Procesador 1: . . . ; x = x + 1; y = x + y; . . . Procesador 2: . . . ; y = x + 1; . . . ¿Cuáles son los posibles valores resultantes para x y y, suponiendo que el código es implementado usando una arquitectura de carga-almacenamiento? Para cada posible

29

resultado, explique como x y y han obtenido esos valores. (Sugerencia: Es posible examinar al nivel del lenguaje ensamblador).

2. Imaginar que los empleados de una enorme compañía ignoran quien es el gerente

general y solo saben quien es su jefe inmediato. La administración esta considerando si utilizará una de las siguientes posibilidades:

• “Que hoy cada empleado pregunte a su jefe quien es su jefe, y mañana se pregunte a

esa persona quien es su jefe, y así sucesivamente, hasta que eventualmente se descubra quien es el gerente general de la compañía”

• “Que cada persona por favor escriba el nombre de su jefe en una hoja de papel.

Investigar que nombre tiene en su hoja de papel la persona cuyo nombre aparece en la hoja de cada uno, y el día de mañana escribir ese nombre sobre la hoja de papel antes de venir al trabajo. Repetir este proceso hasta que se descubra quien es el gerente general de la compañía”

Hacer un resumen con las diferencias entre estas dos posibilidades y los resultados de cada una. El resumen debe incluir una explicación de la relación existente entre las dos posibilidades y lo que se describió en el documento acerca de la concurrencia y los procesos internos de sincronización y comunicación.

3. En el ejemplo del programa paralelo, con paso de mensajes, esbozar el código por

medio del cual se conseguirá que el procesador con los 100, 000 números envíe un subconjunto a cada uno de los nodos de los 100 procesadores. Suponer que es el procesador 0 el que tiene los datos, desafortunadamente esta parte se ejecutaría en forma secuencial, sólo habrá que cuidar la sincronización entre los diferentes procesadores.

4. Otra posible topología de red es una rejilla tridimensional, dibujar la topología como la

figura 6.14 para 64 nodos. ¿Cuál es el ancho de banda de bisección para esta topología? 5. Supongamos que contamos con una máquina con un multiprocesador con 4

procesadores, y se nos presenta el problema de contar el número de 1’s en una imagen binaria (matriz que solo contiene 0’s y 1’s). Ignorando como se obtuvo la imagen, con base en los ejemplos anteriores, esbozar el programa que resolvería este problema considerando:

a. Que se tiene un solo Bus (sección 6.3). b. Y que se tiene una red (con paso de mensajes, sección 6.4)

Nota: Esbozar significa escribir el código que resuelve la parte principal del problema, sin entrar a detalles, como la declaración de variables. Para ello es conveniente indicar todas las suposiciones que se realicen.